Wannafly 挑战赛5

柔情只为你懂 2022-06-03 01:58 320阅读 0赞

A 题:

星神是来自宇宙的

所以珂朵莉也是吧

所以我就出了个题

给你一个长为n的序列a，有n\*(n+1)/2个子区间，问这些子区间里面和为完全平方数的子区间个数

input

第一行一个数n

第二行n个数表示序列a

output

答案

样例

0 1 0 9 1 0

1 <= n <= 100000 0 <= ai <= 10

题目分析：因为子区间非常多，遍历每一个区间显然不可能，但是完全平方数并不多1000个，我们维护数组的前缀和，然后去遍历每一个完全数

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
     
    const int maxn=1e6+10;
    int a[maxn];
     
    int main()
    {
        int n;
        while (scanf("%d",&n)!=EOF) {
            memset (a,0,sizeof (a));
            int sum=0,b;
            ll ans=0;
            a[0]=1;
            for (int i=0;i<n;i++) {
                scanf("%d",&b);
                sum+=b;
                for (int j=0;j<=1000&&j*j<=sum;j++) {
                    ans+=a[sum-j*j];
                }
                a[sum]++;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }

B题

“这个比赛，归根结底就是控制一个虚拟的小拖拉机跑完整个赛道。一般一场比赛会有 9 个到 13 个赛道，最后看能跑完多少个赛道。”  
通常在一场可编程拖拉机比赛中，分别会有实际参赛队伍数 10%、20%、30% 向下取整的队伍获得金、银、铜牌，其余队伍获得荣誉提名，俗称“铁牌”。  
但是主办方往往会多准备一些奖牌，那么在发奖牌的时候会按照比例向上取整发出的奖牌以减少浪费，就会有一些原本获得银牌的队伍获得了金牌。  
现在给出一个赛区的规模，也就是这个赛区的实际参赛队伍数，小 Q 同学想知道有多少队伍的奖牌会由银变金、由铜变银、由铁变铜。

输入只有一行，包含一个整数 n (10 <= n <= 1000)，表示实际参赛队伍数。

输出一行，包含三个由空格分隔的整数，分别表示奖牌会由银变金、由铜变银、由铁变铜的队伍数。

115

1 1 2

代码如下://代码比较傻

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
     
    int main()
    {
        int n;
        while (scanf("%d",&n)!=EOF) {
            int x,y,z,cnt=0;
            x=(int) n*0.1;
            y=(int) n*0.2;
            z=(int) n*0.3;
            double a=n*0.1;
            if (a>x) {
                a=x+1;
                cnt=1;
            }
            else {
                a=x;
                cnt=0;
            }
            double b=n*0.2;
            if (b>y) {
                b=y+1+cnt;
                cnt++;
            }
            else {
                b=y+cnt;
            }
            double c=n*0.3;
            if (c>z) {
                c=z+1+cnt;
            }
            else {
                c=z+cnt;
            }
            printf("%.0lf %.0lf %.0lf\n",a-x,b-y,c-z);
        }
        return 0;
    }

D题:

给定一个小写字母字符串T

求有多少长度为m的小写字母字符串S满足，T是S的一个子序列(不需要连续)

第一行一个字符串T
    第二行一个正整数m

输出答案对109+7取模的值

a
    2

1<=|T|,m<=105

题目分析:对于m个字符，我们把n个字符丢进出Com(m,n),其他字符可以有26种方法，但是这样做的话就会有重复的。为了去重我们只需要保证：

\----a-----b----z---c---k---- 比如a和b之间不能有b，b和z之间不能有z，，也就是中间的只有25种选法。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #include<string>
    #define ll long long
    using namespace std;
    
    const int maxn=1e5+100;
    const int mod=1e9+7;
    string str;
    ll fac[maxn],inv[maxn];
    
    ll fast_pow(ll base,ll k)
    {
        ll ans=1;
        while (k) {
            if (k&1)
                ans=ans*base%mod;
            base=base*base%mod;
            k>>=1;
        }
        return ans;
    }
    ll get_inv(ll n)
    {
        if (n==1) return 1;
        else return get_inv(mod%n)*(mod-mod/n)%mod;
    }
    void solve()
    {
        fac[1]=fac[0]=1;
        inv[0]=1;
        for (int  i=1;i<maxn;i++) {
            fac[i]=fac[i-1]*i%mod;
            inv[i]=get_inv(fac[i]);
        }
    }
    ll Com(ll n,ll m)//求C(n,m)%mod
    {
        return fac[n]*inv[m]%mod*inv[n-m]%mod;
    }
    int main()
    {
        int m;
        solve();
        while (cin>>str>>m) {
            int len=str.size();
            ll ans=0;
            for (int i=len;i<=m;i++) {//最后一个字符的位置
                ans=(ans+Com(i-1,len-1)%mod*fast_pow(25,i-len)%mod*fast_pow(26,m-i)%mod)%mod;
            }
            printf("%lld\n",ans);
        }
        return 0;
    }