由于很多低级错误（* 写成了 +），D RE了2发，E WA了5发

D. Bonfire

题意

在一个足够大的平面上，有一堆篝火

在时间 $t=0$ 时，仅在单元格 $(0,0)$ 有一团烟

给你 $N,R,C$ 和字符串 $S$，对于时间 $t=1,2,...,N$，按顺序 执行以下操作：

• 对于所有存在烟的单元格 $(x,y)$：

  如果 $S_t$ = N，则单元格 $(x,y)$ 中烟移动到单元格 $(x-1,y)$。

  同理，W：$(x,y-1)$ S：$(x+1,y)$ E：$(x,y+1)$

• 如果此时单元格 $(0,0)$ 没有烟，就在单元格 $(0,0)$ 再生成一团烟

• 判断此时单元格 $(R,C)$ 是否有烟，若有，输出 1，否则输出 0 （不要换行）

思路

用二维 $\text{set}$ 存储单元格信息：set<int> st[1000005]

第一维代表行，第二维（单个 $\text{set}$）代表列，整体表示当前行所包含的所有的有烟的单元格列号

由于要整体移动，复杂度极高，我们直接考虑将行号和列号移动：

定义变量 $x,y$ 使得坐标 $(p,q)$ 表示实际单元格 $(p+x,q+y)$ ，即单元格$(i,j)$ 对应坐标为 $(i-x,j-y)$

对于每个 $1\le t\le N$，具体操作如下
$$\begin{gathered} \text{N}:x=x+1 \\ \text{S}:x=x-1 \\ \text{E}:y=y+1 \\ \text{W}:y=y-1 \end{gathered}$$
接下来判断单元格 $(0,0)$ 是否有烟，即 st[0-x].find(0-y)!=st.end() 是否成立，若成立，无事发生；否则 st[0-x].insert(0-y)

最后判断单元格 $(R,C)$ 是否有烟，即 st[R-x].find(C-y)!=st.end() 是否成立，若成立，输出 1；否则输出 0

注意对应坐标可能为负数，注意下标不要越界

C++ 代码

#include<bits/stdc++.h>
using namespace std;
set<int> st[1000005];//此处我RE了2次，就是因为数组开的太小，单元格(R,C)所对应的坐标可能小到-4e5
int n,r,c;
string s;
int main(){
	cin>>n>>r>>c>>s;
	int x=-500000,y=0;
	st[-x].insert(0);//为方便理解，下文-a统一写成0-a
	for(int i=0;i<n;i++){
        //步骤1：整体移动烟的位置
		if(s[i]=='N') x--;
		else if(s[i]=='S') x++;
		else if(s[i]=='W') y--;
		else y++;
		
        //步骤2：判断单元格(0,0)是否有烟
		if(st[0-x].find(0-y)==st[0-x].end()) st[0-x].insert(0-y);
        
        //步骤3：判断单元格(R,C)是否有烟
		if(st[r-x].find(c-y)==st[r-xd].end()) cout<<0;
		else cout<<1;
	}
	return 0;
}

E. Tree Game

题意

本题为交互题，请使用 endl 作为换行符（这是最方便的刷新方式）

给你一棵 $N$ 个节点的树，$U_i$ 与 $V_i$ 之间有一条双向边

你现在要玩一个游戏，可以 自行选择先手/后手，双方轮流进行一下操作：

• 选择两个点 $i,j$，要求 $1\le i<j\le N$， $(i,j)$ 之间尚未连边，在 $(i,j)$ 之间连一条边
• 连边之后，不可出现 奇环
• 若无法执行上述操作，这个人就输了

你现在和交互机轮流操作，你必须得赢（保证可以实现），给出方案，格式如下：

• 首先输出 First（先手）或 Second（后手）
• 再轮流输出 $i$ 和 $j$
• 最后，若对方输出 $(-1,-1)$ 表示你已经赢了

思路

显然，树是一个二分图，可以先染色，将节点分为集合 $A$ 和集合 $B$，显然 $|A|+|B|=N$，其中 $|S|$ 表示集合 $S$ 中元素的个数

将 $A$ 与 $B$ 中的点两两连边，显然这个图还是二分图，不会出现奇环，可得共有连 $|A|\times |B|$ 条边

由于树中已经有 $N-1$ 条边，所以一共可以再连 $|A|\times |B|-(N-1)$ 条边，所以操作轮数是 固定的！

设操作轮数为 $k$，若 $k$ 为奇数，则先手必胜；否则后手必胜

把所有可连的边用 set<pair<int,int> > 存储，一定要注意 $i<j$，因为我就是这么WA了5发，每次取 set 中任意一条边输出（建议第一个或最后一个）并删除，随后删除对方所选边，直到第 $\lfloor \frac{k}{2}\rfloor$ 次操作结束

C++ 代码

#include<bits/stdc++.h>
#define mpr make_pair
#define sz(v) (int)v.size()
using namespace std;
const int maxn=105;
int n;
vector<int> g[maxn];
int col[maxn];
bool e[maxn][maxn];
bool used[maxn];
void dfs(int v,int p){
	used[v]=true;
	col[v]=p;
	for(int x:g[v]){
		if(!used[x]){
			dfs(x,p^1);
		}
	}
}
int main(){
    //读入并连边
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
		e[u][v]=e[v][u]=1;
	}
    
    //染色并分割
	dfs(1,0);
	vector<int> a,b;
	for(int i=1;i<=n;i++){
		if(col[i]==0) a.pb(i);
		else b.pb(i);
	}
    
    //计数并统计可连边
	int num=sz(a)*sz(b)-(n-1);
	set<pair<int,int> > st;
	for(int x:a){
		for(int y:b){
			if(!e[x][y]){//注意i<j
				if(x<y) st.insert(mpr(x,y));
				else st.insert(mpr(y,x));
			}
		}
	}
    
    //开始交互并输出
	if(num%2==1){//先手必胜状态
		cout<<"First"<<endl;
		cout<<st.begin()->first<<" "<<st.begin()->second<<endl;
		st.erase(st.begin());
		for(int i=0;i<num/2;i++){
			int p,q;
			cin>>p>>q;
			st.erase(mpr(p,q));
			cout<<st.begin()->first<<" "<<st.begin()->second<<endl;
			st.erase(st.begin());
		}
	}else{//后手必胜状态
		cout<<"Second"<<endl;
		for(int i=0;i<num/2;i++){
			int p,q;
			cin>>p>>q;
			st.erase(mpr(p,q));
			cout<<st.begin()->first<<" "<<st.begin()->second<<endl;
			st.erase(st.begin());
		}
	}
	return 0;
}