Educational Codeforces Round 79 (Rated for Div. 2)

比赛链接

唉。。。(ACM)赛制(CBAD)的顺序开题可还行。。.

({frak{A. New Year Garland}})

贪心即可。

({frak{code:}})

    #include<bits/stdc++.h>
    #define IL inline
    #define LL long long
    using namespace std;
    const int N=1e5+3;
    int a[5];
    IL LL in(){
        char c;int f=1;
        while((c=getchar())<'0'||c>'9')
          if(c=='-') f=-1;
        LL x=c-'0';
        while((c=getchar())>='0'&&c<='9')
          x=x*10+c-'0';
        return x*f;
    }
    int main()
    {
    	int t=in();
    	while(t--){
    		a[1]=in(),a[2]=in(),a[3]=in();
    		sort(a+1,a+4);
    		if(a[3]>a[1]+a[2]+1) puts("No");
    		else puts("Yes");
    	}
    	return 0;
    }

({frak{B. Verse For Santa}})

求出前缀和与前缀最大值，贪心即可。

({frak{code:}})

#include<bits/stdc++.h>
#define IL inline
#define LL long long
using namespace std;
const int N=1e5+3;
int n,a[N],c[N],p[N],pos;
LL ans,res,b[N],m;
IL LL in(){
    char c;int f=1;
    while((c=getchar())<'0'||c>'9')
      if(c=='-') f=-1;
    LL x=c-'0';
    while((c=getchar())>='0'&&c<='9')
      x=x*10+c-'0';
    return x*f;
}
int main()
{
	int t=in();
	while(t--){
		n=in(),m=in(),pos=ans=res=0;
		for(int i=1;i<=n;++i) b[i]=b[i-1]+(a[i]=in());
		for(int i=1;i<=n;++i){
			if(a[i]>a[pos]) pos=i;
			if(m>=b[i]) res=i;
			else if(m>=b[i]-a[pos]){res=i-1,ans=pos;} 
			else break;
		}
		printf("%lld
",ans);
	}
	return 0;

({frak{C. Stack of Presents}})

如果当前礼物的位置比到达过的最大值小，就必然可以通过对礼物的重排列使之只有(1)的代价，若比其大，则要花费(2*(h-i)+1)的代价。

({frak{code:}})

    #include<bits/stdc++.h>
    #define IL inline
    #define LL long long
    using namespace std;
    const int N=1e5+3;
    int n,m,tp,a[N],b[N],c[N],p[N];
    LL ans;
    IL LL in(){
        char c;int f=1;
        while((c=getchar())<'0'||c>'9')
          if(c=='-') f=-1;
        LL x=c-'0';
        while((c=getchar())>='0'&&c<='9')
          x=x*10+c-'0';
        return x*f;
    }
    int main()
    {
    	int t=in();
    	while(t--){
    		n=in(),m=in(),ans=tp=0;
    		for(int i=1;i<=n;++i) a[i]=c[i]=in();
    		sort(c+1,c+n+1);
    		for(int i=1;i<=n;++i) a[i]=lower_bound(c+1,c+n+1,a[i])-c;
    		for(int i=1;i<=n;++i) p[a[i]]=i;
    		for(int i=1;i<=m;++i) b[i]=lower_bound(c+1,c+n+1,in())-c;
    		for(int i=1;i<=m;++i){
    			if(tp>=p[b[i]]) ++ans;
    			else{
    				ans+=2*(p[b[i]]-i)+1;
    				tp=p[b[i]];
    			}
    		}
    		printf("%lld
",ans);
    	}
    	return 0;
    }

({frak{D. Santa's Bot}})

设(s_i)为想要礼物i的孩子的集合，(buk_i)为(s_i)的基数，(k_i)为孩子(i)的礼物集合的基数，则期望为(sumlimits_{i=1}^{N}{cfrac{sumlimits_{jin s_i}^{}{frac{1}{k_j}}}{n^2}buk_i})。

({frak{code:}})

    #include<bits/stdc++.h>
    #define IL inline
    #define LL long long
    using namespace std;
    const int N=1e6+3,p=998244353;
    int n,buk[N],num[N];
    LL inv[N],ans;
    IL LL in(){
        char c;int f=1;
        while((c=getchar())<'0'||c>'9')
          if(c=='-') f=-1;
        LL x=c-'0';
        while((c=getchar())>='0'&&c<='9')
          x=x*10+c-'0';
        return x*f;
    }
    IL LL ksm(LL a,LL b){
    	LL c=1;
    	while(b){
    		if(b&1) c=c*a%p;
    		a=a*a%p,b>>=1;
    	}
    	return c;
    }
    IL void mod(LL &x){if(x>=p) x-=p;}
    int main()
    {
    	n=in();int x;
    	for(int i=1;i<=n;++i){
    		num[i]=in();
    		for(int j=1;j<=num[i];++j){
    			x=in();
    			mod(inv[x]+=ksm(num[i],p-2));
    			++buk[x];
    		} 
    	}
    	for(int i=1;i<=N;++i) 
    		if(buk[i]) mod(ans+=buk[i]*inv[i]%p);
    	ans=ans*ksm(1ll*n*n%p,p-2)%p;
    	printf("%lld
",ans);
    	return 0;
    }