| 题目名称 | 2620. [HEOI 2012]朋友圈 |
|---|---|
| 输入输出 | friends.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 再见
于2017-02-25加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：22， 提交：86， 通过率：25.58% | ||||
 可以的. |
100 | 0.193 s | 70.12 MiB | C++ |
 Go灬Fire |
100 | 0.370 s | 190.88 MiB | C++ |
 小一米 |
100 | 0.524 s | 8.63 MiB | C++ |
 onlysky |
100 | 0.564 s | 30.54 MiB | C++ |
 Flere825 |
100 | 0.711 s | 46.37 MiB | C++ |
 再见 |
100 | 0.985 s | 60.83 MiB | C++ |
 FoolMike |
100 | 1.169 s | 85.28 MiB | C++ |
 半汪 |
100 | 1.222 s | 73.67 MiB | C++ |
 _Itachi |
100 | 1.338 s | 81.33 MiB | C++ |
|
_Itachi |
100 | 1.341 s | 81.33 MiB | C++ |
| 关于 朋友圈 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @小一米 :
e，身为常数狗(永远的大常数)表示几乎不敢用memset,一般都是用时间戳，不能用时间戳的就手动清零（比如我的费用流） _Itachi
2017-02-27 21:03
11楼
| ||||
|
回复 @_Itachi :
作为出题人确实很难做到考虑全所有的错误做法，表示体谅 不过个人认为，既然作为线下练习，而不是比赛，更应该是让大家体会到题目性质与解题思路，而不是通过本不能AC的做法AC题目，这既不利于锻炼选手的思维能力和代码能力，也是对出题人的不尊重。 之前的评论仅代表个人建议，希望大家还是要认真思考，不要投机取巧 小一米
2017-02-27 20:28
10楼
| ||||
|
回复 @小一米 :
en，你的诚实非常可贵 删提交好像是不可以的，至于数据。。你总不能让造数据的人考虑到所有错误写法怎么写然后专门写一个错误写法然后通过对拍得到数据吧。。（出题人怎么知道你怎么错的），所以要体谅一下出题人，尤其是当出题人是一个神犇的时候@Mike _Itachi
2017-02-27 19:37
9楼
| ||||
|
循环展开好像不起作用了。。
那就果断暴力使得 访问下标连续，多次内存访问用引用变量预存。快了0.5s+。 暴力开数组当边表快了1.0s+ | ||||
|
回复 @FoolMike :
真是个sading的故事。。 _Itachi
2017-02-26 08:57
6楼
| ||||
|
回复 @_Itachi :
我们拿到的是个错误的题面，声明的数据范围都不对，所以没加 FoolMike
2017-02-26 08:35
5楼
| ||||
|
虽然有A<=200,B<=3000,M<=A*B A*B<=40000的暗示，但是这个题你不像原题一样标明：
思考的难度会加大。。（其实是我太弱了） _Itachi
2017-02-26 07:43
4楼
| ||||
|
回复 @Marvolo :
卡常数是OI的一环，经过WC2017的洗礼之后深刻的体会到了这一点。省选被卡常难道不算吗？况且这个题我开的是2.5倍用时，没什么问题吧…… 本题有一个合理的优化，就是在匈牙利的时候动态清空而不是memset，这一点的应用在09年NOI中考察过。虽然现在memset可以卡过，但是那时候应该会TLE吧……这个优化还是非常有效的嘛。 FoolMike
2017-02-25 23:08
3楼
| ||||
|
原题时限20S，虽然数据比较弱，但是放题人非要将时限卡的刚刚能让自己一个数量级的程序通过。没有考虑到实际的题目要求。强烈谴责这种不齿行为！
 Marvolo
2017-02-25 21:13
2楼
| ||||
【题目描述】
在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。
一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述：
1、 A国：每个人都有一个友善值，当两个A国人的友善值a、b，如果a xor b mod 2=1，那么这两个人都是朋友，否则不是；
2、 B国：每个人都有一个友善值，当两个B国人的友善值a、b，如果a xor b mod 2=0 或者 (a or b)化成二进制有奇数个1，那么两个人是朋友，否则不是朋友；
3、 A、B两国之间的人也有可能是朋友，数据中将会给出A、B之间“朋友”的情况。
4、 对于朋友的定义，关系是是双向的。
在AB两国，朋友圈的定义：一个朋友圈集合S，满足
S A B，对于所有的 i，j S，i 和 j 是朋友
由于落后的古代，没有电脑这个也就成了每年最大的难题，而你能帮他们求出最大朋友圈的人数吗？
【输入格式】
第一行t<=6,表示输入数据总数。
对于每组数据：
第一行三个整数A,B,M，分别表示A国人数，B国人数，AB两国之间是朋友的对数
第二行A个数ai，表示A国第i个人的友善值
第三行B个数bi，表示B国第i个人的友善值
第4~3+M行，每行两个整数x,y表示A国的第x个人和B国第y个人是朋友
【输出格式】
输出t行，每行，输出一个整数，表示最大朋友圈的数目。
【样例输入】
1 2 4 7 1 2 2 6 5 4 1 1 1 2 1 3 2 1 2 2 2 3 2 4
【样例输出】
5
【提示】
最大朋友圈包含A国第1、2人和B国第1、2、3人。
A<=200,B<=3000,友善为int类型正整数
M<=A*B A*B<=40000
实际数据中t=1
【来源】
HEOI2012