好！
上分了！
好吧讲正题啦（没切 D 真是太不爽了）
A:AB Balance
题意：给出一个只包含 A B 的字符串 \(S\) ，要求用最小的步数使其变成合法。
合法：字符串 \(S\) 所包含的 AB 和 BA 个数相同。
考虑将 AB 视作 +1 ， 将 BA 视作 -1 ，那么就是要求整串的和是 0 ，所以 合法 当且仅当 开头和结尾相同。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=110;
int T,n;
char s[N];
int main(){
scanf("%d",&T);
while(T--){
scanf("%s",s+1);
n=strlen(s+1);
if(s[1]!=s[n])s[1]=(s[1]=='a'?'b':'a');//完全可以直接写成 s[1]=s[n]
printf("%s\n",s+1);
}
return 0;
}
B:Update Files
题意：有 \(n\) 个电脑，每次可以将至多 \(m\) 个电脑的数据转移到另外 \(m\) 个电脑里，不能同时接收两个或同时接收发送，问最少用多少次可以把所有数据放到一个电脑里。
每次把最左边的 \(m\) 个放到最右边 \(m\) 个去，这一定是最优的，剩余个数少于 \(2m\) 时把 \(m\) 缩一下即可。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
int T;
ll n,ans,m;
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&n,&m);
ans=0;
while(n>1){
m=min(m,n/2);
ans+=n/m-1;
n=n%m+m;
}
printf("%lld\n",ans);
}
return 0;
}
C:Banknotes
大概也是一个SB题。。。给出几种钞票和最大总张数 \(m\) ，问最小的不能表示的数，保证最小面额为 1 ，且每种面额都是 10 的幂。
贪心放就好。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
int n,a[20],T,m,mi[20];
ll ans;
int main(){
mi[0]=1;
fo(i,1,9)mi[i]=mi[i-1]*10;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
fo(i,1,n)scanf("%d",&a[i]);
ans=0;
fo(i,1,n){
if(i==n || mi[a[i+1]-a[i]]-1>m){
ans+=(ll)mi[a[i]]*(m+1);
break;
}else{
ans+=mi[a[i+1]]-mi[a[i]];
m-=(mi[a[i+1]-a[i]]-1);
}
}
printf("%lld\n",ans);
}
return 0;
}
E:Arena
一场战斗由多个回合组成，每个回合每个英雄对其他所有英雄造成 1 点伤害，回合结束后生命值 < 1$ 的死去。
给出 \(n\) 、 \(k\) ，表示一共有 \(n\) 个英雄，每个英雄的血量上限为 \(k\) ，给每个英雄分配初始生命值，问最后无人获胜（即没有人独自存活）的方案数。
考虑 DP ，设 \(f_{i,j}\) 为 \(n=i , k=j\) 时的答案，转移考虑枚举本轮死了多少英雄。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
#define ll long long
using namespace std;
const int N=510;
const int mod=998244353;
int n,m;
ll f[N][N],g[N][N],fac[N],ifac[N];
ll power(ll x,int n){
ll a=1;
while(n){
if(n&1)a=a*x%mod;
x=x*x%mod;
n>>=1;
}
return a;
}
ll C(int n,int m){
return fac[n] *ifac[m] %mod *ifac[n-m] %mod;
}
int main(){
scanf("%d%d",&n,&m);
fac[0]=1;
fo(i,1,n)fac[i]=fac[i-1]*i%mod;
ifac[n]=power(fac[n],mod-2);
fd(i,n,1)ifac[i-1]=ifac[i]*i%mod;
fo(i,1,m){
g[i][0]=1;
fo(j,1,n){
g[i][j]=g[i][j-1]*i%mod;
}
}
f[0][0]=1;
fo(i,2,n){
fo(j,0,i-1)f[i][j]=g[j][i];
fo(j,i,m){
fo(k,0,i){
// if(k==i-1)continue;
f[i][j]=(f[i][j] + f[i-k][j-i+1]*g[i-1][k]%mod * C(i,k) % mod)%mod;
}
f[i][j]=(f[i][j] + g[i-1][i])%mod;
}
}
printf("%lld\n",f[n][m]);
return 0;
}
呜呜呜没切 D 真是太可惜了呜呜呜