P3960 [NOIP2017]列队-50分暴力

Sylvia 是一个热爱学习的女孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有n×m名学生，方阵的行数为 n，列数为 m。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中的学生从 1 到 n×m 编上了号码（参见后面的样例）。即：初始时，第 ii 行第 jj 列的学生的编号是(i−1)×m+j。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天中，一共发生了 qq件这样的离队事件。每一次离队事件可以用数对(x,y) (1≤x≤n,1≤y≤m)描述，表示第 x 行第 y 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条指令之后，空位在第 x 行第 m列。

向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条指令之后，空位在第 n 行第 m列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后，下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 n 行第 m 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后方阵中同学的编号可能是乱序的。

https://www.luogu.org/problemnew/show/P3960#sub

这是一篇50分暴力题解！！！想要AC的大佬请跳过~~~

相信大部分人在考场上是不会考虑Splay的......毕竟这也不是noip考点！

但是这道题的暴力分足足有50分！！拿到这50分也是很值得的！

因为50%的时候，q是小于等于500的，但是很重要的一点，每一次出队只会影响所在的行和最后一列，也就是说最坏的情况只需要维护500行和最后一列即可！！！

STL：unique是把数组去重后，返回新的数组长度！具体自行百度。

以下具体看50分代码吧~~~

#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
inline int r()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node
{
    int x,y;
}e[300001];
int n,m,q,tot;
ll last[300001],h[300001],pos[501][50001];
ll ans;
int main()
{
    n=r();m=r();q=r();
    for(int i=1;i<=q;i++){
        e[i].x=r();
        e[i].y=r();
        h[i]=e[i].x;//h数组存的是每一次出队人的横坐标
    }
    for(int i=1;i<=n;i++){
        last[i]=last[i-1]+m;//last维护最后一列的编号！
    }
    sort(h+1,h+q+1);//去重之前要排序
    tot=unique(h+1,h+q+1)-h-1;//去重之后原数组只剩下tot大小，也就是说我们只需要维护tot行即可
    ll t;
    for(int i=1;i<=tot;i++){
        t=(ll)(h[i]-1)*m;
        for(int j=1;j<=m;j++){
            pos[i][j]=++t;//给每一行每一列都标上号
        }
    }
    int nx;
    for(int i=1;i<=q;i++){
        for(int j=1;j<=tot;j++){
            if(h[j]==e[i].x){//寻找e[i].x在h数组中的位置，也就是其在去重后的行数
                nx=j;
                break;
            }
        }
        if(e[i].y==m){//如果出队的这个人在最后一列
            ans=last[h[nx]];
        }
        else{
            ans=pos[nx][e[i].y];
        }
        printf("%lld\n",ans);
        if(e[i].y!=m){//向左看齐
            for(int j=e[i].y;j<m-1;j++){
                pos[nx][j]=pos[nx][j+1];
            }
            pos[nx][m-1]=last[h[nx]];
        }
        for(int j=h[nx];j<n;++j){向前看齐
            last[j]=last[j+1];
        }
        last[n]=ans;
    }
    return 0;
}

P3960 [NOIP2017]列队-50分暴力

相关推荐