Educational Codeforces Round 81 (Rated for Div. 2) A、B、C、D_d. same gcds time limit per test2 seconds memory l

A. Display The Number
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You have a large electronic screen which can display up to 998244353 decimal digits. The digits are displayed in the same way as on different electronic alarm clocks: each place for a digit consists of 7 segments which can be turned on and off to compose different digits. The following picture describes how you can display all 10 decimal digits:

As you can see, different digits may require different number of segments to be turned on. For example, if you want to display 1, you have to turn on 2 segments of the screen, and if you want to display 8, all 7 segments of some place to display a digit should be turned on.

You want to display a really large integer on the screen. Unfortunately, the screen is bugged: no more than n segments can be turned on simultaneously. So now you wonder what is the greatest integer that can be displayed by turning on no more than n segments.

Your program should be able to process t different test cases.

Input
The first line contains one integer t (1≤t≤100) — the number of test cases in the input.

Then the test cases follow, each of them is represented by a separate line containing one integer n (2≤n≤105) — the maximum number of segments that can be turned on in the corresponding testcase.

It is guaranteed that the sum of n over all test cases in the input does not exceed 105.

Output
For each test case, print the greatest integer that can be displayed by turning on no more than n segments of the screen. Note that the answer may not fit in the standard 32-bit or 64-bit integral data type.

题意：给了1~9中每个数字需要多少个木棍组成
然后选择给了你n个木棍 求能表示的最多数字
思路：可以发现 我们优先让能表示的数字越多 则越多 因为位数多 肯定比位数少的大
那么 要求花的木棍比较少 所以就是数字1 一个1要两个木棍
如果木棍个数是偶数 只要输出n/2个1就好
如果是奇数 多了一个木棍 我们发现三个木棍可以组成一个7 所以输出一个7 然后输出
(n-3)/2个1即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int main()
{
 
    int t;cin>>t;
    while(t--){
 
        int n;
        cin>>n;
        if(n&1) cout<<7,n-=3;
        
        int num=n/2;
        
        while(num--) cout<<1;
        puts("");
 
    }
 
    return 0;
}
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

B. Infinite Prefixes
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given string s of length n consisting of 0-s and 1-s. You build an infinite string t as a concatenation of an infinite number of strings s, or t=ssss… For example, if s= 10010, then t= 100101001010010…

Calculate the number of prefixes of t with balance equal to x. The balance of some string q is equal to cnt0,q−cnt1,q, where cnt0,q is the number of occurrences of 0 in q, and cnt1,q is the number of occurrences of 1 in q. The number of such prefixes can be infinite; if it is so, you must say that.

A prefix is a string consisting of several first letters of a given string, without any reorders. An empty prefix is also a valid prefix. For example, the string “abcd” has 5 prefixes: empty string, “a”, “ab”, “abc” and “abcd”.

Input
The first line contains the single integer T (1≤T≤100) — the number of test cases.

Next 2T lines contain descriptions of test cases — two lines per test case. The first line contains two integers n and x (1≤n≤105, −109≤x≤109) — the length of string s and the desired balance, respectively.

The second line contains the binary string s (|s|=n, si∈{0,1}).

It’s guaranteed that the total sum of n doesn’t exceed 105.

Output
Print T integers — one per test case. For each test case print the number of prefixes or −1 if there is an infinite number of such prefixes.

题意：就是说给了一个字符串 和一个数字x
然后 说你可以让无数个这个字符串拼接在一起
问让前缀0的个数减去前缀1的个数 为x的 前缀个数有多少种

思路：前缀和 记录下num(0)-num(1) 如果最后一个的差为0 那么就是无限个 或者0个 需要判断一下 其他的 只要取枚举长度 x-前缀的差 看x是不是能被整个字符串的差整除即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
int a[200005],b[200005],qz[200005];
string s;
void solve()
{
    map<ll,ll>mp;
    ll n,x;
    cin>>n>>x>>s;
    qz[0]=0;
    for(int i=0; i<n; i++)
        if(s[i]=='0')
            qz[i+1]=qz[i]+1;
        else
            qz[i+1]=qz[i]-1;
    if(!qz[n])
    {
        int f=0;
        for(int i=0; i<=n; i++) if(qz[i]==x) {f=1;break;}
        puts(f?"-1":"0");
    }
    else
    {
        ll qq=0;
        for(int i=0; i<=n; i++)
        {
            ll tt=x-qz[i];
            if(!(tt%qz[n]))
            {
                if(tt/qz[n]>=0 && !mp[(tt/qz[n])*n+i])
                {
                    qq++;
                    mp[(tt/qz[n])*n+i]=1;
                }
            }
        }
        printf("%lld\n",qq);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}
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
50
51
52

C. Obtain The String
time limit per test1 second
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two strings s and t consisting of lowercase Latin letters. Also you have a string z which is initially empty. You want string z to be equal to string t. You can perform the following operation to achieve this: append any subsequence of s at the end of string z. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements. For example, if z=ac, s=abcde, you may turn z into following strings in one operation:

z=acace (if we choose subsequence ace);
z=acbcd (if we choose subsequence bcd);
z=acbce (if we choose subsequence bce).
Note that after this operation string s doesn’t change.

Calculate the minimum number of such operations to turn string z into string t.

Input
The first line contains the integer T (1≤T≤100) — the number of test cases.

The first line of each testcase contains one string s (1≤|s|≤105) consisting of lowercase Latin letters.

The second line of each testcase contains one string t (1≤|t|≤105) consisting of lowercase Latin letters.

It is guaranteed that the total length of all strings s and t in the input does not exceed 2⋅105.

Output
For each testcase, print one integer — the minimum number of operations to turn string z into string t. If it’s impossible print −1.

题意：给了两个字符串 s和t 让构造一个字符串z 使得z等于t
z可以由字符串s的序列中获取 问最小操作数

思路：如果字符串t中的字母 s中不存在 那么就是-1
否则就一定可以 那么暴力找的话 复杂度就是两个字符串长度的乘积 显然不可取
所以 我们可以这样 ans[i][j]表示i位置的下一个字符串为j的位置
这样整体复杂度只要O(len(t))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
string s,t;
int a[200005],b[200005],ans[200005][30];
void Init()
{
    for(int i=0; s[i]; i++)
        a[i+1]=s[i]-'a'+1;
 
    for(int i=0; t[i]; i++)
        b[i+1]=t[i]-'a'+1;
    int len=s.size();
    for(int i=1; i<=26; i++)
        ans[len+1][i]=len+1;
}
void solve()
{
    Init();
    int e=s.size();
    for(int i=e; i>=1; i--)
    {
        for(int j=1; j<=26; j++)
        {
            if(a[i]==j)
                ans[i][j]=i;
            else
                ans[i][j]=ans[i+1][j];
        }
    }
    int q=1,ok=0;
    int len=t.size();
    while(q<=len)
    {
        ok++;
        if(ans[1][b[q]]-1==e)
            break;
        int num=1;
        while(ans[num][b[q]]!=e+1&&q<=len)
        {
            num=ans[num][b[q]]+1;
            q++;
        }
    }
    if(q-1==len)
        printf("%d\n",ok);
    else
        puts("-1");
}
int main()
{
    int T;
    cin>>T;
    while(T--){
            
        cin>>s>>t;
        solve();
    }
    return 0;
}
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

PROBLEMSSUBMIT CODEMY SUBMISSIONSSTATUSHACKSSTANDINGSCUSTOM INVOCATION
D. Same GCDs
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You are given two integers a and m. Calculate the number of integers x such that 0≤x<m and gcd(a,m)=gcd(a+x,m).

Note: gcd(a,b) is the greatest common divisor of a and b.

Input
The first line contains the single integer T (1≤T≤50) — the number of test cases.

Next T lines contain test cases — one per line. Each line contains two integers a and m (1≤a<m≤1010).

Output
Print T integers — one per test case. For each test case print the number of appropriate x-s.

题意 ：给了a和m 现在问gcd(a,m)=gcd(a+x,m) 且0≤x＜m 满足的x的个数有多少个
思路：
记gcd(a,m)=k gcd(a+x,m)=gcd((a+x)%m,m)=k
因为gcd(a,b)=gcd(b,a%b) 这里代入一下 a+x和m 即可知道上式

记(a+x)%m=b
则有 0≤b＜m 即gcd(b,m)=k 且b＜m
则 gcd(b/k,m/k)=1 b/k＜m/k
所以就是求euler(m/k) 也就是在1~m/k间 与m/k互质的数的个数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define pb(a) push_back(a)
#define pa pair<int,int>
#define fi first
#define se second
ll a,m;
ll el(ll x)
{
    ll q=x,w=x;
    for(ll i=2; i*i<=w; i++){
 
        if(w%i==0){
            while(w%i==0) w/=i;
            q=q/i*(i-1);
        }
    }
    if(w>1) q=q/w*(w-1);
 
    return q;
}
void solve()
{
    int T;cin>>T;
    while(T--){
 
       cin>>a>>m;
       cout<<el(m/__gcd(a, m))<<endl;
   }
}
int main()
{
    solve();
    return 0;
}
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

看完如果觉得写的还不错 能看懂 麻烦给个赞 码字不易
有更好的更简单的做法的 也欢迎大佬指教