HGOI 20190218 题解


/*
又是AK局...
hjc又双叒叕AK了...
Hmmm...我侥幸
*/

Problem A card

给出无序序列a[]可以选择一个数插入到合适的位置作为一次操作，至少多少次操作后可以把序列变成有序。

对于100%的数据，序列长度 $lleq5e5$

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(2)
# include <iostream>
# include <cstring> 
# include <cstdio>
# include <algorithm>
using namespace std;
const int N=1e6+10;
int a[N],ans,n,f[N];
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}
int main()
{
    freopen("card.in","r",stdin);
    freopen("card.out","w",stdout);
    n=read();
    int ans=0;
    for (int i=1;i<=n;i++) a[i]=read();
    memset(f,0x3f,sizeof(f));
    f[1]=a[1];
    for (int i=2;i<=n;i++) {
        int p=upper_bound(f,f+1+n,a[i])-f-1;
        if (p==-1) { f[1]=min(f[1],a[i]); ans=max(ans,1); continue;}
        ans=max(ans,p+1);
        f[p+1]=min(f[p+1],a[i]);
    }
    cout<<n-ans<<'
';
    return 0;
}
Card.cpp

Problem B pikaqiu

给出n*m的地图每个点可以是石头(1)和路(0)，经过路的代价是1，经过石头的代价是5，有起点(5)和终点(9)，问起点到终点最小代价是多少，

若代价大于可支付的能量T，输出-1，否则输出剩余能量。

对于100%的数据： $n,mleq 500$

Solution ： 拆点跑Dijkstra最短路，考虑一个点和上下左右四个点有有向连边，若这个点是石头那么建长为5的边否则建长为1的边

然后这个图变成是n2个点，4n2条边的有向图，然后跑Dijkstra，求出[s,t]的最短路即可。（注意一定是单向加边，由于重边会导致本来是石头的边变成路，造成冲突）

-spfa已经死了 -不他没活过

复杂度O(n2 log2 n2)

# pragma G++ optimize(2)
# include <iostream>
# include <cstring> 
# include <algorithm>
# include <cstdio> 
# include <queue> 
using namespace std;
const int N=1e6+10;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
int T,n,m;
int head[N],d[N],mp[N];
int s,tot=0,INF;
bool vis[N];
struct record{
    int pre,to,w;
}a[N<<1];
# define Num(i,j) (m*(i-1)+j)
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),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,127,sizeof(d));INF=d[0];d[s]=0;
    rec Node; Node.id=s; Node.lenth=0; 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!=0;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=1;i<=n;i++)
     for (int j=1;j<=m;j++) {
          int t=Num(i,j);mp[t]=read();
          if (mp[t]==5) Str=t;
          else if (mp[t]==9) End=t;
    }
    for (int i=1;i<=n;i++)
     for (int j=1;j<=m;j++) {
         int now=Num(i,j);
         
         for (int tp=0;tp<4;tp++) {
             int x=i+dx[tp],y=j+dy[tp];
             if (x<1||x>n||y<1||y>m) continue;
             int num=Num(x,y);
             if (mp[num]==1) adde(now,num,5);
             else adde(now,num,1);
         }
     }
     int Ans=dijkstra(Str,End);
     if (Ans>=T) puts("-1");
     else cout<<T-Ans<<'
';
    return 0;
}
pikaqiu.cpp

Problem C min

一个含有n项的数列a[]，求出每一项前面的第m个数到它这个区间内的最小值Mini

对于100%的数据 $nleq 1e7$

Solution : 

单调队列题目，显然给了60%的线段树的暴力分。考虑O(n)做法。

弄一个双端队列deque然后前面弹出不在范围内的数，后面弹出不优的数和插入一个新的数。

队列维护的是下标单增，值单增的数列，同时保证在范围内，取数时取队头。

luogu 滑动窗口 单调队列裸题。

# pragma G++ optimize(2)
# include <deque>
# include <iostream>
# include <cstdio> 
using namespace std;
const int N=1e6+10;
int a[N],n,m;
deque<int>q;
inline int read()
{
    int X=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}
void write(int x)
{
    if (x<0) x=-x,putchar('-');
    if (x>9) write(x/10);
    putchar('0'+x%10);
}
signed main()
{
    freopen("min.in","r",stdin);
    freopen("min.out","w",stdout);
    n=read();m=read();
    int Test=1;
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;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('
');
    return 0;
}
min.cpp

Problem D smrtfun

给出n个数对$(left_i,right_i)$选出若干组，

最大化 $sumlimits_{i=1}^k left_i + sumlimits_{i=1}^k right_i$ 且 $ sumlimits_{i=1}^k left_i geqslant 0 ,  sumlimits_{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(2)
# include <iostream>
# include <cstdio>
# include <cstring>
# define left Lift
# define right Right
using namespace std;
const int N=105,M=1e5+10;
const int E=1e5;
const int INF=1e5-1;
int f[N][M<<1];
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=0,w=0; char c=0;
    while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
    while(c>='0'&&c<='9') X=(X<<3)+(X<<1)+(c^48),c=getchar();
    return w?-X:X;
}
int main()
{
    freopen("smrtfun.in","r",stdin);
    freopen("smrtfun.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++) 
        left[i]=read(),right[i]=read();
    memset(f[0],~0x3f,sizeof(f[0]));
    f[0][E]=0;
    for (int i=1;i<=n;i++)
     for (int j=-INF;j<=INF;j++) {
         f[i][j+E]=f[i-1][j+E];
         if (j-left[i]<-INF||j-left[i]>INF) continue;
         f[i][j+E]=max(f[i-1][j-left[i]+E]+right[i],f[i][j+E]);
     }
     for (int j=0;j<=INF;j++) if (f[n][j+E]>=0) ans=max(ans,f[n][j+E]+j);
    cout<<ans<<'
';
    return 0;
 }
smrtfun.cpp
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ljc20020730/p/10395157.html