Educational Codeforces Round 81 (Rated for Div. 2)ABCD题解

Educational Codeforces Round 81 (Rated for Div. 2)A,B,C,D题解

比赛链接：https://codeforces.com/contest/1295

A.Display The Number（思维+构造）

题意：

11GzEq.png

思路：

如果想让构造一个最大的数，我们要使它的位数越多越好，而且使用最少的线段的数字是1（需要两根线段）。当线段的数量为偶数时我们把所有线段都用来构造1，此时构造的数字最大。当数量为奇数时，构造完全1的数字后还剩一根线段，我们肯定要把这根线段用在构造的数字最高位，将1变为7，此时便构造出了最大的数字。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[100000+7];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        if(n==3) {printf("7\n");continue;}
        int dig=n/2;
        int lef=n%2;
        for(int i=1;i<=dig;i++)
        {
            ans[i]=1;
        }
        if(lef==1) ans[1]=7;
        for(int i=1;i<=dig;i++) printf("%d",ans[i]);
        printf("\n");
    }
    return 0;
}

B. Infinite Prefixes（思维+构造转化）

题意：

11JP8U.png

思路：

对于每一个前缀，我们用ans[i]记录前i个字符的$cnt0-cnt1$的值，同时$k=整个串的cnt0-cnt1=ans[last]$。

那么比如，$ans[z]=h$，若前面有n个串的$cnt0-cnt1$=$x-h$，那么$x-h+ans[z]=x$,即可以找出一个值为x的串。

即寻找$n*k=x-h=x-ans[z]$符合这个式子的z和n的对数。

注意：空串也算答案！

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int ans[100000+7];
char s[100000+5];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,x,cnt0=0,cnt1=0;
        scanf("%d%d",&n,&x);
        scanf("%s",s);
        for(int i=0;i<n;i++)
        {
            if(s[i]-'0'==0) cnt0++;
            else cnt1++;
            ans[i]=cnt0-cnt1;
        }
        int k=cnt0-cnt1,flag=1,fin=0;
        if(k==0)
        {
            for(int i=0;i<n;i++)
            {
                if(ans[i]==x) {flag=0;break;}
            }
        }
        if(flag==0)
        {
            printf("-1\n");
            continue;
        }
        if(flag&&k==0) {printf("0\n");continue;}
        for(int i=0;i<n;i++)
        {
            if((x-ans[i])%k==0&&(x-ans[i])/k>=0) fin++;
        }
        if(x==0) fin++;
        printf("%d\n",fin);
    }
    return 0;
}

C-Obtain The String（二分+贪心）

题意：

11JeV1.png

思路：

$pos[x][y]$代表第y个字母x的位置 这个位置有单调性是单增的，我们对t串的每一个字符在s串中进行查询，比如查询字母a,通过二分$dig[a-‘0’][ t ]$对t二分出第一个大于当前s串指针的位置，如果二分不出来就把指针移到s串开头，从头开始二分，同时ans++。

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char t[100000+5];
char s[100000+5];
int pos[27][100000+5];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        scanf("%s",s);
        scanf("%s",t);
        int ed[27];
        memset(ed,-1,sizeof ed);
        int lens=strlen(s);
        for(int i=0;i<lens;i++)
        {
            int tep=s[i]-'a';
            ed[tep]++;
            pos[tep][ed[tep]]=i;
        }
        int lent=strlen(t),ans=1,now=-1,flag=1;
        for(int i=0;i<lent;i++)
        {
            int tep=t[i]-'a';
            int l=0,r=ed[tep];
            if(r==-1) {printf("-1\n");flag=0;break;}
            while(l<r)
            {
                int mid=(l+r)>>1;
                if(pos[tep][mid]>now) r=mid;
                else l=mid+1;
            }
            if(l==ed[tep]&&pos[tep][l]<=now)
            {
                now=-1;
                ans++;
                i--;
                continue;
            }
            else now=pos[tep][l];
        }
        if(flag) printf("%d\n",ans);

    }
    return 0;
}

D-Same GCDs（辗转相除法转化+phi）

题意：

11JM8O.png

思路：

11ay4I.png

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll phi(ll n)
{
    ll result = n; // Initialize result as n
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {

            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
    if (n > 1)
        result -= result / n;
    return result;
}
int main()
{
    ll t; cin >> t;
    while(t--) {
        ll a, m;
        cin >> a >> m;

        ll g = __gcd(a, m);

        m /= g;
        cout << phi(m) << endl;
    }
    return 0;
}