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

A：Doremy’s IQ

题目大意

给你一个序列，然后你从左到右可以选择弄或者不弄。
然后你有一个智商值，如果你当前弄的数小于等于它就无影响，否则智商值减一，如果变成了 $0$ 就无法操作。
要你最大化弄的次数，并构造方案。

思路

小溪了这题就卡了半天。
甚至不如先做 T2。

正着我们会有一个 DP，但是似乎不太能优化。
所以考虑反着来，会发现问题就变成了一开始你是 $0$，每次如果碰到大于的你可以选择 $+1$ 并通过它，然后你只能加到 $q$。
会发现显然可以贪心，就能 $+1$ 就加一，然后模拟一遍过程就好了。

代码

#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

题目大意

给你一个排好序数组，你要对它不断进行以下操作直至数组长度变为 $1$，并输出最后的数。
把它差分，把差分得到的数组排序。

思路

我只能说有点诈骗。
首先发现数组每一项的和只会最多是数组长度的两倍。

那很多地方都会相同， 那因为一开始就排好序所以差分就会有很多 $0$。
然后你会你只需要保留一个 $0$ 来进行操作，所以真正操作的量会很少。
所以直接模拟即可。

代码

#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

题目大意

给你一个图，然后问你从每个点出发得到的 dfs 树是否是最小生成树。
每条边边权不同且为 $1\sim m$ 的值。

思路

麻用错性质想了半天。（虽然看起来想法能写但来不及了，主要是想到的性质太复杂啦）

你会发现因为是最小生成树所以你对于一条非树边，你如果从一段走过去，你还是优先走树边。
那怎样会出现问题呢？就是你走完树边，发现到不了非树边连的点，那你就只能走非树边了。
画个图理解一下，你就会发现这些不行的位置都是在非树边两个点之间的路径上的点（以及它的子树），就是中间的部分，你只要从一头进去都是没问题的。

那我们考虑对每条非树边都得到一些判断：
从某些点出发 dfs 可以某些不行，具体一点我们把非树边 $x,y$ 在树上的路径断开，然后 $x,y$ 的子树是可以的。
那如果一个点要完全可以，它要满足每条非树边的条件，那我们就维护每个点满足了多少了条件。
至于子树赋值就直接打标记然后最后跑个 dfs 下传下去即可。

代码

#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;
}