脚本宝典收集整理的这篇文章主要介绍了Educational Codeforces Round 120，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
两个月没打CF了，好不容易打一次，写个题解（
这场C题因为一个小bug 调了好久 还WA了三发，加上考场以为是cf赛制 心态持续爆炸
好在5min想出D题 并且在结束前2min写出来，最后结果还算满意
给定三个长为 $ l_1,l_2,l_3(l_1,l_2,l_3in mathbb{N}^*) $ 的木棍，要求任选一个拆成两段，且每段长度都是正整数，使得四个木棍可以组成一个矩形。
考虑拆出来的两段是对边还是邻边。若是对边，则要求该木棍长为偶数且另外两个木棍长度相等。若是邻边则要求另外两个木棍长度相加等于该木棍。
#include<iostream>
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int main(){
int T=read(),a,b,c;
while(T--){
a=read();b=read();c=read();
if(a==b && c%2==0) puts("YES");
else if(b==c && a%2==0) puts("YES");
else if(c==a && b%2==0) puts("YES");
else if(a==b+c||b==a+c||c==a+b) puts("YES");
else puts("NO");
}
return 0;
}
给定 (p_1,p_2,...p_n) 和 (s_1,s_2,...,s_n) （ (p) 是排列， (s) 是01串），要求满足条件
的 (q_1,q_2,...,q_n) 中， (sum_{i=1}^n |p_i-q_i|) 最小的。
显然 (s_i=1) 的 (i) 对应的 (q_i) 应为 (1,2,3,...,x)，而 (s_i=0) 的 (i) 对应的 (q_i) 应为 (x+1,x+2,x+3,...,n-1,n) 感性理解一下，原来 (p_i) 小的 (q_i) 也应该小，嗯就这样。
#include<iostream>
#include<cstdio>
#include<algorIThm>
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x;
}
const int N=200005;
struct P{
int id,p,q,s;
}x[N];
bool cmp(P a,P b){
if(a.s!=b.s) return a.s<b.s;
return a.p<b.p;
}
bool cmpid(P a,P b){return a.id<b.id;}
int main(){
int T=read(),n;char c;
while(T--){
n=read();
for(int i=1;i<=n;++i) x[i].p=read(),x[i].id=i;
for(int i=1;i<=n;++i) cin>>c,x[i].s=(c-'0');
sort(x+1,x+n+1,cmp);
for(int i=1;i<=n;++i) x[i].q=i;
sort(x+1,x+n+1,cmpid);
for(int i=1;i<=n;++i) printf("%d ",x[i].q);
puts("");
}
return 0;
}
给定 (a_1,a_2,...,a_n) 和 (k)，有两种操作
要求用尽可能少的操作使得 (sum_{i=1}^n a_i leq k)
首先，最优策略一定是先对最小的数进行若干次操作1，再对最大的几个数依次进行操作2。
把 (a) 从小到大排序，假设我们进行了 (j) 次操作2和 (i) 次操作1。记 (sum_i=sum_{k=1}^i a_k)。
那么操作结束后的数列应该是： (a_1-j,a_2~a_{n-k},a_1-j,a_1-j,...,a_1-j)
由 (sum_{i=1}^n a_i leq k),
有 ((i+1)(a_1-j)+sum_{n-k}-a_1leq k)，
所以 (jgeq frac{sum_{n-k}-a_1-k}{i+1}+a_1)
因为我们要求 (i+j) 的最小值 故令 (j=max(lceil frac{sum_{n-k}-a_1-k}{i+1}+a_1 rceil,0))
枚举 (i) 即可。
(有两点要注意 一是答案初始值应为(max(sum_n-k,0))且(i)应从(1)枚举到(n-1)，二是更新答案时应该用ans=min(ans,max(0,j)+i)或ans=min(ans,max(i,i+j))而不是ans=min(ans,i+j)或ans=min(ans,max(0,i+j))
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
inline int read(){
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x;
}
int a[200005],sum[200005];
signed main(){
int T=read(),n,k,ans;
while(T--){
n=read();k=read();
for(int i=1;i<=n;++i) a[i]=read();
sort(a+1,a+n+1);
for(int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
ans=max(0ll,sum[n]-k);
for(int i=1;i<n;++i) {ans=min(ans,max(i,(long long)ceil(i+a[1]-((double)(k-sum[n-i]+a[1]))/(i+1))) );}
printf("%lldn",max(ans,0ll));
}
return 0;
}
给定一个长为 (n) 的01串。你可以选定一个包含恰好 (k) 个 (1) 的子串，并将它任意排序。求可以得到的不同01串个数。模(998244353)。
不妨假定我们选的子串一定是一个包含 (k) 个 (1) 的极大子串。将它们预处理出来。 观察可以发现，重复计算的方案数就是两个相邻子串交集的不同排列数，将它们减掉即可。 一个01串的不同排列数是一个组合数，可以 (O(n^2)) 预处理。
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int n,k,ans,cnt;
int pos[5050],l[5050],r[5050],c[5050][5050];
const int p=998244353;
string s;
int C(int a,int b){if(b==0) return 1; return c[a][b];}
signed main(){
cin>>n>>k;
cin>>s;
for(int i=0;i<=n;++i) c[i][0]=1;
for(int i=1;i<=n;++i)
for(int j=1;j<=i;++j)
c[i][j]=(c[i-1][j-1]+c[i-1][j])%p;
// while(1){
// cin>>n>>k;
// cout<<C(n,k)<<endl;
// }
for(int i=0;i<n;++i) if(s[i]=='1') pos[++cnt]=i; pos[cnt+1]=n; pos[0]=-1;
if(k>cnt||k==0) {cout<<1;return 0;}
for(int i=k;i<=cnt;++i) l[i-k+1]=pos[i-k]+1,r[i-k+1]=pos[i+1]-1;
// for(int i=1;i<=cnt-k+1;++i) cout<<l[i]<<r[i]<<endl;
for(int i=1;i<=cnt-k+1;++i) ans+=C(r[i]-l[i]+1,k)%p,ans%=p;
for(int i=1;i<=cnt-k;++i) ans-=C(r[i]-l[i+1]+1,k-1)%p,ans%=p,ans+=p,ans%=p;
cout<<ans%p;
return 0;
}
以上是脚本宝典为你收集整理的Educational Codeforces Round 120全部内容，希望文章能够帮你解决Educational Codeforces Round 120所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。