poj 1417 True Liars
题目大意:
某一岛上有p1个只说真话的人(好人),p2个只说谎话的人(坏人),所有人都有一个唯一的编号(1~p1+p2)询问n次.
询问格式 a b res:
问a号,b号是否是好人,res可以是yes或者no.
判断是否能找出所有好人,可以的话输出好人的编号再加个end,否则输出no.
题目思路:
当回答是yes:
如果a是好人,那么b肯定也是好人,反之a是坏人,那么b也肯定是坏人.
所以回答是yes时,a和b是同一类人. www.zzzyk.com
当回答是no时,同样可以证明,a和b不是同一类人.
所以我们可以用并查集把所有可以判断是否同类的人归在一个集合.
之后我们就要判断是否有唯一的一种组合使得有p1个人为好人.
这里我们可以用到dp,因为这个很像背包.
dp[i][j],表示前i个集合中有j人是好人的组合有几个.
显然如果dp[集合数][p1]如果等于1,那么就是有答案了.
状态方程也很容易推导的.
代码:
[cpp]
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
#define ls rt<<1
#define rs ls|1
#define lson l,mid,ls
#define rson mid+1,r,rs
#define middle (l+r)>>1
#define eps (1e-8)
#define type int
#define clr_all(x,c) memset(x,c,sizeof(x))
#define clr(x,c,n) memset(x,c,sizeof(x[0])*(n+1))
#define MOD 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define _max(x,y) (((x)>(y))? (x):(y))
#define _min(x,y) (((x)<(y))? (x):(y))
#define _abs(x) ((x)<0? (-(x)):(x))
#define getmin(x,y) (x= (x<0 || (y)<x)? (y):x)
#define getmax(x,y) (x= ((y)>x)? (y):x)
template <class T> void _swap(T &x,T &y){T t=x;x=y;y=t;}
int TS,cas=1;
const int M=1200+5;
int n,p1,p2;
int fa[M],vis[M],tot,dp[M][M];
vector<int>a[M][2];
int res[M],m,pre;
int find(int x){
return (fa[x]==x)? x:(fa[x]=find(fa[x]));
}
void uni(int x,int y){
fa[find(x)]=find(y);
}
void run(){
int i,j;
for(i=1;i<=2*(p1+p2);i++) fa[i]=i;
char op[11];
while(n--){
scanf("%d%d%s",&i,&j,op);
if(op[0]=='y') uni(i,j),uni(i+p1+p2,j+p1+p2);
else uni(i,j+p1+p2),uni(i+p1+p2,j);
}
bool ok=1;
clr_all(vis,0);
for(i=1;i<=p1+p2;i++){
if(find(i) == find(i+p1+p2)){
puts("no");
return;
}
}
tot=0;
for(i=1;i<=p1+p2;i++) if(!vis[i]){
int f0=find(i),f1=find(i+p1+p2);
++tot;
a[tot][0].clear();
a[tot][1].clear();
for(j=1;j<=p1+p2;j++) if(!vis[j]){
int jf=find(j);
if(jf==f0) a[tot][0].push_back(j),vis[j]=1;
else if(jf==f1) a[tot][1].push_back(j),vis[j]=1;
}
}
for(i=1;i<=tot;i++){
}
clr_all(dp,0);
dp[0][0]=1;
for(i=1;i<=tot;i++){
int sz0=a[i][0].size();
int sz1=a[i][1].size();
for(j=p1;j>=sz0;j--) dp[i][j]+=dp[i-1][j-sz0];
for(j=p1;j>=sz1;j--) dp[i][j]+=dp[i-1][j-sz1];
}
if(dp[tot][p1]==1){
m=0;
pre=p1;
for(i=tot;i>=1;i--){
int sz0=a[i][0].size();
if(dp[i-1][pre-sz0]==1){
pre-=sz0;
for(j=0;j<sz0;j++) res[++m]=a[i][0][j];
continue;
}
int sz1=a[i][1].size();
if(dp[i-1][pre-sz1]==1){
pre-=sz1;
for(j=0;j<sz1;j++) res[++m]=a[i][1][j];
continue;
}
}
sort(res+1,res+m+1);
for(i=1;i<=m;i++) printf("%d\n",res[i]);
puts("end");
}else puts("no");
}
void preSof(){
}
int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
preSof();
//run();
while(~scanf("%d%d%d",&n,&p1,&p2) && (n||p1||p2)) run();
//for(scanf("%d",&TS);cas<=TS;cas++) run();
return 0;
}
补充：软件开发 , C++ ,
