Atcoder Beginner Contest 272

A - Integer Sum

题目大意: 给定$n$个数字，求$n$个数字的和

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
// typedef long long ll;
const int maxn = 2e5 + 10;
int n,sum;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	for(int i = 1,x;i <= n;++i)
	{
		cin >> x;
		sum += x;
	}
	cout << sum << "\n";
	return 0;
}

B - Everyone is Friends

题目大意: 给定$n$个人以及$m$个分组，问是否每两个人都曾经出现在同一组过

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
// typedef long long ll;
const int maxn = 2e5 + 10;
int n,sum,m;
set<int> a[maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i = 1,num;i <= m;++i)
	{
		cin >> num;
		for(int j = 1,x;j <= num;++j)
		{
			cin >> x;
			a[x].insert(i);
		}
	}
	int f = 0;
	for(int i = 1;i <= n;++i)
	{
		for(int j = i + 1;j <= n;++j)
		{
			int nm = 0;
			for(auto to:a[i])
			{
				auto it = a[j].find(to);
				if(it != a[j].end()) 
				{
					nm++;
				}
			}
			if(nm >= 1) f++;
		}
	}
	if(f == n * (n - 1) / 2) cout << "Yes\n";
	else cout << "No\n";
}

C - Max Even

题目大意: 给定$n(1 \leq n \leq 2e5)$个数字，问两个不相同的数字加起来的最大偶数是多少

解题思路: 分析题目我们可以发现一个关键问题就是两个数字加起来是偶数，那么要么是奇数和奇数相加要么是偶数和偶数相加，我们分类一下数字的奇偶性即可

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
// typedef long long ll;
const int maxn = 2e5 + 10;
int n,sum,m;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	set<int> odd,even;
	cin >> n;
	for(int i = 1,x;i <= n;++i)
	{
		cin >> x;
		if(x & 1) odd.insert(x);
		else even.insert(x);
	}
	int ans = -1;
	if(odd.size() >= 2)
	{
		int res = 0;
		res += *odd.rbegin();
		odd.erase(prev(odd.end()));
		res += *odd.rbegin();
		ans = max(ans,res);
	}
	if(even.size() >= 2)
	{
		int res = 0;
		res += *even.rbegin();
		even.erase(prev(even.end()));
		res += *even.rbegin();
		ans = max(ans,res);
	}
	cout << ans << "\n";
}

D - Root M Leaper

题目大意: 给定一个$n * n(1\leq n \leq 400)$的棋盘，初始点在$(1,1)$，一个点如果在$(i,j)$当且仅当它可以到$(k,l)$存在他们的$\sqrt{(i - k) ^ 2 + (j - l) ^ 2} = \sqrt{m} (1 \leq m \leq 1e5)$

求这个矩阵中的所有点最少需要几步能被走到

解题思路: 发现无论怎么走实际上我们是走不出这个棋盘的，那么实际上$m$最多不会超过$n$，那么我们就可以预处理出所有可以走的步数然后进行$BFS$即可

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
// typedef long long ll;
const int maxn = 5e2 + 10;
const int inf = 1e9;
int n,m;
int tx[] = {1,-1,1,-1};
int ty[] = {1,1,-1,-1};
int dis[maxn][maxn];
int vis[maxn][maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	vector<pair<int,int>> stp;
	int lmt = min(n,m) + 100;
	for(int i = 0;i <= lmt;++i)
	{
		for(int j = 0;j <= lmt;++j)
		{
			if(i * i + j * j == m)
			{
				stp.push_back({i,j});
				stp.push_back({j,i});
			}
		}
	}
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j) dis[i][j] = inf;
	}
	queue<array<int,2>> que;
	que.push({1,1});
	vis[1][1] = 1;
	dis[1][1] = 0;
	while(!que.empty())
	{
		auto [x,y] = que.front();
		que.pop();
		for(auto [spx,spy]:stp)
		{
			for(int k = 0;k <= 3;++k)
			{
				auto fx = x + spx * tx[k];
				auto fy = y + spy * ty[k];
				if(fx >= 1 && fx <= n && fy >= 1 && fy <= n && dis[fx][fy] == inf && vis[fx][fy] == 0)
				{
					dis[fx][fy] = dis[x][y] + 1;
					vis[fx][fy] = 1;
					que.push({fx,fy});
				}
			}
		}
	}
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j)
		{
			if(dis[i][j] == inf) dis[i][j] = -1;
		}
	}
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= n;++j)
		{
			cout << dis[i][j] << " \n"[j == n];
		}
	}
}

E - Add and Mex

题目大意: 给定一个长度为$n (1 \leq n \leq 2e5)$的数组，数组是$int$范围，给定$m$次操作，每次操作第$i$个位置上面的数字都会加上$i$，问这个数组的$mex$是多少

解题思路: 首先我们通过模拟样例可以发现一件事情，就是如果这个序列中的数字是负数，那么它实际上是没有用的，其次是考虑$mex$的性质，因为对于长度为$n$的数组来说，$mex$最大就是$n + 1$，那么对于每一个数字来说最多也不会超过$n + 1$，既然这样，因为对于一个下标为$i$的数字来说，最多加$n / i$次，那么对于整个序列来说就是一个调和级数，模拟即可

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
// typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 1e9;
int n,m;
int ans[maxn],a[maxn];
vector<int> pos[maxn];
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;++i)
	{
		cin >> a[i];
		int st = 0;
		if(a[i] < 0)
		{
			int rd = abs(a[i]) / i;
			if(abs(a[i]) % i) rd++;
			a[i] += i * rd;
			st = rd;
			if(st <= m)
			{
				pos[st].push_back(a[i]);
			}
		}
		while(a[i] + i <= n && st <= m)
		{
			st++;
			a[i] += i;
			if(a[i] >= 0)
			{
				pos[st].push_back(a[i]);
			}
		}
	}
	for(int i = 1;i <= m;++i)
	{
		sort(pos[i].begin(),pos[i].end());
		pos[i].erase(unique(pos[i].begin(),pos[i].end()),pos[i].end());
		int now = 0;
		for(auto to:pos[i])
		{
			if(to != now) break;
			now++;
		}
		cout << now << "\n";
	}
	
}

G - Yet Another mod M

题目大意: 给定一个长度为$n(1 \leq n \leq 5000)$，然后找到一个数字$M$，使得这个序列中每一个数字$mod$ $M$后存在唯一的众数

解题思路: 在赛时就在想随机是否可行但是没有一个好的$check$方案，然后参考了一下严格鸽的题解

首先因为是唯一的众数，那么假设我们在序列中取两个数字，这两个数字$mod$ $M$ 都是$0$的，那么就存在$(x - y) $ $mod$ $m == 0$

那接下来我们去找$(x - y)$的因子就可以了

这样子做的正确概率是：因为$x,y$都有$\frac{1}{2}$的概率取到，那么总的取到的概率就是$\frac{1}{4}$，那我们选择多次选择不到的概率实际上很小，对赌就可以了

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
// #define int long long
// typedef long long ll;
const int maxn = 2e5 + 10;
const int inf = 1e9;
int n,m;
int ans[maxn],a[maxn];
vector<int> pos[maxn];
int check(int x)
{
	if(x < 3) return 0;
	map<int,int> mp;
	for(int i = 1;i <= n;++i)
	{
		mp[a[i] % x]++;
		if(mp[a[i] % x] * 2 > n) return 1;
	}
	return 0;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	srand(time(NULL));
	cin >> n;
	for(int i = 1;i <= n;++i)
	{
		cin >> a[i];
	}
	int cnt = 200;
	while(cnt--)
	{
		int x = a[rand() % n + 1];
		int y = a[rand() % n + 1];
		int d = x - y;
		if(d == 0) continue;
		for(int i = 1;i * i <= d;++i)
		{
			if(d % i != 0) continue;
			if(check(i))
			{
				cout << i << "\n";
				return 0;
			}
			if(check(d / i))
			{
				cout << d / i << "\n";
				return 0;
			}
		}
	}
	cout << -1 << "\n";
	return 0;
}