第三题 路径染色

提交文件 : painting.cpp 输入文件 : painting.in 输出文件 : painting.out 时间空间限制： 2 秒 , 512 MB Z 国可以看作是一个 n 个点， n-1 条道路组成的连通图，每一条 证任意两点间都至少有一条路径。 道路有长度，还有颜色。一开始所有的道路都是白色的。突然有一 过于单调了，于是他决定将某些道路染成黑色。不幸的是，由于种种 人来完成这个目标。具体来说，现在有 M 个机器人，第 i 个机器人所 一个终点 q i ，然后机器人就会沿着最短的距离从 p i 前往 q i 。在前进的 取反，即白色变成黑色，黑色变成白色。当然，指定机器人运动是需 距离，就需要 1 的能量。 现在 Z 国的国王找到了你，他希望你能帮他计算出将所有道路染 不可能。 输入格式 第一行两个整数， n,m 。分别表示 Z 国有 n 个点， m 个机器人。 紧接着 n-1 行，每行四个整数 u,v,l,c 。表示存在有一条道路，连 c=0 ，则表示着该道路希望被染成白色。如果 c=1 ，则表示该道路希望 最后一行，有 m 个整数 p i ，表示第 i 个机器人所在的位置。 输出格式 输出一行一个整数，表示最少需要多少能量。如果无法达到要求 样例数据 painting.in pa 3 2 1 2 1 1 2 3 2 1 1 3 3 5 4 1 2 3 0 2 3 1 1 3 4 2 0 4 5 2 1 1 1 1 1 21 数据范围 对于 20 % 的数据，保证 n, m ≤ 7 对于另外 20 % 的数据，保证 n, m ≤ 100 对于另外 10 % 的数据，保证树的形态是一条链。 对于另外 10 % 的数据，保证 u=1 。

T1

我写了个玄学解法，tm测试样例都错了结果，还AC了这道题，就离谱。

#include<bits/stdc++.h>
using namespace std;
int a[100010];
deque<int> q;
bool dfs(int x,int last){
	bool ans = 0,ans2 = 0;
	if(x == 1)return 1;
	int tmp_f = q.front(),tmp_b = q.back();
	if(q.front() > last){
	    q.pop_front();
		ans =  dfs(x-1,tmp_f);
		//for(int i = 0;i < q.size();i++)cout<<q.front()<<" ";
		//cout<<x<<" "<<ans<<endl;
		q.push_front(tmp_f);
		if(ans == 0)return 1;
    }
    if(q.back() > last){
	    q.pop_back();
		ans2 =  dfs(x-1,tmp_b);
		q.push_back(tmp_b);
		//cout<<x<<" "<<ans2<<endl;
		if(ans2 == 0)return 1;
    }
    if(ans2&&ans)return 0;
    if(q.back() <= last &&q.back() <= last){
    	return 0;
	}
	

}
int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	bool pd1 = 1,pd2 = 1; 
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		q.push_back(a[i]);
		
	}
	if(dfs(n,0)){
		cout<<"Alice";
	}
	else{
		cout<<"Bob";
	}
	return 0;
} 

好了，我发现我哪里挂掉了，这数据真水。

x = 1时不一定要return 1;

真AC代码

#include<bits/stdc++.h>
using namespace std;
int a[100010];
deque<int> q;
bool dfs(int x,int last){
	bool ans = 0,ans2 = 0;
	if(x == 1)return last < q.back()?1:0;
	int tmp_f = q.front(),tmp_b = q.back();
	if(q.front() > last){
	    q.pop_front();
		ans =  dfs(x-1,tmp_f);
	
		q.push_front(tmp_f);
		if(ans == 0)return 1;
    }
    if(q.back() > last){
	    q.pop_back();
		ans2 =  dfs(x-1,tmp_b);
		q.push_back(tmp_b);
		if(ans2 == 0)return 1;
    }
    if(ans2&&ans)return 0;
    if(q.back() <= last &&q.back() <= last){
    	return 0;
	}
	

}
int main(){
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	bool pd1 = 1,pd2 = 1; 
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		q.push_back(a[i]);
		
	}
	if(dfs(n,0)){
		cout<<"Alice";
	}
	else{
		cout<<"Bob";
	}
	return 0;
} 

T2 正解