最近因为去考驾照了,所以615 Div.3也没参加,驾考挺简单的,可算再也不用见我们那个讨厌的教练了,顺利拿到了驾照。

A题
很简单,纯模拟,我算了下时间复杂度是够得,一开始WA了一次我以为时间复杂度有问题,仔细审查发现没毛病,于是又***了两次,连着WA了三次,最后自己找特殊数据测发现边界不对,一次是下边界出,另外一次是上边界,以后测试的时候要考虑到边界情况。

B题
其实这种题本质都是数学题,代码只是实现,盲猜结论过了,要好好学数学啊!

C题
想到BFS和DFS,有考虑到连着询问不该这么复杂,而且我对时间复杂度和空间复杂度的概念还不够清晰,写了半小时的DFS最后超时了,BFS和DFS还不能熟练的快速实现,而且经常会忘记回溯、做标记之类的。还需要重新再学一下。

这道题其实没那么复杂
只要检测输入点 对应的另外一行的 对应点 对应点的前一位 对应点的后一位 构造锁链即可;

想象成每有2个点都为1不能通过则锁链+1,锁链可以左斜 右斜 竖直。

我也不知道这叫什么算法,主要是要建立出这个模型,不断维护,才能满足询问次数可能为1e5的情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;

int a[3][maxn];
 
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	int n,q,x,y;
	ll cnt=0;
	memset(a,0,sizeof(a));
	cin>>n>>q;
	while(q--){
		cin >> x >> y;
		a[x][y] ^= 1;
		if(a[x][y] == 1){
			cnt += a[3-x][y-1] + a[3-x][y] + a[3-x][y+1];
		} else{
			cnt -= a[3-x][y-1] + a[3-x][y] + a[3-x][y+1];
		}
		cout << (cnt == 0 ? "Yes" : "No") << '\n';
	}
    return 0;
} 

codeforces掉分已经成了日常。 TnT