The 2022 ICPC Asia Nanjing Regional Contest IGDA,和令人疑惑的MI - 完美回文
题意
把单词改成一串相同的字母，最小修改次数
思路
把所有字母改成这个单词中出现次数最多的字母
代码
#include <bits/stdc++.h>
using namespace std;void solve() {string s;map<char, int> mp;cin >> s;int mx = 0;for (char ch : s) {mp[ch]++;mx = max(mx, mp[ch]);}cout << s.size() - mx << '\n';
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
G - 邪恶铭刻
题意
按顺序有三种情况
1获取野兽，攻击力为1
-1合成两只野兽
0选择1或-1
求最后野兽的平均战力最高是多少
思路
贪心的考虑0应该怎么分配
由于算的是平均值，合成野兽的贡献比增加野兽的贡献大，那么尽量选-1，只剩一只野兽的时候再选1
但是如果出现\(1,1,1,0,-1,-1,\) 这种序列，遇到0取-1是无法完成所有事件的
那么可以把0位置记录下来，一旦碰到无法完成所有任务的情况，就把0从-1改成1
代码
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'void solve() {int n;cin >> n;vector<int> a(n);for (int &i : a) cin >> i;int cnt = 0;int p = 1, q = 1;for (int i = 0; i < n; i++) {if (a[i] == 1) {p++;q++;} else if (a[i] == -1) {if (q > 1) {q--;} else {if (cnt) {p++, q++;cnt--;} else {cout << -1 << endl;return;}}} else {if (q > 1) {q--;cnt++;} else {p++, q++;}}}int z = __gcd(p, q);cout << p / z << " " << q / z << endl;
}int main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) solve();return 0;
}
D - 聊天程序
题意
给初始序列 \(a\)，要求最大化 \(a\) 的第 \(k\) 大的数
可以对 \(a\) 进行如下操作，给定等差数列的长度\(m\)，首项\(c\)，公差\(d\)
选择 \(a\) 的连续序列，把等差数列加上去
最多加1次
思路
采用二分第k大的值
关键在于check函数怎么写
暴力就是枚举每个位置的 \(a_i\) 作为开头，加一遍后看看能不能满足第 \(k\) 大的数大于 \(x\)
即便是暴力方式，也不能每次新建一个数组来排序，我们选择用计数的方式
大于等于 \(x\) 的个数大于等于 \(k\) 说明满足要求（注意这里的第k大是指从大到小排序的第k个数字，不用去重
那么接下来思考优化，对于等差数列，我们先只观察一个位置 以\([1,1,4,5,1,4]\)为例
\(c=1,d=2,m=3\)，那么数列就是\(1,3,5\)
假定二分的第k大的值是4，观察 \(a_4=1\) ，如果 \(a_4\) （下标从0开始）作为等差数列的第二项，是满足要求的
但是如果作为等差数列的第3项，加起来也比4大
那么枚举 \(a_2\) 为开头，从 \(a_2\) 到 \(a_4\) ，排除原本就大于4的值，现在对答案的贡献就是 \(a_4\) 位置的1个
枚举 \(a_3\) 为开头，从 \(a_3\) 到 \(a_5\)，对答案的贡献还是 \(a_4\)
每个位置作为等差开头从而新增的大于 \(x\) 的数量加上原本就大于 \(x\) 的数量如果大于等于 \(k\)，return true
差分维护
代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'const int N = 2e5 + 10;
int a[N];
int n, k, m, c, d;
int sum[N];
bool check(int x) {fill_n(sum, n + 1, 0);int cnt = 0;for (int i = 0; i < n; i++) {if (a[i] < x) {int rk;if (d != 0) {if (x <= a[i] + c)rk = 1;elserk = (x - a[i] - c + d - 1) / d + 1;if (rk > m) continue;if (i - rk + 1 >= 0) sum[i - rk + 1]++;if (i - m >= 0) sum[i - m] -= 1;} else {if (x - a[i] - c <= 0) {rk = 0;sum[i]++;if (i - m >= 0) {sum[i - m] -= 1;}}}} else {cnt++;}}for (int i = n - 1; i >= 0; i--) {sum[i] += sum[i + 1];if (cnt + sum[i] >= k) return 1;}return 0;
}void solve() {cin >> n >> k >> m >> c >> d;for (int i = 0; i < n; i++) {cin >> a[i];}int l = 0, r = 1e18;int ans = 0;while (l <= r) {int mid = l + r >> 1;if (check(mid)) {l = mid + 1;ans = mid;} elser = mid - 1;}cout << ans;
}signed main() {ios::sync_with_stdio(0), cin.tie(0);int t = 1;while (t--) {solve();}return 0;
}
A - 停停，昨日请不要再重现
题意
一个棋盘上站满了袋鼠，给操作序列，袋鼠跟随操作序列移动，如果跳出棋盘就移除
棋盘上有个洞，掉进洞的袋鼠也被移除
问最后剩下 \(k\) 只袋鼠的话，有多少可能的位置上有洞，每次棋盘上只有一个洞
思路
在没有洞的情况下，可以判断出最后剩下的袋鼠是一个固定的矩形部分\(n',m'\)
在有洞的情况下，可以看成 \(n'm'\) 固定，这样洞就有一个路径
并且洞的路径不会超，洞的路径与操作相反，L说明洞往右走
而如果洞的路径超了，说明袋鼠全都走出去了，判掉就行
也就是说，我们把洞的路径看成一个方形g，用[[二维差分]]维护一下
\(g[x][y]\) 表示在 \((x,y),(x-U,y-L)\) 这个矩形内的洞经过的格子数
用所有剩下的袋鼠 \(x-g[x][y]\) 就是剩余的袋鼠数
代码
代码抄袭参考这篇
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1000 + 10;
int n, m, k;
int U, D, L, R, U_, D_, L_, R_;
bool st[N][N]; // stone，表示石头是否存在在这一格
int g[N][N];
string op;void add(int x1, int y1, int x2, int y2) {// 去重，洞走过多次等同于走一次if (st[x1][y1]) return;st[x1][y1] = true;// 差分g[x1][y1]++;g[x2 + 1][y1]--;g[x1][y2 + 1]--;g[x2 + 1][y2 + 1]++;
}void solve() {cin >> n >> m >> k >> op;// 左上角为坐标原点U_ = L_ = U = L = 1;R_ = R = m;D_ = D = n;memset(st, 0, sizeof st);memset(g, 0, sizeof g);// 确定边界for (char ch : op) {// 往左，说明左边两行不用了if (ch == 'L') L_++, R_++;if (ch == 'R') L_--, R_--;if (ch == 'U') U_++, D_++;if (ch == 'D') U_--, D_--;L = max(L, L_);R = min(R, R_);U = max(U, U_);D = min(D, D_);}// 无袋鼠剩余if (U > D || L > R) {// 如果k>0 不可能完成，反之，洞随便放if (k)cout << "0\n";elsecout << n * m << endl;return;}// 统计袋鼠经过格子的情况int x = (D - U + 1) * (R - L + 1), cnt = 0;add(U, L, D, R);for (char ch : op) {// 往左，说明洞往右if (ch == 'L') L--, R--;if (ch == 'R') L++, R++;if (ch == 'U') U--, D--;if (ch == 'D') U++, D++;add(U, L, D, R);}// 二分前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];}}// 统计答案for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (x - g[i][j] == k) cnt++;}}cout << cnt << endl;
}int main() {int t;cin >> t;while (t--) {solve();}
}
M - 清空水箱
题意
逆时针给一个简单图形，没有交叉和重合，但是有共线的，这个图形是个水箱，里面有水，要开若干个洞才能把水全排出去
疑惑
题解还是挺多的，但是我有个wa30的思路表示十分疑惑，希望有佬能帮我看看哪里有问题
如图，逆时针的话，前一条边的极角是 \(a1\) ，后一条边是 \(a2\)，用 \(atan2\) 函数来算
只要满足 \(a1>0\),\(a2>0\) ,\(a1>a2\)就说明需要开口
代码
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define endl '\n'
const double eps = 1e-7;
struct P {int x, y;
} a[2010];void solve() {int n;cin >> n;for (int i = 0; i < n; i++) {cin >> a[i].x >> a[i].y;}a[n].x = a[0].x;a[n].y = a[0].y;a[n + 1].x = a[1].x;a[n + 1].y = a[1].y;n++;int ans = 0;for (int i = 1; i < n; i++) {long double a1 = atan2l(a[i - 1].y - a[i].y, a[i - 1].x - a[i].x);long double a2 = atan2l(a[i + 1].y - a[i].y, a[i + 1].x - a[i].x);if (a1 > eps && a2 > eps) {if (a2 <= a1) ans++;}}cout << ans << endl;
}
int t = 1;
int main() {ios::sync_with_stdio(0), cin.tie(0);while (t--) {solve();}return 0;
}
