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