AcWing第一场周赛

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;
}
上一篇:S2-RCE漏洞复现之S2-008、S2-009、S2-012


下一篇:CSP202104-2领域均值