Codeforces Round 717 Div.2
A - Tit for Tat
这题贪心就行了。要使字典序尽可能小,当然是从首至尾贪心,只要可以操作且还有操作次数,都是是当前数字减小,末尾数字增加。这样得到的字典序一定是最小的。
#include <bits/stdc++.h>
using namespace std;
int T;
int n, k;
vector<int> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> T;
while (T--) {
cin >> n >> k;
v.resize(n);
for (int &it:v) cin >> it;
for (int i = 0; i < n - 1; i++) {
int delta = min(v[i], k);
v[i] -= delta;
v.back() += delta;
k -= delta;
if (k == 0) break;
}
for (int i = 0; i < n - 1; i++) cout << v[i] << ' ';
cout << v.back() << endl;
}
return 0;
}
B - AGAGA XOOORRR
这题其实只需要运用一点位运算的知识。
一开始我以为想出正解了,结果是把题目读错了(大错特错),那时候正好拿外卖吃饭,就找LYH交流了手,发现自己病情严重……
由于异或的特性,偶数个相同的数异或和等于$0$,例如$a\oplus a = 0$,奇数个相同的数异或和等于其本身,例如$a\oplus a\oplus a = a$。
那么,若我们一开始求出所有数的异或和为$ans$,如果$ans=0$,意味着序列可以被划分为两段,这两段异或和相同;如果$ans>0$,我们应检查序列能被分为几段异或和为$ans$的部分,且这个部分数一定为奇数。
按照题意,$ans=0$意味着YES,$ans>0$时如果只能被分为完整的一段为NO,其余为YES。
#include <bits/stdc++.h>
using namespace std;
int T, n;
vector<int> v;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> T;
while (T--) {
cin >> n;
v.resize(n);
int ans = 0;
for (int &it:v) {
cin >> it;
ans ^= it;
}
if (ans == 0) {
cout << "YES\n";
continue;
}
int tmp = 0, cnt = 0;
for (int it:v) {
tmp ^= it;
if (tmp == ans) {
cnt++;
tmp = 0;
}
}
if (cnt > 1) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
C - Baby Ehab Partitions Again
题目大意是给定一个序列,让你删除尽可能少的数,使得删除后的序列不能够被完全划分成两个和相同的部分。
所有首先要做的肯定是判断这个序列不删的时候能不能被划分成两个和相同的部分,判断的方法和《kkksc03考前临时抱佛脚》那题一样,可以用01背包求出两部分中和最小的最大值,如果这个最大值为sum/2,那么就不需要找数删,否则不用删数就已经满足要求了,输出0.