Codeforces Round 867 (Div. 3)

2023-05-04 23:32 由 scoxty 发表于 #其他

A. TubeTube Feed

分析:

从所有a[i]+i-1<=t的选择种取个max即可

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 55;
int a[N], b[N];
 
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 0; i < n; i ++)
			cin >> a[i];
			
		for (int i = 0; i < n; i ++)
			cin >> b[i];
			
		int s = 0, res = 0, idx = -1;
		bool flag = false;
		
		for (int i = 0; i < n; i ++)
		{
			if (s + a[i] <= m)
			{
				flag = true;
				if (b[i] > res)
				{
					res = b[i];
					idx = i + 1;
				}
			}
			s ++;	
		}
		
		if (!flag)
			cout << -1 << endl;
		else
			cout << idx << endl;
	}    
	
    return 0;
}

B. Karina and Array

分析:

实际上就是取同符号乘积的最大值

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
int a[N], b[N];
 
typedef long long LL;
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		if (n == 2)
		{
			int num1, num2;
			cin >> num1 >> num2;
			
			cout << (LL)num1 * num2 << endl;
		}
		else
		{
			int cnt1 = 0, cnt2 = 0;
			
			for (int i = 0; i < n; i ++)
			{
				int x;
				cin >> x;
			
				if (x >= 0)
					a[cnt1 ++] = x;
				else
					b[cnt2 ++] = x;
			}
		
			sort(a, a + cnt1);
			sort(b, b + cnt2);
			
			LL res;
			if (cnt1 >= 2 && cnt2 >= 2)
			{
				res = max((LL)b[0] * b[1], (LL)a[cnt1 - 2] * a[cnt1 - 1]);
			}
			else if (cnt1 >= 2 && cnt2 < 2)
				res = (LL)a[cnt1 - 2] * a[cnt1 - 1];
			else if (cnt1 < 2 && cnt2 >= 2)
				res = (LL)b[0] * b[1];
			
			cout << res << endl;
		}
	}
	
    return 0;
}

C. Bun Lover

分析:

找规律，发现结果与边长n的关系是：res = n * (n + 3) - (n - 2)

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
int a[N], b[N];
 
typedef long long LL;
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		LL n;
		cin >> n;
		
		cout << n * (n + 3) - (n - 2) << endl;
	}
	
    return 0;
}

D. Super-Permutation

分析:

①当n为奇数时，除了1其他均无解
②当n为偶数时，我们可以构造一个形如n,1,n - 2,3,...的数列
首先我们可以发现n必定出现在起始位置。如果n不在起始位置，假设在位置i，那么s[i - 1] % n == (s[i - 1] + n) % n = s[i] % n。
接着，考虑构造方式。最方便的即是考虑让序列取模结果为：0，1，-1，2，-2...(-1取模意义下溢出实际上就是n - 1),按上述结果形式构造的序列n,1,n - 2,3,...即可满足所有条件
最后从结果来看就是n在偶数位递减，1在奇数位递增。

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
int a[N];
 
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		if (n == 1)
			cout << 1 << endl;
		else if (n & 1)
			cout << -1 << endl;
		else
		{
			for (int i = 0, j = n; i < n; i += 2, j -= 2)
				a[i] = j;
			for (int i = 1, j = 1; i < n; i += 2, j += 2)
				a[i] = j;
			for (int i = 0; i < n; i ++)
				cout << a[i] << " ";
			cout << endl;
		}
	}
	
	return 0;
}

E. Making Anti-Palindromes

分析:

①当n为奇数时：根据定义无解。
②当n为偶数时：
当某个字符出现的次数大于n / 2时，根据容斥原理，一定存在s[i] = s[n - i + 1]。
若不存在上述情况则一定有解，考虑如何处理对称字符：倘若存在形如..a..b..b..a的字符对我们优先选择交换a和b，这样一次操作可以处理两对字符，否则将对称对形如..a..b..d..a的情况交换a和d，一次操作处理一对字符。统计出现次数最多的字符对，其出现次数记为cnt1，所有字符对总数量记为cnt2，优先处理cnt1，所以当cnt1 <= cnt2 - cnt1时，答案即cnt2 / 2，否则答案即cnt1

code:

#include <bits/stdc++.h>
using namespace std;
 
const int N = 27;
int h[N], h2[N];
 
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		string s;
		cin >> s;
		
		if (n & 1)
			cout << -1 << endl;
		else
		{
			bool check = true;
			memset(h2, 0, sizeof h2);
			memset(h, 0, sizeof h);
			
			for (int i = 0; i < n; i ++)
			{
				h2[s[i] - 'a'] ++;
				if (h2[s[i] - 'a'] > n / 2)
				{
					check = false;
					break;
				}
			}
			
			
			if (check)
			{
				int Max = 0, cnt = 0;
				for (int i = 0, j = n - 1; i < n / 2; i ++, j --)
				{
					if (s[i] == s[j])
					{
						h[s[i] - 'a'] ++;
						Max = max(Max, h[s[i] - 'a']);
						cnt ++;
					}
				}
				
				if (Max <= cnt - Max)
					cout << (cnt + 1) / 2 << endl;
				else
					cout << Max << endl;
			}
			else
				cout << -1 << endl;
		}
	}
	
	return 0;
}