20220309 - 模拟赛 | Final Fantasy = xixike = 人间忽晚，山河已秋

枚举 + 数学，二分图匹配 + 最大流，点分树

依旧是喜闻乐见的暴力写挂（好吧虽然只挂了 15pts）。

# A. 完全平方数

设 $a = gx,\ b = gy \ (g = \gcd(a, b))$ ，然后我们有：

$\begin{cases} a + b =\frac n2 \\ g^2xy = k^2 \\ \gcd(x, y) = 1 \end{cases}$

因此还能推出 $x, y$ 均为完全平方数。

这时我们可以枚举 $g$ ，得到一个 $O(\sum\limits_{2g \mid n}\sqrt{\frac n{2g}})$ 的做法，期望得分 70pts。

考虑进一步缩小 $g$ 的范围。

我们去掉 $g$ 中的完全平方因子，分给 $x, y$ ，仍然可以不重不漏的枚举答案，然后就可以通过此题了。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 5e4 + 5;
	int n, T;
	int p[N], tot;
	bool vis[N];
	int f[N];

	void euler(int n){
	for(int i = 2; i <= n; i++){
	if(!vis[i]) p[++tot] = i;
	for(int j = 1; j <= tot && i * p[j] <= n; j++){
	vis[i * p[j]] = 1;
	if(i % p[j] == 0) break;
	}
	}
	return;
	}

	int calc(int n){
	int res = 0;
	for(int i = 1; i * i <= n && n - i * i >= i * i; i++){
	int t = sqrt(n - i * i);
	res += (t * t == (n - i * i));
	}
	return res;
	}

	void solve(int n){
	if(n & 1) return puts("0"), void();
	n >>= 1;
	int ans = 0, t = n;
	vector <int> vec;
	for(int i = 1; i <= tot && p[i] <= t; i++){
	if(t % p[i] == 0) vec.pb(p[i]);
	while(t % p[i] == 0) t /= p[i];
	}
	if(t > 1) vec.pb(t);
	int sta = 1 << vec.size();
	for(int s = 0; s < sta; s++){
	int g = 1;
	for(int i = 0; i < vec.size(); i++)
	if((s >> i) & 1) g *= vec[i];
	ans += calc(n / g);
	}
	write(ans), puts("");
	return;
	}

	int main(){
	euler(5e4);
	T = read();
	while(T--) solve(read());
	return 0;
	}
	// X.K.

# B. 素数

我们把每个数看做一个节点，和为素数的连边，然后求最大匹配，设为 $k$ 。当 $m < k$ 时，答案就是 $2 \times m$ ；反之，设 $sum$ 为所有可能的和其他牌凑出素数的牌数，答案为 $\min(sum, k + m)$ 。

接下来看如何求最大匹配。

和为素数的两个数必定是一奇一偶（除非两个数都是 1）。

先不考虑 1，我们把偶数放到左边，奇数放到右边，建二分图，使用 $\text{dinic}$ 算法求最大匹配为 $tmp1$ 。
再把 1 当作奇数连边，重新求一遍最大匹配，设为 $tmp2$ ，意味着至少有 $tmp2 - tmp1$ 个 1 可以和左边的偶数匹配，然后剩下的 1 自己两两匹配。

所以最终答案就是 $k = tmp2 + \lfloor \frac {cnt_1 - (tmp2 - tmp1)}{2}\rfloor$

$cnt_1$ 为 1 的个数。

	#include <bits/stdc++.h>
	#define pb push_back

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 3010;
	const int M = 2e6;
	const int INF = 1e9;
	int n, m, s, t, cnt1, sum;
	int a[N];
	struct node{
	int v, w, nxt;
	}edge[N * N];
	int head[N], tot = 1;
	bool vis[M];
	int p[M], cnt;

	inline void euler(){
	vis[1] = 1;
	for(int i = 2; i <= M; ++i){
	if(!vis[i]) p[++cnt] = i;
	for(int j = 1; j <= cnt && i * p[j] <= M; ++j){
	vis[i * p[j]] = 1;
	if(i % p[j] == 0) break;
	}
	}
	}

	inline void add(int x, int y, int z){
	edge[++tot] = (node){y, z, head[x]};
	head[x] = tot;
	}

	inline void Add(int x, int y, int z){
	add(x, y, z), add(y, x, 0);
	}

	inline void build(int k){
	s = n + 1, t = n + 2;
	for(int i = 1; i <= n; ++i){
	cnt1 += (a[i] == k);
	a[i] & 1 ? Add(i, t, 1) : Add(s, i, 1);
	for(int j = 1; j <= n; ++j)
	if(i != j && !vis[a[i] + a[j]]) {sum += k; break;}
	if(a[i] == k \|\| (a[i] & 1)) continue;
	for(int j = 1; j <= n; ++j)// 左边是偶数，右边是奇数
	if(a[j] != k && (a[j] & 1) && !vis[a[i] + a[j]]) Add(i, j, 1);
	}
	}

	inline void clear(){
	memset(head, 0, sizeof(head));
	tot = 1;
	}

	int dep[N], tmp1, tmp2;

	inline bool bfs(){
	queue <int> q;
	memset(dep, 0, sizeof(dep));
	q.push(s), dep[s] = 1;
	while(!q.empty()){
	int x = q.front();
	q.pop();
	for(int i = head[x]; i; i = edge[i].nxt){
	int y = edge[i].v;
	if(edge[i].w && !dep[y]) dep[y] = dep[x] + 1, q.push(y);
	}
	}
	return dep[t];
	}

	inline int dfs(int x, int lim){
	if(x == t \|\| !lim) return lim;
	int flow = 0;
	for(int i = head[x]; i; i = edge[i].nxt){
	int y = edge[i].v;
	if(edge[i].w && dep[y] == dep[x] + 1){
	int res = dfs(y, min(lim, edge[i].w));
	lim -= res, flow += res, edge[i].w -= res, edge[i ^ 1].w += res;
	}
	}
	if(!flow) dep[x] = 0;
	return flow;
	}

	inline void dinic(int &tmp){
	while(bfs()) tmp += dfs(s, INF);
	}

	signed main(){
	// freopen("B.in", "r", stdin);
	// freopen("B.out", "w", stdout);
	euler();
	while(scanf("%d%d", &n, &m) != EOF){
	for(int i = 1; i <= n; ++i) a[i] = read();
	tmp1 = tmp2 = sum = cnt1 = 0;
	build(1), dinic(tmp1), clear();
	build(0), dinic(tmp2), clear();
	tmp2 += (cnt1 - (tmp2 - tmp1)) / 2;
	write(min(sum, min(tmp2, m) + m)), puts("");
	}
	return 0;
	}
	// X.K.

# C. 广播

暴力做法可以强行连边跑最短路。

点分树

先建出点分树，然后在点分树上预处理出一个点可以到达哪些点，以及哪些点可以到达这个点，同时记录下消耗的距离，都存到 $\text{vector}$ 里面。

由于预处理的过程是 $\text{bfs}$ ，所以消耗距离是从小到大的，这时我们把它 $\text{reverse}$ 一下，为了后面方便删点。

然后跑一遍 $\text{bfs}$ ，设当前点为 $x$ ，枚举所有能到达 $x$ 的点 $y$ ，计算一下还能监控的距离，然后枚举 $y$ 能到达的点 $v$ （倒序枚举），判断是否还能监控到，如果可以，更新答案，并把 $v$ 弹出 $\text{vector}$ ，否则退出（因为倒序是从小到大的）。

	#include <bits/stdc++.h>
	#define pb push_back
	#define fi first
	#define se second

	using namespace std;

	namespace IO{
	inline int read(){
	int x = 0;
	char ch = getchar();
	while(!isdigit(ch)) ch = getchar();
	while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	return x;
	}

	template <typename T> inline void write(T x){
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
	}
	}
	using namespace IO;

	const int N = 2e5 + 10;
	int n, all, rt;
	int a[N], siz[N], mx[N];
	bool vis[N];
	vector <int> g[N];

	inline void getroot(int x, int f){
	siz[x] = 1, mx[x] = 0;
	for(auto y : g[x]){
	if(y == f \|\| vis[y]) continue;
	getroot(y, x);
	siz[x] += siz[y], mx[x] = max(mx[x], siz[y]);
	}
	mx[x] = max(mx[x], all - siz[x]);
	if(!rt \|\| mx[rt] > mx[x]) rt = x;
	}

	typedef pair<int, int> P;
	queue <int> q;
	int dis[N], col[N];
	vector <P> to[N], from[N];

	inline void solve(int x){
	q.push(x);
	vis[x] = 1, dis[x] = 0, col[x] = x;
	while(!q.empty()){
	int u = q.front();
	q.pop();
	to[x].pb(P(u, dis[u])), from[u].pb(P(x, dis[u]));
	for(auto v : g[u]){
	if(col[v] == x \|\| vis[v]) continue;
	col[v] = x, dis[v] = dis[u] + 1;
	q.push(v);
	}
	}
	int sum = all;
	reverse(to[x].begin(), to[x].end());
	for(auto y : g[x])
	if(!vis[y]){
	all = siz[y] > siz[x] ? sum - siz[x] : siz[y];
	rt = 0, getroot(y, x), solve(rt);
	}
	}

	int ans[N];

	inline void bfs(){
	memset(vis, 0, sizeof(vis));
	q.push(1), vis[1] = 1;
	while(!q.empty()){
	int x = q.front();
	q.pop();
	for(auto y : from[x]){
	int u = y.fi, d = a[x] - y.se;
	while(to[u].size() && to[u].back().se <= d){
	int v = to[u].back().fi;
	if(!vis[v]) ans[v] = ans[x] + 1, q.push(v), vis[v] = 1;
	to[u].pop_back();
	}
	}
	}
	}

	signed main(){
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 1; i < n; ++i){
	int u = read(), v = read();
	g[u].pb(v), g[v].pb(u);
	}
	all = n, mx[rt = 0] = n;
	getroot(1, 0), solve(rt), bfs();
	for(int i = 2; i <= n; ++i) write(ans[i]), putchar(' ');
	puts("");
	return 0;
	}
	// X.K.

# A. 完全平方数

# B. 素数

# C. 广播

20220307

20220311