Codeforces Round 972（Div.2）题解
A. Simple Palindrome 贪心
贪心，尽可能元素数量平均，并且相同字母放在一起。
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;
void Showball(){
int n;
cin>>n;
const string a="aeiou";
int t=n/5;
vector<int> cnt(5,t);
for(int i=0;i<5;i++) if(i<n%5) cnt[i]++;
for(int i=0;i<5;i++){
while(cnt[i]--) cout<<a[i];
}
cout<<endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T=1;
if(cases) cin>>T;
while(T--)
Showball();
return 0;
}
B2. The Strict Teacher (Hard Version) 二分+贪心
首先，答案只和 \(David\) 相邻的老师有关，因此二分一下找到相邻的老师，两端的情况，直接做差即可。
中间的情况，因为两个老师同时向中间逼近，显然答案就是距离差值的一半。
void Showball(){
int n,m,q;
cin>>n>>m>>q;
vector<int> b(m);
for(int i=0;i<m;i++) cin>>b[i];
sort(all(b));
while(q--){
int x;
cin>>x;
auto p=lower_bound(all(b),x);
if(p==b.end()){
cout<<n-b[m-1]<<endl;
continue;
}
if(p==b.begin()){
cout<<b[0]-1<<endl;
continue;
}
cout<<(*p-*(p-1))/2<<endl;
}
}
C. Lazy Narek DP
首先考虑贪心，显然不行，因为两段字符串拼接到一起可以组成一段 \(narek\) 使得答案更优。
考虑 \(DP\), 为了和前面一段拼接，所以状态里要描述匹配到哪个字符。
不妨，我们令 \(DP_{i,j}\) 表示考虑到第 \(i\) 个字符串，匹配到第 \(j\) 个字符所获得的最大分数。
状态转移： \(DP_{i,j}=DP_{i-1,from} + calc()\)
\(calc()\) 用来计算这一段构成了多少个完整的串。
可以状态压缩，这里需要避免更新的新状态又去更新了别的状态，因此，我们可以复制一份dp数组。
每次记录好得分后，直接更新即可。最后的答案需要减去匹配到的字符数量 \(i\) ，因为那是 \(GPT\) 的得分。
void Showball(){
int n,m;
cin>>n>>m;
vector<string> a(n);
for(int i=0;i<n;i++) cin>>a[i];
const string s="narek";
vector<int> dp(5,-inf);
dp[0]=0;
for(int i=0;i<n;i++){
auto ndp=dp;
for(int j=0;j<5;j++){
int k=j;
int res=dp[j];
for(auto c:a[i]){
if(c==s[k]){
k++;
if(k==5){
k=0;
res+=5;
}
}else if(s.find(c)!=s.npos){
res--;
}
}
ndp[k]=max(ndp[k],res);
}
dp=ndp;
}
int ans=0;
for(int i=0;i<5;i++) ans=max(ans,dp[i]-i);
cout<<ans<<endl;
}
E1. Subtangle Game (Easy Version) 博弈+DP
不妨令 \(DP_{i,j,k}\) 表示第 \(i\) 步时选择 \(b_{j,k}\) 时是否可以必胜。
那么状态转移，我们倒着考虑，如果存在 \(s>j\) , \(t>k\) 且 \(DP_{i+1,s,t}=1\) 时，那么 \(DP_{i,j,k}\) 必败。
否则，如果 \(a_i=b_{j,k}\) 时，\(DP_{i,j,k}=1\)。对于上面这部分，我们可以用二位前缀和优化，因此 \(O(n^3)\)
可以通过该题。
void Showball(){
int l,n,m;
cin>>l>>n>>m;
vector<int> a(l+1);
for(int i=1;i<=l;i++) cin>>a[i];
vector<vector<int>> b(n+1,vector<int>(m+1));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>b[i][j];
}
}
vector<vector<vector<int>>> dp(l+2,vector<vector<int>>(n+2,vector<int>(m+2)));
for(int i=l;i;i--){
for(int j=n;j;j--){
for(int k=m;k;k--){
if(b[j][k]==a[i]&&!dp[i+1][j+1][k+1]) dp[i][j][k]=1;
dp[i][j][k]+=(dp[i][j+1][k]+dp[i][j][k+1]-dp[i][j+1][k+1]);
}
}
}
if(dp[1][1][1]) cout<<"T\n";
else cout<<"N\n";
}