AcWing第一场周赛

AcWing有周赛了，好耶

A 特殊数字

从a往后枚举，每次算数位和，判断

码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
const int INF=0x3f3f3f3f;

int a,sum=0,tot=0,n;

int main(){

    scanf("%d",&a);

    for(int i=a;i;i++){
        n=i;
        sum=0;
        while(n){
            sum+=n%10;
            n/=10;
        }
        if(sum%4==0){
            cout<<i<<endl;
            return 0;
        }
    }
    
    
    return 0;
}

B 双端队列

题意：实现一个双端队列，支持三个操作：在队列左端插入数，在队列右端插入数，查询取出在队列里的某个数最少要弹出多少数

解：将每个数映射到其位置上，查询时取其位置与左右端点距离最小值

码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
const int INF=0x3f3f3f3f,N=200010;

int mapp[N],n,l=0,r=-1;

int main(){
    
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        char op;
        int x;
        cin>>op;
        scanf("%d",&x);
        if(op=='L') mapp[x]=--l;
        else if(op=='R') mapp[x]=++r;
        else printf("%d\n",min(mapp[x]-l,r-mapp[x]));
    }

    return 0;
}

C 最长非递减子序列

题意：给定一个长为n的12序列，翻转其中的一段，使得翻转后最长非递减子序列最长，求最长序列的长度

解：在序列中只有12两个数，所以非递减子序列可以抽象成前面一段是1，后面一段是2，这两段长度可以为0，所以我们要求的就是11...1122...2211...1122...22的长度，可以记录下每一段相同数字序列的最后一位下标，进行DP，转移方程为

\[\begin{cases} a=a+1&mapp[i]=1\\ b=max(a+1,b+1)&mapp[i]=2\\ c=max(b+1,c+1)&mapp[i]=1\\ d=max(c+1,d+1)&mapp[i]=2 \end{cases} \]

最后的答案就是\(ans=max(c,d)\)

码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<stack>
#include<bitset>
#include<cstring>
#define ll long long
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
using namespace std;
const int INF=0x3f3f3f3f,N=100010;

int n,mapp[N];
int a=0,b=0,c=0,d=0;

int main(){

    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&mapp[i]);
    for(int i=1;i<=n;i++){
        if(mapp[i]==1){
            a=a+1;
            c=max(b+1,c+1);
        }else{
            b=max(a+1,b+1);
            d=max(c+1,d+1);
        }
    }
    printf("%d",max(c,d));
    
    return 0;
}