Educational Codeforces Round 132 (Rated for Div. 2)

https://codeforces.com/contest/1709

C. Recover an RBS

题意：

这里原本有一个合法的括号序列，现在将这个合法的括号序列中的一部分字符串替换为 ？

你可以将 ？替换为 （ 或者 ）问替换出合法括号序列的方式是否唯一

分析：

题目要求判断方式是否唯一 考虑每个？是否唯一即可

void slove() {
    cin >> s;
    int wh = 0, cnt = 0;//问号
    for (char c : s) {
        if (c == '(')cnt++;
        if (c == ')')cnt--;
        if (c == '?')wh++;
        if (cnt + wh == 1) {
            cnt = 1;
            wh = 0;
        }
    }
    if (abs(cnt) == wh)YES;
    else NO;
}

D. Rorororobot

分析:

void slove() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)cin >> a[i];
    segtree<int, op, e>seg(a, m);//区间最大值线段树
    int q; cin >> q;
    while (q--) {
        cin >> st_x >> st_y >> ed_x >> ed_y >> k;
        if (abs(st_x - ed_x) % k || abs(st_y - ed_y) % k) {
            NO;
            continue;
        }
        //int d = (n - st_x); 
        int nowx = st_x + (n - st_x) / k * k;
        if (seg.que(min(st_y, ed_y), max(st_y, ed_y)) < nowx)YES;
        else NO;
    }
}

很好的一道启发式合并题

E. XOR Tree

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
#define int ll 
const int maxn=2e5+5;
vector<int>Q[maxn];
multiset<int>st[maxn];
multiset<int>::iterator it;
int n,ans;
int a[maxn],dis[maxn];
void solve();
void dfs(int u,int fa){
	for(int i=0;i<Q[u].size();i++){
		int to=Q[u][i];
		if(to==fa)continue;
		dis[to]=dis[u]^a[to];
		dfs(to,u);
	}
}
void dff(int u,int fa){
	bool pd=0;
	st[u].insert(dis[u]);
	for(int i=0;i<Q[u].size();i++){
		int to=Q[u][i];
		if(to==fa)continue;
		dff(to,u);
		if(st[u].size()<st[to].size())
		st[u].swap(st[to]);
		for(it=st[to].begin();it!=st[to].end();it++)
			if(st[u].count((*it)^a[u])){
				pd=1;break;
			}
		for(it=st[to].begin();it!=st[to].end();it++)
		st[u].insert(*it);
		st[to].clear();
	}
	if(pd){
		ans++;
		st[u].clear();//u选择之后 整个u子树不再与其他的点造成贡献！！！！
	}
}
signed main(){
	int T;T=1;
	while(T--)solve();
     return 0;
}
void solve(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	for(int uu,vv,i=1;i<n;i++){
		scanf("%lld%lld",&uu,&vv);
		Q[uu].push_back(vv);
		Q[vv].push_back(uu);
	}
	dis[1]=a[1];
	dfs(1,1);
	dff(1,1);
	printf("%lld",ans);
}