spring-outing decision(2).cpp

杭电acm解题报告2001---2099.

//比较BT的模拟题，处理超繁琐，我编了一个钟头差不多，但是调试只用了5分钟，一次AC
//这类题目一定要先整理好处理的思路，多考虑特殊情况
//以免在实际编程过程中出现反复修改，导致程序健壮度降低
//并且要保持自己的思路清晰，全局上控制好程序执行的流动
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int n,m,r;
string name[110];
int table[2][110];
char feel[110][110];
bool go[2][110];
string ans[110];

inline int get_pos(string st,int e)
{
	for (int i=0;i<e;i++) {
		if (name[i] == st) {
			return i;
		}
	}
	return -1;
}

int main()
{
	int p,q,s1,s2;
	int total;
	string str;
	while (cin>>n>>m) {
		total = 0;
		memset(feel,0,sizeof(feel));
		memset(go,0,sizeof(go));
		for (int i=0;i<n;i++) {
			cin>>str;
			s1 = get_pos(str,total);
			if (s1 == -1) {
				s1 = total;
				name[total++] = str;
			}
			cin>>p;
			for (int j=0;j<p;j++) {
				cin>>str;
				s2 = get_pos(str,total);
				if (s2 == -1) {
					s2 = total;
					name[total++] = str;
				}
				feel[s1][s2] = 'g';//good
			}
			
			cin>>q;
			for (j=0;j<q;j++) {
				cin>>str;
				s2 = get_pos(str,total);
				if (s2 == -1) {
					s2 = total;
					name[total++] = str;
				}
				feel[s1][s2] = 'b';//bad
			}
		}
		cin>>r;
		for (i=0;i<r;i++) {
			cin>>str;
			table[0][i] = get_pos(str,n);
			go[0][ table[0][i] ] = true;
		}
		///table[][] mean list of student who go to spring-out
		///table[0] is pre, table[1] is now
		///
		///go[][i] mean the ith student is go or not 
		///go[0] is pre, go[1] is now
		///
		bool hate,like;
		int newr;
		while (m--) {
			newr = 0;
			for (i=0;i<n;i++) {//any body
				hate = like = false;
				for (int j=0;j<r;j++) {//i vs table[j]
					if (go[0][ table[0][j] ]) {
						if (feel[i][ table[0][j] ] == 'g') {
							like = true;
						}
						else if (feel[i][ table[0][j] ] == 'b') {
							hate = true;
						}
					}
				}//j
				if ( like ^ hate) {//one feel
					if (like) {//like
						table[1][newr] = i;
						go[1][i] = true;
						newr++;
					}
					else {//hate
						go[1][i] = false;
					}
				}
				else {
					go[1][i] = go[0][i];
					if (go[1][i]) {
						table[1][newr] = i;
						newr++;
					}
				}
			}//for n
			//类似滚动数组的处理方法
			memcpy(go[0],go[1],sizeof(go[0]));
			memcpy(table[0],table[1],sizeof(table[0]));
			memset(go[1],0,sizeof(go[1]));
			memset(table[1],0,sizeof(table[1]));
			r = newr;
		}//while m
		if(r == 0) {
			cout << "None" <<endl;
			continue;
		}
		for (i=0;i<r;i++) {
			ans[i] = name[ table[0][i] ];
		}
		sort(ans,ans+r);//字典序
		for (i=0;i<r;i++) {
			if (i!=0) {
				cout << ' ';
			}
			cout << ans[i];
		}
		cout<<endl;
	}
}