2021“MINIEYE”杯中国大学生算法设计超级联赛（7）

比赛记录 2021/10/6

参考鸣谢

赛场A题

1010Smzzl with Tropical Taste 签到题

题目大意：在一个水池内有体积为V的冰红茶，商店老板会以每秒qV的速度往水池当中倒冰红茶，而另一个人以每秒pV的速度进行喝冰红茶，问是否对于任意的冰红茶G，总能有时间T使得，当t大于T的时候，喝的冰红茶的数量大于G。

解题思路：每秒喝冰红茶的速度与加冰红茶的速度与体积是成正相关的，当喝的速度大于加的速度的时候，肯定会有喝完的时候，此时，加的速度变为0所有一定无法达成条件，只有当加的速度大于等于喝的速度才能够使得冰红茶不减少甚至更多。

1007 基环树

Link with Limit

建图，点向点连边，那么迭代的过程实质上是在图上行走的过程。原题实际上问的是每一个环的

点权平均值是否相同，使用任意方法找出所有环并求出平均值即可。

贴出标程里优美的基环树找环

#include <stdio.h>
#include <queue>
#define MN 100000
typedef long long ll;

int n,a[MN+5],din[MN+5];

void solve(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		din[i] = 0;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		din[a[i]]++;
	}
	std::queue<int> Q;//queue就是队列
	for(int i=1;i<=n;i++){
		if(din[i]==0) Q.push(i);
	}
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		din[a[u]]--;
		if(din[a[u]]==0){
			Q.push(a[u]);
		}
	}
	ll p=-1,q=-1;
	for(int i=1;i<=n;i++){
		if(din[i]==0) continue;
		ll tp=0,tq=0;
		for(;din[i];i=a[i]){
			tp += i;
			tq++;
			din[i] = 0;
		}
		if(p==-1){
			p = tp;
			q = tq;
		}else{
			if(p*tq!=q*tp){
				puts("NO");
				return;
			}
		}
	}
	puts("YES");
	return;
}

int main(){
	int T;
	scanf("%d",&T);
	while(T--) solve();
}

对于找环来说一般直接dfs就好，可以开个栈存一下也可

1003C（等差等比推公式）

1004D 感觉还是挺巧妙的数学题

1004 Link with Balls

就是给出2n个篮子其中n个可以取i的倍数个，其他n个可以取0~i个。

然后让你求拿m个方案数。

组合数模板

#include<bits/stdc++.h>
#define N 2000010
#define ll long long
using namespace std;
const int mod=1e9+7;
ll Pow(ll x,int y){ll ans=1;while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
ll fac[N],ifac[N];
void init(){
	fac[0]=1;
	for(int i=1;i<N;i++)fac[i]=fac[i-1]*i%mod;
	ifac[N-1]=Pow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;i--)ifac[i]=ifac[i+1]*(i+1)%mod;
}
ll C(int n,int m){
	if(m<0||n<m)return 0;
	return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main(){
   
    	init();
	int T,n,m;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&m);
		if(n<m)
		printf("%lld\n",(C(n+m,n)-C(m-1,n)+mod)%mod);
		else printf("%lld\n",C(n+m,n));
	}
	return 0;
}

1005 Link with EQ

题面太真实了。

注意到只要不选一开始不选第x个座位x∈{1,2,n−1,n−2}第1和第n个座位早晚会坐上人。而且一定是x两侧最先选的（像极了自己坐角落），然后剩下的问题其实就是在最左空位的左侧和最右空位的右侧都有人了的连续空区间做人的问题。

对于两边都坐了人中间没人的情况可以递推考虑

1012

求每个字母为最后一个字母的所有子串的值按不同字母考虑

因为每增加一个字母，假设这是第i个字母，那么整个字符串的子串数量就会加i个，这时候只要计算这i个新增字串对答案的贡献即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e5+5;
const int mod=998244353;
int T,n,m,ans,len,x;
int tot[maxn],sum[maxn];
char s[200000];
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%s",s+1);
        len=strlen(s+1);
        int ans=0;
        for (int i=1;i<=len;i++)
        {
            int x=s[i]-'a';
            if (i==1) { sum[x]=1; tot[x]=1;}
            else
            {
                for (int j=0;j<=25;j++) ans=(ans+sum[j])%mod;
                sum[x]+=(2*tot[x] % mod +i)%mod;
                sum[x]=sum[x]%mod;
                tot[x]+=i;
                tot[x]%=mod;
            }
        }
        for(int i=0; i<26; i++)
            ans=(ans+sum[i])%mod;
        printf("%lld\n",ans);
        memset(tot,0,sizeof tot);
        memset(sum,0,sizeof sum);
    }
    return 0;
}

1011

任意模数分治ntt模板题

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
const ll N=4e5*4+10,sqq=32768,p=998244352,P=998244353;
const double Pi=acos(-1);
struct complex{
    double x,y;
    complex (double xx=0,double yy=0)
    {x=xx;y=yy;return;}
}A[N],B[N],C[N],D[N];
struct Poly{
	ll a[N],n;
}F[20];
ll power(ll x,ll b,ll P){
	ll ans=1;
	while(b){
		if(b&1)ans=ans*x%P;
		x=x*x%P;b>>=1;
	}
	return ans;
}
complex operator+(complex a,complex b)
{return complex(a.x+b.x,a.y+b.y);}
complex operator-(complex a,complex b)
{return complex(a.x-b.x,a.y-b.y);}
complex operator*(complex a,complex b)
{return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
complex w[N];
ll n,m,T,u[N],v[21],r[N];
void FFT(complex *f,ll op,ll n){
    for(ll i=0;i<n;i++)
        if(i<r[i])swap(f[i],f[r[i]]);
    for(ll p=2;p<=n;p<<=1){
        ll len=p>>1;
        for(ll k=0;k<n;k+=p)
            for(ll i=k;i<k+len;i++){
                complex tmp=w[n/len*(i-k)];
                if(op==-1)tmp.y=-tmp.y;
                complex tt=f[i+len]*tmp;
                f[i+len]=f[i]-tt;
                f[i]=f[i]+tt;
            }
    }
    if(op==-1){
        for(ll i=0;i<n;i++)
            f[i].x=(ll)(f[i].x/n+0.49);
    }
    return;
}
void MTT(ll *a,ll *b,ll *c,ll m,ll k){
    ll n=1;
    while(n<=m+k)n<<=1;
    for(ll i=0;i<n;i++){
        r[i]=(r[i>>1]>>1)|((i&1)?(n>>1):0);
    	A[i].x=A[i].y=B[i].x=B[i].y=0;
    	C[i].x=C[i].y=D[i].x=D[i].y=0;
	}
    for(ll len=1;len<n;len<<=1)
        for(ll i=0;i<len;i++)
            w[n/len*i]=complex(cos(i*Pi/len),sin(i*Pi/len));
    for(ll i=0;i<m;i++)A[i].x=a[i]/sqq,B[i].x=a[i]%sqq;
    for(ll i=0;i<k;i++)C[i].x=b[i]/sqq,D[i].x=b[i]%sqq;
    FFT(A,1,n);FFT(B,1,n);FFT(C,1,n);FFT(D,1,n);
    complex t1,t2;
    for(ll i=0;i<n;i++){
        t1=A[i]*C[i];t2=B[i]*D[i];
        B[i]=A[i]*D[i]+B[i]*C[i];
        A[i]=t1;C[i]=t2;
    }
    FFT(A,-1,n);FFT(B,-1,n);FFT(C,-1,n);
    for(ll i=0;i<n;i++){
    	c[i]=0;
        (c[i]+=(ll)(A[i].x)*sqq%p*sqq%p)%=p;
        (c[i]+=(ll)(B[i].x)*sqq%p)%=p;
        (c[i]+=(ll)(C[i].x))%=p;
    }
    return;
}
void Mul(Poly &a,Poly &b){
	MTT(a.a,b.a,a.a,a.n,b.n);
	a.n=a.n+b.n-1;return;
}
ll findq(){
	for(ll i=0;i<20;i++)
		if(!v[i]){v[i]=1;return i;}
}
ll Solve(ll l,ll r){
	if(l==r){
		ll p=findq();
		for(ll i=0;i<=u[l];i++)
			F[p].a[i]=0;
		F[p].a[0]=1;F[p].a[u[l]]=1;
		F[p].n=u[l]+1;return p;
	}
	ll mid=(l+r)>>1;
	ll ls=Solve(l,mid),rs=Solve(mid+1,r);
	Mul(F[ls],F[rs]);v[rs]=0;return ls;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld",&n);
		bool flag=0;ll ans=1,sum=0;
		for(ll i=1;i<=n;i++){
			scanf("%lld",&u[i]);
			flag|=!u[i];sum+=u[i];
		}
		if(flag){puts("0");continue;}
		ll id=Solve(1,n);u[id]=0;
		for(ll i=1;i<=sum;i++)
			ans=ans*power(i,F[id].a[i],P)%P;
		printf("%lld\n",ans);
	}
}

原文链接：https://blog.csdn.net/zzrh2018/article/details/120630977

你可能也喜欢