T1--调换纸牌(card)
Alex有 n张纸牌，每张纸牌上都有一个值ai，Alex把这些纸牌排成一排，希望将纸牌按值从小到大的顺序排好。现在他把这个任务交给你，你只能进行一种操作：选中一张牌，然后插入到这一排纸牌中的任意位置。他想知道最少需要进行几次操作才能将纸牌排好，如果你能用最少的操作达到他的要求，他就请你吃大鸡排^ ^。
解法
求出最长不下降子序列，答案是\(n-len\)。
ac代码
#include<bits/stdc++.h>
#define N 500005
using namespace std;
int len,n;
int a[N],d[N];
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
int find(int x){
int l=1,r=len,mid,ans=0;
while(l<=r){
mid=l+r>>1;
if(d[mid]>x) r=mid-1,ans=mid;
else l=mid+1;
}
return ans;
}
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=read();
len=0;
for(int i=1;i<=n;i++){
int x=find(a[i]);
if(d[x]!=0) d[x]=a[i];
else d[++len]=a[i];
}
printf("%d\n",n-len);
return 0;
}T2--皮卡丘逃亡(pikaqiu)
皮卡丘和小智一行人在经过古代遗迹沙漠的时候被火箭队抓走了，皮卡丘一直在寻找机会逃走，一小时之后，皮卡丘趁火箭队不注意使用高压电击终于脱身，可它却掉落在荒无人烟的地方，皮卡丘没有多少体力了，它希望尽快回到小智身边。沙漠中有很多岩石，有些可以绕过，而有些却阻挡着皮卡丘前进的道路！皮卡丘每走一步都会消耗1点体力值，遇到岩石的时候，为了少跑一些路或者无路可走的时候，皮卡丘可以消耗5点体力值用钢尾来击碎岩石后到达岩石所在位置。已知皮卡丘现有的体力值T，沙漠大小为n*m,皮卡丘不能走出沙漠，因为沙漠外总是潜伏着可怕的黑眼鳄。请问它可以保证体力大于0的情况下到达小智身边吗？如果可以，输出到达能够保存的最大体力值，如果不行则输出-1。
解法
把所有的点都放到一个一维数组，建一个图，跑一遍spfa。
ac代码
#include<bits/stdc++.h>
#define N 505
#define M 1000005
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int to,nt,w;
}E[M<<1];
int a[N][N];
int dis[N*N],H[N*N];
int cnt,tot,n,m,t,s,e;
bool vis[N*N];
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
void addedge(int u,int v,int w){
E[++cnt]=(edge){v,H[u],w}; H[u]=cnt;
}
int calc(int x,int y){
return (x-1)*m+y;
}
void spfa(int s,int e){
queue<int>q;
while(!q.empty())q.pop();
for(int i=1;i<=tot;i++) dis[i]=inf,vis[i]=1;
dis[s]=0; vis[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=1;
for(int e=H[u];e;e=E[e].nt){
int v=E[e].to;
if(dis[u]+E[e].w<dis[v]){
dis[v]=dis[u]+E[e].w;
if(vis[v]){
vis[v]=0;
q.push(v);
}
}
}
}
}
int main(){
t=read(),n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
a[i][j]=read();
if(a[i][j]==5) s=calc(i,j);
if(a[i][j]==9) e=calc(i,j);
}
cnt=0,tot=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
int x=calc(i,j);
tot++;
if(i+1<=n){
if(a[i+1][j]==1) addedge(x,calc(i+1,j),5);
else addedge(x,calc(i+1,j),1);
}
if(i-1>0){
if(a[i-1][j]==1) addedge(x,calc(i-1,j),5);
else addedge(x,calc(i-1,j),1);
}
if(j+1<=m){
if(a[i][j+1]==1) addedge(x,calc(i,j+1),5);
else addedge(x,calc(i,j+1),1);
}
if(j-1>0){
if(a[i][j-1]==1) addedge(x,calc(i,j-1),5);
else addedge(x,calc(i,j-1),1);
}
}
spfa(s,e);
if(dis[e]>t) puts("-1"); else printf("%d\n",t-dis[e]);
return 0;
}T3--区间最小(min)
一个含有n项的数列(n<=1000000)，求出每一项前面的第m个数到它这个区间内的最小值Mini。
解法
非常明显的单调队列，思路：每次将已经超出的全部弹出队首，然后将大于插入数的队尾的数全部弹出，答案就是队首。
ac代码
#include<bits/stdc++.h>
#define N 1000005
using namespace std;
int n,m;
int a[N],p[N];
struct node{
int x,p;
};
struct Queue_o{
node q[N];
int l,r;
void init(){
l=1,r=0;
}
bool empty(){
return l>r;
}
void push_back(node x){
q[++r]=x;
}
node front(){
return q[l];
}
void pop_front(){
l++;
}
node back(){
return q[r];
}
void pop_back(){
r--;
}
}q;
int read(){
int w=0,x=0;char ch=0;
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return w?-x:x;
}
int main(){
q.init();
n=read(),m=read();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=1;i<=n;i++){
while(i-q.front().p>m) q.pop_front();
while(a[i]<q.back().x&&!q.empty()) q.pop_back();
q.push_back((node){a[i],i});
printf("%d ",q.front().x);
}
return 0;
}T4--聪明幽默的(smrtfum)
JYM 的博客非常有名，他在博客里写了N 篇文章，他给每片文章定义了智慧值si 和有趣值fi，他希望选出一些文章来展览使得这些文章的sumsi+sumfi 最大，当然选出的文章的sumsi 和sumfi 的值都不能小于0，这样会使别人觉得他很笨或者很无趣，因为他写的文章太多，就由你告诉他，sumsi+sumfi 的最大值为多少。
解法
简单的背包问题，状态是\(f[i][j]\)表示前\(i\)件物品，\(j\)的\(sums\)下的最大的\(sumf\)
\[f[i][j+s[i]]=max(f[i-1][j]+s[i]+f[i],f[i-1][j+s[i]],f[i]+s[i]]);\]
ac代码
#include<bits/stdc++.h>
#define N 105
using namespace std;
const int base=1e5;
int n,ss[N],sf[N];
int f[N][(int)(1e5)<<1];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&ss[i],&sf[i]);
memset(f,-0x3f,sizeof(f));
f[0][(int)1e5]=0;
for(int i=1;i<=n;i++) for(int j=max(0,-ss[i]);j+ss[i]<2e5;j++) f[i][j+ss[i]]=max(max(f[i-1][j]+ss[i]+sf[i],f[i-1][j+ss[i]]),f[i][j+ss[i]]);
int ans=-1e8;
for(int i=1e5;i+ss[n]<2e5;i++) if(f[n][i]>=i-1e5) ans=max(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}