2022.7.2 simulation match

T1 counting

  like a breath of fresh air $T1$ . A sequence of numbers , No modification , Each inquiry is greater than or equal to $x$ The number of . Directly ask each time $lowe{r}_{b}ound()$ Just like the .

  In the examination room $5$ Minutes to finish qwq.

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

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 q = 0;

int main(){
    
	freopen("counting.in", "r", stdin);
	freopen("counting.out", "w", stdout);
	n = in; q = in;
	for(int i = 1; i <= n; i++) a[i] = in;
	sort(a + 1, a + n + 1);
	while(q--){
    
		int x = in;
		cout << n - (lower_bound(a + 1, a + n + 1, x) - a) + 1 << '\n';
	}
	return 0;
}

T2 graph

  Also send sub questions . Just simulate directly according to the meaning of the topic （ The most violent isomorphism qwq）.

#include<bits/stdc++.h>
using namespace std;
#define MAXN 101

int n = 0; int m = 0;
int mmap1[MAXN][MAXN] = {
     0 };
int mmap2[MAXN][MAXN] = {
     0 };

bool flag = 0;
bool chk(int a[]){
    
	bool temp = true;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j < i; j++){
    
			int x = a[i], y = a[j];
			if(mmap1[i][j])
				if(!mmap2[x][y]) temp = false;
		}
	return temp;
}

int a[MAXN] = {
     0 };
bool vis[MAXN] = {
     0 };
void dfs(int x){
    
	if(x == n + 1){
    
		if(chk(a)) flag = 1;
		return;
	}
	for(int i = 1; i <= n; i++){
    
		if(vis[i]) continue;
		vis[i] = 1; a[x] = i;
		dfs(x + 1);
		vis[i] = 0; a[x] = 0;
	}
}

int main(){
    
	freopen("graph.in", "r", stdin);
	freopen("graph.out", "w", stdout);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
    
		int x = 0, y = 0;
		cin >> x >> y;
		mmap1[x][y] = mmap1[y][x] = 1;
	}
	for(int i = 1; i <= m; i++){
    
		int x = 0, y = 0;
		cin >> x >> y;
		mmap2[x][y] = mmap2[y][x] = 1;
	}
	dfs(1);
	flag ? cout << "Yes" << '\n' : cout << "No" << '\n';
	return 0;
}

T3 dishes

  At first, I misunderstood the meaning of the topic , Want to become the topological order with the smallest dictionary order . After typing, I found that the sample was wrong , Then I read the topic for a long time to understand .

  What you want is to satisfy the topological order and successively Make the number as small as possible in front . Then you will find that the smallest dictionary order is obviously wrong . Then let's consider doing it backwards .

  Specifically, we need to make the number smaller successively Try to be at the top , It can be understood that we should make the ones with large numbers rank behind the topological order as much as possible . So we can think of reverse mapping , Then run the topological order with the largest dictionary order on the inverse graph , Finally, reversing the topological order is the required answer （ The essence is greed , But I can't prove the correctness , Just pass the question qwq）.

  $upd$： The correctness of this method is proved ：

  First of all, we find the topological order with the largest dictionary order in reverse , therefore $1$ It must be in the back , Because if you move forward a little, the dictionary order will become smaller . Then after the reverse $1$ Right at the front , therefore $1$ The position of must be correct .

  Then we use mathematical induction , Before hypothesis $k$ The position of the number is correct , Then we need to prove that $k+1$ The number is also correct . The method of proof is the same as that just proved $1$ The position of is correct, and the method is exactly the same .

  So this practice must be correct .

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 100100
#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 t = 0;
int n = 0; int m = 0;
int a[MAXN] = {
     0 };
int tot = 0; int cnt = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
int   deg[MAXN] = {
     0 };
inline void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y; deg[y]++;
}

void init(){
    
	tot = cnt = 0;
	memset(a, 0, sizeof(a));
	memset(to, 0, sizeof(to));
	memset(nxt, 0, sizeof(nxt));
	memset(deg, 0, sizeof(deg));
	memset(first, 0, sizeof(first));
}

priority_queue<int> q;
void topsort(){
    
	for(int i = 1; i <= n; i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
    
		int x = q.top(); q.pop();
		a[++cnt] = x;
		for(int e = first[x]; e; e = nxt[e]){
    
			int y = to[e];
			if(!(--deg[y])) q.push(y);
		}
	}
}

int main(){
    
	freopen("dishes.in", "r", stdin);
	freopen("dishes.out", "w", stdout);
	t = in;
	while(t--){
    
		init();
		n = in; m = in;
		for(int i = 1; i <= m; i++){
    
			int x = in, y = in;
			add(y, x);
		} topsort();
		if(cnt < n) cout << "Impossible!\n";
		else {
     for(int i = n; i >= 1; i--) cout << a[i] << ' '; puts(""); }
	}
	return 0;
}

T4 network

  Portal ：HNOI2016 The Internet

  front $30pts$ You can use a $O(m^2\log n)$ Of violence , Specifically, it's like this .

  Obviously we can $O(n\log n)$ After pretreatment $O(\log n)$ seek $lca(x,y)$, So we can be in $O(\log n)$ Find out in time $dis(x,y)$. So now we only need to know one point $m$ Whether in $path(x,y)$ On the path of .

  If $m$ In path $path(x,y)$ On , So obviously there is $dis(x,m)+dis(m,y)=dis(x,y)$. So we can judge from this $m$ Whether in $path(x,y)$ Yes .

#include<bits/stdc++.h>
using namespace std;
#define in read()
#define MAXN 200200
#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 m = 0;
int tot = 0;
int first[MAXN] = {
     0 };
int   nxt[MAXM] = {
     0 };
int    to[MAXM] = {
     0 };
void add(int x, int y){
    
	nxt[++tot] = first[x];
	first[x] = tot; to[tot] = y;
}


int dep[MAXN] = {
     0 };
int f[MAXN][35] = {
     0 };
void prework(int x, int fa){
    
	dep[x] = dep[fa] + 1;
	for(int i = 0; i <= 30; i++)
		f[x][i + 1] = f[f[x][i]][i];
	for(int e = first[x]; e; e = nxt[e]){
    
		int y = to[e];
		if(y == fa) continue;
		f[y][0] = x; prework(y, x);
	}
}

int query(int x, int y){
    
	if(dep[x] < dep[y]) swap(x, y);
	for(int i = 30; i >= 0; i--){
    
		if(dep[f[x][i]] >= dep[y]) x = f[x][i];
		if(x == y) return x;
	}
	for(int i = 30; i >= 0; i--)
		if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];	
	return f[x][0];
}

int cnt = 0;
struct Tpath{
    
	int t;
	int x, y, v;
	bool isd;
}path[MAXN];

int main(){
    
	n = in; m = in;
	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 <= m; i++){
    
		int op = in;
		if(op == 0){
    
			int a = in, b = in, v = in;
			path[++cnt].x = a, path[cnt].y = b, path[cnt].t = i, path[cnt].v = v;
		}
		else if(op == 1){
    
			int t = in;
			for(int j = 1; j <= cnt; j++) if(path[j].t == t) path[j].isd = 1;
		}
		else if (op == 2){
    
			int k = in; int ans = -1;
			for(int j = 1; j <= cnt; j++){
    
				if(path[j].isd) continue;
				int x = path[j].x, y = path[j].y;
				int lcaxy = query(x, y), lcaxk = query(x, k), lcaky = query(k, y);
				int disxy = dep[x] + dep[y] - 2 * dep[lcaxy];
				int disxk = dep[x] + dep[k] - 2 * dep[lcaxk];
				int disky = dep[k] + dep[y] - 2 * dep[lcaky];
				if(disxy != disxk + disky) ans = max(ans, path[j].v);
			}
			cout << ans << '\n';
		}
	}
	return 0;
}

  Then we found that there are $20pts$ It is the case that the whole tree becomes a chain . In this case, the problem becomes a relatively simple operation problem on the sequence . Now it is obvious that this problem has been transformed into a board of tree covering tree （ During the exam, I played the board and didn't adjust it for more than an hour, so I didn't post the code qwq）.