【CF补题】Codeforces Round #806 (Div. 4)C++代码

A - YES or YES?

#include
using namespace std;
#define ll long long
const int mo = 1e3;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin >> n ;
	string str;
	while(n--)
	{
		cin>>str;
		transform(str.begin(),str.end(),str.begin(),::tolower);
		if(str=="yes")cout<<"YESn";
		else cout<<"NOn";
	} 
	return 0;
}

B - ICPC Balloons

#include
using namespace std;
#define ll long long
const int mo = 1e3;
bool v[300];
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t ;
	int n;
	long long cnt;
	while (t--)
	{
		cin >> n;
		memset(v, 0, sizeof(v));
		char c;
		long long cnt = 0;
		for (int i = 1; i <= n; i++)
		{
			cin >> c;
			if (v[c] == 0)cnt++;
			cnt++;
			v[c] = 1;
		}
		cout << cnt << 'n';
	}
	return 0;
}

C - Cypher

#include
using namespace std;
#define ll long long
const int mo = 10;
int a[200];
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	char c;
	int n, x;
	while (t--)
	{
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		for (int i = 1; i <= n; i++)
		{
			cin >> x;
			for (int j = 1; j <= x; j++)
			{
				cin >> c;
				if (c == 'D')a[i] = (a[i] + 1) % mo;
				if (c == 'U')a[i] = (a[i] + 9) % mo;
			}
			cout << a[i] << ' ';
		}
		cout << endl;
	}
	return 0;
}

D - Double Strings

这题不用想太复杂，就直接模拟好了，我一开始开了2个vector然后tle了，应该是find有点耗时？

#include
using namespace std;
int t,n;
const int N=1e5+5;
string s[N];
int main()
{
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--)
	{
		cin>>n;
		set st;
		for(int i=1;i<=n;i++)
		{
			cin>>s[i];
			st.insert(s[i]);
		}
		for(int i=1;i<=n;i++)
		{
			bool f=0;
			for(int len=1;len 
E - Mirror Grid​​​​​​
这题有点搞，主要把正方形缩小1/4，看旋转的4个（奇数的话中间只有1个） 的“1”的数量，要么全变成1，要么全变成0.
 
#include
using namespace std;
#define ll long long
const int mo = 1e3;
char a;
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t;
	int n;
	int num[200][200];
	long long ans;
	while (t--)
	{
		cin >> n;
		memset(num, 0, sizeof(num));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			{
				cin >> a;
				if (a == '1')
				{

					if (i <= (n + 1) / 2 && j <= (n + 1) / 2) {
						num[i][j]++;//cout<<"i= "< (n + 1) / 2) {
						num[n - j + 1][i]++;//cout<<"i= "< (n + 1) / 2 && j <= (n + 1) / 2) {
						num[j][n - i + 1]++;//cout<<"i= "< (n + 1) / 2 && j > (n + 1) / 2) {
						num[n - i + 1][n - j + 1]++;//cout<<"i= "< 
F - Yet Another Problem About Pairs Satisfying an Inequality
 
因为long long 所以也可以用树状数组做，有需要的话后期我补一下。
 
这个题解有点巧妙，有vector，因为i在push_back的时候就是排好序的，lower_bound一下就可以找到一共有几个i数比a[j]小了
 
#include
using namespace std;
#define ll long long
const int mo = 1e3;

void solve()
{
	int n;
	cin >> n;
	int x;
	long long res = 0;
	vector v;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		if (x >= i)
		{
			continue;
		}
		res += (long long)(lower_bound(v.begin(), v.end(), x) - v.begin());
		v.push_back(i);
	}
	cout << res << 'n';
}

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

 
G - Good Key, Bad Key 
 
我们将证明使用好的键作为前缀总是最优的，然后只使用坏的键。 考虑我们使用了一个坏密钥然后一个好密钥，通过这样做我们获得了⌊ai/2⌋+⌊(ai+1)/2⌋-k个硬币。 如果我们先切换并使用一个好密钥，一个坏密钥然后我们得到 ai+⌊(ai+1)/2⌋−k，这个数字显然更大，所以在最优解中我们永远不会在好密钥之前遇到坏密钥，因此我们 将使用好键的前缀，然后继续使用坏键。
 
注意！！移位的数量很重要，int 最多移位31次，不然会爆（就是“除以2”的操作31次是最多了）
 
其他都写在注释里
 
#include
using namespace std;
#define ll long long
const int mo = 1e3;
ll a[100001];
int main()
{
	ios::sync_with_stdio(false);
	int t;
	cin >> t ;
	int n, k;
	while (t--)
	{
		cin >> n >> k;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		ll sum = 0, ans = 0;
		for (int i = 0; i <= n; i++)//好钥匙和坏钥匙的断点。
		{
			ll now = sum;//包括这一个的前面全用好钥匙得到的硬币
			for (int j = i + 1; j <= min(n, i + 31); j++)//下一个开始用坏钥匙
			{
				ll copy = a[j];
				copy >>= j - i;
				now += copy;
			}
			ans = max(ans, now);
			if (i != n) //下一个用好钥匙
			{
				sum += a[i + 1] - k;
			}
		}
		cout << ans << endl;
	}
	return 0;
}