Codeforces Round #650 (Div. 3)（D-E）

D. Task On The Board

考虑bi =0的特殊点

bi=0的点一定是当前字母最大的,否则会和更大的字母产生贡献 b_i=0的点一定是当前字母最大的,否则会和更大的字母产生贡献bi =0的点一定是当前字母最大的,否则会和更大的字母产生贡献

所以第一步,用最大且足够数目的字母去填充所有bi=0,标记填过 所以第一步,用最大且足够数目的字母去填充所有b_i=0,标记填过所以第一步,用最大且足够数目的字母去填充所有bi=0,标记填过

那么其余没填过的都比这些字母小,所以对其余的bi修改 那么其余没填过的都比这些字母小,所以对其余的b_i修改那么其余没填过的都比这些字母小,所以对其余的bi修改

怎么修改?比如bi=0且没被标记的点位置是num 怎么修改?比如b_i=0且没被标记的点位置是num怎么修改?比如b=0且没被标记的点位置是num

那么对于所有的bj!=0,bj=bj−abs(num−j),也就是减掉num对j的影响 那么对于所有的b_j!=0,b_j=b_j-abs(num-j),也就是减掉num对j的影响那么对于所有的bj!=0,bj=bj−abs(num−j),也就是减掉num对j的影响

修改后,又有一些没标记的bi变成0,那么这些点是余下点中最大的 修改后,又有一些没标记的b_i变成0,那么这些点是余下点中最大的修改后,又有一些没标记的bi 变成0,那么这些点是余下点中最大的
重复上面的步骤即可完成步骤 重复上面的步骤即可完成步骤重复上面的步骤即可完成步

#include<bits/stdc++.h>
#define intn long long
#define _0for(i, a) for(int i = 0; i < (a); ++i)
#define _1for(i, a) for(int i = 1; i <=(a); ++i)
using namespace std;
int b[2000];
int a[2000];
char c[2000];
main(void)
{
	int t,n;
	cin>>t;
	
	_0for(p,t)
	{
		char q;	
		getchar();
		int cnt=0;
		while((q=getchar())!='\n')
		{
			a[++cnt]=q-'a';
		}
		int cntt=0;
		sort(a+1,a+1+cnt);
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>b[i];
		}
		int ans=0;
		while(ans!=n)
		{
			int reg;
			vector<int >ling;
			ling.clear();
			for(int k=1;k<=n;k++)
			{
				if(b[k]==0)
				{
					ling.push_back(k);
				}
			}
			int l=ling.size();
			int ll=l;
			for(int i=cnt;i>=1;i--)
			{
				if(ll==l)
				{
					reg=a[i];
				}
				else
				{
					if(reg!=a[i])
					{
						ll=l;
						reg=a[i];
					}
				}
				ll--;
				cnt--;
				if(!ll)
				{
					for(int j=cnt;j>=1;j--)
					{
						if(a[cnt]==a[cnt+1])
						{
							cnt--;
						}
					} 
					break;
				}
			}
			for(int i=1;i<=n;i++)
			{
				if(b[i]==-1)continue;
				if(!b[i])
				{
					c[i]=reg;
					b[i]=-1;
					ans++;
				}
				else
				{
					for(int j=0;j<l;j++)
					{
						b[i]-=abs(i-ling[j]);
					}
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			printf("%c",c[i]+'a');
		}
		printf("\n");
	}
}

E. Necklace Assembly

题意
给定一个字符串s，长度为n，一根项链为一个环，定义一根项链为k−beautiful，则该项链顺时针转k下后与原项链相等，给出k，请构造一根最长的k−beautiful项链，项链由s中的一些字符组成，长度为1的项链和组成字符全部相等的项链满足任意k

长度为n的字符串，转k下后相等，就是等式

经过一系列过程，最终旋转得到 i=(i+x*k)%n,解同余方程
(x,y为整数)
所以xk=ny,又因为

因此可以得到x、y的最小整数解

回到分析， 我们x的意义是i经过x个k回到i,因此一组相同数量的字符有0–x-1个即x个，而gcd(k,n)就是字符的组数
因此得到代码

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int T; cin >> T;
    while(T--) {
        int N, K; cin >> N >> K;
        string S; cin >> S;
        int cnt[26]; F0R(i, 26) cnt[i] = 0;
        F0R(i, N) cnt[S[i]-'a'] ++;
        int ans = 0;
        FOR(i, 1, N+1) {
            int nc = __gcd(i, K);
            int percyc = i / nc;
            F0R(j, 26) {
                nc -= cnt[j] / percyc;
            }
            if (nc <= 0) ans = i;
        }
        cout << ans << nl;
    }
	
	return 0;
}