P10872 [COTS 2022] 移位 Maliand

用户头像 发布于 20 小时前 10 次阅读 OI

P10872 [COTS 2022] 移位 Maliand

考虑 S,TS, T 的每个位置只会相匹配 1 次，共匹配 NN 次，产生贡献的有 K⋅LK\cdot L 次，

所以想要所有匹配中贡献最大的最小，平均分配即可，答案就应该是 ⌈KLN⌉\lceil \frac{KL}{N} \rceil。

先考虑 SS，1 是可以随便放的，为了方便，可以前 KK 个都放 1。

再考虑 TT，为了使每 KK 个都有平均数量的 1，我们直接循环区间放 1 即可。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=5e5+5;
int n,k,l;
int ans[N];

signed main(){
	cin>>n>>k>>l;
    cout<<ceil(1.0*k*l/(1.0*n))<<"\n";
    for(int i=1;i<=n;i++) cout<<(i<=k);
    cout<<"\n";
    int i=0;
    while(l--){
        while(ans[i]) (i+=1)%=n;
        ans[i]=1;
        (i+=k)%=n;
    }
    for(int i=0;i<n;i++) cout<<ans[i];
	return 0;
}