Atcoder ABC 391

思路：模拟题目操作的同时，记录每个巢里有多少鸽子，同时维护有多少个巢穴鸽子的数量大于

1

；

CPP

#include<bits/stdc++.h>
using namespace std; 
const int N = 1e6+5;
int cnt[N];
int pos[N];
signed main(){
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		pos[i] = i; // 记录i的位置 
		cnt[i] = 1; // i处的数量 
	}
	int ans = 0; // 维护大于1的数量 
	while(q--){
		int op, p, h;
		cin >> op;
		if(op == 1){
			cin >> p >> h;
			cnt[pos[p]]--;
			if(cnt[pos[p]] == 1) ans--;
			pos[p] = h;
            cnt[pos[p]]++;
			if(cnt[pos[p]] == 2) ans++;
		}else{
			cout << ans << endl;
		}
	}
	return 0;
}

D - Gravity

有一个

10^{9}

行 W 列的网格。左起第

x

列和下起第

y

行的单元格用

(x,y)

表示。

N

个图块。每个区块是

1×1

的正方形，第

i

个区块

（1≤i≤N）

在

0

时刻位于单元格

(X_{i},Y_{i}

)。

在

t=1,2,...,10^{100}

时，区块按照以下规则移动：

如果整个底部都布满了图块，则移除底部的所有图块
对于剩余的每个图块，按照从下到上的顺序，执行以下操作；
- 如果该图块最为最下面一行，或者它下面的单元格中有一块图块，则不做任何操作。
- 否则，将该图块向下移动一格。

Q

个查询，对于第

j

个查询，回答区块

A_j

在时间

T_j + 0.5

是否存在。

预处理答案。

哪些块一定会消失？会构成底行都为图块的块。那么先就求会消掉的层数，即每列的最少块数。

那么最后会处于同一行的什么时候消失呢？这个由最终同行的最高点决定。

不消失的块则一直存在。

CPP

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n, w;
	cin >> n >> w;
	vector<int>dt(n + 1, -1); //记录第i块消失的时间
	vector< vector< pair<int, int> > > db(w + 1); // 记录第i列信息(高度，第几块) 
    
	for(int x, y, i = 1; i <= n; i++){
		cin >> x >> y;
		db[x].push_back({y, i});
	}
	
	int tot = INT_MAX;// 统计最多能删除的行的数量 
	for(int i = 1; i <= w; i++){
		sort(db[i].begin(), db[i].end());// 对每列按行高排列 
		tot = min(tot, (int)db[i].size());//能删除的数量为每列当中最少的行数 
	}
	
	for(int i = 1; i <= tot; i++){//处理每一次删除操作 
		int cur = 0;  // 当前这次删除的时间 
		for(int j = 1; j <= w; j++)
			cur = max(cur, db[j][i - 1].first); // 时间为当前这次最高的行 
		                                        // 即第j列第i-1最大的数 
		for(int j = 1; j <= w; j++)
			dt[db[j][i - 1].second] = cur; // 将消除时间记录下来 
	}
	
	int q;
	cin >> q;
	while(q--){
		int t , a;
		cin >> t >> a;
		if(dt[a] == -1 || dt[a] > t) puts("Yes");
		else puts("No");
	}
}
int main(){
	solve();
	return 0;
}

E - Hierarchical Majority Vote

手动画一下样例1，则能发现：原来字符串每个字符是叶子节点，每三个往上合并一个成为新节点。最后形成一棵树。

题目就是求这个树根节点原数值发生改变所需的最少修改次数。

可以递归求解。

记录每棵子树的根节点修改成0或者1时所需的最少次数，自底向上求解，显然，这过程其实是动态规划，这里用

dp[i][0/1]

来保存结果。

具体过程详见代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6 + 5;
vector<int>g[N];
int tot, n;
int dp[N][2], cur[N];
// dp[i][0/1]表示节点i，变成0/1需要的修改次数
// cur[i]不修改i的情况下，i节点的数字 
string s;

void dfs(int u){
	if(u <= n){ // 叶子节点 
		if(s[u] == '1') dp[u][0] = 1;
		else dp[u][1] = 1;
		cur[u] = s[u] - '0';
		return;
	}
	int cnt = 0; // 计算不修改情况下，u的3个儿子有多少个1
	for(auto v : g[u]){
		dfs(v);
		cnt += cur[v];
	}
	
	if(cnt == 2 || cnt == 3) cur[u] = 1; // 得出当前u节点在未修改的情况下的数值 
	else cur[u] = 0;
	
	// 接下来考虑修改为0或者1，需要的最少操作次数
	 
	for(int t = 0; t <= 1; t++){// 假设u点改成t的话，需要的最少次数 
		int sum = 0, mx = 0; // sum表示改成t时，所有子节点的所需的次数之和，mx表示最多的那条分支 
		for(auto v : g[u]){
			sum += dp[v][t];
			mx = max(mx, dp[v][t]); 
		}
		dp[u][t] = sum - mx; // 总共修改次数 - 最多的修改分支，即为剩余最少修改的次数之和 
	}
}
int main(){
	cin >> n >> s;
	n = tot = s.size();// tot表示总的节点个数
	s = ' ' + s;
	for(int i = 1; i + 2 <= tot; i += 3){ // 建树过程
		++tot;
		g[tot].push_back(i);
		g[tot].push_back(i + 1);
		g[tot].push_back(i + 2);
	}
	dfs(tot); // tot就是建完数据后的根节点
	cout << dp[tot][cur[tot] ^ 1] << endl; 
	return 0;
}

文章操作

相关推荐

评论

Atcoder ABC 391