https://codeforces.com/contest/1980
A. Problem Generator
题意：There is going to be m rounds next mouth, each of the month should be consist of "ABCDEFG", count the numebr of alphabet we should add to satisfy this requirement under a giving sequence.
总结：题比较难读懂， Each round should contain one problem..说明了每个round都应该包含这些东西，没包含就要补上去。
void solve() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
array<int, 26> a{};
for (const auto& x : s) {
a[x - 'A']++;
}
int res = 0;
for (int i = 0; i <= 6; ++i) {
res += max(0, m - a[i]);
}
cout << res << '\n';
}
B. Choosing Cubes
题意：查看要被删除的数在非升序排序后是否一定会被删除。
思路：排序，分3种情况讨论。
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
int s = a[m];
sort(a.rbegin(), a.rend() - 1);
if (a[k] > s) {
cout << "NO\n";
}
else if (a[k] < s) {
cout << "YES\n";
}
else if (a[k] == s) {
if (k < n && a[k + 1] == s) {
cout << "MAYBE\n";
}
else {
cout << "YES\n";
}
}
}
C. Sofia and the Lost Operations
题意：给定序列a和b和d，问能否通过按序列d中的数按顺序对序列a进行操作，最后将序列a转为序列b。其中每次操作可以任选一个数将a[k]变为d[j].
思路：一次遍历序列d,看是否d中的所有的数都能被用掉，并且使用完后序列a已经完全变成了序列b.如果d中某个数在b中没出现，说明该操作是冗余操作，在冗余操作后必须有一个可以进行的操作，来将冗余操作使用掉。
总结：问题还是出在了语言上，理解错题目3次。第1次以为b中操作可以无序，第2次以为a中操作必须有序。第3次好好看了看才看懂题目。应该慢慢读题目的。
void solve() {
int n;
cin >> n;
vector<int> a(n);
vector<int> b(n);
for (auto& x : a){
cin >> x;
}
map<int, int> diff;
for (int i = 0; i < n; ++i){
cin >> b[i];
if (a[i] != b[i]){
diff[b[i]] ++;
}
if (!diff.count(b[i])){
diff[b[i]] = 0;
}
}
int m;
cin >> m;
bool ok = false;
for (int i = 0; i < m; ++i){
int x;
cin >> x;
if (diff.count(x) && diff[x] > 0){
ok = true;
diff[x] --;
}
else if(!diff.count(x)){
ok = false;
}
else{
ok = true;
}
}
for (const auto& [x, y] : diff){
if (y > 0){
ok = false;
break;
}
}
cout << (ok ? "YES\n" : "NO\n");
}
D. GCD-sequence
题意：给定一个序列a，根据相邻的数的gcd构造b，问能否exactly删除a中的一个元素，使序列b非递减。
思路：求出序列b，找到第一个拐点，然后依此尝试移除跟这次比较相关联a中的元素，暴力求解。时间复杂度(n * log(n) * c)。
总结：因为重新构造的次数一定是一个常数，所以可以直接使用暴力破解的方法。一开始想的是找到谷点以后，分情况讨论移除哪个数，来判断移除该点后是否可行，发现代码量实在是太大，最后转暴力了。 做题原则1：暴力能ac，就别犹豫。。莫装逼。
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto& x : a) {
cin >> x;
}
vector<int> b;
for (int i = 0; i < n - 1; ++i) {
b.push_back(gcd(a[i], a[i + 1]));
}
auto check = [&](int p) {
if (p < 0 || p > n - 1) {
return false;
}
auto c = a;
c.erase(c.begin() + p);
vector<int> d;
for (int i = 0; i < n - 2; ++i) {
d.push_back(gcd(c[i], c[i + 1]));
if (i && d[i] < d[i - 1]) {
return false;
}
}
return true;
};
for (int i = 0; i < n - 2; ++i) {
if (b[i] > b[i + 1]) {
if (check(i - 1) || check(i) || check(i + 1) || check(i + 2)) {
cout << "YES\n";
return;
}
else {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
}
E. Permutation of Rows and Columns
题意：给定两个矩阵a和b，并且矩阵中的数是个permutation。问矩阵a能否通过交换任意次数行和列得到矩阵b。
思路：记录a中每个元素所在的行和列，遍历b中的元素。依此统计出该元素变换到b中的所在行和列，a的行要交换到哪个行，列要交换到哪个列，如果有冲突，则No。
总结：一开始想复杂了，以为是什么构造边，然后拓扑排序，或者并查集什么的。后来想了想，只要行列交换没有冲突，那就可以了。。
void solve() {
int n, m;
cin >> n >> m;
vector<pair<int, int>> a(n * m + 1);
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
int x;
cin >> x;
a[x] = {i, j};
}
}
vector<vector<int>> b(n + 1, vector<int> (m + 1));
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
cin >> b[i][j];
}
}
vector<int> row(n + 1, -1);
vector<int> col(m + 1, -1);
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
const int& x = b[i][j];
int r = a[x].first;
int c = a[x].second;
if (row[r] != -1 && row[r] != i){
cout << "NO\n";
return;
}
if (col[c] != -1 && col[c] != j){
cout << "NO\n";
return;
}
row[r] = i;
col[c] = j;
}
}
cout << "YES\n";
return;
}
上面是赛时A掉的题，大概快半年没打cf了，rank2000多，在预期内。
准备补剩下的题。
F1. Field Division (easy version)
题意：给定一个矩阵和一堆喷泉fountains，alice从左边或上边出发，问alice不碰到喷泉，最多能占到多少格子（路线左下+路线格子是alice的）。再问，考虑所有的i，如果第i个喷泉给了alice，alice是否能增加格子。
思路：模拟题，对fountains按列升序排序，行降序排序。然后依此考虑每个fountain和上一步的x和y坐标，求出上一步到当前这一步alice可以占到多少格子。如果当前x>上一步的x，说明这个fountain给了alice可以为alice带来效益。
总结：前面几个题写的太慢了，不然的话这个赛时应该能写出来，不过处理这二维坐标问题和移动，确实非常抽象。。还有就是坐标计算没有转long long，溢出了。
void solve() {
int n, m, k;
cin >> n >> m >> k;
vector<pair<long long, long long>> fountains(k);
for (auto& x : fountains){
cin >> x.first >> x.second;
}
vector<int> pos(k);
iota(pos.begin(), pos.end(), 0);
sort(pos.begin(), pos.end(), [&](const int& a, const int& b){
return fountains[a].second != fountains[b].second ?
fountains[a].second < fountains[b].second : fountains[a].first > fountains[b].first;
});
vector<int> ans(k, 0);
long long res = 0;
long long lastx = 0, lasty = 0;
bool first_time = true;
for (int i = 0; i < k; ++i){
const auto&[x, y] = fountains[pos[i]];
if (first_time){
lastx = 0;
lasty = 1;
first_time = false;
}
if (y > lasty){
res += (n - lastx) * (y - lasty);
}
if (x > lastx){
ans[pos[i]] = 1;
}
lastx = max(x, lastx);
lasty = y;
}
res += (m - lasty + 1) * (n - lastx);
cout << res << '\n';
for (int i = 0; i < k; ++i){
cout << ans[i] << " \n"[i == k - 1];
}
}
F2. Field Division (hard version)
题意：比上个题增加了一个要求输出将fountain给了alice后，alice增加了exactly多少个格子。
思路：对于有贡献的fountain，想到了使用单调栈，在下一个>=当前fountain的x喷泉出现之前，这一段中的所有列都有贡献。但是对于每个列，计算贡献又不太好计算，要遍历所有的喷泉才行，如果要遍历所有的喷泉，单调栈好像又显得没有意义。
先缓缓
标签：int,950,Codeforces,fountains,cin,vector,diff,Div,alice From： https://www.cnblogs.com/yxcblogs/p/18230155