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

本文主要是介绍2021“MINIEYE”杯中国大学生算法设计超级联赛（7），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

比赛记录 2021/10/6

参考鸣谢

赛场A题 

1010Smzzl with Tropical Taste 签到题

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

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

1007 基环树

#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

这篇关于2021“MINIEYE”杯中国大学生算法设计超级联赛（7）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！