第1题     01游戏（game）

Alice和Bob在玩游戏。初始有一个仅由01构成的字符串。Alice和Bob轮流进行游戏，Alice先行。轮到某个人的时候，他需要从原串中找到并删除两个相邻且不同的字符（01或10)，无法操作者输。两人都用最优的策略进行，你需要确定谁能够赢得游戏。

输入格式

第一行输入一个整数t表示测试数据的数量。

接下类每组数据输入一个字符串s,表示初始字符串。

输出格式

对于每组数据，如果Alice赢，输出DA,否则输出NET。

输入/输出例子1

输入：

3

01

1111

0011

输出：

DA

NET

NET

样例解释

数据范围

对于50%数据，保证字符串的长度|s|≤10。

对于100%数据，保证字符串的长度|s|≤100，1≤t≤1000。

#include
using namespace std;
string s;
int n;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>s;
		int zero,one;
		zero=one=0;
		for(int i=0;i 
 
第2题     有趣的水管 
 
P城想建立一条管道系统，城市中恰巧有n间房屋，市长想要每一间房屋都能通上自来水。起初，市长只有一个可以供水的水管，和几个分离器。
 
 
分离器由一个输入口（输入口可以连接到水管或者上一个能流出水的输出管道）和x个输出口构成，当分离器连接到水管时，水会从每个输出口流出。因为总水源只有一个，所以只有一根水管的入口可以与水源连接。
 
 
 
 
市长有k - 1种分离器，每种分离器只有一个，k - 1种分离器的输出口分别为2，3，4 ...... k个。 现在需要有n户房屋通水，即恰好有n个输出口流出水来，市长至少需要多少个分离器呢？ 
 
  
  
输入格式 
  
输入只有一行，包括两个用空格隔开的整数n和k（1 <= n <= 1e18，2 <= k <= 1e9） 
 
  
  
  
输出格式 
  
输出需要的最少分离器的数量，如果方案不存在则输出-1 
 
  
  
  
输入/输出例子1 
  
输入：
 
  
4 3
 
  
输出：
 
  
2
 
  
  
  
输入/输出例子2 
  
输入：
 
  
5 5 
 
  
输出：
 
  
1
 
  
  
  
输入/输出例子3 
  
输入：
 
  
8 4
 
  
输出：
 
  
-1
 
  
 
  
#include
using namespace std;
long long n,k;
bool check(int x)
{
	long long sum=(k+k-x+1)*x/2-x+1;
	return sum>=n;
}
int main()
{
	cin>>n>>k;
	int low=0;
	int high=k+1;
	while(low+1 
  
第3题     平面上的直线 
  
在一个坐标平面中，有n个点，定义第i个点的坐标是(i, yi)。 现在给小C一个点集，小C的任务是确定是否有可能绘制出两条平行且不重叠的直线，使集合中的每个 点都恰巧可以落在其中一条直线上，并且保证每条直线上至少有一个点。 现在请你来帮助小C解决这个问题。 
 
   
   
输入格式 
   
多组测试数据，第一行输入测试的组数T，1 <= T < 10
 
   
第2n（n = 1, 2, 3 ... T）行：一个正整数n（3 <= n <= 1000），代表点的数量
 
   
第2n + 1（n = 1, 2, 3 ... T）行：有n个用空格隔开的整数y1, y2 ... yn（|yi| <= 1000000000），代表每个点的纵坐标 
 
   
   
   
输出格式 
   
输出T行分别表示T组数据的判断结果，如果小C可以找到这样的两条线，输出"Yes"，如果找不到这样的两条线，输出"No"
 
   
   
   
输入/输出例子1 
   
输入：
 
   
1
 
   
5
 
   
100 0 0 0 0 
 
   
输出：
 
   
Yes
 
   
   
   
输入/输出例子2 
   
输入：
 
   
1
 
   
6
 
   
2 2 3 3 4 4 
 
   
输出：
 
   
Yes
 
   
   
   
输入/输出例子3 
   
输入：
 
   
1
 
   
5
 
   
2 3 4 5 6 
 
   
输出：
 
   
No
 
   
   
   
样例解释 
   
样例解释
 
   
样例一：
 
   
（1，100）在一条直线上，
 
   
（2，0）（3，0）（4，0）在一条直线上，并且两条直线平行
 
   
样例二：
 
   
（1，2）（3，3）（5，4）在一条直线上，
 
   
（2，2）（4，3）（6，4）在一条直线上，并且两条直线平行
 
   
数据范围
 
   
对于50%的数据，3 <= n <= 50
 
   
对于75%的数据，3 <= n <= 500
 
   
对于100%的数据，3 <= n <= 1000，1 <= T < 10 
 
   
#include 
using namespace std;

int n, a[1005], T;

bool Check(double k){
	bool flag = 0;
	int w = -1;
	for(int i = 2; i <= n; i++){
		if((a[i] - a[1]) == k * (i - 1))	continue;
		flag = 1;
		if(w == -1)	w = i;
		else if((a[i] - a[w]) != k * (i - w)){
			flag = 0;
			break;
		}
	}
	return flag;
}

int main(){
    scanf("%d", &T);
    while(T--){
    	scanf("%d", &n);
	    for(int i = 1; i <= n; i++)	scanf("%d", &a[i]);
	    double k1 = (a[2] - a[1]) * 1.0;  
	    double k2 = (a[3] - a[1]) * 1.0 / 2;
	    double k3 = (a[3] - a[2]) * 1.0;
	    if(Check(k1) || Check(k2) || Check(k3))	printf("Yesn");
	    else printf("Non");
    }
}
 
   
第4题     画画(paint) 
   
小A是一名画家。
 
   
现在有一张大小为n* m的网格图，小A用k种颜色在网格图上作画。其中第i种颜色编号为i，初始时网格图中每个格子都没有颜色，编号为0。
 
   
已知每种颜色小A都会使用且只使用一次，但使用的顺序是未知的。使用一种颜色时需要选定一个连续的子矩阵，将该子矩阵涂上这种颜色。
 
   
后涂的颜色会覆盖之前的颜色。现在给出小A画完后的图，问有多少种颜色可能是小A最先使用的。
 
    
    
输入格式 
    
第一行三个数n,m,k，表示网格图的大小和颜色的数量。
 
    
之后n行，每行m个数，描述网格图中每个格子的颜色。
 
    
    
    
输出格式 
    
一个数，表示有多少种颜色可能时小A最先使用的。
 
    
    
    
输入/输出例子1 
    
输入：
 
    
3 4 8
 
    
2 3 0 5
 
    
2 3 7 7
 
    
2 7 7 7
 
    
输出：
 
    
7 
 
    
    
    
样例解释 
    
【样例解释】
 
    
只有3号颜色不可能是最先使用的。
 
    
【数据规模】
 
    
对于30%的数据，1≤n * m, k ≤20
 
    
对于60%的数据，1≤n * m,k ≤1000
 
    
对于另外20%的数据，1≤m, k ≤ 10^5, n= 1
 
    
对于100%的数据，1≤n * m,k ≤ 10^5
 
    
#include
using namespace std;
int n,m,k;
int a[2000100],vis[2000100],f[2000100],f1[2000100];
int grid(int i,int j) 
{
	return (i-1)*(m+1)+j;
}
struct Color{
	int l,r,t,b;
	Color()
	{
		r=0;l=100010;
		t=100010;b=0;
	}
	void update(int ll,int rr,int tt,int bb)
	{
		l=min(l,ll);r=max(r,rr);t=min(t,tt);b=max(b,bb);
	}
}color[100010];
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int p=grid(i,j);
			cin>>a[p];
			color[a[p]].update(j,j,i,i);
		}
	}
	for(int i=1;i<=k;i++){
		if(color[i].r==0) continue;
		int xx1=color[i].t;int xx2=color[i].b;
		int yy1=color[i].l; int yy2=color[i].r;
		int p1=grid(xx1,yy1);int p2=grid(xx1,yy2+1);
		f[p1]++;f[p2]--;
		int p3=grid(xx2+1,yy1);
		int p4=grid(xx2+1,yy2+1);
		f[p3]--;	f[p4]++;
	}
	for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				int p=grid(i,j);
				f1[p]=f1[grid(i-1,j)]+f1[grid(i,j-1)]-f1[grid(i-1,j-1)]+f[p];
				if(f1[p]>1)
					vis[a[p]]=1;
			}
		}
	int ans=0;int use=0;
	for(int i=1;i<=k;i++)
	{
		if(vis[i]){
			ans++;
		}
		if(color[i].r!=0) use++;
	}
		
	if(use==1&&k!=1) ans=1; 
	cout<