D - Root M Leaper

链接: https://atcoder.jp/contests/abc272/tasks/abc272_d

大概就是BFS剪枝，T了两次差点没过去

打完才意识到这个M可以直接预处理的，我是傻逼(哭

#include<bits/stdc++.h>
using namespace std;

int n,m;
const int N = 500;
queue<pair<int, int> > q;
int mp[N][N];

int main(){
//	freopen("1.in", "r", stdin);
//	freopen("1.out", "w", stdout);
	int n,m;
	cin>>n>>m;
	q.push(pair<int,int>(1, 1));
	while(!q.empty()){
		int xx = q.front().first, yy = q.front().second;
		q.pop();
		int st = sqrt(m) + 1;
		for(int i = xx - st; i <= xx; i++){
			if(i < 1 || i > n) continue;
			int xt = pow(i - xx, 2);
			double j = sqrt(m - xt);
			if(j > n) break;
			if(int(j) == j){
				if(yy-int(j) > 0 && !mp[i][yy-int(j)]){
					mp[i][yy-int(j)] = mp[xx][yy] + 1;
					q.push(pair<int,int>(i, yy-int(j)));
				}
				if(yy+int(j) <= n && !mp[i][yy+int(j)]){
					mp[i][yy+int(j)] = mp[xx][yy] + 1;
					q.push(pair<int,int>(i, yy+int(j)));
				}	
			}
		}
		for(int i = xx + st; i >= xx; i--){
			if(i < 1 || i > n) continue;
			int xt = pow(i - xx, 2);
			double j = sqrt(m - xt);
			if(j > n) break;
			if(int(j) == j){
				if(yy-int(j) > 0 && !mp[i][yy-int(j)]){
					mp[i][yy-int(j)] = mp[xx][yy] + 1;
					q.push(pair<int,int>(i, yy-int(j)));
				}
				if(yy+int(j) <= n && !mp[i][yy+int(j)]){
					mp[i][yy+int(j)] = mp[xx][yy] + 1;
					q.push(pair<int,int>(i, yy+int(j)));
				}	
			}
		}
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			if(i + j == 2){
				printf("0 ");
				continue;
			}
			printf("%d ", mp[i][j] ? mp[i][j] : -1);
		}
		printf("\n");
	}
} 

E - Add and Mex

原来直接找到每一个数第一次出现的点和最后一次可能出现的点就进行了....(因为是求Mex，所以最大就是n)

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int INF = 1e9;
unordered_map<int, bool> mp[N];

int main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1; i <= n; i++){
		int x;
		scanf("%d", &x);
		if(x + i > n) continue;
		int f,t;
		if(x < 0){
			f = (x % i);
			t = (-x / i);
		} else {
			f = x + i;
			t = 1;
		}
		
		while(f <= n && t <= m){
			mp[t][f] = true;
			f+=i, t++;
		}
	}
	
	for(int i = 1; i <= m; i++){
		int flag = 1;
		for(int j = 0; j <= n; j++){
			if(!mp[i][j]){
				printf("%d\n", j);
				flag = 0;
				break;
			}
		}
		if(flag) printf("%d\n", n);
	}
}