当前位置：网站首页>Codeforces Round ＃736 (Div. 2) (A-D)

Codeforces Round ＃736 (Div. 2) (A-D)

2022-07-18 01:52:00 【51CTO】

A. Gregor and Cryptography

The question ：

Let you choose two numbers to make n Modulus is equal to these two numbers , Guarantee n Is prime and greater than 5

analysis ：

We know n Is prime and greater than 5, Then he must be an odd number , So we export it directly 2 and n-1 that will do .

1.

B. Gregor and the Pawn Game

The question ：

Give you a,b Two arrays , Then let you control b Array of 1 Location , He can move to a There are two ways ：

When b Array i Location is 1, If a Array i Location is 0 It must be above ,
When b Array i Location is 1, If a Array (i-1) Location is 1 Can move to (i-1) Similarly, you can move (i+1)

One place can store at most one , Ask at most ？

analysis ：

It can be simulated directly , Just put it , You can't just jump over , Judge from three situations , Select from i Is the position 0 Judge , Pay attention to the marking 1 The location of .

       
       ll n;
       
string str, s;
       
map<ll, ll>mp;
       
void solve()
       
{
       
    mp.clear();
       
    cin >> n;
       
    cin >> str >> s;
       
    ll sum = 0;
       
    for(int i = 0; i < n; i++)
       
    {
       
        if(s[i] == '1')
       
        {
       
            if(mp[i] == 0 && str[i] == '0')
       
            {
       
                sum++;
       
                mp[i] = 1;
       
            }
       
            else if(i - 1 >= 0 && mp[i - 1] == 0 && str[i - 1] == '1')
       
            {
       
                sum++;
       
                mp[i - 1] = 1;
       
            }
       
            else if(i + 1 < n && mp[i + 1] == 0 && str[i + 1] == '1')
       
            {
       
                sum++;
       
                mp[i + 1] = 1;
       
            }
       
        }
       
    }
       
    cout << sum << endl;
       
}
      
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.

C. Web of Lies

The question ：

n Number ,m side , Three operations ：

Add edge u and v Make sure there is no such side before
Delete edge u and v Make sure there is this side before
Inquire about , Finally, there are a few points left , The principle is to make contributions if there is no connection at this point , Remove the smallest point value by connecting the edges , Finally, they are all isolated .

analysis ：

Let's calculate the point with small value on the edge , Because the deletion point is from small to large , If , This dot is connected with a dot larger than him , Then it must be deleted , So we only need to maintain the number that is not connected by him , Each update only needs to maintain whether there is a larger number difference than him .

       
       ll n,m;
       
string str, s;
       
map<ll, ll>mp;
       
void solve()
       
{
       
    mp.clear();
       
    scanf("%lld%lld",&n,&m);
       
    ll sum=n;
       
    for(int i=1;i<=m;i++){
       
        ll u,v;
       
        scanf("%lld%lld",&u,&v);
       
        if(u<v) swap(u,v);// u>v;
       
        if(mp[v]==0){
       
            sum--;          
       
        }
       
        mp[v]++;
       
    }
       
    ll k;
       
    cin>>k;
       
    while(k--){
       
        ll op;
       
        scanf("%lld",&op);
       
        if(op==3){
       
            printf("%lld\n",sum);
       
        }else if(op==1){
       
            ll u,v;
       
            scanf("%lld%lld",&u,&v);
       
            if(u<v) swap(u,v);// u>v;
       
            if(mp[v]==0){
       
                sum--;          
       
            }
       
            mp[v]++;
       
        }else{
       
            ll u,v;
       
            scanf("%lld%lld",&u,&v);
       
            if(u<v) swap(u,v);// u>v;
       
            if(mp[v]==1){
       
                sum++;          
       
            }
       
            mp[v]--;
       
        }
       
    }
       
}
      
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.

D. Integers Have Friends

The question ：

After a continuous number takes a modulus of a number, the value is equal , For maximum length .

analysis ：

We are equal after taking a pair of modules , hear , Their difference must be gcd>1 Because only in this way can we take modulus equality , So the problem turns into maintenance interval gcd, Find the longest interval gcd>1 The length of . RMQ Can maintain , If you are interested, you can learn .

       
       ll gcd(ll a,ll b){
       
    while(b){
       
        ll tmp=a%b;
       
        a=b;
       
        b=tmp;
       
    }
       
    return a;
       
}
       
ll a[maxn],b[maxn],n;
       
ll log_n[maxn];
       
ll dp[maxn][33];
       
void LOG(){
       
    log_n[1]=0;
       
    for(int i=2;i<=n+1;i++){
       
        log_n[i]=log_n[i/2]+1;
       
    }
       
}
       
void RMQ(){
       
    for(int i=1;i<=n;i++){
       
        dp[i][0]=abs(b[i]);
       
    }
       
    for(int j=1;(1<<j)<=n;j++){
       
        for(int i=1;i+(1<<(j-1))<=n;i++){
       
            dp[i][j]= gcd(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
       
        }
       
    }
       
}
       
ll serch(ll l,ll r){
       
    ll k = log_n[r-l+1];
       
    return gcd(dp[l][k],dp[r-(1<<k)+1][k]);
       
}
       
bool check(ll x){
       
    if(x==1) return true;
       
    for(int i=1;i<=n;i++){
       
        ll j=i+x-1;
       
        if(j>n) break;
       
        if(serch(i+1,j)>=2) return true;
       
    }
       
    return false;
       
}
       
void solve()
       
{
       
    scanf("%lld",&n);
       
    for(int i=1;i<=n;i++){
       
        scanf("%lld",&a[i]);
       
        b[i]=abs(a[i]-a[i-1]);
       
    }
       
    LOG();
       
    RMQ();
       
    ll l=1,r=n;
       
    ll ans=2;
       
    while(l<=r){
       
        ll mid=(l+r)/2;
       
        if(check(mid)) {
       
            ans=mid;
       
            l=mid+1;
       
        }
       
        else r=mid-1;
       
    }
       
    cout<<ans<<endl;
       
}
      
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.