【ISA的胡策】联校11.8（dp）

T1：

题解：

多队列排序。。。。
我记得很久以前做过“双栈排序”，因为是个栈，考虑两个数字不能在一个栈里的状况，ta比我大而且ta后面有比我小的数字，那恐怕就不能放在一个栈里，然后进行黑白图染色就好咯
我们同样考虑两个数字不能在一个队列里的情况，我们发现只要ta比我小就不能在一个队列里，按照上面的想法连边，我们发现ta只会往后连并且只连比自己小的，我们对于这个链取一个最长的就知道需要多少个队列了！
取一个最长。。。等等，这不就是个最长下降子序列而且是nlogn？
满分咯？

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int g[50005];
int main()
{
    freopen("d.in","r",stdin);
    freopen("d.out","w",stdout);
    int n,k,T,i,a;
    scanf("%d",&T);
    while (T--)
    {
        memset(g,0,sizeof(g));
        scanf("%d%d",&n,&k);
        int tot=0;
        for (i=1;i<=n;i++)
        {
            int l=1,r=tot;
            scanf("%d",&a);
            while (l<=r)
            {
                int mid=(l+r)>>1;
                if (g[mid]<=a) r=mid-1;
                else l=mid+1;
            }
            g[r+1]=a;
            tot=max(tot,r+1);
        }
        if (tot>k) printf("NO\n");else printf("YES\n");
    }
}

T2：

题解：

今天的T2大家全都爆0辣
正解来一波！

代码：

T3：

题解：

这个连边的方式可以用O(n)的单调栈
然后我用的方法是给询问排个序，这样以1为开始的都会在一起（栗子），我们对于这一堆以1为开始的询问求一波spfa，复杂度：？？？
然后就可以拿到30pts并（在30pts里）跑的飞快！
至于满分做法。。。。
十分毒瘤。。。。
要不我也不贴了吧。。。。
哎呀你竟然说我懒！
ISA学长的题解有两页啊喂！

代码：

30pts

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=100005;
struct hh{int x,y,id;}e[N];
int h[N],n,m,l[N],r[N],stack[N];
int tot,nxt[N*2],point[N],v[N*2],dis[N],ans[N];
bool vis[N];
void addline(int x,int y)
{
    ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
    ++tot; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
int cmp(hh a,hh b){return a.x<b.x;}
void spfa(int s)
{
    queue<int>q;
    memset(dis,0x7f,sizeof(dis));
    q.push(s);
    dis[s]=0;
    memset(vis,0,sizeof(vis));
    while (!q.empty())
    {
        int now=q.front(); q.pop(); vis[now]=0;
        for (int i=point[now];i;i=nxt[i])
          if (dis[v[i]]>dis[now]+1)
          {
            dis[v[i]]=dis[now]+1;
            if (!vis[v[i]]) vis[v[i]]=1,q.push(v[i]);
          }
    }
}
int main()
{
    freopen("f.in","r",stdin);
    freopen("f.out","w",stdout);
    int i,top=0;
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++) scanf("%d",&h[i]),l[i]=1,r[i]=n;
    for (i=1;i<=n;i++)//右边达到的 
    {
        while (top&&h[stack[top]]<h[i])
        {
            addline(stack[top],i);
            top--;
        }
        stack[++top]=i;
    }
    top=0;
    for (i=n;i>=1;i--)//左边达到的 
    {
        while (top&&h[stack[top]]<h[i])
        {
            addline(stack[top],i);
            top--;
        }
        stack[++top]=i;
    }
    for (i=1;i<=m;i++) 
    {
        int x,y;
        scanf("%d%d",&x,&y);
        e[i].x=min(x,y); e[i].y=max(x,y);
        e[i].id=i;
    }
    sort(e+1,e+m+1,cmp);
    for (i=1;i<=m;i++)
      if (e[i].x!=e[i-1].x)
      {
        spfa(e[i].x);
        ans[e[i].id]=dis[e[i].y];
      }
      else ans[e[i].id]=dis[e[i].y];
    for (i=1;i<=m;i++) printf("%d\n",ans[i]);
}