# [A.A-characteristic](https://codeforces.com/contest/1823/problem/A "## A.A-characteristic") 构造一个长度为 $n(1\le n \le 100)$ ，且由 $1$ 或 $-1$ 构成的数组 $a_i$ ,使得 - $1\le i < j \le n $ - $ a_i \cdot a_j = 1$ 的组数恰好为 $k$ 组 那就考虑 **1** 的个数和 **-1** 的个数 假设 **1** 的个数为 $a$ , **-1** 的个数为 $b$ 满足 $a + b = n$. 那么该数组满足条件的组数为$ x = a * (a - 1)/2 + b * (b-1) /2$ 我们只用枚举$a$后来检验$x$是否等于$k$即可 ```cpp void solve() { int n, k; cin >> n >> k; for (int i = 0; i <= n; i++) { int j = n - i; if (i * (i - 1) / 2 + (j - 1) * j / 2 == k) { cout << "YES\n"; for (int o = 1; o <= i; o++) { cout << 1 << ' '; } for (int o = 1; o <= j; o++) { cout << -1 << ' '; } cout << '\n'; return; } } cout << "NO\n"; } ``` ------------ # [B. Sort with Step](https://codeforces.com/contest/1823/problem/B "B. Sort with Step") **给你一个长度为 $n\ (1\le n \le 2\cdot 10 ^ 5)$ 的排列,每一次你只能交换下标距离为 $k$ 的两个数(你可以进行无限次该操作)，在一开始，你有一次机会去交换任意两个位置的数字，问最后是否可以得到递增数组？** ------------ 想法比较简单，只用根据下标模 $k(1\le k \le n)$ 去分开考虑即可，检查不满足条件的个数，如果没有不满足的就直接可行，如果不满足条件的个数为 $2$ ，则可以通过一次交换实现，其他情况则就不能实现。 ```cpp int A[N], In[N]; void solve() { int n, k; cin >> n >> k; for (int i = 1, x; i <= n; i++) { cin >> x; In[x] = i % k + 1; } int cnt = 0; for (int i = 1; i <= n; i++) { if (In[i] != i % k + 1) { cnt++; } } if (cnt == 0) { cout << 0 << '\n'; } else if (cnt <= 2) { cout << 1 << '\n'; } else { cout << -1 << '\n'; } } ``` ------------ # [C. Strongly Composite](https://codeforces.com/contest/1823/problem/C "C. Strongly Composite") **定义一个 $x$ 为一个强合数，若 $x$ 的所有因子中，素因子的数量小于等于合因子的数量。 给你一个长度为 $n \ (1\le n \le 10^3)$ 的数组 $a_i\ (1 < a_i \le 10^7)$ 。 现在需要你构造一个长度为 $k$ 的数组 $b_i$ 满足以下条件** - $\prod_{i=1}^{i=n}{a_i} = \prod_{i=1}^{i=k}{b_i}$ - $b_i (1\le i \le n)$ 为强合数 - $k$ 值最大 ------------ 经过手玩你会发现以下情况是最优秀的 - $ p^2 $ , 其中 $p$ 为任意素因子 但是有可能不全是以上情况，此时我们就需要用到3个素因子来完成即可。 - $ p_1 \cdot p_2 \cdot p_3 $ ```cpp int A[1010]; int pri[N], vis[N], cnt; void init() { for (int i = 2; i <= 10000; i++) { if (!vis[i]) pri[++cnt] = i; for (int j = 1; j <= cnt && pri[j] * i <= 10000; j++) { vis[i * pri[j]] = 1; if (i % pri[j] == 0)break; } } } map<int, int> mp; void solve() { mp.clear(); int n; cin >> n; for (int i = 1, x; i <= n; i++) { cin >> x; for (int j = 1; j <= cnt && pri[j] * pri[j] <= x; j++) { while (x % pri[j] == 0) { x /= pri[j]; mp[pri[j]]++; } } if (x > 1) mp[x]++; } int sum = 0; int tot = 0; for (auto [x, num]: mp) { sum += num & 1; tot += num / 2; } tot += sum / 3; cout << tot << '\n'; } ``` ------------ # [D. Unique Palindromes](https://codeforces.com/contest/1823/problem/D "D. Unique Palindromes") - 定义 $s[i] $ 为 字符串 $s$ 的前缀长度为 $i$ 的字符串 ，即 $s_1 + s_2 + \cdots + s_i$ - 定义 $f(A)$ 表示为字符串 $A$ 中本质不同回文子串的个数。 **需要你构造一个长度为 $n \ (1\le n \le 2 \cdot 10^5)$ 的字符串满足 $k \ (1\le k \le 20)$ 个限制条件** 每一个限制条件如下： - 给定一个 $x_i$ 和 $c_i$ , 表示 $f(s[x_i]) = c_i $ ------------ 首先我们容易发现 $ f(s[x]) \le x $ ,如果出现 $ f(s[x]) > x $ 直接结束。 每次添加一个字母，至多加一个新的本质不同回文字符串。 考虑对于单一一个字母来说，会发现很好的性质，如下例子： `ccc`到 `cccc` 多了一个字母的同时，恰好多了一个本质不同回文子串。 这样可以比较好的解决 $ f(s[x+1]) = f(s[x]) + 1 $ 的情况。 那么我们接下来要如何解决 $ f(s[x+1]) = f(s[x]) $ 的情况呢？ 就是说我们后面不能再一次构造出回文子串了。 我们根据一些特殊情况分析 ， `abc` 是当前的字符串，那么我们可以将 `abc`这个字符串按照固定的顺序不断拼接上去，最终形成类似于 `abcabcabc`的串，你会发现他的本质不同回文子串个数依旧是 $3$ 又恰好考虑到 $ k \le 20 $,于是我们会发现对于每一次限制，我们可以添加一个新的小写字母作为我们需要的新字母来实现 $ f(s[x+1]) = f(s[x]) + 1 $ 的情况，而$ f(s[x+1]) = f(s[x]) $ 的情况则用 `abc`循环替代即可。 最终构造出来的字符串会形如 `abcdddaeebfffcabggg` ```cpp int x[30], c[30]; char s[N]; void solve() { int n, k; cin >> n >> k; for (int i = 1; i <= k; i++) cin >> x[i]; for (int i = 1; i <= k; i++) cin >> c[i]; for (int i = 1; i <= k; i++) { if (c[i] > x[i]) { cout << "NO\n"; return; } c[i] = x[i] - c[i]; } for (int i = 1; i < k; i++) { if (c[i] > c[i + 1]) { cout << "NO\n"; return; } } for (int i = 1; i <= 3; i++) s[i] = 'a' + i - 1; int now = 0, p = 3; char id = 'd'; char op = 'a'; for (int i = 1; i <= k; i++, id++) { int cnt = c[i] - now; now = c[i]; while (cnt--) { if (op == 'a') { s[++p] = 'a'; op = 'b'; } else if (op == 'b') { s[++p] = 'b'; op = 'c'; } else { s[++p] = 'c'; op = 'a'; } } while (p < x[i]) { s[++p] = id; } } cout << "YES\n"; for (int i = 1; i <= n; i++) { cout << s[i]; } cout << "\n"; } ```