2021-08-24暑假集训

发表于

完全平方数

难度:

思维难度 : 三星

代码难度 : 一星

标签:

数学

思路:

求出 nn 的所有约数，对于每个不含平方因子的因数，求出把它拆成两个完全平方数的方案数。可以保证不重不漏。 因为对于 abab ，可以看成 g2xyg^2xy ，gg 是 gcd⁡(a,b)\gcd(a,b) , 所以 abab 的贡献会在 abgcd⁡(a,b)\frac{ab}{\gcd(a,b)} 处被统计。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cmath>
#include <cstdio>
#define MAXN 32000
#include <iostream>
using namespace std;
int minFactor[MAXN];
int prime[MAXN], primeNum;
void prime_table() {
    for (int i = 2; i < MAXN; i++) {
        if (!minFactor[i]) {
            prime[primeNum++] = i;
            minFactor[i]      = primeNum;
        }
        for (int j = 1; j <= minFactor[i]; j++) {
            int t = i * prime[j - 1];
            if (t >= MAXN)
                break;
            minFactor[t] = j;
        }
    }
}
int fact[20];
int cal(int n) {
    int ret = 0;
    int i = 1, j = sqrt(n);
    while (i <= j) {
        int x = i * i + j * j;
        if (x == n) {
            ret++;
        }
        if (x >= n) {
            j--;
        }
        if (x <= n) {
            i++;
        }
    }
    return ret;
}
int T, n;
int main() {
    prime_table();
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        if (n % 2 == 1) {
            printf("0\n");
            continue;
        }
        n /= 2;
        int cnt = 0, ans = 0, m = n;
        for (int i = 0; i < primeNum; i++) {
            int x = prime[i];
            if (x * x > m)
                break;
            if (m % x == 0) {
                fact[cnt++] = x;
                while (m % x == 0) {
                    m /= x;
                }
            }
        }
        if (m != 1)
            fact[cnt++] = m;
        for (int i = 0; i < (1 << cnt); i++) {
            int x = 1;
            for (int j = 0; j < cnt; j++) {
                if (i & (1 << j))
                    x *= fact[j];
            }
            ans += cal(n / x);
        }
        printf("%d\n", ans);
    }
    return 0;
}

总结:

一般和完全平方数有关的题可以考虑拆成因数或质因数.

素数

难度:

思维难度 : 三星

代码难度 : 三星半

标签:

网络流

思路

发现除了 11 以外，其它数可以的和要想是素数就必须分别是一个奇数和一个偶数。那么先考虑不放 11 跑一遍费用流，然后对于没有匹配的数要考虑和 11 匹配，于是把 11 放到图中跑一遍费用流，如果还有剩余的 11 , 就让这些 11 两两配对组成 22 ，显然这样是最优的.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
/*
    \  | ^  ^  \
   -- | #    # \
   \_|   	   \
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define inf 0x3f3f3f3f

using namespace std;

const int N = 1e7 + 10;
int head[N], to[N], nxt[N], c[N], e_tot, cur[N], dep[N], deg[N];
int pri[3000010], vis[3000010], tot;
int q[N], h, t, a[N];
int n, m;
int S, T, S1, num, res1, res2;

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

void add(int x, int y, int z)
{
    nxt[++e_tot] = head[x];
    head[x] = e_tot;
    to[e_tot] = y;
    c[e_tot] = z;
}

int bfs(int S, int T)
{
    for (int i = 1; i <= n + 3; ++i) cur[i] = head[i];
    for (int i = 1; i <= n + 3; ++i) dep[i] = 0;
    for (int i = 1; i <= n + 3; ++i) q[i] = 0;
    dep[S] = 1;
    q[h = t = 1] = S;
    while (h <= t)
    {
        int u = q[h++];
        for (int i = head[u]; i; i = nxt[i])
        {
            int v = to[i];
            if (!dep[v] && c[i]) dep[v] = dep[u] + 1, q[++t] = v;
        }
    }
    return dep[T];
}

int dfs(int u, int T, int lim)
{
    if (u == T || !lim) return lim;
    int flow = 0, k;
    for (int i = head[u]; i && lim; i = nxt[i])
    {
        cur[u] = i;
        int v = to[i];
        if (dep[v] != dep[u] + 1 || !c[i]) continue;
        k = dfs(v, T, min(c[i], lim));
        if (!k) dep[v] = 0;
        flow += k, lim -= k;
        c[i] -= k, c[i ^ 1] += k;
    }
    return flow;
}

int dinic(int S, int T)
{
    int res = 0;
    while (bfs(S, T)) res += dfs(S, T, inf);
    return res;
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif
    euler(3000000);
    while(scanf("%d%d", &n, &m) != EOF)
    {
        S = n + 1, T = n + 2, S1 = n + 3, num = 0, e_tot = 1;
        memset(deg, 0, sizeof(deg));
        memset(head, 0, sizeof(head));
        memset(nxt, 0, sizeof(nxt));
        memset(c, 0, sizeof(c));
        memset(to, 0, sizeof(to));
        e_tot = 1;
        for (int i = 1; i <= n; ++i) {scanf("%d", &a[i]); if(a[i] == 1) ++num;}
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                if (a[i] == 1 || a[j] == 1) continue;
                if (!vis[a[i] + a[j]]) 
                {
                    if (a[i] % 2 == 1) add(i, j, 1), add(j, i, 0);
                    else add(j, i, 1), add(i, j, 0);
                }
            }
        }
        add(S, S1, m), add(S1, S, 0);
        for (int i = 1; i <= n; ++i)
        {
            if (a[i] % 2 == 1 && a[i] != 1) add(S1, i, 1), add(i, S1, 0);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (a[i] % 2 == 0) add(i, T, 1), add(T, i, 0);
        }
        res1 = dinic(S, T);
        memset(head, 0, sizeof(head));
        memset(nxt, 0, sizeof(nxt));
        memset(c, 0, sizeof(c));
        memset(to, 0, sizeof(to));
        e_tot = 1;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j < i; ++j)
            {
                if (a[i] == 1 || a[j] == 1) continue;
                if (!vis[a[i] + a[j]]) 
                {
                    if (a[i] % 2 == 1) add(i, j, 1), add(j, i, 0);
                    else add(j, i, 1), add(i, j, 0);
                }
            }
        }
        add(S, S1, m), add(S1, S, 0);
        for (int i = 1; i <= n; ++i)
        {
            if (a[i] % 2 == 1 && a[i] != 1) add(S1, i, 1), add(i, S1, 0);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (a[i] % 2 == 0) add(i, T, 1), add(T, i, 0);
        }
        for (int i = 1; i <= n; ++i)
        {
            if (a[i] == 1)
            {
                add(S1, i, 1), add(i, S1, 0);
                for (int j = 1; j <= n; ++j)
                {
                    if (a[j] != 1 && !vis[a[i] + a[j]]) add(i, j, 1), add(j, i, 0);
                }
            }
        }
        res2 = dinic(S, T);
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i + 1; j <= n; ++j)
            {
                if (!vis[a[i] + a[j]]) ++deg[i], ++deg[j];
            }
        }
        if (m + res2 + (num - (res2 - res1)) / 2 > 2 * m)
        {
            cout << 2 * m << endl;
            continue;
        }
        int ywk = 0;
        for (int i = 1; i <= n; ++i) if (deg[i] > 0) ++ywk;
        cout << min(ywk, m + res2 + (num - (res2 - res1)) / 2) << endl;
    }
    return 0;
}

总结:

注意特判 11 的情况，还有 22 也是质数。

广播

难度:

思维难度 : 四星

代码难度 : 三星半

标签:

点分治 + 最短路

思路:

对于一个点，开一些结点 CC , CiC_i 向 Ci−1C_{i-1} 连长度为 00 的边， 这个点在点分树上的儿子，如果距离这个点是 ii , 就向 CiC_i 连边。同时从 CiC_i 向它连边。这样最多一共会有 O(nlg⁡n)O(n\lg n) 个结点，然后跑最短路就行.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <iostream>
#include <cstdio>
#include <vector>
#include <deque>
#include <cstring>

using namespace std;

const int N = 1e7 + 10;
int n;
int val[N];
int head[N], nxt[N], to[N], len[N], e_tot;
int dep[N], fa[N], siz[N];
int d[N];
int vis[N];
int rt;
int mx[N];
vector<int> path[N];
int c[N], a[N];
int tot, sz;

void add(int x, int y, int z) {
    nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y, len[e_tot] = z;
}

void getroot(int u, int _fa, int S) {
    siz[u] = 1, mx[u] = 0;
    for (auto v : path[u]) {
        if (v == _fa || vis[v]) continue;
        getroot(v, u, S);
        siz[u] += siz[v];
        mx[u] = max(mx[u], siz[v]);
    }
    mx[u] = max(mx[u], S - siz[u]);
    if (!rt || mx[u] < mx[rt]) rt = u;
}

int dfs1(int u, int _fa) {
    a[++sz] = u;
    int mx = 0;
    for (auto v : path[u]) {
        if (v == _fa || vis[v]) continue;
        d[v] = d[u] + 1;
        mx = max(dfs1(v, u) + 1, mx);
    }
    return mx;
}

void calc(int s) {
    sz = 0;
    d[s] = 0;
    int max_dep = dfs1(s, 0);
    for (int i = 0; i <= max_dep; ++i) {
        c[i] = ++tot;
        if (i > 0) add(c[i], c[i - 1], 0);
    }
    for (int i = 1; i <= sz; ++i) {
        int v = a[i];
        add(c[d[v]], v, 0);
        if (val[v] - d[v] < 0) continue;
        add(v, c[min(max_dep, val[v] - d[v])], 1);
    }
}

void solve(int u) {
    vis[u] = 1;
    calc(u);
    for (auto v : path[u]) {
        if (vis[v]) continue;
        rt = 0;
        getroot(v, 0, siz[v]);
        solve(rt);
    }
}

deque<int> q;
int dis[N];

void bfs(int S) {
    memset(dis, 0x3f, sizeof(dis));
    q.push_front(S);
    dis[S] = 0;
    while (q.size()) {
        int u = q.front();
        q.pop_front();
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (dis[v] > dis[u] + len[i]) {
                dis[v] = dis[u] + len[i];
                if (len[i] == 0) q.push_front(v);
                else q.push_back(v);
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) 
        scanf("%d", &val[i]), val[i] = min(val[i], n);
    for (int i = 2; i <= n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        path[x].push_back(y);
        path[y].push_back(x);
    }
    tot = n;
    rt = 0;
    getroot(1, 0, n);
    solve(rt);
    bfs(1);
    for (int i = 2; i <= n; ++i) {
        printf("%d ", dis[i]);
    }
    return 0;
}

总结:

有一个套路，就是对于一个点，开一些结点 CC , CiC_i 向 Ci−1C_{i - 1} 连长度为 00 的边，对于其它点, 如果距离这个点是 ii , 就向 CiC_i 连边。这样就可以用很少的边来代替距离小于某个值的点之间的连边.

【2019FJ省队集训】树

难度:

思维难度 : 三星半

代码难度 : 三星

标签:

分块

思路:

对区间分块，对于整块，预处理出每个点到这个块中最近的点的距离，dpdp 一下就行。对于零散块，直接暴力算, 复杂度 O(mn)O(m \sqrt{n}) .

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 2e5 + 10;
int n, m;
int B, cntB;
int head[N], nxt[N], to[N], len[N],  e_tot;
int dis[N], w[N];
int pos[N];
int l[N], r[N], f[330][100010];
int dep[N], fa[N];
int dfn[N], id[N], tim;
int beg[N], eul[N], tot;
int lg[N];

void add(int x, int y, int z) {
    nxt[++e_tot] = head[x], head[x] = e_tot, to[e_tot] = y, len[e_tot] = z;
}

void dfs(int u, int _fa) {
    beg[u] = ++tot;
    eul[tot] = u;
    dfn[u] = ++tim;
    id[tim] = u;
    fa[u] = _fa;
    dep[u] = dep[_fa] + 1;
    for (int i = head[u]; i; i = nxt[i]) {
        int v = to[i];
        if (v == _fa) continue;
        w[v] = len[i];
        dis[v] = dis[u] + len[i];
        dfs(v, u);
        eul[++tot] = u;
    }
}

struct ST {
    int minn[N][20], id[N][20];

    void init() {
        for (int i = 1; i <= tot; ++i) {
            minn[i][0] = dep[eul[i]], id[i][0] = eul[i];
        }
        lg[1] = 0;
        for (int i = 2; i <= tot; ++i) {
            lg[i] = lg[i / 2] + 1;
        }
        for (int k = 1; k <= 18; ++k) {
            for (int i = 1; i <= tot - (1 << k) + 1; ++i) {
                if (minn[i][k - 1] <= minn[i + (1 << (k - 1))][k - 1]) {
                    minn[i][k] = minn[i][k - 1];
                    id[i][k] = id[i][k - 1];
                }
                else {
                    minn[i][k] = minn[i + (1 << (k - 1))][k - 1];
                    id[i][k] = id[i + (1 << (k - 1))][k - 1];
                }
            }
        }
    }

    int lca(int x, int y) {
        int l = beg[x], r = beg[y];
        if (l > r) swap(l, r);
        int len = (r - l + 1);
        int k = lg[len];
        if (minn[l][k] <= minn[r - (1 << k) + 1][k]) {
            return id[l][k];
        }
        else return id[r - (1 << k) + 1][k];
    }
}st;

int main() {
    scanf("%d", &n);
    memset(f, 0x3f, sizeof(f));
    B = sqrt(n);
    for (int i = 1; i < n; ++i) {
        int u, v, l;
        scanf("%d%d%d", &u, &v, &l);
        add(u, v, l);
        add(v, u, l);
    }
    dfs(1, 0);
    st.init();
    scanf("%d", &m);
    for (int i = 1; i <= n; ++i) {
        pos[i] = ((i - 1) / B) + 1;
        if (pos[i] != pos[i - 1]) {
            r[cntB] = i - 1;
            l[++cntB] = i;
        }
    }
    r[cntB] = n;
    for (int i = 1; i <= cntB; ++i) {
        for (int j = l[i]; j <= r[i]; ++j) {
            f[i][j] = 0;
        }
        for (int j = n; j; --j) {
            int u = id[j];
            f[i][fa[u]] = min(f[i][fa[u]], f[i][u] + w[u]);
        }
        for (int j = 1; j <= n; ++j) {
            int u = id[j];
            f[i][u] = min(f[i][fa[u]] + w[u], f[i][u]);
        }
    }
    for (int p = 1; p <= m; ++p) {
        int L, R, x;
        scanf("%d%d%d", &L, &R, &x);
        int ans = 0x7f7f7f7f;
        for (int i = pos[L] + 1; i <= pos[R] - 1; ++i) {
            ans = min(ans, f[i][x]);
        }
        for (int i = L; i <= min(R, r[pos[L]]); ++i) {
            ans = min(ans, dis[x] + dis[i] - 2 * disggggg[st.lca(x, i)]);
        }
        for (int i = max(L, l[pos[R]]); i <= R; ++i) {
            ans = min(ans, dis[x] + dis[i] - 2 * dis[st.lca(x, i)]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

总结:

分块大法好