Codeforces Round #808 (Div. 1)（A~C）

A：Doremy’s IQ

The main idea of the topic

Give you a sequence , Then you can choose to do it or not from left to right .
Then you have an IQ value , If your current number is less than or equal to it, it will have no effect , Otherwise, the IQ value will be reduced by one , If it becomes $0$ You can't operate .
I want you to maximize the number of times , And construct the scheme .

Ideas

I got stuck with this question for a long time .
You might as well do it first T2.

Just then we will have one DP, But it doesn't seem to be able to optimize .
So consider the opposite , You will find that the problem becomes that you are $0$, Every time you encounter something larger than, you can choose $+1$ And through it , Then you can only add $q$.
You will find that you can obviously be greedy , can $+1$ Plus one , Then simulate the process once .

Code

#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
//#define mo 998244353
//#define mo 1000000007

using namespace std;

const int N = 1e5 + 100;
int T, n, q, a[N], jian[N], big, newbig;
int ans[N];

int main() {
    
	scanf("%d", &T);
	while (T--) {
    
		scanf("%d %d", &n, &q);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]), ans[i] = 0;
		if (q >= n) {
    
			for (int i = 1; i <= n; i++) putchar('1'); putchar('\n'); continue;
		}
		int now = 0;
		for (int i = n; i >= 1; i--)
			if (now < a[i]) {
    
				if (now == q) continue;
				now++; ans[i] = 1;
			}
			else {
    
				ans[i] = 1;
			}
		for (int i = 1; i <= n; i++) printf("%d", ans[i]);
		printf("\n");
	}
	
	return 0;
}

B：Difference Array

The main idea of the topic

Give you an ordered array , You should continue to perform the following operations on it until the array length becomes $1$, And output the last number .
Difference it , Sort the array obtained by the difference .

Ideas

I can only say a little fraud .
First, it is found that the sum of each item of the array will only be twice the length of the array at most .

Many places will be the same , Because the order is arranged at the beginning, there will be many differences $0$.
Then you will only need to keep one $0$ To operate , So the amount of real operation will be very small .
So direct simulation can .

Code

#include<set>
#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
//#define mo 998244353
//#define mo 1000000007

using namespace std;

const int N = 1e5 + 100;
int T, n, a[N], l, r, tmp[N];

void work() {
    
	for (int i = l; i < r; i++) tmp[i] = a[i + 1] - a[i];
	sort(tmp + l, tmp + r);
	for (int i = l; i < r; i++) a[i] = tmp[i];
	if (l > 1) l--; r--;
}

int main() {
    
	scanf("%d", &T);
	while (T--) {
    
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		l = 1; r = n; while (l < r && !a[l] && !a[l + 1]) l++;
		for (int i = 1; i < n; i++) {
    
			work();
			while (l < r && !a[l] && !a[l + 1]) l++;
		}
		printf("%d\n", a[l]);
	}
	
	return 0;
}

C：DFS Trees

The main idea of the topic

Here's a picture for you , Then ask what you got from each point dfs Whether the tree is the minimum spanning tree .
Each side has different edge weights and is $1\sim m$ Value .

Ideas

Ma used the wrong nature for a long time .（ Although it seems that the idea can be written, it's too late , The main reason is that the nature of the thought is too complex ）

You will find that because it is the smallest spanning tree, you have a non tree edge , If you walk through a section , You'd better go by the tree first .
Then how can there be a problem ？ Is that you walk by the tree , You can't find points that are not connected by the tree , Then you can only walk by the non tree .
So let me draw a picture of that , You will find that these bad positions are points on the path between two points on the edge of the non tree （ And its subtree ）, It's the middle part , As long as you go in from one end, it's no problem .

Then let's consider getting some judgments for each non tree edge ：
From some point dfs Some can't , To be specific, let's put non tree side $x,y$ The path on the tree is broken , then $x,y$ The subtree of is ok .
If a point is completely OK , It must satisfy every non tree edge condition , Then we will maintain how many conditions each point meets .
As for the assignment of subtree, mark it directly, and then run it finally dfs Pass it down .

Code

#include<cstdio>
#include<vector>

using namespace std;

const int N = 1e5 + 100;
int n, m, fa[N], sum[N], go[N];
vector <int> g[N], G[N], bh[N];
bool tree[N << 1], in[N];

int find(int now) {
    return fa[now] == now ? now : fa[now] = find(fa[now]);}

void dfs(int now, int father) {
    
	in[now] = 1;
	for (int i = 0; i < g[now].size(); i++) {
     int x = g[now][i];
		if (x == father) continue;
		go[now] = x; dfs(x, now);
	}
	for (int i = 0; i < G[now].size(); i++) {
     int x = G[now][i];
		if (tree[bh[now][i]]) continue;
		tree[bh[now][i]] = 1;
		if (!in[x]) sum[now]++, sum[x]++;
			else sum[now]++, sum[1]++, sum[go[x]]--;
	}
	in[now] = 0;
}

void get_sum(int now, int father) {
    
	for (int i = 0; i < g[now].size(); i++) {
     int x = g[now][i];
		if (x == father) continue;
		sum[x] += sum[now]; get_sum(x, now);
	}
}

int main() {
    
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++) {
    
		int x, y; scanf("%d %d", &x, &y);
		if (find(x) != find(y)) fa[find(x)] = find(y), tree[i] = 1, g[x].push_back(y), g[y].push_back(x);
			else G[x].push_back(y), bh[x].push_back(i), G[y].push_back(x), bh[y].push_back(i);
	}
	
	dfs(1, 0);
	get_sum(1, 0);
	
	for (int i = 1; i <= n; i++)
		printf("%d", (sum[i] == m - (n - 1)) ? 1 : 0);
	
	return 0;
}