2022.7.22 simulation match

T1 tree

  First , Thank you, the author /wx

  It is required to find out the number of schemes that divide a tree into several connected parts .

  First of all, it's easy to think of , Points out the “ subtree ” Size $d$ Is to meet $d|n$ Of . That is to say, we only need to judge each $d$ If it is feasible , among $d$ The number of is equal to ${\sigma }_0(n)<\sqrt{n}$ Of .

  It is quite simple to judge whether it is feasible , You only need to write one $dfs$ Just simulate the process of tree splitting , therefore $check$ Namely $O(n)$ Of . Then the total complexity is less than $O(n\sqrt{n})$ Of .

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 2002000
#define MAXM MAXN << 2
#define MOD 998244353

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0;
int cnt = 0;
int d[MAXN] = {
     0 };
int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int sz[MAXN] = {
     0 };
void prework(int x, int fa){
    
	sz[x]++;
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		prework(y, x);
		sz[x] += sz[y];
	}
}

int check(int x, int fa, int w){
    
	int siz = 1;
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		if(sz[y] >= w){
                             //  Greater than continue down first  
			int f = check(y, x, w);
			if(f == -1) return -1;
			siz += f;	                        //  Add the following contributions  
		}
		else siz += sz[y];
		if(siz > w) return -1;                  //  All wood is big  
	}
	if(siz == w) return 0;                      //  It's equivalent to cutting directly   Not a contribution  
	return siz;
}

int main(){
    
// freopen("a.in", "r", stdin);
	n = in; int ans = 0;
	for(int i = 1; i < n; i++){
    
		int x = in, y = in;
		add(x, y), add(y, x);
	} prework(1, 0);
	for(int i = 1; i * i <= n; i++)
		if(n % i == 0) d[++cnt] = i;
	for(int i = cnt; i >= 1; i--)
		if(n / d[i] != d[i]) d[++cnt] = n / d[i];
// for(int i = 1; i <= cnt; i++) cout << d[i] << ' '; puts("");
	for(int i = 1; i <= cnt; i++)
		if(check(1, 0, d[i]) != -1) ans = (ans + 1) % MOD;
	cout << ans << '\n';
	return 0;
} 

  But this kind of writing seems to $T$ fall $2,3$ A little bit , So we have to continue to see if there is any nature .

  We consider finding $size$ yes $d$ The key point of the multiple of （ Because we just looked for these points when simulating tree demolition ）. We consider finding the upper limit of these points , We extract these key points , Of leaf nodes in the new tree $size$ At least $d$, And non leaf node $size$ It must be better than all its sons $size$ And to be big , And at least big $d$. So obviously, the upper limit of the number of key points is $\frac{n}{d}$.

  If we happen to find $\frac{n}{d}$ A key point , It means that each point is exactly one with the size of $d$ The root of the subtree of , And these subtrees do not contain each other . in other words , If there is $\frac{n}{d}$ A key point , The requirements of the topic can be established . So we can rewrite it through this $check()$ Function can $A$ 了 .

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 1001000
#define MAXM MAXN << 2

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int n = 0;
int d[MAXN] = {
     0 };
int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}

int siz[MAXN] = {
     0 };
int cnt[MAXN] = {
     0 }; 
void prework(int x, int fa){
    
	siz[x]++;
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		prework(y, x);
		siz[x] += siz[y];
	}
	cnt[siz[x]]++;
}

bool check(int d){
    
	int num = 0;
	for(int i = d; i <= n; i += d)
		num += cnt[i];
	return num == (n / d);
}

int main(){
    
	n = in; int ans = 0;
	for(int i = 1; i < n; i++){
    
		int x = in, y = in;
		add(x, y), add(y, x);
	} prework(1, 0);
	for(int i = 1; i <= n; i++)
		if(n % i == 0) ans += check(i);
	cout << ans << '\n'; 
	return 0;
} 

T2 seq

  $30pts$ It's a simple one $dp$. We make $f_{i,j}$ Before presentation $i$ A digital , And then finally $j$ The minimum value of , So there are ：

$$f_{i,j}=\underset{j=a_i}{\overset{A}{\min }}\{\underset{k=a_{i-1}}{\overset{A}{\min }}\{f_{i-1,k}+c|j-k|+(a_i-j{)}^2\}\}$$

  Initialization is $f_{1,j}=(j-a_1{)}^{2}j\in [a_i,A]$, among $A$ yes $a_i$ Range of values . The time complexity of doing this is $O(n{A}^2)$ Of .

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 1010
#define INFI 1 << 30

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int a[MAXN] = {
     0 };
int n = 0; int c = 0;
int f[MAXN][MAXN] = {
     0 };

int main(){
    
	n = in; c = in; int A = 0, ans = INFI;
	for(int i = 1; i <= n; i++) a[i] = in, A = 101;
	memset(f, 0x3f, sizeof(f));
	for(int j = a[1]; j <= A; j++) f[1][j] = (j - a[1]) * (j - a[1]);
	for(int i = 2; i <= n; i++)
		for(int j = a[i]; j <= A; j++)
			for(int k = a[i - 1]; k <= A; k++)
				f[i][j] = min(f[i][j], f[i - 1][k] + c * abs(j - k) + (j - a[i]) * (j - a[i]));
	for(int i = 1; i <= A; i++) ans = min(ans, f[n][i]);
	cout << ans << '\n';
	return 0;
} 

  We consider optimizing this approach . Let's change the above formula slightly ：

$$f_{i,j}=\underset{j=a_i}{\overset{A}{\min }}\{\underset{k=a_{i-1}}{\overset{A}{\min }}\{f_{i,k}+c|j-k|\}+(a_i-j{)}^2\}$$

  Then if we order $s_{i,j}=\underset{k=a_{i-1}}{\overset{A}{\min }}\{f_{i,k}+c|j-k|\}$, And the $s_{i,j}$ Preprocess it , Then we can enumerate less once $A$, The equation can be written like this ：

$$f_{i,j}=\underset{j=a_i}{\overset{A}{\min }}\{s_{i,j}+(a_i-j{)}^2\}$$

  Now let's consider how to preprocess $s_{i,j}$. We consider that if we take the absolute value apart, it is good to transfer , That's our $s_{i,j}$ If it is equal to $\underset{k=a_{i-1}}{\overset{A}{\min }}\{f_{i,k}+c(j-k)\}$ That's a lot easier to deal with , Because we can ：

$$\min \{f_{i,k}+c(j-k)\}=\min \{\min \{f_{i,k}+c(j-1-k)\}+c,f_{i-1,j}\}$$

  in other words ：

$$s_{i,j}=\min \{s_{i,j-1}+c,f_{i-1,j}\}$$

  But there is an absolute value here , So we'll think about scanning it directly and then scanning it backwards , In this way, the problem of absolute value can be solved （ Note that here we need to use a scrolling array to avoid space explosion ）. In this way, the time complexity becomes $O(nA)$ Of course. .

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define in read()
#define MAXN 100100
#define MAXA 101
#define INFI 1e18

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int a[MAXN] = {
     0 };
int n = 0; int c = 0;
int f[MAXN][MAXA] = {
     0 };
int g1[MAXN] = {
     0 };
int g2[MAXN] = {
     0 };

signed main(){
    
	n = in; c = in; int A = 0, ans = INFI;
	for(int i = 1; i <= n; i++) a[i] = in, A = max(A, a[i]);
	memset(f, 0x3f, sizeof f);
	for(int j = a[1]; j <= A; j++) f[1][j] = 1ll * (j - a[1]) * (j - a[1]);
	for(int i = 2; i <= n; i++){
    
		for(int j = 0; j <= A + 1; j++) g1[j] = g2[j] = INFI;
		for(int j = A; j >= a[i]; j--)
			g1[j] = min(g1[j], min(g1[j + 1] + c, f[i - 1][j]));
		for(int j = a[i - 1]; j <= A; j++)
			g2[j] = min(g2[j], min(g2[j - 1] + c, f[i - 1][j]));
		for(int j = a[i]; j <= A; j++)
			f[i][j] = min(f[i][j], min(g1[j], g2[j]) + 1ll * (j - a[i]) * (j - a[i]));
	}
	for(int i = 1; i <= A; i++) ans = min(ans, f[n][i]);
	cout << ans << '\n';
	return 0;
}

T3 color

  Feeling $T3$ Is the simplest problem （ It seems that the original $T3$ Replaced ）.

  Brain pumping in the examination room , The idea has been wrong , Push ：

$$\begin{array}{rl}ans=& \sum _{S\subset U}|\sum _{i\in S}{a}_i-\sum _{i\in C_{U}S}{a}_i|\\ =& \sum _{S\subset U}|2\sum _{i\in S}{a}_i-X|\\ X=& \sum _{i=1}^n{a}_i\end{array}$$

  It was supposed to be this step , The solution will come out soon , Then I began to get sick ：

$$\begin{array}{rl}X=& \sum _{i=1}^n{a}_i\\ & \\ ans=& \sum _{S\subset U}|\sum _{i\in S}{a}_i-\sum _{i\in C_{U}S}{a}_i|\\ =& \sum _{S\subset U}|2\sum _{i\in S}{a}_i-X|\\ =& \sum _{S\subset U}\left(2\sum _{i\in S}{a}_i-X\right)[2\sum _{i\in S}{a}_i\ge X]-\sum _{S\subset U}\left(2\sum _{i\in S}{a}_i-X\right)[2\sum _{i\in S}{a}_i<X]\\ & \\ =& \left(2\sum _{S\subset U}\sum _{i\in S}{a}_i-\sum _{S\subset U}X\right)[2\sum _{i\in S}{a}_i\ge X]-\left(2\sum _{S\subset U}\sum _{i\in S}{a}_i-\sum _{S\subset U}X\right)[2\sum _{i\in S}{a}_i<X]\end{array}$$

  Then I can't push it .

  In fact, the above formula can already be done . We make $f_j$ Represents the selected subset $S$ in $\sum _{i\in S}{a}_i=j$ The number of sets of . So obviously now this is a backpack . We have ：

$$f_j=\sum _{a_k\le j}{f}_{j-a_k}$$

  Just transfer the backpack directly , Complexity is $O(nS)$.

  Then the answer is obvious ：

$$ans=\sum _{i=1}^X{f}_i|2i-X|$$

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 100100
#define MOD 998244353

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int T = 0;
int x = 0; int n = 0;
int w[MAXN] = {
     0 };
int f[MAXN] = {
     0 };

int main(){
    
	T = in;
	while(T--){
    
		x = in; n = in; int ans = 0;
		f[0] = 1;
		for(int i = 1; i <= x; i++) f[i] = 0;
		for(int i = 1; i <= n; i++) w[i] = in;
		for(int i = 1; i <= n; i++)
			for(int j = x; j >= w[i]; j--)
				f[j] = (f[j] + f[j - w[i]]) % MOD; 
		for(int i = 0; i <= x; i++) ans = (ans + 1ll * f[i] * abs(2 * i - x) % MOD) % MOD;
		cout << ans << '\n';
	}
	return 0;
} 

T4 mex

  It seems that I have done the same problem before …

  Portal ：P4587 [FJOI2016] Mysterious number

  Unfortunately, I didn't remember it in the examination room , There is no time to write .

  $TJ$ I have written one before , Now move over directly .

  Find the number that cannot be represented by the subset with the smallest interval .

  Consider an interval $[l,r]$, Sort this paragraph in ascending order , Set the numbers after sorting as $a_l\le a_{l+1}\le \cdots \le a_r$, For now $a_l$ If not equal to $1$, Then you can output directly $1$. If it is equal to the $1$ Let's consider a simple $dp$.

  Now use $pos$ Indicates that the current number that can be expressed belongs to the interval $[1,pos]$（ Obviously, this interval includes $1$）, For the next number $a_i$, Now there are two situations ：

1. If $a_i\le pos+1$, Then the set of numbers that can be expressed now is $[1,pos]\bigcup [1+a_i,pos+a_i]=[1,pos+a_i]$.
2. If $a_i>pos+1$, Then the set of numbers that can be expressed now is $[1,pos]\bigcup [1+a_i,pos+a_i]$, Obviously, this set does not contain $pos+1$, So the answer is $pos+1$.

  The time complexity of doing this for each inquiry is $O(n\log n)$ Of , So we should consider optimizing this practice .

  If the current value range is $[1,pos]$, Now the answer should be $pos+1$. Remember that it is less than or equal to $ans$ The sum of the numbers is $res$, If $res\ge ans$, Then it means that you must have chosen （ Choose the sum of some numbers as $ans$） And less than or equal to $ans$ The number of exists , Now let $ans=res+1$. If not satisfied $res\ge ans$ That means the answer is $ans$, direct $break$ Just fine , be aware $\sum a_i<1e9$, Therefore, we can consider using the chairman tree to maintain the interval value range and .

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 100100
#define INFI 1 << 30

inline int read(){
    
	int x = 0; char c = getchar();
	while(c < '0' or c > '9') c = getchar();
	while('0' <= c and c <= '9'){
    
		x = x * 10 + c - '0'; c = getchar();
	}
	return x;
}

int a[MAXN] = {
     0 };
int n = 0; int m = 0;

struct Tnode{
    
	int dat;
	int ls, rs;
}t[MAXN << 5];
int tot = 0;
int root[MAXN] = {
     0 };

inline void up(int p) {
     t[p].dat = t[t[p].ls].dat + t[t[p].rs].dat; }
int update(int now, int l, int r, int x, int val){
    
	int p = ++tot; t[p] = t[now];
	if(l == r) {
     t[p].dat += val; return p; }
	int mid = (l + r) >> 1;
	if(x <= mid) t[p].ls = update(t[p].ls, l, mid, x, val);
	else t[p].rs = update(t[p].rs, mid + 1, r, x, val);
	up(p); return p;
}

int query(int p, int q, int l, int r, int ql, int qr){
    
	if(ql <= l and r <= qr) return t[p].dat - t[q].dat;
	int mid = (l + r) >> 1, ans = 0;
	if(ql <= mid) ans += query(t[p].ls, t[q].ls, l, mid, ql, qr);
	if(qr > mid) ans += query(t[p].rs, t[q].rs, mid + 1, r, ql, qr);
	return ans;
}

int main(){
    
	n = in;
	for(int i = 1; i <= n; i++) a[i] = in;
	for(int i = 1; i <= n; i++) root[i] = update(root[i - 1], 1, INFI, a[i], a[i]);
	m = in;
	while(m--){
    
		int l = in, r = in, ans = 1;
		while(true){
    
			int res = query(root[r], root[l - 1], 1, INFI, 1, ans);
			if(res >= ans) ans = res + 1;
			else break;
		}
		cout << ans << '\n';
	}
	return 0;
}