比赛链接：
https://ac.nowcoder.com/acm/contest/33192
C.Constructive Problems Never Die
题意：
已知序列 \(a\)，找出一个排列 \(p\) 使得 \(a_i != p_i(1 <= i <= n)\)。
思路：
赛时思路。根据序列 \(a\) 中每一个数出现的次数来放置 \(p\)。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
LL n;
cin >> n;
vector < pair<LL, LL> > a(n + 1);
vector <LL> cnt(n + 1);
for (int i = 1; i <= n; i ++ ){
cin >> a[i].first;
a[i].second = i;
cnt[a[i].first] ++ ;
}
priority_queue < pair<LL, LL>, vector< pair<LL, LL> >, less< pair<LL, LL> > > q;
for (int i = 1; i <= n; i ++ ){
q.push({cnt[i], i});
}
auto cmp = [&](pair<LL, LL> x, pair<LL, LL> y){
return cnt[x.first] > cnt[y.first];
};
sort(a.begin() + 1, a.end(), cmp);
vector < pair<LL, LL> > ans(n + 1);
for (int i = 1; i <= n; i ++ )
ans[i].second = a[i].second;
for (int i = 1; i <= n; i ++ ){
if (a[i].first != q.top().second){
ans[i].first = q.top().second;
q.pop();
}
else{
auto t = q.top();
q.pop();
if (q.empty()){
if(i == n && n > 1){ //特判最后一个数相同的情况
ans[i].first = t.second;
if (ans[n - 1].first != a[n].first && ans[n].first != a[n - 1].first){
swap(ans[n - 1].first, ans[n].first);
break;
}
}
cout << "NO\n";
return;
}
auto x = q.top();
q.pop();
ans[i].first = x.second;
q.push(t);
}
}
auto cmp1 = [&](pair<LL, LL> x, pair<LL, LL> y){
return x.second < y.second;
};
sort(ans.begin() + 1, ans.end(), cmp1);
cout << "YES\n";
for (int i = 1; i <= n; i ++ )
cout << ans[i].first << " \n"[i == n];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
直接放置，然后判断最后一个是不是相同即可。
#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
LL n;
cin >> n;
vector <LL> a(n);
for (int i = 0; i < n; i ++ )
cin >> a[i];
bool same = true;
for (int i = 1; i < n; i ++ )
if (a[i] != a[i - 1]){
same = false;
break;
}
if (same){
cout << "NO\n";
return;
}
LL L = 1, R = n;
vector <LL> p(n);
for (int i = 0; i < n; i ++ ){
if (a[i] != L) p[i] = L ++ ;
else p[i] = R -- ;
}
if (a[n - 1] == p[n - 1]){
for (int i = 0; i < n; i ++ ){
if (a[i] != p[n - 1]){
swap(p[i], p[n - 1]);
break;
}
}
}
cout << "YES\n";
for (int i = 0; i < n; i ++ )
cout << p[i] << " \n"[i == n - 1];
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
F.Candies
题意：
给定一个序列 \(a\)，当 \(a_i = a_{i + 1} or a_i + a_{i + 1} = x\) 时，可以删除 \(a_i\) 和 \(a_{i + 1}\)，问最多能删除多少对，序列是一个环。
思路：
通过 vector 模拟即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n, x;
cin >> n >> x;
LL ans = 0, t;
vector <LL> a;
for (int i = 0; i < n; i ++ ){
cin >> t;
if (!a.empty() && (a.back() == t || a.back() + t == x)){
a.pop_back();
ans ++ ;
}
else{
a.push_back(t);
}
}
for (int L = 0, R = a.size() - 1; L < R; L ++ , R -- ){
if (a[L] == a[R] || a[L] + a[R] == x) ans ++ ;
else break;
}
cout << ans << "\n";
return 0;
}
G.Regular Expression
题意：
给定一个字符串，问表示该字符串的最短正则表达式为多长，以及该长度的正则表达式有几种。
思路：
长度只可能为 1 或者 2。
当字符串长度为 1 的时候，可以用该字母和 '.' 来表示，即输出 "1 2"。
当字符串长度为 2 的时候。
如果相同，则有八种，"xx", "x.", "x+", "x", ".+", ".", "..", ".x"。
不同的话，只有六种，"x+" 和 "x*" 不行。
如果长度大于 2。
当所有字母相同，有四种，"x+", "x", ".", ".+"。
有不同，只有两种，"x+" 和 "x*" 不行。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
void solve(){
string s;
cin >> s;
LL n = s.size();
if (n == 1){
cout << "1 2\n";
}
else if (n == 2){
if (s[0] == s[1]) cout << "2 8\n";
else cout << "2 6\n";
}
else{
bool same = true;
for (int i = 1; i < n; i ++ ){
if (s[i] != s[i - 1]){
same = false;
break;
}
}
if (same) cout << "2 4\n";
else cout << "2 2\n";
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL T = 1;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
J.Melborp Elcissalc
题意：
一个数如果是 \(k\) 的倍数，则它是 \(good\) 数。
对于一个每个数都在 \([0, k - 1]\) 范围中的数组，它的 \(goodness\) 被定义为该数组中连续子段和为 \(good\) 数的数量。
现已知数组长度为 \(n\)，求 \(gooodness\) 为 \(t\) 的数组的数量。
思路：
直接求不好求，考虑原数组的前缀和数组 \(sum\)，\(sum_i = (sum_{i - 1} + a_i)\) % \(k\)。
当 \(sum_i - sum_{j - 1} = 0\) 的时候，\([j, i]\) 这一段的和就是 \(good\) 数。
定义 \(dp[i][j][p]\) 表示在 \([0, i]\) 的范围中，选择了 \(j\) 个数，组成 \(goodness\) 为 \(t\) 的数组的数量。
得到转移方程 \(dp[i][j][p] = \sum_{q = 0}^{j} dp[i - 1][j - q][p - C_{q}^{2}] C_{n - (j - q)}^{q}\)。
\(C_{a}^{b}\) 可以通过逆元递推或者杨辉三角求。
代码：
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 110, M = 2110, P = 998244353;
LL dp[N][N][M], C[N][N];
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n, k, t;
cin >> n >> k >> t;
for (int i = 0; i <= 100; i ++ )
for (int j = 0; j <= i; j ++ ){
if (!j) C[i][j] = 1;
else C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % P;
}
for (int j = 0; j <= n; j ++ )
dp[0][j][C[j + 1][2]] = 1;
for (int i = 1; i < k; i ++ )
for (int j = 0; j <= n; j ++ )
for (int p = 0; p <= t; p ++ )
for (int q = 0; q + j <= n; q ++ )
dp[i][j + q][p + C[q][2]] = (dp[i][j + q][p + C[q][2]] + dp[i - 1][j][p] * C[j + q][q]) % P;
cout << dp[k - 1][n][t];
return 0;
}