Codeforces Round 932 (Div. 2)

Codeforces Round 932 (Div. 2) (A~D)

目录：A B C D

A题：Entertainment in MAC

标签: 构造算法（constructive algorithms）字符串处理（strings）

题目大意

• 给你一个 数字符串 s 和一个偶整数 n。你可以对它进行两种运算
• 1. 将反转字符串 s 添加到字符串 s 的末尾
• 2. 反转s
• 找到进行的 n 操作后，得到的字典序最小的字符串

思路

• t是s的反转字符串
• 不难看出，答案的前缀总是 s 或 t 。然后，我们找到两个前缀为 s和 t的词性最小字符串
• 执行2再执行1操作，得到前缀为t的字符串。重复反转得到前缀为s的字符串，比较即可

AC代码

#include <bits/stdc++.h>
using namespace std;
void solve()
{
	int n;
	string s1;
	cin >> n >> s1;
	string s2 = s1;
	reverse(s2.begin(), s2.end());
	s2 = s2 + s1;
	if(s1 < s2) cout << s1 << endl;
	else cout << s2 << endl; 
} 
int main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

B题：Informatics in MAC

标签: 构造算法（constructive algorithms）

题目大意

• 有一个长度为 n的数组 a，要把它划分为 k>1个连续子段，使每个子段上的 MEX都等于相同的整数。
• 数组中的 MEX 是不属于该数组的最小非负整数

思路

• 数组中每个数字都会被用到分段，要想每个子段含有想同的MEX，那么每个分段的MEX值一定等于总数组的MEX值
• 判断能将总数组拆分为两个片段 每个片段MEX=总数组的MEX
• MEX(1,i) = MEX(i+1,n) 找到一些 i 。

AC代码

#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second 
using namespace std;
const int N = 100100;
int f[N];
void solve()
{
	int n; cin >> n;
	map<int, int> mp; 
	for(int i = 1; i <= n; i++){
		cin >> f[i];
		mp[f[i]] ++;
 	}
 	// 找到原数组的MEX值t 
	int t = 0;
	while(mp[t]) t ++;
	set<int> st; 
	vector<int> v;
	for(int i = 1; i <= n; i++)
	{
		if(f[i] >= 0 && f[i] < t)
			st.insert(f[i]); 
		if(st.size() >= t){
			v.push_back(i);
			st.clear();
		}
	}
    //如果有两个i 
	if(v.size() >= 2)
		printf("2\n1 %d\n%d %d\n", v[0], v[0]+1, n);
	else cout << -1 << endl;
} 
signed main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

C题：Messenger in MAC

标签: 二分搜索（binary search）暴力枚举（brute force）构造算法（constructive algorithms）数据结构（data structures）动态规划（dp）贪心策略（greedy）排序算法（sortings）

题目大意

• 共有 n条信息。每条信息由两个整数 ai和 bi表示

• 花费时间计算：pi为选择的消息序号

• $$
  \sum_{i = 1}^{k}a_{p_i} + \sum_{i = 1}^{k-1} |b_{p_i} - b_{p_{i+1}}|
  $$

• 花费时间不超过l，最多读取多少条信息。

思路

• 按bi 从小到大排序，枚举每个(l, r)区间，bi这一维度花费为br - bl
• 从l r区间中选取的ai，如果时间超过l，去掉较大的ai这条，用大根堆即可 O(n^2^logN)复杂度

AC代码

#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second 
using namespace std;
typedef pair<int, int> PII;
const int N = 2010;
PII f[N];
bool cmp(PII a, PII b){
	return a.se < b.se;
}
void solve()
{
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++)
		cin >> f[i].fr >> f[i].se;
	sort(f + 1, f + 1 + n, cmp);
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		priority_queue<int> q;
		int sum = 0;
		for(int j = i; j <= n; j++)
		{
			q.push(f[j].fr);
			sum += f[j].fr; 
			while(!q.empty() && sum + f[j].se - f[i].se > k){
				sum -= q.top();
				q.pop();
			}
			res = max((int)q.size(), res);
		}
	}
	cout << res << endl;
} 
signed main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

D题：Exam in MAC

标签: 二分搜索（binary search）组合数学（combinatorics）数学（math）

题目大意

• 给一个大小为 n 的集合 s 和一个整数 c 。对于这个集合，需要计算0 ≤ x ≤ y ≤ c (x, y)对的个数，满足x + y 和 y−x 都不包含在集合 s 中。

思路

• 可能的 x, y对数为 $\frac{(c + 1)(c + 2)}{2}$，思路：用总数减去不满足的对数
• x + y == ai（x, y)的对数为c - ai + 1 — (0, ai)，(1, ai+1)，(2, ai+2)……，(c-ai, c)
• y - x == ai (x, y)的对数为ai / 2 + 1 — (0, ai)，(1, ai-1)，(2, ai-2)……
• 考虑去重：
• 1. x + y == ai y - x == ai 都满足的对数为1 （0，a)
• 2. 将ai从小到大排序
  • 满足x + y == ai的(x, y)对一定不会在前面被去重
  • ai 为偶数那么 y - x 可发现也为偶数，并且为小于ai的全部偶数，即ai前面如果有cnt个偶数那么就被多去重了cnt次（奇数同理）

AC代码

#include <bits/stdc++.h>
#define int long long
#define fr first
#define se second 
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int a[N];
void solve()
{
	int n, m; 
	cin >> n >> m;
	int res = m * (m + 1) / 2 + m + 1;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + 1 + n);
	int cnt1 = 0, cnt2 = 0;
	for(int i = 1; i <= n; i++){
		int t = a[i];
		res -= m - t + 1;
		res -= t / 2;
		if(t % 2) res += cnt1, cnt1++;
		else res += cnt2, cnt2 ++; 
	} 
	cout << res << endl;
} 
signed main()
{
	int T; cin >> T;
	while(T--)
		solve();
	return 0;
}

logo

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　⊂⊃〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//

/*
          __   _,--="=--,_   __
         /  \."    .-.    "./  \
        /  ,/  _   : :   _  \/` \
        \  `| /o\  :_:  /o\ |\__/
         `-'| :="~` _ `~"=: |
            \`     (_)     `/
     .-"-.   \      |      /   .-"-.
.---{     }--|  /,.-'-.,\  |--{     }---.
 )  (_)_)_)  \_/`~-===-~`\_/  (_(_(_)  (
(                         				)
 )                                     (
'---------------------------------------'
*/