/*
又是AK局...
hjc又双叒叕AK了...
Hmmm...我侥幸
*/
Problem A card
给出无序序列a[]可以选择一个数插入到合适的位置作为一次操作，至少多少次操作后可以把序列变成有序。
对于100%的数据，序列长度 $l\leq5e5$
Solution ： 最长上升子序列(LIS)-n
这个是显然的结论，最优的话一定是保证LIS情况下，把除LIS外的数依次加到有序的LIS里面刚好加了这么多个。
所以答案是n-LIS，最优性显然: LIS保证需要插入的数字数量最少，而需要插入的数字最少只需要1步移动就一定可以保证把数列LIS增加1.
O(n log2 n)复杂度求LIS是这道题的关键。记f[i]表示长度为i的上升子序列末尾元素最大是多少。
显然当i变大的时候f[i]单调不降，有单调性，可以二分优化转移。找到第1个j，$f[j] \leq a[i]$，转移就行。
注意这个需要最大化j才能保证转移最优，所以是upper_bound而不是lower_bound。
# pragma G++ optimize()
# include <iostream>
# include <cstring>
# include <cstdio>
# include <algorithm>
using namespace std;
const int N=1e6+;
int a[N],ans,n,f[N];
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
int main()
{
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
n=read();
int ans=;
for (int i=;i<=n;i++) a[i]=read();
memset(f,0x3f,sizeof(f));
f[]=a[];
for (int i=;i<=n;i++) {
int p=upper_bound(f,f++n,a[i])-f-;
if (p==-) { f[]=min(f[],a[i]); ans=max(ans,); continue;}
ans=max(ans,p+);
f[p+]=min(f[p+],a[i]);
}
cout<<n-ans<<'\n';
return ;
}
Card.cpp
Problem B pikaqiu
给出n*m的地图每个点可以是石头(1)和路(0)，经过路的代价是1，经过石头的代价是5，有起点(5)和终点(9)，问起点到终点最小代价是多少，
若代价大于可支付的能量T，输出-1，否则输出剩余能量。
对于100%的数据： $n,m\leq 500$
Solution ： 拆点跑Dijkstra最短路，考虑一个点和上下左右四个点有有向连边，若这个点是石头那么建长为5的边否则建长为1的边
然后这个图变成是n2个点，4n2条边的有向图，然后跑Dijkstra，求出[s,t]的最短路即可。（注意一定是单向加边，由于重边会导致本来是石头的边变成路，造成冲突）
-spfa已经死了 -不他没活过
复杂度O(n2 log2 n2)
# pragma G++ optimize()
# include <iostream>
# include <cstring>
# include <algorithm>
# include <cstdio>
# include <queue>
using namespace std;
const int N=1e6+;
const int dx[]={-,,,};
const int dy[]={,,,-};
int T,n,m;
int head[N],d[N],mp[N];
int s,tot=,INF;
bool vis[N];
struct record{
int pre,to,w;
}a[N<<];
# define Num(i,j) (m*(i-)+j)
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void adde(int u,int v,int w)
{
a[++tot].pre=head[u];
a[tot].to=v;
a[tot].w=w;
head[u]=tot;
}
struct rec{
int id,lenth;
bool operator < (const rec a)const{
if (lenth!=a.lenth) return lenth>a.lenth;
else return id>a.id;
}
};
priority_queue<rec>q;
int dijkstra(int s,int e)
{
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));INF=d[];d[s]=;
rec Node; Node.id=s; Node.lenth=; q.push(Node);
while (! q.empty()){
rec Node=q.top(); q.pop();
int u=Node.id;
if (vis[u]==true) continue;
vis[u]=true;
for (int i=head[u];i!=;i=a[i].pre){
int v=a[i].to;
if (d[v]-a[i].w>d[u]) {
d[v]=a[i].w+d[u];
rec N; N.id=v;N.lenth=d[v];
q.push(N);
}
}
}
return d[e];
}
int main()
{
freopen("pikaqiu.in","r",stdin);
freopen("pikaqiu.out","w",stdout);
T=read(); n=read(); m=read();
int Str,End;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++) {
int t=Num(i,j);mp[t]=read();
if (mp[t]==) Str=t;
else if (mp[t]==) End=t;
}
for (int i=;i<=n;i++)
for (int j=;j<=m;j++) {
int now=Num(i,j); for (int tp=;tp<;tp++) {
int x=i+dx[tp],y=j+dy[tp];
if (x<||x>n||y<||y>m) continue;
int num=Num(x,y);
if (mp[num]==) adde(now,num,);
else adde(now,num,);
}
}
int Ans=dijkstra(Str,End);
if (Ans>=T) puts("-1");
else cout<<T-Ans<<'\n';
return ;
}
pikaqiu.cpp
Problem C min
一个含有n项的数列a[]，求出每一项前面的第m个数到它这个区间内的最小值Mini
对于100%的数据 $n\leq 1e7$
Solution :
单调队列题目，显然给了60%的线段树的暴力分。考虑O(n)做法。
弄一个双端队列deque然后前面弹出不在范围内的数，后面弹出不优的数和插入一个新的数。
队列维护的是下标单增，值单增的数列，同时保证在范围内，取数时取队头。
luogu 滑动窗口 单调队列裸题。
# pragma G++ optimize()
# include <deque>
# include <iostream>
# include <cstdio>
using namespace std;
const int N=1e6+;
int a[N],n,m;
deque<int>q;
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
void write(int x)
{
if (x<) x=-x,putchar('-');
if (x>) write(x/);
putchar(''+x%);
}
signed main()
{
freopen("min.in","r",stdin);
freopen("min.out","w",stdout);
n=read();m=read();
int Test=;
for (int i=;i<=n;i++) a[i]=read();
for (int i=;i<=n;i++) {
while (!q.empty()&&q.front()<i-m) q.pop_front();
while (!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
q.push_back(i);
write(a[q.front()]);putchar(' ');
}
putchar('\n');
return ;
}
min.cpp
Problem D smrtfun
给出n个数对$(left_i,right_i)$选出若干组，
最大化 $\sum\limits_{i=1}^k left_i + \sum\limits_{i=1}^k right_i$ 且 $ \sum\limits_{i=1}^k left_i \geqslant 0 , \sum\limits_{i=1}^k right_i \geqslant 0$
对于100%的数据 $n \leq 100$
Solution： 背包问题，令$f[i][j]$表示前i个数对，$left$求和等于$k$，$right$求和的最大值。
转移比较简单就是 $f[i][j]=max \{ f[i-1][j],f[i-1][j-left_{now}]+right_{now} \} $
答案就是 max{f[n][j]} (0<=j<=INF)
然后初始值比较恶心，f[0][]都是负无穷，然后f[0][0]=0
然而c++没有下标为负数的数组，需要加上基底E=1e5才行，
时间复杂度O(n*mx2)
# pragma G++ optimize()
# include <iostream>
# include <cstdio>
# include <cstring>
# define left Lift
# define right Right
using namespace std;
const int N=,M=1e5+;
const int E=1e5;
const int INF=1e5-;
int f[N][M<<];
int left[N],right[N];
int n,mx,ans;
int max(int x,int y) {return (x>y?x:y);}
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
int main()
{
freopen("smrtfun.in","r",stdin);
freopen("smrtfun.out","w",stdout);
n=read();
for (int i=;i<=n;i++)
left[i]=read(),right[i]=read();
memset(f[],~0x3f,sizeof(f[]));
f[][E]=;
for (int i=;i<=n;i++)
for (int j=-INF;j<=INF;j++) {
f[i][j+E]=f[i-][j+E];
if (j-left[i]<-INF||j-left[i]>INF) continue;
f[i][j+E]=max(f[i-][j-left[i]+E]+right[i],f[i][j+E]);
}
for (int j=;j<=INF;j++) if (f[n][j+E]>=) ans=max(ans,f[n][j+E]+j);
cout<<ans<<'\n';
return ;
}
smrtfun.cpp