返回信息流给定N个宝箱，每个宝箱可能是普通宝箱或者宝箱怪中的一种，每个宝箱上贴着一张字条，字条给定以下两种信息的一种：1）第x个宝箱是普通宝箱。2）第x个宝箱是宝箱怪
其中普通宝箱上的信息一定是真的，宝箱怪上的信息__可能__是假的，问根据这些信息，有多少个宝箱__一定__是普通宝箱，有多少个宝箱__一定__是宝箱怪？
>输入：
>第一行一个整数N，1<=N<=10^5
>接下来N行，每行两个整数t,x，1<=t<=2,1<=x<=N，若t=1,则表示第i个宝箱说第x个宝箱是普通宝箱，若t=2，则表示第i个宝箱说第x个宝箱是宝箱怪
>输出：
>一行两个整数c1，c2，空格隔开，c1表示__一定__是普通宝箱的数量,c2表示__一定__是宝箱怪的数量
>输入：
>3
>1 2
>2 1
>1 3
>输出：
>0 1
现在好奇两个问题：
1）到底要在什么情况下才能确定一个宝箱是普通宝箱，因为宝箱怪也有可能说真话所以我一直觉得c1=0
2）本来用的dfs思路去观察有没有矛盾，例如就是先假设1是普通宝箱(设为true)，然后顺着1说的话往下推，最后有矛盾则说明1是宝箱怪，但是问题在于如果没有矛盾又不能说明什么。而且没有矛盾还得把1的值true重置掉，实际写代码感觉超复杂，呜呜呜
求解呀
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #96669同步于 2018/9/27
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
【问题】百度笔试题
a2013211232
2018/9/27镜像同步24 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
上班时间粗略的想了一下，最暴力的就是穷举2^n中情况，然后求可行解的交集。优化的话只想到dfs加上剪枝，根据当前假设为真宝箱上的信息减少需要判断的情况
Emmm...感觉复杂度还是有点高...
c1总为0，c2只需要求最多有多少个可以为真
我是这么做的，穷举：
def：
如果当前点到了最后：返回当前为真的个数
若当前点为真：
当前点不能为真：返回0
当前点可以为真：
当前点为真
按照当前点的指向：指向为真的标记为真，为假标记为假
return max(def(下个点为真)，def(下个点为假))
当前点为假反之
这样算出最大的可以为真的个数
自己写的太乱了，最后没实现成功[ema1]
【 在 a2013211232 的大作中提到: 】
: [md]
: 给定N个宝箱，每个宝箱可能是普通宝箱或者宝箱怪中的一种，每个宝箱上贴着一张字条，字条给定以下两种信息的一种：1）第x个宝箱是普通宝箱。2）第x个宝箱是宝箱怪
: 其中普通宝箱上的信息一定是真的，宝箱怪上的信息__可能__是假的，问根据这些信息，有多少个宝箱__一定__是普通宝箱，有多少个宝箱__一定__是宝箱怪？
: ...................
ans1 = 0，有个同学100%过了
首先题目要求的是一定是普通宝箱或者宝箱怪的个数.
那么我们来看一下C1的情况,
如果一定是普通宝箱？这种情况是无法确定的，因为嘤嘤怪只要都说真话那就等同于普通宝箱,
所以我们并不能说一个箱子一定是普通宝箱,所以C1=0.
然后我们再来看一下C2,即一定是嘤嘤怪的个数,那么什么样的情况下这个宝箱一定是嘤嘤怪呢？
我们假设从某个宝箱为普通宝箱，然后从他出发，因为此时一定说的是真话，那么此时他就可以指出
下一个宝箱是什么，如果是2(嘤嘤怪),那么信息就丢失了,因为我们要求的是一定是，而这个嘤嘤怪可能说真
也可能说假，相当于啥都没说，所以我们要选择是下一个也是1(普通宝箱)的来进行转移，那么什么时候会出现问题呢？
假设到了某个时刻又转移到了以前已经到达的某个状态，并且此时的回答是2，那么就矛盾了。因为刚才普通宝箱说了这个
状态是1，但此时又有一个普通宝箱说他的状态是2，矛盾了！所以说我们的假设不正确，这个箱子不是普通宝箱，那它必是
嘤嘤怪。
所以我觉得此题有点类似于一个贪吃蛇不断吃东西，回答为1就吃，突然吃到自己尾巴了(环),然后就矛盾了。
这种想法的代码如下：
public static int solve(int[] a, int[] b)
{
boolean[] used = new boolean[a.length];
int count = 0;
for (int i = 0; i < a.length; i++)
{
Arrays.fill(used, false);
used[i] = true;
int target = b[i]-1;
int responce = a[i];
while (responce == 1 && !used[target])
{
used[target] = true;
responce = a[target];
target = b[target]-1;
}
if (used[target] && responce == 2)
count++;
}
return count;
}
今年多校原题啊...百度"hdu6370"...
可以所有箱子都是宝箱怪，所以c1=0
假设一个箱子是普通宝箱，如果顺着第一种信息指下去出现矛盾，那么路径上的都是箱子都是宝箱怪...建反向边然后dfs可以做到O(N)复杂度，代码百度就成了