3547. 特殊数字 【签到题】

https://www.acwing.com/problem/content/3550/

#include<bits/stdc++.h>
using namespace std;
bool check(int x)
{
    int sum=0;
    while(x) sum+=x%10,x/=10;
    return sum%4?0:1;
}
int main(void)
{
    int n; cin>>n;
    while(n) if(check(n++)) break;
    cout<<n-1;
    return 0;
}

3548. 双端队列 【难度: 中 / 思维 映射】

https://www.acwing.com/problem/content/3551/

题目的意思就是给你一个数你可以左边插入队，右边插入队。求你某一个数到队头和队尾的距离中小的那个距离。

思路: 对于每一个数我们将其映射到下标，
用当前的下标减去左端点就等于到队头的距离
用右端点减去其当前的下标就等于到队尾的距离
两者取较小的数.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
map<int,int> mp;
int l=0,r=-1;
int main(void)
{
    int n; cin>>n;
    while(n--)
    {
        string op; int x; cin>>op>>x;
        if(op=="L") mp[x]=--l;
        if(op=="R") mp[x]=++r;
        if(op=="?")
        {
            cout<<min(mp[x]-l,r-mp[x])<<endl;
        }
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e5*3+10;
int a[N],n;
int main(void)
{
    cin>>n;
    int l=0,r=0;
    while(n--)
    {
        string op; cin>>op;
        int x; cin>>x;
        if(op=="L")
        {
            a[x]=--l;
        }
        if(op=="R")
        {
            a[x]=++r;
        }
        if(op=="?")
        {
            if(a[x]<0) cout<<min(abs(a[x]-l),r+abs(a[x])-1)<<endl;
            else cout<<min(abs(a[x]-r),abs(l)+a[x]-1)<<endl;
        }
    }
    return 0;
}

3549. 最长非递减子序列 【难度: 中 / 知识点: DP 思维】

https://www.acwing.com/problem/content/3552/

题目分析:

最优的一定是这种11221122
只有这样翻转后才最优变成11112222
对于给定的字符串有以下四种状态：

• 11111…
• 11112222…
• 11111122221111…
• 1111222211112222…

我们将四种状态分别设为s1 ,s2 ,s3 , s4
可以得出如下的状态转移方程:

• 如果当前读入的是1 则 s1++
• 如果当前读入的是2 则 s2可以由两种状态转移过来一种是从s1转移过来，一种是从s2本身转移过来。
  故转移方程为s2=max(s1+1,s2+1)
• 如果当前读入的是1 则 s3可以由两种状态转移过来一种是从s2转移过来，一种是从s3本身转移过来。
  故转移方程为s3=max(s2+1,s3+1)
• 如果当前读入的是2 则 s4可以由两种状态转移过来一种是从s3转移过来，一种是从s4本身转移过来。
  故转移方程为s4=max(s3+1,s4+1)

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int s1,s2,s3,s4;
int main(void)
{
    int n; cin>>n;
    while(n--)
    {
        int x;cin>>x;
        if(x==1)
        {
            s1=s1+1;
            s3=max(s2+1,s3+1);
        }
        else
        {
            s2=max(s1+1,s2+1);
            s4=max(s3+1,s4+1);
        }
    }
    cout<<max(s3,s4)<<endl;
    return 0;
}