Contestant. Rank 1585. Rating +7.
A. A-characteristic
题意
给定一个由 \(±1\) 组成的数组 \(a\)，定义特征 \(A\) 为数组 \(a\) 中满足 \(a \leq i < j \leq n\) 且 \(a_i \cdot a_j = 1\) 的个数。
给定个数，构造这个数组。
思路
直接暴力枚举 \(-1\) 的个数，因为可以无视顺序，我们直接在输出 \(-1\) 后剩下的全填上 \(1\) 即可。
因为 \((-1) \cdot (-1) = 1, 1 \cdot 1 = 1\)，所以我们不妨初始化 \(p\) 数组，其中 \(p_i = p_{i - 1} + i - 1\)，那么 \(p_i + p_{n - i} = k\) 时就找到了答案。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
vector<int> p(110);
for(int i=2;i<=100;i++) p[i] = p[i - 1] + i - 1;
for(int i=0;i<=n;i++){
if(p[i] + p[n - i] == k){
cout << "YES\n";
for(int x=1;x<=i;x++) cout << "-1 ";
for(int x=i;x<n;x++) cout << "1 ";
cout << '\n';
return;
}
}
cout << "NO\n";
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}傻逼（指出题
B. Sort with Step
题意
给定一个 排列 以及整数 \(k\)，规定 \(a_i\) 可以和 \(a_{i + k}\) 交换。
如果在若干次交换后可以让排列升序，那么输出 \(0\)；
否则，如果在交换之前可以任选两个数交换一次，该条件下可以让排列升序，那么输出 \(1\)；
否则，输出 \(-1\)。
思路
首先，既然这是一个排列，那么如果可以升序，一定满足 \(a_i \bmod k = i \bmod k\)。
那么，我们直接统计不满足该条件的个数，如果为 \(0\)，输出 \(0\)；如果为 \(2\)，输出 \(1\)，否则输出 \(-1\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
int f = 0;
for(int i=1;i<=n;i++) {
cin >> a[i];
if(a[i] % k != i % k) f ++;
}
if(f == 0) {
cout << 0 << '\n';
}else if(f == 2){
cout << 1 << '\n';
}else cout << -1 << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}如果不是排列那我就似了
C. Strongly Composite
题意
对于一个合数，如果它的所有因子满足质数的个数小于等于合数的个数，那么定义该数为强合数。
现在，给定一个序列 \(a\)，构造一个序列 \(b\)，并输出它的长度：
\(a_1 \cdot a_2 \cdot \ldots \cdot a_n = b_1 \cdot b_2 \cdot \ldots \cdot b_m\)；
\(b\) 中所有数都是强合数；
\(b\) 的长度尽可能最大
思路
首先，我们不妨分解质因数，并统计所有质因数的个数。
因为两个相同的质数相乘后，我们会得到一个因子满足质数个数为 \(1\) 且合数个数也为 \(1\) 的强合数，所以我们在统计之后枚举所有个数 \(cnt_p\)，统计 \(\lfloor \frac{cnt_p}{2} \rfloor\) 的总和，作为答案的一部分。
对于剩余的数的集合，不难发现没有重复数字，而三个不同的质数相乘后，我们会得到一个因子满足质数个数为 \(3\) 且合数个数为 \(4\) 的强合数，此时对于剩余的数的个数 \(sum\)，\(\lfloor \frac{sum}{3} \rfloor\) 就是答案的另一部分。
因此，\(ans = \sum \lfloor \frac{cnt_p}{2} \rfloor + \lfloor \frac{sum}{3} \rfloor\)。
当然，对于分解质因数，我们可以用线性筛。
时间复杂度：不大
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 1e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
vector<int> pri;
vector<bool> vis(N);
void init(int n) {
for (int i = 2; i <= n; ++i) {
if (!vis[i]) pri.emplace_back(i);
for (auto j : pri) {
if (i * j > n) break;
vis[i * j] = true;
if (i % j == 0) break;
}
}
}
void solve() {
int n;
cin >> n;
map<int, int> cnt;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
for (auto x : pri) {
if (cur % x == 0) {
while (cur % x == 0) cur /= x, cnt[x] ++;
}
}
if (cur != 1) {
cnt[cur] ++;
}
}
int ans = 0, sum = 0;
for(auto e : cnt){
ans += e.sc / 2;
sum += e.sc % 2;
}
cout << sum / 3 + ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
init(1e5);
int t = 1;
cin >> t;
while(t --) solve();
}有点水，但又有点不水（x
D. Unique Palindromes
题意
对于一个至少有三个字符的字符串 \(s\)，定义 \(p(s, m)\) 为 \(s\) 的前 \(m\) 个字符的所有连续子串中 不同回文串 的个数。
现在，给定最多 \(20\) 个限制，一条限制包括 \(m_i\) 和 \(p(s, m_i)\) 的值，输出满足限制的一个字符串。
思路
首先，题目说了回文串不同才计数，那么对于 \(n\) 个连续相同的子串，就有 \(n\) 个不同的回文串（如 \(a, aa, aaa, aaaa, \dots\)）。
很有趣，题目给了限制的最大个数，这让我们不难联想到字母表的个数，\(20 < 26\)。
那么，对于两个相邻的限制，我们可以求出多出的回文串的个数，并填上连续的对应个数的字符。我们不妨从 \(d\) 开始，第一个限制我们都放 \(d\)，第二个限制我们都放 \(e\)，以此类推，字母表是够我们用的。
那么空出来的地方，我们就一定得保证不会多出来回文串了。
可以很简单的观察到，我们只要循环放 \(abc\) 即可，如 \(\color{rgb(149,117,205)}{a}\color{rgb(124,179,66)}{b}\color{rgb(0,172,193)}{c}\)\(dd\)\(\color{rgb(149,117,205)}{a}\color{rgb(124,179,66)}{b}\)\(eee\)\(\color{rgb(0,172,193)}{c}\color{rgb(149,117,205)}{a}\color{rgb(124,179,66)}{b}\)\(ff\)，这样就可以满足我们的需求了。
这样，只要每次多出来的回文数的个数大于等于空出来的位置，我们都可以完成构造。
当然，如果空间不够了，其实可以证明一定无解，这边不给出证明。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, k;
cin >> n >> k;
vector<int> x(k + 2), c(k + 2);
for(int i=1;i<=k;i++) cin >> x[i];
for(int i=1;i<=k;i++) cin >> c[i];
x[++ k] = n, c[k] = c[k - 1];
int pre = 0;
for(int i=1;i<=k;i++){
if(x[i] - c[i] < pre){
cout << "NO\n";
return;
}
pre = x[i] - c[i];
}
string ans = "abc";
int now = 0;
c[0] = 3;
for(int i=1;i<=k;i++){
for(int j=1;j<=c[i]-c[i-1];j++) ans += (char) ('c' + i);
int l = ans.size();
for(int j=1;j<=x[i]-l;j++) ans += (char) ('a' + (now ++ % 3));
}
cout << "YES\n" << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}其实是不会证（x