今天只有3题，有点遗憾，D题几乎一眼切，但是时间不够，分类讨论没写完，vp结束几分钟后写出来。
A题开始还以为要并查集，后面发现只有一个N不行
B题漏写括号WA一发
C题感觉不好写啊，因为直接计算可能会爆，所以要先从后往前，确定边界，然后就是跟普通的填数差不多，二分一下。
又是找串，还得特别小心会不会爆，真的有点烦，但好在一次AC
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<cmath>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const int N=2e5+5;
char s[N];
ll n,a[N],tot,k,x,ans[N],t,b[N];
void work(ll x,ll &y){
ll l,r,mid;
l=0; r=a[x]*k+1;
while (l<r){
mid=(l+r)>>1;
if ((db)y/(db)(mid+1)<=(db)b[x+1]) r=mid;
else l=mid+1;
}
y-=b[x+1]*l;
// printf("%lld\n",l);
ans[x]=l;
}
int main() {
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while (T--){
memset(b,0,sizeof(b));
memset(a,0,sizeof(a));
memset(ans,0,sizeof(ans));
tot=0;
scanf("%lld %lld %lld",&n,&k,&x);
scanf("%s",s+1);
int z=0;
fo(i,1,n) {
if (s[i]=='*') z++;
if (i==n || s[i+1]!='*') {
if (z) a[++tot]=z;
z=0;
}
}
// fo(i,1,tot) printf("%lld ",a[i]);
// return 0;
int l=1;
b[tot+1]=1;
fd(i,tot,1) {
if ((db)a[i]*(db)k+1 > (db)x/(db)b[i+1]) {
l=i;
break;
}
b[i]=b[i+1]*(a[i]*k+1);
}
fo(i,1,l-1) ans[i]=0;
fo(i,l,tot){
work(i, x);
}
// return 0
int j=0;
fo(i,1,n) {
if (s[i]=='a') printf("%c",'a');
else{
if (i==1 || s[i-1]=='a') {
j++;
fo(p,1,ans[j]) printf("%c",'b');
}
}
}
printf("\n");
}
return 0;
}
D题肯定是尽量用3，1，2的数量不超2，枚举一下，计算即可。
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<set>
#include<queue>
#include<cmath>
#include<unordered_map>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
#define lc (o<<1)
#define rc ((o<<1)|1)
#define A puts("YES")
#define B puts("NO")
using namespace std;
typedef double db;
typedef long long ll;
const int N=2e5+5;
int a[N],n,ans,mx,z;
int main() {
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while (T--){
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i]);
ans=1e9;
fo(p1,0,2) fo(p2,0,2) {
mx=0;
fo(i,1,n) {
if (a[i]%3==0) {
mx=max(mx, max(0, (a[i]-3*min(p1,p2))/3));
}
if (a[i]%3==1) {
if (a[i]==1 && !p1) mx=1e9;
if (p2!=2 && !p1) mx=1e9;
if (p1) {
mx=max(mx,(a[i]-1)/3);
}
if (p2==2) {
mx=max(mx,(a[i]-4)/3);
}
if (p1==2 && p2) {
mx=max(mx, (a[i]-4)/3);
}
}
if (a[i]%3==2) {
if (p1!=2 && !p2) mx=1e9;
if (p1==2) mx=max(mx, (a[i]-2)/3);
if (p2) mx=max(mx, (a[i]-2)/3);
if (p2==2 && p1) mx=max(mx, max(0,(a[i]-5))/3);
}
}
ans=min(ans,mx+p1+p2);
}
printf("%d\n",ans);
}
return 0;
}