| Title number | A | B | C | D | E | F | G | H | I | J | K |
|---|---|---|---|---|---|---|---|---|---|---|---|
| In the game | 💠| 🎈 | 🎈 | ||||||||
| After the game | ✅ | ✅ | ✅ |
A - Social Distancing
meaning of the title
thinking
code
B - Mask Allocation
meaning of the title
Pack \ (n\times m \) masks into several copies. It is required that after packing, they can be divided equally whether they are distributed to \ (n \) hospitals or \ (m \) hospitals. The scheme that requires the least total number of output copies has the largest dictionary order. (\(1\le T\le 100, 1\le n,m\le 10^4\))
thinking
Assuming \ (n > m \), the best plan for \ (m \) hospitals is \ (n, n,\cdots,n(m n) \), and the best plan for \ (n \) hospitals is \ (m, m,\cdots,m(n m) \), then there are at least \ (n \) answers (that is, the best plan for \ (n \). Consider adjusting this scheme and keep the first \ (m \) to \ (m \) hospitals (this can maximize the dictionary order). Then the problem changes from \ (\ text{solve}(n, m) \) to \ (\ text{solve}(n-m,m) \), so it can be solved recursively, and the recursive boundary is \ ([n=m] \).
Time complexity \ (O(\max(n,m)) \).
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 1e4 + 10;
int n, m;
vector<int> ans;
void DFS(int n, int m)
{
if(n < m)
swap(n, m);
for(int i = 1; i <= m; i++)
ans.push_back(m);
if(n != m)
DFS(n - m, m);
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n, &m);
ans.clear();
DFS(n, m);
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); i++)
{
if(i > 0)
printf(" ");
printf("%d", ans[i]);
}
printf("\n");
}
return 0;
}
C - A National Pandemic
meaning of the title
A rootless tree, each point has a point weight f(x), and its initial value is 0. There are three operations.
Operation 1: for all y, modify f(y) to w - dist(x,y)
Operation 2: modify f(x) to min(f(x),0)
Operation 3: query f(x)
thinking
Method of transforming rootless tree to rooted tree:
\(w - dist(x,y) = w - dep[x] - dep[y] + 2 * dep[lca] \), \ (w - dep[x] - dep[y] \) can be maintained directly. The tree section modifies \ (x \) to the point on the root path so that cnt += 2, then \ (2 * dep[lca] \) is equal to the sum of point weights on the root path, the complexity is \ (n\log^2n \), and the constant is small
analysis:
\(w - dist(x,y) = w - dep[x] - dep[y] + 2 * dep[lca]\)
For \ (w - dep[x] - dep[y] \) which can be maintained directly, the key is the statistics \ (2 * dep[lca] \), when querying point u, the violence climbs the chain and enumerates all the fathers of U. let the fathers of u be sorted by depth from large to small as \ (x_1,x_2,...,x_n \), then the contribution of point u \ (2 * dep[lca] \) is: \ (2 * CNT [x_1] * dep [x_1] + 2 * (CNT [x_2] - CNT [x_1]) * dep 2 * (CNT [x_3] - CNT [x_2]) * dep [x_3] ++ 2*(cnt[x_n] - cnt[x_{n-1}])*dep[x_n]\)
Where \ (cnt[u] \) represents the number of modified points in the subtree of \ (U \), and the above contribution formula is simplified to obtain \ (2 * CNT [x_1] + 2 * CNT [x_2] +... + 2 * CNT [x_n] * dep[x_n] \), while \ (x_n \) must be the root node and \ (dep[x_n] \) is 1. Therefore, when modifying \ (x \), the \ (x \) will be added to the \ (cnt += 2 \) of all points on the root node path. When querying, the answer to this point is the sum of point weights on the root node path
Point by tree method:
Build a point divided tree. For each point, maintain the sum of the distances from all modified points \ (x \) in the subtree. During query, all \ (w - dist(x,y) \) are obtained by violent chain climbing and merging, with a complexity of \ (n\log n \), small constant and fast running
https://blog.csdn.net/qq_41997978/article/details/107742275
code
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 100;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n, m, RT, t;
inline int read()
{
int x=0,f=1;char ch;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
struct Graph {
int head[maxn], to[maxn << 1], cnt, nxt[maxn << 1], w[maxn << 1];
void init() {
for (int i = 1; i <= n; i++)
head[i] = -1;
cnt = 0;
}
void add(int u,int v,int c) {
to[cnt] = v;
nxt[cnt] = head[u];
w[cnt] = c;
head[u] = cnt++;
to[cnt] = u;
nxt[cnt] = head[v];
w[cnt] = c;
head[v] = cnt++;
}
} G;
struct divide_tree {
int dep[maxn],vis[maxn],f[maxn],root,sz[maxn],siz,p[maxn][20],dis[maxn][20]; //Center of gravity tree preprocessing
ll val[maxn], fval[maxn], optcnt[maxn], sum[maxn]; //Maintain answers, etc. val is the contribution within the subtree, fval[maxn] is the contribution from the subtree to the parent node, and sum maintains delta
void getroot(int u,int fa) { //Find the center of gravity of a subtree
sz[u] = 1; f[u] = 0;
for (int i = G.head[u]; i + 1; i = G.nxt[i]) {
int v = G.to[i];
if (v == fa || vis[v]) continue;
getroot(v,u);
sz[u] += sz[v];
if (sz[v] > f[u]) f[u] = sz[v];
}
if (siz - sz[u] > f[u]) f[u] = siz - sz[u];
if (!root || f[u] < f[root]) root = u;
}
void getship(int u,int anc,int father,int d) {
for (int i = G.head[u]; i + 1; i = G.nxt[i]) {
int v = G.to[i];
if (!vis[v] && v != father) {
++dep[v];
p[v][dep[v]] = anc;
dis[v][dep[v]] = d;
getship(v,anc,u,d + 1);
}
}
}
void Buildtree(int u) { //Point by point construction point by point tree
vis[u] = 1; getship(u,u,0,1);
int all = siz;
for (int i = G.head[u]; i + 1; i = G.nxt[i]) {
int v = G.to[i];
if (vis[v]) continue;
root = 0, siz = sz[v];
if (siz > sz[u]) siz = all - sz[u];
getroot(v,u); Buildtree(root);
}
}
void prework() {
for (int i = 1; i <= n; i++)
val[i] = fval[i] = optcnt[i] = sum[i] = dep[i] = vis[i] = 0;
siz = n; f[0] = inf; root = 0;
getroot(1,0);
Buildtree(root);
for (int i = 1; i <= n; i++)
p[i][dep[i] + 1] = i;
}
void update(int x,int w) {
val[x] += w; optcnt[x] += 1;
for (int i = dep[x]; i; i--) {
val[p[x][i]] += w - dis[x][i];
fval[p[x][i + 1]] += w - dis[x][i];
optcnt[p[x][i]] += 1;
}
}
ll qry(int u) {
ll ans = 0;
ans = val[u]; int tmp = u;
for (int i = dep[u]; i; i--)
ans = ans + (val[p[u][i]] - fval[p[u][i + 1]]) - 1ll * dis[u][i] * (optcnt[p[u][i]] - optcnt[p[u][i + 1]]);
return ans + sum[u];
}
}tree;
int main() {
t = read();
while (t--) {
n = read(); m = read();
G.init();
for (int i = 1; i < n; i++) {
int u,v,w; u = read(); v = read();
G.add(u,v,1);
}
tree.prework();
while (m--) {
int op, x, w; op = read();
if (op == 1) {
x = read(); w = read();
tree.update(x,w);
} else if (op == 2) {
x = read();
ll tmp = tree.qry(x);
if (tmp > 0)
tree.sum[x] -= tmp;
} else if (op == 3) {
x = read();
printf("%lld\n",tree.qry(x));
}
}
}
return 0;
}
D - Fake News
meaning of the title
Judge whether \ (\ sum {k = 1} ^ n k ^ 2 \) is a complete square (\ (1\le T\le 10^6, 1\le n\le 10^{15} \))
thinking
Hit the table to \ (10 ^ 6 \) and found that only \ (1 \) and \ (24 \) were sent. It can be proved in practice.
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 1e5 + 10;
LL n;
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%lld", &n);
if(n == 1 || n == 24)
printf("Fake news!\n");
else
printf("Nobody knows it better than me!\n");
}
return 0;
}
E - NeoMole Synthesis
meaning of the title
thinking
code
F - Tokens on the Tree
meaning of the title
thinking
code
G - Topo Counting
meaning of the title
thinking
code
H - Dividing
meaning of the title
\((1,k) \) is a legend tuple, \ ((xk,k) \) is a legend tuple, \ ((1 + xk,k) \) is a legend tuple. Given \ (n,K \), how many \ ((x,y) \) satisfy \ (x \leq n, y \leq K \) and (x,y) is a legend tuple
thinking
Enumerating \ (K \), \ ((xk,k) \) contributes \ (\ lfloor\frac{n}{k}\rfloor \), \ ((1 + xk,k) \) contributes \ (\ lfloor\frac{n - 1}{k}\rfloor + 1 \). When k is 1, \ (k > 1 \) divides the next block
Complexity is \ (\ sqrt{(min(n,K))} \)
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
ll n, k, inv2 = 500000004;
int main() {
scanf("%lld%lld",&n,&k);
ll ans = 0, res = 0;
for (ll i = 2, j; i <= min(n,k); i = j + 1) {
j = min(n / (n / i),k);
ans = (ans + (n / i) % mod * (j - i + 1) % mod) % mod;
}
n--;
for (ll i = 1, j; i <= min(n,k); i = j + 1) {
j = min(n / (n / i),k);
ans = (ans + (n / i) % mod * (j - i + 1) % mod) % mod;
}
printf("%lld\n",(ans + k) % mod);
return 0;
}
I - Valuable Forests
meaning of the title
Define the sum of squared degrees of all nodes as the weight of the forest, and calculate the weight sum of all forests with \ (n \) labeled nodes. (\(1\le T\le 5000, 1\le N\le 5000\))
thinking
prufer sequence, the artifact of rootless tree counting, is known for the first time. It mainly uses the following two properties:
- A rootless tree with \ (n \) nodes uniquely corresponds to a prufer sequence with a length of \ (n-2 \), and each number in the sequence is in the range of \ (1 \) to \ (n \);
- The number of occurrences of a number in the prufer sequence is equal to the degree of the node of this number in the rootless tree \ (- 1 \).
According to property 1, the number of rootless trees with \ (n \) nodes is:
The counting of this problem is quite ingenious. First, preprocess the number of forests with \ (n \) nodes:
That is, select \ (i \) and \ (n \) nodes from the original \ (n-1 \) nodes to form a rootless tree.
Combine the properties of 2 \ \, and then deal with another root free tree:
Enumerate the degrees of a node and calculate the contribution. Since all points have the same contribution, multiply it by \ (n \).
Finally, calculate the weight sum of the forest of \ (n \) nodes:
That is, select \ (i \) and \ (n \) nodes from the original \ (n-1 \) nodes to form a rootless tree, which will produce two parts of contribution (as shown in the above formula). The former is the contribution generated by the rootless tree (multiplied by the number of forests formed by other points), and the latter is the contribution generated by the forest formed by other points (multiplied by the number of rootless trees formed).
Preprocessing time complexity \ (O(N^2) \).
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int maxn = 5000 + 10;
int MOD, N;
LL comb[maxn][maxn], power[maxn][maxn];
LL calc(LL n)
{
if(n < 2)
return 1;
else
return power[n][n - 2];
}
LL f[maxn], g[maxn], h[maxn];
void preprocess()
{
comb[0][0] = 1;
for(int i = 1; i <= 5000; i++)
{
comb[i][0] = 1;
for(int j = 1; j <= i; j++)
comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
}
for(int i = 0; i <= 5000; i++)
{
power[i][0] = 1;
for(int j = 1; j <= 5000; j++)
power[i][j] = power[i][j - 1] * i % MOD;
}
f[0] = 1;
for(int i = 1; i <= 5000; i++)
for(int j = 0; j <= i - 1; j++)
f[i] = (f[i] + comb[i - 1][j] * calc(j + 1) % MOD * f[i - 1 - j] % MOD) % MOD;
for(int i = 1; i <= 5000; i++)
{
for(int d = 1; d <= i - 1; d++)
g[i] = (g[i] + comb[i - 2][d - 1] * power[i - 1][i - 1 - d] % MOD * d % MOD * d % MOD) % MOD;
g[i] = g[i] * i % MOD;
}
for(int i = 1; i <= 5000; i++)
for(int j = 0; j <= i - 1; j++)
h[i] = (h[i] + comb[i - 1][j] * ((f[i - 1 - j] * g[j + 1] % MOD + calc(j + 1) * h[i - 1 - j] % MOD) % MOD) % MOD) % MOD;
}
int main()
{
int T;
scanf("%d %d", &T, &MOD);
preprocess();
while(T--)
{
scanf("%d", &N);
printf("%lld\n", h[N]);
}
return 0;
}
J - Pointer Analysis
meaning of the title
\An object represented by (26 \) lowercase letters. Each object has a member variable represented by \ (26 \) lowercase letters. The member variable is a pointer\ (26 \) global pointer variables in uppercase letters.
There are \ (n \) assignment statements of \ (4 \) types. During execution, the execution order of these \ (n \) statements can be disordered arbitrarily. Ask which objects each global pointer can point to.
thinking
Considering that the maximum number of \ (n \) is only \ (200 \), which is relatively small, this \ (n \) statement can be repeated \ (n \) times, so as to ensure that all other statements have been executed at least once before the last execution of each statement, so as to achieve the effect of disorderly execution of statements.
\(p1[i][j] \) mark whether the global pointer \ (I +'a '\) can point to the object \ (j+'a'\),\(p2[i][j][k] \) indicates whether the member pointer \ (j+'a '\) of the object \ (I +'a' \) points to the object \ (k+'a '\), judge the statement type when traversing all statements, and update the two arrays according to the topic meaning. Note that the form of \ (B.f \) is only available after the global pointer points to the object (because only the object in this question has a member pointer). When reading \ (getline \) into the whole line, don't forget to speed up the reading of \ (cin \).
Time complexity \ (O(n^2{26}^2) \), space complexity \ (O(26^3) \)
code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5;
int n;
string s[maxn];
string t;
bool p1[26][26], p2[26][26][26];
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n;
getline(cin, t);
for(int i=1; i<=n; ++i) getline(cin, s[i]);
for(int t=1; t<=n; ++t) //The previous n expressions are repeated N times
for(int i=1; i<=n; ++i) s[t*n+i]=s[i];
n=n*n;
for(int i=1; i<=n; ++i)
{
if(s[i].size()==5&&islower(s[i][4]))
{
int a=s[i][0]-'A';
int x=s[i][4]-'a';
p1[a][x] = true;
}
else if(s[i].size()==5&&isupper(s[i][4]))
{
int a=s[i][0]-'A';
int b=s[i][4]-'A';
for(int j=0; j<26; ++j) if(p1[b][j]) p1[a][j] = p1[b][j];
}
else if(s[i].size()==7&&s[i][1]=='.')
{
int a=s[i][0]-'A', f=s[i][2]-'a';
int b=s[i][6]-'A';
for(int j=0; j<26; ++j)
if(p1[a][j])
for(int k=0; k<26; ++k) if(p1[b][k]) p2[j][f][k] = p1[b][k];
}
else if(s[i].size()==7&&s[i][5]=='.')
{
int a=s[i][0]-'A';
int b=s[i][4]-'A', f=s[i][6]-'a';
for(int j=0; j<26; ++j)
if(p1[b][j])
for(int k=0; k<26; ++k) if(p2[j][f][k]) p1[a][k] = p2[j][f][k];
}
}
for(int i=0; i<26; ++i)
{
cout << char('A'+i) << ": ";
for(int j=0; j<26; ++j)
if(p1[i][j]) cout << char('a'+j);
cout << endl;
}
}