特殊数字

特殊数字
送分题，没啥好说的

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int n,l=0,r=-1;
map<int,int> m;

int main() {
    cin>>n;
    while(n--) {
        char opt;
        int x;
        cin>>opt>>x;
        if(opt=='L')
          m[x]=--l;
        if(opt=='R')
          m[x]=++r;
        if(opt=='?')
          cout<<min(abs(l-m[x]),abs(m[x]-r))<<endl;
    }
    return 0;
}

双端队列

双端队列

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+5;
int n,l=0,r=-1; //；类似莫队的思想，当前维护[l,r]这一区间
map<int,int> m;

int main() {
    cin>>n;
    while(n--) {
        char opt;
        int x;
        cin>>opt>>x;
        if(opt=='L')
          m[x]=--l; //左端加入，实际上可以不看队列，直接记录位置
        if(opt=='R')
          m[x]=++r; //右端加入
        if(opt=='?')
          cout<<min(abs(l-m[x]),abs(m[x]-r))<<endl; //上文给出的公式
    }
    return 0;
}

最长非递减子序列

最长非递减子序列

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+5;
int n,a[N];
int f[N],g[N];

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%d",&a[i]);
    int ans=0,las=0,maxn=0;
    for(int i=1;i<=n;maxn=max(maxn,f[i]),i++)   //从前往后求LNDS（最长不降子序列）
      if(a[i]==1)
        f[i]=f[las]+1,las=i;
      else
        f[i]=maxn+1;
    las=n+1,maxn=0;
    for(int i=n;i>=1;maxn=max(maxn,g[i]),i--)   //从后往前求LNIS（最长不升子序列）
      if(a[i]==2)
        g[i]=g[las]+1,las=i;
      else
        g[i]=maxn+1;
    for(int i=0;i<=n;i++)   //枚举断点
      ans=max(ans,f[i]+g[i+1]);
    printf("%d",ans);
    return 0;
}

以后的周赛会坚持写总结报告哒~