20241019

这两天的题和今天的考试题。都是城外的
今天考试爆蛋了。

• 【探险队】
  题意：
  思路：发现这是个基环树森林，考虑怎么做。发现如果是一条链的话很好做，直接一选一不选就行了，那就可以先这样把基环树都搞成一个个环。然后想到对于一个环可能它之前连着个链，然后最后一个被选了，这就导致环上这个点选不了，但是我们并不知道，所以我们考虑如果有这种情况的话就直接把这个环接着遍历掉就行了，然后发现可能这个环上可能还连着别的链，这么直接做的话可能导致不优，所以考虑遇到下一个入度大于一的时候就不继续遍历了，让下一个没有入度的链头或者一整个环再做，发现不劣。然后考虑遍历纯环的时候便历的第一个选不选。发现偶数的时候没有任何关系，但是奇数就不一样了，如果第一个选了，那选到最后一个的时候会发现最后一个选的和第一个挨着，就不对了，所以把第一个设成不选。其实纯环的时候就是环上节点个数除二下取整。这道题好像之前见过一个很类似的题。
  代码：

#include <iostream>
#include <cstdio>

using namespace std;
const int N = 3e5 + 10;

int n, ans;
int to[N], in[N];
bool vis[N];

void dfs (int u, int flag) {
	if(vis[u]) return;
	vis[u] = 1;
	if(flag) ans++;
	if(~to[u]) in[to[u]]--;
	if(~to[u])
		if(flag || !in[to[u]]) 
			dfs(to[u], flag ^ 1);
}

int main () {
	freopen("explore.in", "r", stdin);
	freopen("explore.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &to[i]), in[to[i]]++;
	for(int i = 1; i <= n; ++i)	
		if(!in[i]) dfs(i, 1);
	for(int i = 1; i <= n; ++i)
		if(!vis[i]) dfs(i, 0);
	printf("%d\n", ans);
	return 0;
}

-【大数据处理】
题意：


思路：考虑建一棵线段树。改变节点颜色就是改变那个叶子节点上的颜色。每个节点就代表这个节点代表的这段染了什么颜色。显然可能不是一个，然后再记一个更新到当前节点的这段最少用多少次染色。再考虑向上合并的过程，发现如果它的两个子节点的颜色有交集的话那就直接记录他们的交集就行了，这样显然是最优的，那染色次数就是左+右-1，如果没有交集的话那就直接向上传递并集就行了。这题动态开点线段树很好做。
代码：

#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;
const int N = 1e6 + 10;

int k, n, m;
int tot, rt, ans;
int c[N], v[N], s[N];
struct Seg { 	
	int l, r; 
	vector <int> v;
} t[N << 2];

void modify (int &rt, int l, int r, int L, int R, int k) {
	if(!rt) rt = ++tot;
	if(l >= L && r <= R) {
		t[rt].v.push_back(k);
		return;
	}
	int mid = (l + r) >> 1;
	if(L <= mid) modify(t[rt].l, l, mid, L, R, k);
	if(R > mid) modify(t[rt].r, mid + 1, r, L, R, k);
}

void solve (int rt) {
	if(t[rt].v.size()) return;
	solve(t[rt].l), solve(t[rt].r);
	set_intersection(t[t[rt].l].v.begin(), t[t[rt].l].v.end(), t[t[rt].r].v.begin(), 
	t[t[rt].r].v.end(), back_inserter(t[rt].v));
	if (t[rt].v.empty()) {
		ans++;
		set_union(t[t[rt].l].v.begin(), t[t[rt].l].v.end(), t[t[rt].r].v.begin(), 
		t[t[rt].r].v.end(), back_inserter(t[rt].v));
		return;
	}
}

int main () {
	freopen("data.in", "r", stdin);
	freopen("data.out", "w", stdout);
	cin >> k >> n >> m;
	s[0] = -1, k = (1 << k);
	for(int i = 1; i <= n; ++i)
		cin >> v[i] >> c[i], s[i] = s[i - 1] + v[i];
	for(int i = 1; i <= n; ++i) {
		int x = i;
		while(i < n && c[x] == c[i + 1]) i++;
		modify(rt, 0, k - 1, s[x - 1] + 1, s[i], c[i]);
	}
	solve(rt);
	cout << ans + 1 << endl;
	return 0;
}

• 【ATM】
  题意：
  
  思路：