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

Catalog

A. Palindromic Indices

B. AND Sorting

C. LIS or Reverse LIS?

D. Circular Spanning Tree

---

A. Palindromic Indices

Problem - A - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1682/problem/A

The question : Give you a palindrome string , You can delete a string , Ensure that this palindrome string is still a palindrome string , There are several ways to delete

Ideas : Just delete one of the same characters in the middle paragraph .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n;
    string s;
    cin>>n>>s;
    int cnt=0;
    if(s.size()%2==0)
    {
        int l=(s.size()-1)/2;
        for(int i=l;i>=0;i--)
        {
            if(s[i]==s[l])
                cnt++;
            else 
                break;
        }
        cnt*=2;
    }
    else
    {
        int l=s.size()/2;
        for(int i=l;i>=0;i--)
        {
            if(s[i]==s[l])
                cnt++;
            else 
                break;
        }
        cnt=cnt*2-1;
    }
    cout<<cnt<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

B. AND Sorting

Problem - B - Codeforceshttps://codeforces.com/contest/1682/problem/B

The question : Give you an array , There is the original ascending array ( It was 0,1,2,3...n-1), There is one. x, When (a[i]&a[j])==x When , You can exchange , Asking when x When the maximum is, we can get the array given by the title from the original array .

Ideas : Must let x As a transfer station, you can exchange all the numbers in different positions , It is not in the original position of the digital phase & that will do :

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
#define int long long
using namespace std;
const int N =5e5+10,mod=998244353;
void solve()
{
    int n,x;
    cin>>n;
    int ans=-1;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(ans==-1&&x!=i-1)
        {
            ans=x;
        }
        else if(ans!=-1&&x!=i-1)
        {
            ans&=x;
        }
    }
    cout<<ans<<"\n";
    return ;
}
signed main()
{ 
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

C. LIS or Reverse LIS?

Problem - C - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1682/problem/C

The question : Give you an array , You can rearrange it after , Find the length of its positive strictly longest ascending subsequence and the length of its reverse strictly longest ascending subsequence . Take the minimum of both , Find the minimum value and the maximum value .

Ideas : We use it map Record the number of all array elements ,map The length of is the longest length in ascending order , Then we calculate that each element in this ascending sequence exceeds 2 Number of , Put them on the right , That is, the length of the inverse longest ascending subsequence , However, since the length of the forward longest ascending subsequence on the left may be greater than that of the reverse longest ascending subsequence on the right . We can appropriately move some numbers on the left to the right . for instance :

Array

1 1 1 2 3 4 4 4 4 4 4 5 6 6

After we operate , Put the longest ascending subsequence in reverse and forward on both sides :

1 2 3 4 5 6    6 4 1

At this time, the value of the result is 3, But we found that we can appropriately move some values on the left to the right , It becomes :

1 2 4 5 6      6 4 3 1

The answer can be obtained by the above operation

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
const int N =5e5+10,mod=998244353;
map<int,int>ma;
int a[200005];
void solve()
{ 
    ma.clear();
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>x,ma[x]++;
    if(n==1)
    {
        cout<<"1\n";
        return ;
    }
    int len1=ma.size(),len2=0;
    for(auto &it:ma)
    {
        if(it.second>=2)
            len2++;
    }
    int ans=(len1+len2+1)/2;
    cout<<ans<<"\n";
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}

D. Circular Spanning Tree

Problem - D - Codeforceshttps://codeforces.com/contest/1682/problem/D

The question : Give you a string ,(0-n-1) Corresponding 1-n Parity of degrees of points , When the degree of the current point is odd , The character is expressed as '1', Instead of '0'. We need to construct a tree based on this string .

Ideas : First, rule out the impossible situation . We know that trees exist n-1 Edge adjustment , Then there must be even points with odd degrees , And the degree of these points should be greater than 0. In addition, direct output NO.

Then there is the construction of trees . We can take each point with odd degree as the head of a chain , Because there must be an even number of points with odd degrees , Then there must be an even number of chains , We connect the end of the chain directly ( All connected to the tail of the same chain , This can avoid cross ). In this way, each chain tail has its own degree 1, Then link odd points , Degrees must become even . Then it can be established .

#include<map>
#include<cmath>
#include<set>
#include<queue>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_set>
#include<unordered_map>
using namespace std;
vector<int>wei;
void solve()
{
    wei.clear();
    int n,st=0;
    string s;
    cin>>n>>s;
    int cnt=0,len=s.size();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='1')
            cnt++,st=i;
    }
    if(cnt<2||cnt%2==1)
    {
        cout<<"NO\n";
        return ;
    }
    cout<<"YES\n";
    for(int i=0;i<len;i++)
    {
        if(s[(st+i+1)%len]=='1')   
        {
            wei.push_back((st+i)%len);
            continue;
        }
        cout<<(st+i)%len+1<<" "<<(st+i+1)%len+1<<"\n";
    }
    for(int i=1;i<wei.size();i++)
    {
        cout<<wei[0]+1<<" "<<wei[i]+1<<"\n";
    }
    return ;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
       solve();
    return 0;
}