ECR 81 (Rated for Div. 2)

年后打的第一场比赛,假期果不其然的还是颓废了。。。每天在家只做四件事:睡觉、吃饭、打联盟、刷抖音。

这场也果不其然的掉分了。。。费了老大劲做了A和B,结果第二天一看B被hack了,凉凉。。。

再一看关注的一位好友,轻松4题(虽然B第二天也被hack了),但差距一下子就显现出来了,唉。。。不能再这样下去了

A题:Display The Number

原题链接:https://codeforces.com/contest/1295/problem/A

一个时钟数字由7个段组成,给你一个数字n,问亮起这n个段能组成的最大数是多少

显然只有1花费的段最少,只需两个段,因此我们尽量让数的位数足够多,因此n/2就是位数,每位都是1,这样的数是最大的。如果n是奇数会多出来一个段,三个段可以组成7,因此将7放在首位

代码:

#include <bits/stdc++.h>
using namespace std;
long long a=998244353;
int main()
{
    int t;
    scanf("%d",&t);
    long long n;
    a=a*6;
    while(t--)
    {
        scanf("%lld",&n);
        if(n%2==0)
        {
            for(int i=0;i<n/2;i++)
            {
                printf("1");
            }
            printf("\n");
        }
        if(n%2==1)
        {
            printf("7");
            for(int i=1;i<n/2;i++)
            {
                printf("1");
            }
            printf("\n");
        }
    }
    return 0;
}

B题:Infinite Prefixes

原题链接:https://codeforces.com/contest/1295/problem/B

给你一个串s由01组成,给你一个平衡数x(平衡数指在串中0的个数与1的个数之差),再给你一个串t,t可以由任意个s组成,问t中有多少前缀的平衡数为x(空也算前缀)

我想法我感觉我解释不出来,直接上代码吧

代码:

#include <bits/stdc++.h>
using namespace std;
int e[200010];
int main()
{
    int t,n,x;
    char s[200010];
    cin>>t;
    while(t--)
    {
        cin>>n>>x;
        getchar();
        gets(s);
        int l=strlen(s);
        int maxx=-99999999,minn=99999999,a=0,b=0;
        for(int i=0;i<l;i++)
        {
            if(s[i]=='1')
            {b++;}
            if(s[i]=='0')
            {a++;}
            e[i]=a-b;
            if(e[i]>maxx)
            {maxx=e[i];}
            if(e[i]<minn)
            {minn=e[i];}
        }
        int op=a-b;
        int ans=0;
        if(x==0)
        {ans++;}
        if(op==0)
        {
            int flag=0;
            for(int i=0;i<l;i++)
            {
                if(e[i]==x)
                {flag=1;
                break;}
            }
            if(flag==1)
            {cout<<"-1"<<endl;}
            if(flag==0)
            {cout<<"0"<<endl;}
        }
        if(op>0)
        {
            for(int i=0;i<l;i++)
            {
                if(x==e[i])
                {ans++;}
                if(x>e[i]&&((x-e[i])%op==0))
                {ans++;}
            }
             cout<<ans<<endl;
             continue;
        }
        if(op<0)
        {
            for(int i=0;i<l;i++)
            {
                if(x==e[i])
                {ans++;}
                if(x<e[i]&&((x-e[i])%(-op)==0))
                {ans++;}
            }
            cout<<ans<<endl;
            continue;
        }
    }
    return 0;
} 

C题:Obtain The String

原题链接:https://codeforces.com/contest/1295

这题是给你一个s串和t串,问有一个z串(一开始是空串),你可以对z串进行如下操作:将删除某些字符后的s串加到z串后面(也可以不删除),需经过多少次操作后能将z串变为t串,若不能,打印“-1”

乍一看感觉可以暴力去求,但这样时间会超限,因此在求的过程要用二分优化,用了upper_bound()函数

代码:

#include <bits/stdc++.h>
using namespace std;
int e[26][100010];
int z[26];
int main()
{
    int n;
    char s[200010],t[200010];
    cin>>n;
    getchar();
    while(n--)
    {
        memset(z,0,sizeof(z));
        gets(s);
        gets(t);
        int ls=strlen(s);
        int lt=strlen(t);
        for(int i=0;i<ls;i++)
        {
            e[s[i]-'a'][z[s[i]-'a']]=i+1;
            z[s[i]-'a']++;
        }
        int flag=1,ans=0,op=0;
        for(int i=0;i<lt;i++)
        {
            if(z[t[i]-'a']==0)
            {flag=0;
            break;}
            int zop=upper_bound(e[t[i]-'a'],e[t[i]-'a']+z[t[i]-'a'],op)-e[t[i]-'a'];
            if(zop>=z[t[i]-'a'])
            {
                ans++;
                zop=upper_bound(e[t[i]-'a'],e[t[i]-'a']+z[t[i]-'a'],0)-e[t[i]-'a'];
                op=e[t[i]-'a'][zop];
            }
            if(zop<z[t[i]-'a'])
            {op=e[t[i]-'a'][zop];}
        }
        if(flag==0)
        {cout<<"-1"<<endl;
        continue;}
        cout<<ans+1<<endl;
    }
    return 0;
}

D题:Same GCDs

原题链接:https://codeforces.com/contest/1295/problem/D

(1a<m≤1e10)且(0x<m)问能使等式gcd(a,m)=gcd(a+x,m)成立的x有多少个

这里上一张演算纸。。。

最后写的可能有点乱,反正结论就是y的欧拉函数

y就是m/gcd(a,m)

代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    long long a,m;
    while(t--)
    {
        cin>>a>>m;
        long long g=__gcd(a,m);
        long long y=m/g;
        long long ans=y;
        for(long long i=2;i*i<=y;i++)
        {
            if(y%i==0)
            {ans-=ans/i;
            while(y%i==0)
            {y/=i;}
            }
        }
        if(y>1)ans-=ans/y;
        cout<<ans<<endl;
    }
    return 0;
} 

能力有限,只有这四道题。

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注