1496A. Split it!

类回文判断，只要 k = 0 或者 Codeforces Round #706 Editorial - 图1是回文即可

特判情况 n < 2 * k + 1 为 NO

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     int _ = 1;
  4.     for (cin >> _; _--;) {
  5.         string s;
  6.         int n; ll k;
  7.         cin >> n >> k;
  8.         cin >> s;
  9.         bool f = true;
  10.         for (int i = 0; i < k && f; ++i) f = s[i] == s[n - i - 1]);
  12.         cout << (f && n >= 2 * k + 1 ? "YES\n" : "NO\n");
  13.     }
  14.     return 0;
  15. }

1496B. Max and Mex

模拟，当 mex(a) < max(b) 时 必有 Codeforces Round #706 Editorial - 图2 则集合不一样的数可增加一，否则每进行一次操作 + 1

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     int _ = 1;
  4.     for (cin >> _; _--;) {
  5.         int n;
  6.         ll k;
  7.         cin >> n >> k;
  8.         vector<ll> a(n);
  9.         set<ll> s;
  10.         for (int i = 0; i < n; ++i) {
  11.             cin >> a[i];
  12.             s.insert(a[i]);
  13.         }
  14.         sort(a.begin(), a.end());
  15.         if (k == 0) {
  16.             cout << s.size() << "\n";
  17.             continue;
  18.         }
  19.         int i = 0;
  20.         ll b = 0;
  21.         while (b == a[i]) b++, i++;
  22.         if (b <= a[n - 1]) {
  23.             s.insert((b + a[n - 1] + 1) / 2);
  24.             cout << s.size() << "\n";
  25.             continue;
  26.         }
  27.         cout << s.size() + k << endl;
  28.     }
  29.     return 0;
  30. }

1496C. Diamond Miner

将坐标绝对值化存入数组排序

Codeforces Round #706 Editorial - 图3%5E2%20%2B(b%20-%20d)%5E2%7D%20%3D%20%5Csqrt%7Ba%5E2%20%2B%20d%5E2%7D#card=math&code=%5Csqrt%7B%28a-c%29%5E2%20%2B%28b%20-%20d%29%5E2%7D%20%3D%20%5Csqrt%7Ba%5E2%20%2B%20d%5E2%7D) 要想有最小化，只能大值匹配大值

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     int _ = 1;
  4.     for (cin >> _; _--;) {
  5.         int n;
  6.         cin >> n;
  7.         vector<int> xx, yy;
  8.         for (int i = 0; i < 2 * n; ++i) {
  9.             int x, y;
  10.             cin >> x >> y;
  11.             if (x == 0) yy.push_back(abs(y));
  12.             else
  13.                 xx.push_back((abs(x)));
  14.         }
  15.         sort(xx.begin(), xx.end());
  16.         sort(yy.begin(), yy.end());
  17.         double cnt = 0.0;
  18.         for (int i = 0; i < n; ++i) {
  19.             cnt += sqrt(1.0 * xx[i] * xx[i] + 1.0 * yy[i] * yy[i]);
  20.         }
  21.         cout << setprecision(15) << cnt << "\n";
  22.     }
  23.     return 0;
  24. }

1496D. Let’s Go Hiking

学习自 洛绫璃 dalao的思路

这是一道博弈题

由于只能存在一条最长链，否则先手站一条, 后手站一条, 先手必输

其次, 只有一条最长链, 先手和后手都会选在最长链上, 否则谁不在, 另一方直接获胜

在其 先手会在山峰, 否则后手直接卡死

故先手会选择在 最长链的最高端, 后手会选择最长链最远的地方, 保证和先手相隔 偶数个位置(保证两者都走最长链, 后手胜)

后手保证了先手最长链一定会输, 只能走最长链的反方向, 比较先手和后手能走的长度, 判断是否能先手赢

  1. const int N = 1e5 + 5;
  2. int t, n, maxn, ans, a[N], p1[N], p2[N];
  3. int main() {
  4.     scanf("%d", &n);
  5.     for (int i = 1; i <= n; i++) {
  6.         scanf("%d", a + i);
  7.         p1[i] = (a[i] <= a[i - 1] || i == 1) ? 0 : (p1[i - 1] + 1);
  8.         maxn = max(maxn, p1[i]);
  9.     }
  10.     for (int i = n; i >= 1; i--)
  11.         p2[i] = (a[i] <= a[i + 1] || i == n) ? 0 : (p2[i + 1] + 1),
  12.         maxn = max(p2[i], maxn);
  13.     for (int i = 1; i <= n; i++)
  14.         if (p1[i] == p2[i] && p1[i] == maxn && maxn > 0 && ((maxn & 1) == 0)) {
  15.             ans = i;
  16.             break;
  17.         }
  18.     for (int i = 1; i <= n; i++)
  19.         if (ans != i && (p1[i] == maxn || p2[i] == maxn)) {
  20.             ans = 0;
  21.             break;
  22.         }
  23.     printf("%d", ans ? 1 : 0);
  24. }