526互联

Educational Codeforces Round 119

发布时间 2023-08-27 22:52:58作者: gan_coder

今天只有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;
}