Codeforces Round 776 (Div. 3)(vp)
Dashboard - Codeforces Round 776 (Div. 3) - Codeforces
A Deletions of Two Adjacent Letters
题意：看看与题目给的字符一样的字符所在的位置两边的字符能不能合并，合并是指将相邻的字符删除
思路：我们就找到目标字符的位置，判断这个字符两边的字符是否是偶数即可，只要找到一个满足即可
void solve() {
string s;
cin >> s;
char op;
cin >> op;
vector<int> ans;
for (int i = 0; i < s.size(); i++)if (s[i] == op)ans.push_back(i);
for (auto i: ans) {
if (i % 2 == 0 && (s.size() - 1 - i) % 2 == 0) {
cout << "YES" << endl;
return;
}
}
cout << "NO" << endl;
}
B DIV + MOD
题意： 给定\(l\)和\(r\)以及\(a\)，找到一个数在\(l\)和\(r\)之间满足\(f_a(x)=\left\lfloor\frac{x}{a}\right\rfloor + x \bmod a\)最大
思路：我们其实可以发现，尽可能让余数变大以及除以a的倍数变大，我们可以从\(r\)开始往前找能使 \(x \bmod a\)的余数是a-1就是最大的值，因为我们往前找余数为a-1的过程中\(x/a\)最多减少1，而我们余数在这个过程中最少贡献1，最多贡献a-1，所以我们往前找不会让答案变小，如果我峨嵋你找到余数为a-1的位置在\(l\)前面，那还不如选原来的位置
void solve() {
int l, r, a;
cin >> l >> r >> a;
int x=r%a;
int rr=r-(x-1)-2;
if(x==a-1)cout<<r/a+r%a<<endl;
else if(rr>=l)cout<<rr/a+rr%a<<endl;
else cout<<r/a+r%a<<endl;
}
C Weight of the System of Nested Segments
题意：问在题目所给的这些点中，构建一个题目要求的多层嵌套系统，要求这个系统所用到点的权值最小
思路：其实就是一个纯贪心，先按权值最大排个序，题目用不到的那几个点先标记了，再按坐标从小到大排序，从外层一层一层的求解答案，遇到标记过的就跳过即可
void solve() {
vector<PII > a, b;
int k, n;
cin >> k >> n;
map<int, int> mp;
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
a.emplace_back(i, x);
b.emplace_back(i, y);
mp[i] = y;
}
sort(ALL(b), [](PII x, PII y) {
return x.se > y.se;
});
sort(ALL(a), [](PII x, PII y) {
return x.se < y.se;
});
vector<bool> vis(n + 1, false);
vector<PII > ans;
int anss = 0;
for (int i = 0; i < n - k * 2; i++) {
vis[b[i].fi] = true;
}
for (int i = 0, j = n - 1, cnt = 0; cnt < k; i++, j--, cnt++) {
while (vis[a[i].fi] && i < j)i++;
while (vis[a[j].fi] && i < j)j--;
ans.emplace_back(a[i].fi, a[j].fi);
anss += mp[a[i].fi] + mp[a[j].fi];
}
cout << anss << endl;
for (auto [x, y]: ans)cout << x << ' ' << y << endl;
cout << endl;
}
D Twist the Permutation
题意：给一个1~n的排列（没有顺序），问能不能通过题目所给的操作：At the \(i\)-th operation, Petya chose the first \(i\) elements of the array and cyclically shifted them to the right an arbitrary number of times (elements with indexes \(i+1\) and more remain in their places). One cyclic shift to the right is such a transformation that the array \(a=[a_1, a_2, \dots, a_n]\) becomes equal to the array \(a = [a_i, a_1, a_2, \dots, a_{i-2}, a_{i-1}, a_{i+1}, a_{i+2}, \dots, a_n]\).将这个排列还原为升序的，如果能输出每一步移动了多少，不能，输出-1
思路：我们可以发现，一定是有界的，不会出现无解的情况，其次我们可以到这来还原序列，那我们就让序列往左移，我们每次去找目标元素的位置，计算步数，并且更新序列，因为倒着还原前面的元素不会影响后面的元素，模拟一下即可复杂度\(O(\)\(x^{2}\)\()\)
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i++)cin >> a[i];
vector<int> ans;
int goal = n;
for (int i = 1; i <= n; i++) {
int pos;
for (int j = 1; j <= goal; j++) {
if (a[j] == goal) {
pos = j;
break;
}
}
vector<int> temp1, temp2;
temp1.push_back(0);
temp2.push_back(0);
if (pos == goal)ans.push_back(0);
else if (pos > goal) {
ans.push_back(pos - goal);
for (int j = 1; j <= pos - goal; j++)temp1.push_back(a[j]);
for (int j = pos - goal + 1; j <= goal; j++)temp2.push_back(a[j]);
for (int j = 1; j < temp2.size(); j++)a[j] = temp2[j];
for (int j = temp2.size(), len = 1; len < temp1.size(); j++, len++)a[j] = temp1[len];
} else {
ans.push_back(pos);
for (int j = 1; j <= pos; j++)temp1.push_back(a[j]);
for (int j = pos + 1; j <= goal; j++)temp2.push_back(a[j]);
for (int j = 1; j < temp2.size(); j++)a[j] = temp2[j];
for (int j = temp2.size(), len = 1; len < temp1.size(); j++, len++)a[j] = temp1[len];
}
goal--;
}
reverse(ALL(ans));
for (auto i: ans)cout << i << ' ';
cout<<endl;
}