cf-913-div3

发布时间:2024年01月16日

title: cf 913 div3
date: 2024-01-16 16:42:45
tags: vp
categories: 比赛

A. Rook

题目大意

可以在棋盘上横向或纵向移动任意步数,找出车的所有走法

解题思路

直接输出横向和纵向车能移动的位置即可

代码实现

void solve()
{
	string s; cin >> s;
	string s1, s2;
	s1 = s2 = s;
	vector<string> vec;
	for (int i = 0; i < 8; i++) {
		s1[0] = char(i + 'a');
		s2[1] = char(i + '1');
		vec.push_back(s1);
		vec.push_back(s2);
	}
 
	for (auto x : vec) {
		if (x == s) continue;
		cout << x << endl;
	}
	
}

B. YetnotherrokenKeoard

题目大意

按顺序输入字符串,遇到 ′ B ′ 'B' B 删除输入的字符串中最右侧的大写字母,没有则不做改变,输入到 ′ b ′ 'b' b,删除输入的字符串中最右侧的小写字母,没有则不改变

解题思路

类似于队列,维护大写字母和小写字母最优侧下标,那么我们则将小标与对应的字符存储在一起,按照顺序输入,操作。

代码实现

PII a[N];
void solve()
{
	string s; cin >> s;
	//维护序列当中最右边大写小写字母
	vector<PII> lc, uc;
	for (int i = 0; i < (int)s.size(); i++) {
		char x = s[i];
		if (x == 'b') {
			if (lc.size()) lc.pop_back();
		}
		else if (x == 'B') {
			if (uc.size()) uc.pop_back();
		}
		else if (isupper(x)) {
			uc.push_back({ i,x });
		}
		else lc.push_back({ i,x });
	}
 
	vector<PII> vec;
	for (auto it : lc) {
		vec.push_back(it);
	}
	for (auto it : uc) {
		vec.push_back(it);
	}
	sort(vec.begin(), vec.end());
	for (auto it : vec) {
		cout << char(it.second);
	}
	cout << endl;
}

C. Removal of Unattractive Pairs

题目大意

给出一个字符串,满足任意删除相邻的一对不同字符,求出最短的字符串

解题思路

模拟发现,最后的状态一定不存在字符或者只存在一个字符,因此考虑将其余字符删除,能将字符变得多短

代码实现

void solve()
{
	int cnt = 0;
	int n; cin >> n;
	string s; cin >> s;
	map<int, int> mp;
	for (int i = 0; i < (int)s.size(); i++) {
		mp[s[i]]++;
		cnt = max(mp[s[i]], cnt);
	}
	cout << n - min(n / 2, n - cnt) * 2 << endl;
}

D. Jumping Through Segments

题目大意

给出 n n n 个线段,第 i i i 次移动要在第 i i i 个线段上面,可以在 k k k 范围内任意距离移动,求最小的 k k k

解题思路

二分答案。每一次移动范围内,存在移动范围与下一个下段有交集即合法。

代码实现

bool check(int k)
{
	int l = 0, r = 0;
	for (auto it : a) {
		int L = max(0, l - k), R = r + k;
		if (L > it.second || R < it.first) return 0;
        l = max(L,it.first),r = min(R,it.second);
	}
	return 1;
}
void solve()
{
	int n; cin >> n;
	a = b;
	for (int i = 0; i < n; i++) {
		int l, r;;
		cin >> l >> r;
		a.push_back({ l,r });
	}
	int l = 0, r = 2e9;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
}

E. Good Triples

题目大意

给出一个整数 n n n,满足三个非负整数 a 、 b 、 c a、b、c abc之和为 n n n,并且他们的数位之和等于 n n n 的数位之和的方案数。

解题思路

若要满足条件,三个数是不能进位。因此每一位是不受其他位影响,将每一数的每一位贡献相乘即可

代码实现

int pre[10];
void solve()
{
	int n; cin >> n;
	ll ans = 1;
	while (n) {
		ans *= pre[n % 10];
		n /= 10;
	}
	cout << ans << endl;
}
int main()
{
	for (int i = 0; i <= 9; i++) {
		for (int j = 0; i + j <= 9; j++) {
			for (int k = 0; i + k + j <= 9; k++) {
				pre[i + j + k]++;
			}
		}
	}
	int t; cin >> t;
	while (t--) solve();
	return 0;
}

F. Shift and Reverse

题目大意

给出一个数组 a a a,可以进行两种操作
移位:将最后一个数组移到首位
反转:将整个数组反转

解题思路

将数组变成环,遍历找到递增的或者递减的,模拟操作即可

代码实现


void solve()
{
	int n; cin >> n;
	vector<int> a(2 * n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i + n] = a[i];
	}
 
	int ans = -1;
	for (int i = 0; i < n; i++) {
		int st = i;
		int cnt = 1;
		while (i < 2 * n - 1 && a[i] >= a[i + 1]) {
			cnt++;
			i++;
		}
		if (cnt >= n) {
			ans = min(st + 1, n - st + 1);
		}
	}
	
	for (int i = 0; i < n; i++) {
		int st = i;
		int cnt = 1;
		while (i < 2 * n - 1 && a[i] <= a[i + 1]) {
			cnt++;
			i++;
		}
		if (cnt >= n) {
			if (ans == -1) {
				ans = min(n - st, st + 2);//移动多少个,翻转两次,一次时移动多少个
			}
			else {
				ans = min(ans, min(n - st, st + 2));
			}
			if (st == 0) ans = 0;
		}
	}
	cout << ans << endl;
}

G. Lights

题目大意

n n n 盏灯和 n n n 个开关,改变 i i i 的状态,也会改变 a i a_i ai? 状态。求出最少开关关掉所有的灯,不可能输出 -1。

解题思路

建边后发现是一颗基环树,环外的边的操作固定,用拓扑排序处理非环上的点。环的部分,如果剩余亮着的灯数量为奇数,则无法全部熄灭。

代码实现


void solve()
{
	int n; cin >> n;
	vector<int> in(n + 5), e(n + 5);
	string s; cin >> s;
	s = " " + s;
	for (int i = 1; i <= n; i++) {
		int u = i, v;
		cin >> v;
		e[u] = v;
		in[v] ++;
	}
 
	queue<int>q;
	for (int i = 1; i <= n; i++) {
		if (in[i] == 0) q.push(i);
	}
	vector<int>ans;
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		if (s[x] == '1') {
			s[x] = '0';
			ans.push_back(x);
			if (s[e[x]] == '1') {
				s[e[x]] = '0';
			}
			else s[e[x]] = '1';
		}
		in[e[x]] --;
		if (in[e[x]] == 0) {
			q.push(e[x]);
		}
	}
 
	for (int i = 1; i <= n; i++) {
		if (in[i]) {
			int j = i;
			int t = 0;
			int len = 0;
			int res = 0;
			while (in[j]) {//环
				if (s[j] == '1') {
					t ^= 1;
				}
				res += t;
				in[j] = 0;
				len++;
				j = e[j];
			}
			if (t == 1) {
				cout << -1 << endl;
				return;
			}
			for (int k = 0; k < len; k++) {
				if (s[j] == '1') {
					t ^= 1;
				}
				if (t == (res < len - res)) ans.push_back(j);
				j = e[j];
			}
		}
	}
	cout << ans.size() << endl;
	for (auto it : ans) cout << it << ' ';
	cout << endl;
}
文章来源:https://blog.csdn.net/m0_73865722/article/details/135631779
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。