Codeforces Round #700 Div. 2

天天摸鱼身体棒

A. Yet Another String Game

给定一串字符串,两个人轮流进行游戏,每个人轮流选一个之前没选过的字母,将其变成任意一个其他的字母,A的目标是让结果最小,B目标是让结果最大,问理想最终结果是啥

从头开始,奇数位不是a的改成a,a改成b;偶数位不是z的改成z,z改成y即可

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
ll t;
ll n,m;
string s;
char dat[10005][10005];
int main() {
	ios::sync_with_stdio(0);
	cin >> t;
	while (t--)
	{
		cin >> s;
		for (int i = 0; i < s.length(); i++) {
			if (i % 2) {
				if (s[i] == 'z')s[i] = 'y';
				else s[i] = 'z';
			}
			else {
				if (s[i] == 'a')s[i] = 'b';
				else s[i] = 'a';
			}
			
		}
		cout << s << '\n';
	}
}

B. The Great Hero

有个great hero和一系列怪物,great hero每次讨伐怪物可以给怪物造成固定伤害,同时讨伐的怪物也会对英雄造成伤害,给定每个怪物的血量和伤害,英雄的血量和伤害,问能不能全部讨伐怪物(讨伐成功时英雄死了也没关系

可以知道英雄最多可以一换一换掉一个怪物(受到一次致死伤害,而其他的怪物伤害都是要全部硬吃的,那么我们考虑换掉攻击力最高的怪物即可

剩下的部分模拟即可

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
P a[100000 + 5];
int main() {
	ios::sync_with_stdio(0);
	cin >> t;
	while (t--)
	{
		cin >> A >> B >> n;
		ll maxx = 0;
		ll tol = 0;
		for (int i = 0; i < n; i++) {
			cin >> a[i].first;
		}
		for (int i = 0; i < n; i++) {
			cin >> a[i].second;
		}
		sort(a, a + n);
		int flag = 1;
		for (int i = 0; i < n; i++) {
			ll tmp = a[i].first * ceil(a[i].second * 1.0 / A);
			if (i == n - 1) {
				if (B + a[i].first < tmp)flag = 0;
			}
			else {
				if (B < tmp) {
					flag = 0;
					break;
				}
				B -= tmp;

			}
		}
		if (!flag)cout << "NO\n";
		else cout << "YES\n";
	}
}

C. Searching Local Minimum

交互题:给定1到n的一个重排,令a[0]和a[n+1]是无穷大,要在100次询问中找到任意一个i令a[i]<min(a[i-1],a[i+1])

二分搜索,每次查询mid以及左右的点,如果mid比右边的大那mid右边肯定存在i,mid比右边小那mid左边存在i

#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
ll dat[100000 + 5] = {};
int main() {
//	ios::sync_with_stdio(0);
	cin >> n;
	ll l = 1, r = n ;
	dat[0] = 100000 + 5;
	dat[n + 1] = 100000 + 5;
	while (l<r)
	{
		ll m = (l + r) >> 1;
		if (dat[m] == 0) {
			cout << "? " << m << endl;
			cin >> dat[m];
		}
		if (m + 1 <= n && dat[m + 1] == 0) {
			cout << "? " << m+1 << endl;
			cin >> dat[m+1];
		}
		if (m - 1 > 0 && dat[m - 1] == 0) {
			cout << "? " << m-1 << endl;
			cin >> dat[m-1];
		}
		if (dat[m + 1] > dat[m])r = m;
		else l = m + 1;
	}
	cout << "! " << l << endl;
}

D. Painting the Array I&&II

给定一串数列,把它分为0和1两个子串,然后分别把两个子串中相邻的相同数字合并,求两个子串的最短/最长长度

最长:先记下两个子串中最后一个数字,a0和a1,然后判断当前的数字要放到哪个子串中

如果a0 == a1 == dat[i] ,dat[i]放哪都一样没用

如果a0 == dat[i]&&a1 != dat[i] 放入1子串

如果a0 != dat[i] && a1 != dat[i],不能乱放,要比较a0和a1的数字的下一位的位置,放更近的,因为下一位相同数字越近,越容易被合并,更新后就不易合并

最短:如果a0 != dat[i] && a1 != dat[i],要比较a0和a1的数字的下一位的位置,放更远的,

其他情况都可以直接合并,不用更新

I
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
ll dat[100000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> dat[i];
		pos[dat[i]].push_back(i);
	}

	ll a0 = 0, a1 = 0;
	ll l0 = 0, l1 = 0;
	for (int i = 0; i < n; i++)
	{
		pos[dat[i]].erase(pos[dat[i]].begin(), pos[dat[i]].begin() + 1);
		ll nxt0 = pos[a0].empty() ? 1000000 : pos[a0][0];
		ll nxt1 = pos[a1].empty() ? 1000000 : pos[a1][0];
		if (dat[i] != a0 && dat[i] != a1) {
			if (nxt0 < nxt1) {
				l0++;
				a0 = dat[i];
			}
			else {
				l1++;
				a1 = dat[i];
			}
		}
		else if (dat[i] == a0&&dat[i]!=a1) {
			l1++;
			a1 = dat[i];
		}
		else if(dat[i] != a0 && dat[i] == a1){
			l0++;
			a0 = dat[i];
		}

	}
	cout << l0 + l1;
}
	
II
#include <iostream>
#include <cstring>
#include <stdio.h>
#include <algorithm>
#include <set>
#include<vector>
#include<cmath>
#include <map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
ll t;
ll n, m;
ll A, B;
string s;
ll dat[100000 + 5] = {};
vector<ll> pos[100000 + 5];
int main() {
	ios::sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> dat[i];
		pos[dat[i]].push_back(i);
	}

	ll a0 = 0, a1 = 0;
	ll l0 = 0, l1 = 0;
	for (int i = 0; i < n; i++)
	{
		pos[dat[i]].erase(pos[dat[i]].begin(), pos[dat[i]].begin() + 1);
		ll nxt0 = pos[a0].empty() ? 1000000 : pos[a0][0];
		ll nxt1 = pos[a1].empty() ? 1000000 : pos[a1][0];
		if (dat[i] != a0 && dat[i] != a1) {
			if (nxt0 > nxt1) {
				l0++;
				a0 = dat[i];
			}
			else {
				l1++;
				a1 = dat[i];
			}
		}
		
	}
	cout << l0 + l1;
}
	
上一篇:Codeforces Round #700 题解(A-D)


下一篇:Codeforces Round #700 (Div. 2)