Question

pku 1029 Wrong Answer 为什么？错哪里了？

网上说是动态规划，我怎么看都不觉得是啊。。
我是这样想的，如果是“=”，那天平上的硬币都是真的；如果不是“=”，那不在天平上的硬币都是真的。最后就看如果只剩下一个不一定是真的，那么那个就是假的。如果不是剩下一个，那就打印0.

这样想对不对啊？
下面是源代码
解释：
C[i]=1 代表第i个硬币肯定是真的，为0代表有可能是假的
in[i]=1 代表第i个硬币在天平上，为0代表不在天平上。

#include <stdio.h>
#include <string.h>

#define N 1000

int C[N + 1], in[N + 1];//in[i] = 1代表第i个硬币在天平上
int a[N/2 + 1], b[N/2 + 1];
int n, k, m;

int main() {
char ch;
int i, num, pt;

scanf("%d%d", &n, &k);
while(k > 0) {

for(i = 1; i <= n; i++)
in[i] = 0;

scanf("%d", &m);
for(i = 1; i <= m; i++) {
scanf("%d", &a[i]);
in[a[i]] = 1;
}
for(i = 1; i <= m; i++) {
scanf("%d", &b[i]);
in[b[i]] = 1;
}
scanf(" %c", &ch);
if(ch == '=') {
for(i = 1; i <= m; i++) {
C[a[i]] = 1;
C[b[i]] = 1;
}
}else {
for(i = 1; i <= n; i++) {
if(!in[i])
C[i] = 1;
}
}

k--;
}

num = 0;
for(i = 1; i <= n; i++){
if(C[i] == 0) {
pt = i;
num++;
}
}
if(num == 1) {
printf("%d\n", pt);
}else
printf("0\n");
return 0;
}
原来如此！

Answer 1

现在在网吧，没法给你做出来~最近家里断网~
但是可以给你些思路
首先你的做法不全面~这道题的判断是要根据所有可利用的数据。但你只用了=和><的区别，也就是说得到了>和<对你的程序是一样的，但实际上从这里也能分析出很多东西。例如已判断12是真，现有12<34,3>4,以你的程序是判断不了的，但实际上以12<34可知假的比真的重~所以，3是假的
这道题网上的dp思路很犀利~你自己看下，我就不给你粘了~
个人觉得有其他的做法。
这个题貌似要注意的地方不少~（看discuss里写的）不太好ac

Answer 2

你问的是什么呀？