526互联

Educational Codeforces Round 107

发布时间 2023-09-18 20:22:34作者: gan_coder

依然是四题，但是感觉太久没打，好像变得迟钝了。
B题大概就是令

\[c={10}^k, a=c*3^k, b=c*2^k \]

C的话直接暴力维护每种颜色的第一个位置就行，反正只有50个

D的话刚开始没什么想法，构造题什么的真的不会啊

打表之后发现，对于k，在cost为0的情况下，最多能造出长度为\(k^2+1\)的串，也就是能够让每一种关系都出现一次，那么后面的话，我们每次选一个关系出现次数最小的就行，迷迷糊糊地过了。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#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 A puts("YES")
using namespace std;
typedef long long ll;
const int N=3e5+5;
int n,q;
int t,x,sum,k,ans,len;
int h[50][50];

char a[N];
int b[N];
bool flag;
void dfs(int x){
	if (flag) return;
	if (x>len){
		flag=1;
		fo(i,1,n) b[i]=a[i]-'a'; 
		return;
	}
	
	fo(i,1,k){
		a[x]='a'+i-1;
		
		int z=0;
		fo(j,1,x-2) {
			if (a[j]==a[x-1] && a[j+1]==a[x]) z++;
		}
		
		if (z) continue;
		dfs(x+1);
	}
}
int main(){
	
//	freopen("data.in","r",stdin);
	scanf("%d %d",&n,&k);
	
	len=k*k+1;
	dfs(1);
	
	if (n<=len) {
		fo(i,1,n) printf("%c",b[i]+'a');
		return 0;
	}
	
	fo(i,1,len) printf("%c",b[i]+'a');
	fo(i,1,len-1) {
		h[b[i]][b[i+1]]=1;
	}
	
	int id,mn;
	fo(i,len+1,n) {
		
		mn=n;
		fo(j,0,k-1) {
			if (h[b[i-1]][j]<mn){
				mn=h[b[i-1]][j];
				id=j;
			}
		}
		
		b[i]=id;
		h[b[i-1]][id]++;
		
	}
	
	fo(i,len+1,n) printf("%c",b[i]+'a');
	
	return 0;
	
}