1、POJ 1029 False coinSlyar:又是假币判断问题，跟POJ1013类似，不过这个题用1013那个算法W A了...后来换了种枚举的算法才过...思路就是假币应该在每个不等式中都出现，最后只要看哪个硬币出现的次数和不等式出现的次数相同，如果这个硬币唯一，那它就是确认的假币。

#include <iostream>#include <string>using namespace std;const int MAX = 1001;int main(){int n, k, p, total = 0;char sign;/* 记录原始数据*/int t[MAX] = {0};/* 标记硬币真假*/int r[MAX] = {0};/* 记录硬币重量*/int w[MAX] = {0};cin >> n >> k;while (k--){/* 读入原始数据*/cin >> p;for (int i = 0; i < 2 * p; i++){cin >> t[i];}cin >> sign;/* 标记肯定为真的硬币*/if (sign == '='){for (int i = 0; i < 2 * p; i++){r[t[i]] = 1;}}/* 左轻右重*/else if (sign == '<'){total++;for (int i = 0; i < p; i++){w[t[i]]--;}for (int i = p; i < 2 * p; i++){w[t[i]]++;}}/* 左重右轻*/else if (sign == '>'){total++;for (int i = 0; i < p; i++){w[t[i]]++;}for (int i = p; i < 2 * p; i++){w[t[i]]--;}}}/* 假币在不等式中每次都应该出现*/ int count = 0, pos = 0;for (int i = 1; i <= n; i++){if (r[i]){continue;}/* 找出每次都出现的"假币" */if (w[i] == total || w[i] == - total){count++;pos = i;}}2、poj 1013 Counterfeit Dollar关于称硬币的问题：此题中赛利已经设计了正确的称量方案，保证从三组称量数据中能得到唯一的答案。

答案可以用两个变量表示：x 假币的标号、w 假币是比真币轻还是比真币重。

x 共有12 种猜测；w 有2 种猜测。

根据赛利设计的称量方案，(x，w )的24 种猜测中，只有唯一的猜测与三组称量数据都不矛盾。

因此，如果猜测(x，w )满足下列条件，这个猜测就是要找的答案：在称量结果为"even'' 的天平两边，没有出现x ；如果w 表示假币比真币轻，则在称量结果为"up'' 的天平右边一定出现x、在称量结果为"down'' 的天平左边一定出现x如果w 表示假币比真币重，则在称量结果为"up'' 的天平左边一定出现x、在称量结果为"down'' 的天平右边一定出现x具体实现时，要注意两点：1) 选择合适的算法对于每一枚硬币x 逐个试探：x 比真币轻的猜测是否成立？猜测成立则进行输出。

x 比真币重的猜测是否成立？猜测成立则进行输出。

2) 选择合适的数据结构以字符串数组存储称量的结果。

每次称量时，天平左右最多有6 枚硬币。

因此，字符串的长度需要为7，最后一位存储字符串的结束符’\0’，便于程序代码中使用字符串操作函数。

char left[3][7], right[3][7], result[3][7];#include <stdio.h>#include <string.h>char left[3][7], right[3][7], result[3][5];int islight( char x ) {int i;for ( i = 1; i <= 3; i++ )switch( result[i][0] ) {case 'u': if( strchr(right[i], x) == NULL ) return 0;break;case 'e': if(strchr(right[i], x) != NULL || strchr(left[i], x) != NULL) return 0;break;case 'd': if(strchr(left[i], x) == NULL) return 0;break;}return 1;}int isheavy( char x ){int i;for ( i = 1; i <=3; i++ )switch( result[i][0] ) {case 'u': if( strchr(left[i], x) == NULL) return 0;break;case 'e': if(strchr(right[i], x) != NULL || strchr(left[i], x) != NULL) return 0;break;case 'd': if(strchr(right[i], x) == NULL) return 0;break;}return 1;}int main(){int i,j,n;char c;scanf("%d",&n);while(n--){for(i=1; i<=3; i++)scanf("%s %s %s",left[i],right[i],result[i]);for(c='A'; c<='L'; c++){if(islight(c)){printf("%c is the counterfeit coin and it is light.\n",c);break;}if(isheavy(c)){printf("%c is the counterfeit coin and it is heavy.\n",c);break;}}}return 0;}/* 假币唯一则输出*/if (count != 1){cout << 0 << endl;}else{cout << pos << endl;}//system("pause");return 0;}3、poj 1083 Moving Tables就是把这400个房间分成200分，1-2，3-4，。

每次移动时，都要把经过的“份”算上，这样最后找份中最大的那个数即可#include <iostream>#include <climits>#include <cstring>#define SIZE 220using namespace std;void swapnum(int &a,int &b);int getindex(int k);int main (){int t,n;cin>>t;while(t--){cin>>n;int x,y;int cross[SIZE];memset(cross,0,sizeof(cross));for(int i=0;i<n;++i){cin>>x>>y;int start,end;if(x>y){swapnum(x,y);}start=getindex(x);end=getindex(y);for(int i=start;i<=end;++i){cross[i]++;}}int maxnum=INT_MIN;for(int i=0;i<SIZE;++i){maxnum=maxnum>cross[i]?maxnum:cross[i];}cout<<maxnum*10<<endl;}return 0;}void swapnum(int &a,int &b){int temp=a;a=b;b=temp;}int getindex(int k){if(k%2==0){return k/2;}else if(k%2==1){return k/2+1;}}4、poj 2028 When Can We Meet?题意：ICPC委员会要安排一个会议，但是成员们都太忙了，所以很难安排，所以要我们编程找个最合适的日子让更多的人来参加这个会议。

一共有N个人，至少要Q个人参加，第i个人有mi天是有空的，分别是date1，date2…..datem，表示明天开始的第datei天，比如date1为1表示明天有空，date2为2表示后天有空，……要输出最好的那天，要求是参加的人尽可能多，如果用相同人数的要尽量靠前。

思路：从第1到max开始枚举，看多少人在第i天有空，如果用>=q的人有空的话，把人数跟i记录下来，放在结构体数组里，最后按人数从大到小排序，如果最大的那个的人数<q 的话输出0，否则就是最大的那个，还要日子靠前的那个。

Max是这么多人的有空的日子里最晚的那天，#include <stdio.h>#include <string.h>#include <stdlib.h>#define N 55#define M 105typedef struct{int index;int count;}item;item items[M];int cmp(const void *p, const void *q){return (*(int *)p) - (*(int *)q);}int cmp2(const void *p, const void *q){item *a = (item *)p;item *b = (item *)q;if(a->count > b->count)return -1;else if(a->count < b->count)return 1;else{return a->index > b->index ? 1 : -1;}}int main(){int i, j, k;int size, quorum, dateNum, result, count, max;int dates[N][M];int *find;while(scanf("%d%d", &size, &quorum) && size && quorum){memset(dates, 0, sizeof(dates));memset(items, 0, sizeof(items));max = 0;for(i=0; i<size; i++){scanf("%d", &dates[i][0]);for(j=1; j<=dates[i][0]; j++){scanf("%d", &dates[i][j]);if(max < dates[i][j])max = dates[i][j];}}for(i=1, k=0; i<=max; i++){for(j=0, count=0; j<size; j++){find = (int *)bsearch(&i, dates[j]+1, dates[j][0], sizeof(dates[j][1]), cmp);if(find != NULL){count++;}}if(count >= quorum){items[k].count = count;items[k].index = i;k++;}if(count == size)break;}qsort(items, k, sizeof(items[0]), cmp2);if(items[0].count >= quorum)printf("%d\n", items[0].index);else printf("0\n");}return 0;}5 、poj 2234 Matches Game 异或的问题不是很理解，没办法强记策略尼姆博奕（Nimm Game）：有n堆各若干个物品，两个人轮流从某一堆取任意多（或者最多m个，只需把每堆%m）的物品，规定每次至少取一个，多者不限，最后取光者得胜。