CF370 C. Memory and De-Evolution


给你两个整数 x 和 y，满足 3 <= y < x <= 1e5。
从边长为 x 的等边三角形出发，每次操作你可以将其中一条边的长度修改为某个整数，要求修改后的三条边仍能组成一个三角形。
将三角形修改成边长为 y 的等边三角形，最少需要操作多少次？

思路：
正难则反，考虑如何将边长为y的等边三角形变为三条边都大于等于x的三角形。

CF723 C.Polycarp at the Radio

给你一个数组 a，长度不超过 2000，元素值在 [1,1e9]。另外还给你一个数 m (1<=m<=n)。
每次修改操作你可以将某个 a[i] 修改为任意数字。
定义 count(v) 表示 v 在 a 中的出现次数。
请你修改 a，最大化 min(count(v)), v in [1,m]，即最大化 count(1), count(2), …, count(m) 的最小值。
按顺序输出：最大化的结果、最小修改次数、修改之后的 a。

思路：
将x > m以及c > n / m的数都转换成缺少的数
注意：

  1. 7 3
  2. 1 1 2 2 3 4 5

这组测试用例需要将1或2转成6

  1. 5 4
  2. 3 1 495987801 522279660 762868488

这组测试用例只需要将两个数分别转换成2，4即可

问题：
如何使代码更简洁？

CF546 D. Nastya Is Buying Lunch


给你整数 n(<=3e5) 和 m(<=5e5) 表示有 n 个编号从 1 到 n 的人，m 对交换信息。
然后给你一个 1 到 n 的排列 a，表示这 n 个人从左到右排成一队。
然后给你 m 个互不相同的对 (x,y)，表示若 x 和 y相邻且 x 在 y 左侧，则 x 可以和 y 交换位置。
输出队尾那个人最多可以向左移动多远（他到队尾的距离）。

思路：
反向思考，考虑谁可以向右移动到最后一个人的右边
这个人满足的条件是他可以通过移动跨过最后一个人到他之间的所有人。
故考虑用一个集和维护这段区间的左边可以有哪些值

  1. static final int N = 300010, M = 500010;
  2. static int[] a = new int[N];
  3. static int n, m;
  4. static void solve() {
  5.     n = ni();
  6.     m = ni();
  7.     Map<Integer, Set<Integer>> map = new HashMap<>();
  8.     for (int i = 1; i <= n; i++)
  9.         a[i] = ni();
  11.     for (int i = 0; i < m; i++) {
  12.         int x = ni(), y = ni();
  13.         map.computeIfAbsent(y, key -> new HashSet<>()).add(x);
  14.     }
  17.     Set<Integer> set = new HashSet<>();
  18.     var t = map.getOrDefault(a[n], null);
  19.     if (t != null)
  20.         set.addAll(t);
  21.     int cnt = 0;
  22.     for (int i = n - 1; i > 0; i--) {
  23.         if (set.contains(a[i])) {
  24.             cnt++;
  25.             continue;
  26.         }
  27.         t = map.getOrDefault(a[i], null);
  28.         if (t == null) break;
  29.         var iterator = set.iterator();
  30.         while (iterator.hasNext()) {
  31.             int x = iterator.next();
  32.             if (!t.contains(x))
  33.                 iterator.remove();
  34.         }
  35.     }
  37.     out.println(cnt);
  38. }

CF 508 D. Slime

给你一个 n(1<=n<=5e5) 和一个长为 n 的数组 a（-1e9<=a[i]<=1e9)，表示有 n 个卡比排成一排，每个卡比有个分数 a[i]。
每次你可以选择一个卡比，让它吃掉它左边或者右边的一个相邻的卡比，吃完后它的分数要减掉所吃的卡比的分数。
如此操作 n-1 次后，最后剩下的那只卡比的分数的最大值是多少？

思路：
从特殊到一般
先考虑全正，再考虑全负，再考虑正负均有的情况
注意特判长度为1的数组

  1. static int N = 500010;
  2. static int[] a = new int[N];
  3. static int n;
  4. static void solve() {
  5.     n = ni();
  6.     int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
  7.     int maxIdx = -1, minIdx = -1;
  9.     for (int i = 1; i <= n; i++)
  10.         a[i] = ni();
  12.     for (int i = 1; i <= n; i++) {
  13.         if (a[i] > max) {
  14.             max = a[i];
  15.             maxIdx = i;
  16.         }
  17.         if (a[i] <= min) {
  18.             min = a[i];
  19.             minIdx = i;
  20.         }
  21.     }
  23.     if (n == 1)
  24.         out.println(a[1]);
  25.     else {
  26.         long sum = max - min;
  27.         a[maxIdx] = a[minIdx] = 0;
  28.         for (int i = 1; i <= n; i++)
  29.             sum += Math.abs(a[i]);
  30.         out.println(sum);
  31.     }
  33. }

CF 505 C. Plasticine zebra

给你一个字符串 s，仅包含 ‘b’ 和 ‘w’，长度不超过 1e5。

每次操作你可以任意选择一个位置 k，把字符串分为长为 k 的前缀和长为 len(s)-k 的后缀，反转前缀和后缀，再重新拼起来，得到一个新字符串代替原来的 s。（用 Python 来说就是s = s[:k][::-1] + s[k:][::-1]）
k 可以为 0，即翻转整个 s。

你可以操作任意多次。请输出你能得到的最长 bw 交替子串（形如 bwbwbw… 或 wbwbwb…）的长度。

思路：
如果将首尾相连，任意切断后的字符串就是满足题意的字符串，所以是一个破环成链求最大值的过程。

  2. import java.util.Scanner;
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         Scanner sc = new Scanner(System.in);
  7.         String s = sc.next();
  8.         char[] ch = (s + s).toCharArray();
  9.         int n = s.length();
  11.         char pre = 'a';
  12.         int cnt = 0;
  13.         int max = 0;
  14.         for (int i = 0; i < 2 * n; i++) {
  15.             if (ch[i] != pre) {
  16.                 cnt++;
  17.                 pre = ch[i];
  18.             } else {
  19.                 cnt = 1;
  20.                 pre = ch[i];
  21.             }
  22.             max = Math.max(max, cnt);
  23.         }
  24.         System.out.println(Math.min(max, n));
  25.     }
  26. }

CF 1519 D. Maximum Sum of Products

输入 n(≤5000) 和两个长为 n 的整数数组 a 和 b，元素值均在 [1,1e7] 中。
你可以至多反转一次 a 的某个子数组，求 sum(a[i]b[i]) 的最大值（即最大化 a[0]b[0]+a[1]b[1]+…+a[n-1]b[n-1]）。

思路：
暴力枚举的方法是O(n3)
如何减少一维复杂度？
考虑枚举方式，如果是从子数组左边遍历到右边无法处理，考虑从中间向两边枚举，最中间要么是一个数，要么是两个数，找到最大值即可。

  1. static final int N = 5010;
  2. static int[] a = new int[N], b = new int[N];
  3. static int n;
  4. static void solve() {
  5.     n = ni();
  6.     for (int i = 1; i <= n; i++) a[i] = ni();
  7.     for (int i = 1; i <= n; i++) b[i] = ni();
  9.     long s = 0;
  10.     for (int i = 1; i <= n; i++) s += 1L * a[i] * b[i];
  12.     //单
  13.     long max = 0;
  14.     for (int i = 1; i <= n; i++) {
  15.         int l = i - 1, r = i + 1;
  16.         long minus = 0;
  17.         while (l >= 1 && r <= n) {
  18.             minus += (a[r] - a[l]) * (1L * b[l]) + (a[l] - a[r]) * (1L * b[r]);
  19.             max = Math.max(max, minus);
  20.             l--;
  21.             r++;
  22.         }
  23.     }
  24.     //双
  25.     for (int i = 1; i < n; i++) {
  26.         int l = i, r = i + 1;
  27.         long minus = 0;
  28.         while (l >= 1 && r <= n) {
  29.             minus += (a[r] - a[l]) * (1L * b[l]) + (a[l] - a[r]) * (1L * b[r]);
  30.             max = Math.max(max, minus);
  31.             l--;
  32.             r++;
  33.         }
  34.     }
  36.     out.println(s + max);
  37. }

CF 1368 D. AND, OR and square sum

输入 n(≤2e5) 和一个长为 n 的整数数组 a (0≤a[i]<2^20)。每次操作，你可以选择两个数 a[i] 和 a[j]，分别记作 x 和 y，然后更新 a[i] = x AND y, a[j] = x OR y。AND 表示按位与，OR 表示按位或。你可以执行该操作任意次。输出 sum(a[i]a[i]) 的最大值，即 a[0]a[0] + a[1]a[1] + … + a[n-1]a[n-1] 的最大值。

输入
1
123
输出 15129
解释 123*123=15129。

输入
3
1 3 5
输出 51
解释 把 3 和 5 修改成 1 和 7，得到 [1,1,7]，答案为 11+11+7*7 = 51。

输入
2
349525 699050
输出 1099509530625

思路：
x, y = x & y, x^y
不会改变总1的个数
根据不等式思维题 - 图1
故1越集中结果越大

  1. static final int N = 200010;
  2. static int[] c = new int[20];
  3. static int n;
  4. static void solve() {
  5.     n = ni();
  6.     for (int i = 1; i <= n; i++) {
  7.         int x = ni();
  8.         int v = 0;
  9.         for (int j = 0; j < 20; j++)
  10.             c[j] += x >> j & 1;
  11.     }
  13.     long res = 0;
  14.     for (int i = 0; i < N; i++) {
  15.         long x = 0;
  16.         for (int j = 0; j < 20; j++) {
  17.             if (c[j] > 0) {
  18.                 c[j]--;
  19.                 x |= 1 << j;
  20.             }
  21.         }
  22.         res += x * x;
  23.         if (x == 0) break;
  24.     }
  25.     out.println(res);
  26. }