Codeforces round 804 (Div. 2) [competition record]

A — The Third Three Number Problem

        A The question is easy to find ,n There is no solution when it is an odd number ,n For even when ,n/2,n/2,0 that will do .

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int Mod=998244353;
int main(){
    int t,n;sc(t);
    while(t--){
        sc(n);
        if(n%2==0){
            printf("%d %d 0\n",n/2,n/2);
        }else{
            printf("-1\n");
        }
    }
}

B — Almost Ternary Matrix

        Construction question , It's easy to find

1 0 0 1 ...
0 1 1 0 ...
0 1 1 0 ...
1 0 0 1 ...
1 0 0 1 ...
...

          It can be constructed in this form .

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int Mod=998244353;
int dp[100][100];
int main(){
    int t,n;sc(t);
    while(t--){
        int m;sc(n);sc(m);
        int x=1;
        int num=x;
        for(int j=1;j<=m;j+=2){
            dp[1][j]=num;
            dp[1][j+1]=num^1;
            num^=1;
        }
        for(int i=2;i<n;i+=2){
            num=x^1;x=x^1;
            int temp=num;
            for(int k=i;k<=i+1;k++){
                num=temp;
                for(int j=1;j<=m;j+=2){
                    dp[k][j]=num;
                    dp[k][j+1]=num^1;
                    num^=1;
                }
            }
        }
        num=x^1;
        for(int j=1;j<=m;j+=2){
            dp[n][j]=num;
            dp[n][j+1]=num^1;
            num^=1;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                printf("%d ",dp[i][j]);
            }
            printf("\n");
        }
    }
}

C — The Third Problem

        C Question is the most regrettable one . Now let's talk about my game Wrong thinking ：0 and 1 The position of is immutable ,0 and 1 In the middle of the position 2,3,4,5...x(x yes 0 and 1 Sequence number that does not exist in the middle of the position ) Number , These figures must be 0 and 1 Place between positions , And find 0 and 1 Out of position x,x+1,x+2...y(y yes 0 and 1 Sequence numbers that do not exist outside the middle of the position ), These figures must not be moved , The remaining numbers are all arranged .（ Unfortunately, it's almost the positive solution , It's so delicious T-T）

The right way of thinking ： It's easy to find ,0 and 1 The position of is immutable , The interval assumption at this time is 【l,r】, If the number 2 Appear in this interval , be 2 Must move in this range , Do not leave this interval , be 2 The number of possible positions is r-l-1（ The number is i when , The number of species is r-l+1-i）; If 2 Appear outside this interval , that 2 It must not move , The interval is expanded to 【l,pos[2]】 perhaps 【pos[2],r】, And so on .

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int mod=1e9+7;
int a[Max];
int pos[Max];
int main(){
    int t,n;sc(t);
    while(t--){
        sc(n);
        for(int i=1;i<=n;i++){
            sc(a[i]);pos[a[i]]=i;
        }
        int l=pos[0],r=pos[0];
        ll ans=1;
        for(int i=1;i<n;i++){
            if(pos[i]<l) l=pos[i];
            else if(pos[i]>r) r=pos[i];
            else ans*=(r-l+1-i),ans%=mod;
        }
        printf("%lld\n",ans);
    }
}

D — Almost Triple Deletions

Theorem ： Array a1,a2,a3...an Conditions that can be deleted completely ：

1.n For the even .

2. The maximum frequency of any element in the array is n/2.

Definition ： Make dp[i] citing ai And the former i−1 The maximum length of the final array composed of a sub array of elements . first , If the prefix [a1,a2,…,ai−1] It can be deleted completely , be dp[i] Set to 1. otherwise ,dp[i]=0.

If the position a[i]==a[j],i and j Want to merge , that  [aj+1,aj+2,…,ai−1] Must be removable , So we get the recurrence formula

dp[i]=max(dp[i],dp[j]+1),j by i+1~n+1

Be careful ： If we define the final array as coming from the array a  Subarray of equal elements of ,an+1 Is forcibly attached to the subarray , Then the final answer can be written as dp[n+1]− 1. Please note that , In the calculation dp[n+1] when , Should not aj  And an+1 Compare .

#include <bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
const int Max=2e5+5;
const int mod=1e9+7;
int a[Max];
int dp[Max];
int sum[Max],n;
int main(){
    int t;sc(t);
    while(t--){
        sc(n);
        for(int i=1;i<=n;i++) sum[i]=0;
        for(int i=1;i<=n;i++) sc(a[i]);
        int maxa=0;
        for(int i=1;i<=n+1;i++){
            if(i==1) dp[i]=1;
            else if(i%2==0) dp[i]=0;
            else if(maxa>(i-1)/2) dp[i]=0;
            else dp[i]=1;
            sum[a[i]]++;
            maxa=max(maxa,sum[a[i]]);
        }
        for(int i=1;i<=n;i++){
            if(dp[i]==0) continue;
            maxa=0;
            for(int i=1;i<=n;i++) sum[i]=0;
            for(int j=i+1;j<=n+1;j++){
                if((a[i]==a[j]||j==n+1)&&(j-i-1)%2==0&&maxa<=(j-i-1)/2){
                    dp[j]=max(dp[j],dp[i]+1);
                }
                sum[a[j]]++;
                maxa=max(sum[a[j]],maxa);
            }
        }
        printf("%d\n",dp[n+1]-1);
    }
}
/*
1
3 
3 3 1
*/

         summary ： I always thought there was something wrong with the code during the game , I didn't expect that I was wrong , Sit for an hour and a half , In future competitions , Encounter this kind of problem , Jump in time , The most important thing is to re verify whether the idea is wrong .D In fact, the question can be associated with the longest increasing subsequence .