CF 474 C.Subsequence Counting

https://codeforces.com/problemset/problem/960/C
题目描述：
给你两个数 x 和 d，范围在 [1,1e9] 内。定义一个非空子序列 b 是好的，需满足 max(b)-min(b) < d请你构造任意一个满足要求的整数数组 a，要求 a 的长度不超过 1e4，a[i] 均在 [1,1e18] 范围内，且满足：a 恰好有 x 个非空好子序列。（子序列不要求是连续的）
如果无法构造，输出 -1；否则输出 a 的长度和 a 的元素。

思路：分成互不相干的多组数即可

  1. static void solve() {
  2.         int n = ni(), d = ni();
  3.         long x = 1;
  5.         List<long[]> res = new ArrayList<>(100);
  6.         int cnt = 0;
  8.         while (n > 0) {
  9.             int c = (int)(Math.log(n) / Math.log(2));
  10.             if (c == 0) {
  11.                 res.add(new long[]{1, x});
  12.                 cnt++;
  13.                 break;
  14.             }
  15.             n = n - (int)(Math.pow(2, c)) + 1;
  16.             res.add(new long[]{c, x});
  17.             x += d;
  18.             cnt += c;
  19.         }
  21.         out.println(cnt);
  22.         for (long[] p : res) {
  23.             while (p[0] -- > 0)
  24.                 out.print(p[1] + " ");
  25.         }
  26.     }

CF 469 A. Zebras

https://codeforces.com/problemset/problem/949/A

给你一个只包含 01 的字符串 s，长度不超过 2e5。

请你将 s 拆分成若干个子序列（子序列不要求连续），使得每个子序列都是长度为奇数的，从 0 开始的 01 交替串，例如 0 010 01010 等等

如果无法拆分，输出 -1；否则输出组成这些子序列的下标数组（从 1 开始）。可以输出任意一种符合要求的解。

思路：
分奇偶顺序模拟
无解情况：
最终存在偶数串
存在起始为1的串

  2.     static void solve() {
  3.         String s = ns();
  4.         Deque<List<Integer>> even = new ArrayDeque<>(), odd = new ArrayDeque<>();
  5.         boolean flag = true;
  6.         for (int i = 0; i < s.length(); i++) {
  7.             if (s.charAt(i) == '0') {
  8.                 List<Integer> t = even.isEmpty() ? new ArrayList<>() : even.pop();
  9.                 t.add(i + 1);
  10.                 odd.push(t);
  11.             } else {
  12.                 if (odd.isEmpty()) {
  13.                     flag = false;
  14.                     break;
  15.                 }
  16.                 List<Integer> t = odd.pop();
  17.                 t.add(i + 1);
  18.                 even.push(t);
  19.             }
  20.         }
  22.         if (!flag || !even.isEmpty()) {
  23.             out.println(-1);
  24.             return;
  25.         }
  27.         out.println(odd.size());
  28.         while (!odd.isEmpty()) {
  29.             var t = odd.pop();
  30.             out.print(t.size() + " ");
  31.             for (int x : t)
  32.                 out.print(x + " ");
  33.             out.println();
  34.         }
  35.     }

CF 540 E. Yet Another Ball Problem

https://codeforces.com/problemset/problem/1118/E

给你两个数 m 和 n（均在 [2,2e5] 范围内）
请你构造 m 个互不相同的 pair，需满足：
1. 每个 pair 包含两个在 [1,n] 内的不同整数。
2. 两个相邻的 pair，第一个数不能相同，第二个数也不能相同。
如果不能构造，输出 NO，否则输出 YES 和这 m 个 pair

思路：
见代码

  1. import java.util.*;
  3. public class Main {
  4.     public static void main(String[] args) {
  5.         Scanner sc = new Scanner(System.in);
  6.         int m = sc.nextInt(), n = sc.nextInt();
  7.         long can = 1L * n * (n - 1);
  8.         if (can < m) {
  9.             System.out.println("NO");
  10.         } else {
  11.             System.out.println("YES");
  12.             label: for (int i = 1; i <= n; i++) {
  13.                 for (int j = i + 1; j <= n; j++) {
  14.                     System.out.println(i + " " + j);
  15.                     if (--m == 0)
  16.                         break label;
  17.                     System.out.println(j + " " + i);
  18.                     if (--m == 0)
  19.                         break label;
  20.                 }
  21.             }
  22.         }
  23.     }
  24. }

CF 1092 C. Prefixes and Suffixes


给你一个整数 n(2<=n<=100) 和 2n-2 个字符串，这 2n-2 个字符串恰好是某个未知的字符串的所有真前缀和真后缀，即长度从1 到 n-1的字符串各有两个。
请按输入顺序回答每个字符串是前缀还是后缀，前缀输出 ‘P’，后缀输出 ‘S’，如果答案不止一种，回答任意一种即可。
字符串均由小写字母组成。

思路：
假设长度为n - 1的串为p, q则原串s = p + q[-1] || q + p[-1]
分别考虑这两种情况哪个符合
时间复杂度：O(n3)

  1. static int N = 110;
  2. static String[] o = new String[2 * N];
  3. static char[] res = new char[2 * N];
  4. static String[][] a = new String[N][2];
  5. static int[][] b = new int[N][2];
  6. static int n;
  7. static void solve() {
  8.     n = ni();
  9.     for (int i = 0; i < 2 * n - 2; i++) {
  10.         String s = ns();
  11.         o[i] = s;
  12.         int len = s.length();
  13.         if (a[len][0] == null) {
  14.             a[len][0] = s;
  15.             b[len][0] = i;
  16.         }
  17.         else {
  18.             a[len][1] = s;
  19.             b[len][1] = i;
  20.         }
  21.     }
  23.     String s1 = a[n - 1][0] + a[n - 1][1].charAt(n - 2);
  24.     String s2 = a[n - 1][1] + a[n - 1][0].charAt(n - 2);
  27.     if (!check(s1)) check(s2);
  28.     for (int i = 0; i < 2 * n - 2; i++) {
  29.         out.print(res[i]);
  30.     }
  31. }
  33. static boolean check(String s) {
  34.     for (int i = 1; i < n; i++) {
  35.         String x = a[i][0], y = a[i][1];
  36.         String p = s.substring(0, i), q = s.substring(n - i, n);
  37.         if (x.equals(p) && y.equals(q)) {
  38.             res[b[i][0]] = 'P';
  39.             res[b[i][1]] = 'S';
  40.         } else if (x.equals(q) && y.equals(p)) {
  41.             res[b[i][1]] = 'P';
  42.             res[b[i][0]] = 'S';
  43.         } else {
  44.             return false;
  45.         }
  46.     }
  47.     return true;
  48. }

CF 439 C. Devu and Partitioning of the Array
【易错题】
输入整数 n, k(1<=k<=n<=1e5) 和 p(0<=p<=k)，以及 n 个不同的整数表示数组 a（1<=a[i]<=1e9)。

请你将 a 分割为 k 个子序列（子序列不要求连续），使得恰好有 p 个子序列的和均为偶数，k-p 个子序列的和均为奇数。

若不能分割，输出 “NO”；否则输出 “YES” 和 k 行，每行第一个数表示子序列的大小，然后是子序列的数。
输出任意一种合法方案，输出的顺序与输入的顺序无关。

思路：
设k - p = q
设数组中偶数个数为e, 奇数个数为o
需满足o >= q && (o - q) % 2 == 0 && e + (o - q) / 2 >= p
如何快速构造？
若p > 0最后一组偶数特殊考虑，否则，最后一组奇数特殊考虑
先给奇数分配，再给偶数分配(哪种能选就选哪种（要么单独一个偶数，要么两个奇数）)
剩余数字一组即可

  1. static final int N = 100010;
  2.     static Queue<Integer>[] num = new LinkedList[2];
  3.     static int n, p, q;
  4.     static void solve() {
  5.         n = ni();
  6.         int all = ni();
  7.         p = ni();
  8.         q = all - p;
  10.         for (int i = 0; i < 2; i++)
  11.             num[i] = new LinkedList<>();
  13.         for (int i = 0; i < n; i++) {
  14.             int x = ni();
  15.             num[x & 1].offer(x);
  16.         }
  18.         int e = num[0].size(), o = num[1].size();
  19.         if (o < q || (o - q) % 2 != 0 || (o - q) / 2 + e < p) {
  20.             out.println("NO");
  21.             return;
  22.         }
  24.         out.println("YES");
  25.         if (p == 0) q--;
  26.         for (int i = 0; i < q; i++)
  27.             out.println(1 + " " + num[1].poll());
  28.         while (p-- > 1) {
  29.             if (!num[0].isEmpty()) {
  30.                 out.println(1 + " " + num[0].poll());
  31.             } else {
  32.                 out.println(2 + " " + num[1].poll() + " " + num[1].poll());
  33.             }
  34.         }
  36.         out.print(num[0].size() + num[1].size() + " ");
  37.         while (!num[0].isEmpty())
  38.             out.print(num[0].poll() + " ");
  39.         while (!num[1].isEmpty())
  40.             out.print(num[1].poll() + " ");
  41.     }

CF 1032 C. Playing Piano

输入 n (≤1e5) 和一个长为 n 的数组 a (1≤a[i]≤2e5)。
构造一个长为 n 的数组 b，满足：
1. 1≤b[i]≤5；
2. 如果 a[i]3. 如果 a[i]>a[i+1]，则 b[i]>b[i+1]；
4. 如果 a[i]=a[i+1]，则 b[i]≠b[i+1]；

如果不存在这样的 b 则输出 -1，否则输出任意一个满足要求的 b。

思路：
https://www.luogu.com.cn/blog/endlesscheng/solution-cf1032c
贪心构造，代码不好写

  1. static int N = 100010;
  2. static int[] a = new int[N];
  3. static int[] f = new int[N];
  4. static int n;
  5. static void solve() {
  6.     n = ni();
  8.     for (int i = 1; i <= n; i++)
  9.         a[i] = ni();
  10.     if (n == 1) {
  11.         out.println(1);
  12.         return;
  13.     }
  15.     int d = a[2] > a[1] ? 1 : (a[2] < a[1] ? -1 : 0);
  16.     f[1] = d >= 0 ? 1 : 5;
  17.     boolean flag = true;
  18.     for (int i = 2; i <= n; i++) {
  19.         if (a[i] > a[i - 1]) {
  20.             if (i > 2 && a[i - 1] <= a[i - 2]) {
  21.                 f[i - 1] = 1;
  22.                 if (f[i - 2] == 1)
  23.                     f[i - 1] = 2;
  24.             }
  25.             f[i] = f[i - 1] + 1;
  26.         } else if (a[i] < a[i - 1]) {
  27.             if (i > 2 && a[i - 1] >= a[i - 2]) {
  28.                 f[i - 1] = 5;
  29.                 if (f[i - 2] == 5)
  30.                     f[i - 1] = 4;
  31.             }
  32.             f[i] = f[i - 1] - 1;
  33.         } else {
  34.             f[i] = (f[i - 1] - 1) % 3 + 2;
  35.         }
  37.         if (f[i] < 1 || f[i] > 5) {
  38.             flag = false;
  39.             break;
  40.         }
  41.     }
  43.     if (!flag) out.println(-1);
  44.     else {
  45.         for (int i = 1; i <= n; i++)
  46.             out.print(f[i] + " ");
  47.     }
  48. }