USACO2022DecemberContest,Bron-创新互联

Farmer John 有 N（1≤N≤105）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1…N。
由于奶牛们都饿了，FJ 决定在 1…N 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。
每头奶牛愿意移动至多 K（0≤K≤N−1）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。
输入格式（从终端 / 标准输入读入）：
每个测试用例包含 T 个子测试用例，为一种奶牛的排列。输入的第一行包含 T（1≤T≤10）。以下是 T 个子测试用例。
每个子测试用例的第一行包含 N 和 K。第二行包含一个长度为 N 的字符串，其中第 i 个字符表示第 i 头奶牛的品种（G 表示更赛牛，H 表示荷斯坦牛）。
输出格式（输出至终端 / 标准输出）：
对于 T 个子测试用例中的每一个，输出两行。第一行输出喂饱所有奶牛所需的最小草地数量。第二行输出一个长度为 N 的字符串，表示一种使用最小草地数量喂饱所有奶牛的种植方案。第 i 个字符表示第 i 个位置，若不种草则为 ‘.’，若种植喂饱更赛牛的草则为 ‘G’，若种植喂饱荷斯坦牛的草则为 ‘H’。任何合法的方案均可通过。
输入样例：
6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH
输出样例：
5
GHHGG
3
.GH.G
2
…GH.
2
…GH
2
…HG
2
HG
注意对于某些子测试用例，存在多种可通过的方案使用最小数量的草地。例如，在第四个子测试用例中，以下是另一个可以通过的答案：
.GH…
这个方案在第二个位置种植一块喂饱更赛牛的草地以及在第三个位置种植一块喂饱荷斯坦牛的草地。这使用了最小数量的草地并确保了所有奶牛都在她们喜欢的草地的 3 个位置以内。
测试点性质：
测试点 2-4 满足 N≤10。
测试点 5-8 满足 N≤40。
测试点 9-12 满足 N≤105。
供题：Mythreya Dharani

这题……耗了我一个小时。。。
先简要介绍一下，我的思路是：最优解必定是当前位置+k，而如果放置在这儿，那么在当前位置+2k的范围内即无需再放置该种类草。但需要解决一个问题：当当前位置+k>n怎么办？我是这样解决的：while(a[n-pp] == ‘G’||a[n-pp] == ‘H’)++pp;
这样可以统一调配：当然无须担心没位置或位置小于当前位置（出界时必定该种类草已经不需要了）

#includeusing namespace std;

long long k,t,n,fine,way;
char q[100010],ans[100010];

void readp(){cin>>n>>k;
	for(long long i=1;i<=n;++i)cin>>q[i];
}

void work(){long long G=0,H=0;
	for(long long i=1;i<=n;++i){if(q[i]=='G'&&G	long long p=i+k;
			if(p>n){		long long pp=0;
				while(ans[n-pp]=='G'||ans[n-pp]=='H'){++pp;
				}
				p=n-pp;
			}
			ans[p]='G';
			G=i+k+k;
			++way;
		}
		else if(q[i]=='H'&&H	++way;
			long long p=i+k;
			if(p>n){		long long pp=0;
				while(ans[n-pp]=='G'||ans[n-pp]=='H'){++pp;//若出界，在界内以保持最优的原则（哎呀，其实没必要，只要你保证不重且位置在当前位置后即可）从后向前分配
				}
				p=n-pp;
			}
			ans[p]='H';
			H=i+k+k;
		}
		if(ans[i]!='G'&&ans[i]!='H'){	ans[i]='.';
		}
	}
}

void out(){cout<cin>>t;
	for(long long i=1;i<=t;++i){readp();
		work();
		out();
	}
	return 0;
}

从今天起，我要养成好习惯----非空间必要全开long long！！！

Elsie 有一个程序，接受一个 N（1≤N≤100）个变量的数组 b[0],…,b[N−1] 作为输入，其中每个变量等于 0 或 1，并且返回对输入数组应用一系列 if / else if / else 语句的结果。每个语句检查至多一个输入变量的值，并返回 0 或 1。这类程序的一个例子是：
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
例如，如果上方程序的输入是 “10”（即 b[0]=1 及 b[1]=0），那么输出应当为 1。
Elsie 告诉了 Bessie 对于 M（1≤M≤100）个不同输入的正确输出。Bessie 现在正试图对 Elsie 的程序进行逆向工程。不幸的是，Elsie 可能说了谎；可能不存在上述形式的程序行为与 Elsie 所说的均一致。
对于 T（1≤T≤10）个子测试用例中的每一个，判断 Elsie 是否一定在说谎。
输入格式（从终端 / 标准输入读入）：
输入的第一行包含 T，为子测试用例的数量。
每一个子测试用例的第一行包含两个整数 N 和 M，以下 M 行，每行包含一个由 N 个 0 或 1 组成的字符串，表示一个输入（即 b[0]…b[N−1] 的值），以及另一个字符（0 或 1）表示输出。相邻的子测试用例之间用空行分隔。
输出格式（输出至终端 / 标准输出）：
对于每一个子测试用例，输出一行，包含 “OK” 或 “LIE”，分别表示 Elsie 可能没有说谎或是一定在说谎。
输入样例：
4
1 3
0 0
0 0
1 1
2 4
00 0
01 1
10 1
11 1
1 2
0 1
0 0
2 4
00 0
01 1
10 1
11 0
输出样例：
OK
OK
LIE
LIE
以下是第一个子测试用例的一个合法的程序：
if (b[0] == 0) return 0;
else return 1;
以下是第一个子测试用例的另一个合法的程序：
if (b[0] == 1) return 1;
else return 0;
以下是第二个子测试用例的一个合法的程序：
if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
显然，对于第三个子测试用例不存在对应的合法的程序，因为 Elsie 的程序一定始终对相同的输入产生相同的输出。
可以证明对于最后一个子测试用例不存在对应的合法的程序。
测试点性质：
测试点 2-3 满足 N=2。
测试点 4-5 满足 M=2。
测试点 6-12 没有额外限制。
供题：Benjamin Qi

第3题，欲哭无泪……
分析----拿样例举一波例子：

00 0
01 1
10 1
11 0

看，00和01结果不一样但是第一位一样，说明第一个if语句不可能是判断是否为0
10与11结果不一样但是第一位一样，说明第一个if语句也不可能判断是否为1，所以就错了。
（也可以这么看：00与10结果不一样但是第二位一样，说明对应的if语句不可能是判断是否为0，01与11结果不一样但是第二位一样，说明对应的if语句也不可能是判断是否为1，所以出错）
（更多见注释）

#includeusing namespace std;

int main(){int t,m,n;
	string s[110];
	bool v[110];
	cin>>t;
	while(t--){cin>>n>>m;
		for(int i=1;i<=m;++i)cin>>s[i]>>v[i];
		int ans0=0,ans1=0,vh[2][2];//vh数组用于统计数量，如：vh[1][0]统计的是结果是0有的1的个数
		int vh1[110],vh2[110];//vh1，vh2用于标记，如果审核发现没问题（且确定了思路中提到的确定了if的条件），就删掉，接下来就不处理该数据了。vh1标记的是第几位被标记，vh2只标记具体的某一个数
		memset(vh1,0,sizeof(vh1));
		memset(vh2,0,sizeof(vh2));
		for(int i=1;i<=m;++i)
			if(v[i]==0)ans0++;
			else ans1++;//先统计结果中是0还是1的个数
		bool bl=1,bo=0;
		while(bl){	bl=0;
			for(int i=0;i		if(!vh1[i]){memset(vh,0,sizeof(vh));
					for(int ii=1;ii<=m;++ii)
						if(!vh2[ii])vh[s[ii][i]-'0'][v[ii]]++;
					if(vh[0][0]==0&&vh[0][1]!=0){//
						bl=1;
						ans1-=vh[0][1];
						for(int j=1;j<=m;++j)
							if(s[j][i]=='0')vh2[j]=1;
					}
					if(vh[0][1]==0&&vh[0][0]!=0){bl=1;
						ans0-=vh[0][0];
						for(int j=1;j<=m;++j)
							if(s[j][i]=='0')vh2[j]=1;
					}
					if(vh[1][0]==0&&vh[1][1]!=0){bl=1;
						ans1-=vh[1][1];
						for(int j=1;j<=m;++j)
							if(s[j][i]=='1')vh2[j]=1;
					}
					if(vh[1][1]==0&&vh[1][0]!=0){bl=1;
						ans0-=vh[1][0];
						for(int j=1;j<=m;++j)
							if(s[j][i]=='1')vh2[j]=1;
					}
					if(bl){vh1[i]=1;
						break;
					}
				}
			} 
		}
		if(ans0==0||ans1==0)cout<<"OK"<