#include<iostream>

#include<cstdio>

using namespace std;

inline int read(){

    int x=0; bool f=1; char c=getchar();

    while(!isdigit(c)){if(c=='-') f=0; c=getchar();}

    while(isdigit(c)){x=x*10+c-'0'; c=getchar();}

    if(!f) return 0-x;

    return x;

}

int a,b,c;

int main(){

    a=read(),b=read(),c=read();

    printf("%d",a/5+b/10*3+c/2);

    return 0;

}

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

inline int read(){

    int x=0; bool f=1; char c=getchar();

    while(!isdigit(c)){if(c=='-') f=0; c=getchar();}

    while(isdigit(c)){x=x*10+c-'0'; c=getchar();}

    if(!f) return 0-x;

    return x;

}

int n,q,a[1002],len,query,mod,ans;

int main(){

    n=read(),q=read();

    int i,j;

    for(i=1;i<=n;i++) a[i]=read();

    for(i=1;i<=q;i++){

        len=read(),query=read();

        mod=pow(10,len); //pow(10,len)=10的len次方

        ans=2147483647;

        for(j=1;j<=n;j++) if(a[j]%mod==query) ans=min(ans,a[j]);

            if(ans==2147483647) printf("-1\n");

        else printf("%d\n",ans);

    }

    return 0;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxm 102

#define inf 0x3f3f3f3f

using namespace std;

inline int read(){

    int x=0; bool f=1; char c=getchar();

    while(!isdigit(c)){if(c=='-') f=0; c=getchar();}

    while(isdigit(c)){x=x*10+c-'0'; c=getchar();}

    if(!f) return 0-x;

    return x;

}

struct xy{

    int x,y;

}tmp;

int fx[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

int dp[maxm][maxm],m,n,col[maxm][maxm];

/*

void dfs(int x,int y,int facol,bool magic,int coin){ //考场上首打的超时dfs

    if(x==m && y==m){ans=min(ans,coin); return;}

    int i,j,gx,gy;

    vis[x][y]=1;

    for(i=0;i<4;i++){

        gx=x+fx[i][0],gy=y+fx[i][1];

        if(gx<1 || gx>m || gy<1 || gy>m) continue;

        if(vis[gx][gy]) continue;

        printf("%d %d->%d %d\n",x,y,gx,gy);

        if(!col[gx][gy]){//鏃犺壊鏍煎瓙

            if(magic) continue;//涓嶈兘杩炵画鑶滄硶

            dfs(gx,gy,col[x][y],1,coin+2);

            continue;

        }

        if(facol==col[gx][gy]) dfs(gx,gy,col[x][y],0,coin);//鏍煎瓙棰滆壊鐩稿悓

        else dfs(gx,gy,col[x][y],0,coin+1);

    }

    vis[x][y]=0;

}

*/

queue<xy>q; //

int main(){

    memset(dp,inf,sizeof(dp));

    m=read(),n=read();

    int i,j,x,y,z,gx,gy,_gx,_gy;

    for(i=1;i<=n;i++){

        x=read(),y=read(),z=read();

        if(z==0) col[x][y]=-1;

        else col[x][y]=1;

    }

    q.push((xy){1,1});

    dp[1][1]=0;

    while(!q.empty())

    {

        x=q.front().x,y=q.front().y;

        q.pop();

        if(x==m && y==m) continue;//如果是终点就退出（终点的金币花费在终点被推入队列前就dp过了）

        for(i=0;i<4;i++)

        {

            gx=x+fx[i][0], gy=y+fx[i][1];

            if(gx<1 || gx>m || gy<1 || gy>m) continue;

            if(!col[gx][gy])

            {

            	if(gx==m && gy==m){//特判终点是白色格子的情况，防止终点被跨过

            		if(dp[gx][gy]>dp[x][y]+2)

                        dp[gx][gy]=dp[x][y]+2;

                    continue;

				}

                for(j=0;j<4;j++)

                {

                    _gx=gx+fx[j][0], _gy=gy+fx[j][1];

                    if(_gx<1 || _gx>m || _gy<1 || _gy>m) continue;

                    if(!col[_gx][_gy]) continue;

                    if(col[_gx][_gy]==col[x][y])

                    {

                        if(dp[_gx][_gy]>dp[x][y]+2)

                        {

                            dp[_gx][_gy]=dp[x][y]+2;

                            tmp.x=_gx, tmp.y=_gy;

                            q.push(tmp);

                        }

                    }

                    else if(dp[_gx][_gy]>dp[x][y]+3){

                        dp[_gx][_gy]=dp[x][y]+3;

                        tmp.x=_gx, tmp.y=_gy;

                        q.push(tmp);

                    }

                }

            }

            else{

                if(col[gx][gy]==col[x][y]){

                    if(dp[gx][gy]>dp[x][y]){

                        dp[gx][gy]=dp[x][y];

                        tmp.x=gx, tmp.y=gy;

                        q.push(tmp);

                    }

                }

                else if(dp[gx][gy]>dp[x][y]+1){

                    dp[gx][gy]=dp[x][y]+1;

                    tmp.x=gx, tmp.y=gy;

                    q.push(tmp);

                }

            }

        }

    }

    //dfs(1,1,0,0,0);

    if(dp[m][m]==inf) printf("-1");

    else printf("%d",dp[m][m]);

    return 0;

}

#include <iostream>

#include <cstring>

#include <cmath>

using namespace std;

#define inf 3fffffff

int fx[4] = {-1, 0, 1, 0};

int fy[4] = {0, -1, 0, 1};

int f[110][110];

int mp[110][110];

int m, n, ans = inf;

void dfs(int x, int y, int sum, bool frog) {

    if(x < 1 || y < 1 || x > m || y > m) return;

    if(!mp[x][y]) return;

    if(sum >= f[x][y]) return;

    f[x][y] = sum;

    if(x == m && y == m) {

        if(sum < ans) ans = sum;

        return;

    }

    for(int i = 0; i < 4; ++i) {

        int xx = x+fx[i];

        int yy = y+fy[i];

        if(mp[xx][yy]) {

            if(mp[xx][yy] == mp[x][y])

                 dfs(xx, yy, sum, false);

            else dfs(xx, yy, sum+1, false);

        } else if(!mp[xx][yy] && !frog) {

            mp[xx][yy] = mp[x][y];

            dfs(xx, yy, sum+2, true);

            mp[xx][yy] = 0;

        }

    }

}

int main() {

    memset(f, 0x7f, sizeof(f));

    cin >> m >> n;

    for(int i = 1; i <= n; ++i) {

        int x, y, c;

        cin >> x >> y >> c;

        mp[x][y] = c + 1;

    }

    dfs(1, 1, 0, false);

    if(ans == inf) cout << -1;

    else cout << ans;

    return 0;

}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<queue>

#define maxn 500001

using namespace std;

inline int read(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';

    if(!f) return 0-x;

    return x;

}

int n,d,k,x[maxn],s[maxn],dp[maxn];

int head,tail; //monotone queue 单调队列

struct node{

    int x,s;

}mq[maxn];

void insert(node a){

    while(head<=tail && mq[tail].s <= a.s) tail--;

    mq[++tail]=a;

}

bool judge(int xg){

    queue<node>q;

    head=1,tail=0;

    q.push((node){0,0}); //从第0位开始跳

    //memset(dp,0,sizeof dp); //可以不做memset

    for(int i=1;i<=n;i++){

        while(q.size() && q.front().x <= x[i]-d+xg) {insert(q.front()); q.pop();}

        while(head<=tail && mq[head].x < x[i]-d-xg) head++; //把太靠前的 一下跳不到的位置删掉。另外这句话不能和上句话写反！因为缓冲区的格子有可能直接跑到前面那段能跳到的区间之前！ 

        if(head>tail) continue; //单调队列为空，说明前面没有格子能跳到当前格子

        else dp[i] = mq[head].s + s[i];

        if(dp[i]>=k) return 1;

        q.push((node){x[i],dp[i]});

    }

    return 0;

}

int main(){

    n=read(),d=read(),k=read();

    for(int i=1;i<=n;i++) x[i]=read(),s[i]=read();

    int l=0,r=max(d,x[n]-d),mid;

    bool ok;

    while(l<r){

        mid=(l+r)>>1;

        if(judge(mid)) r=mid, ok=1;

        else l=mid+1;

    }

    if(!ok) printf("-1\n");

    else printf("%d\n",l);

    return 0;

}

#include<iostream>

#include<cstdio>

using namespace std;

inline int read(){

    int x=0; bool f=1; char c=getchar();

    while(!isdigit(c)){if(c=='-') f=0; c=getchar();}

    while(isdigit(c)){x=x*10+c-'0'; c=getchar();}

    if(!f) return 0-x;

    return x;

}

long long a,b;

int main(){

    a=read(),b=read();

    if(a<b) swap(a,b);

    printf("%lld",b*(a-1)-a);

    return 0;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<stack>

#define inf 2147483647

using namespace std;

inline int read(){

    int x=0; bool f=1; char c=getchar();

    while(!isdigit(c)){if(c=='-') f=0; c=getchar();}

    while(isdigit(c)){x=x*10+c-'0'; c=getchar();}

    if(!f) return 0-x;

    return x;

}

int T,L,len,deep,cf,intx,inty,o1=inf;//o1用来记录类似于n 1这样的进不去的循环的深度，它里面（比它更深）的循环内容输入完、记录变量后直接跳过，不算复杂度。等回溯回来时再撤掉o1记录。

//deep和s.size()的意义是一样的，都表示在第几层循环

long long ans,ljcf;//ljcf（累计次方）表示到达当前位置时的时间复杂度为O(n^ljcf)

char c[10],F,I,X[10],Y[10];

bool usedbl[128],deepn[101],CE;//usedbl（used变量）记录变量名称是否使用过，deepn记录哪些循环层的复杂度大于O(1)（回溯的时候需要去掉这些层的复杂度），CE(compile error)用来记录是否编译错误

stack<char> s;//存储当前位置在哪些循环之中

int main(){

    int i,j;

    T=read();

    while(T--){

		//初始化

        CE=deep=0;ans=ljcf=0;

        o1=inf;//一开始没有进不去的循环

        while(!s.empty()) s.pop();

        memset(usedbl,0,sizeof(usedbl));

        memset(deepn,0,sizeof(deepn));

        L=read();

        scanf("%s",c);

        if(c[2]=='1') cf=0;//时间复杂度是O(1)

        else{//时间复杂度是O(n^w)

            cf=c[4]-'0';//读取w，即复杂度值

            if(isdigit(c[5])) cf=cf*10+c[5]-'0';//题中说了w小于100，所以w可能是两位数。所以要判断w是不是两位数

        }

        /*

		//我采用了边读入边直接处理的做法，只要把循环层累放入栈，回溯时删除栈顶的循环层就可以判断循环是否合法了。

		  其实常规思路应该是全输入完后从头尾两端往里夹着算复杂度。

		*/

        for(i=0;i<L;i++){

            cin>>F;//考场上用scanf输入字符串炸了，于是只好全程cin

            //cout<<i<<' '<<deep<<' '<<s.size()<<' '<<o1<<' '<<CE<<'\n';

            if(F=='E'){//退出一层循环。建议先看58行起的进入循环的内容

                if(s.empty() || deep<=0){CE=1;continue;}//E的数量超过F的数量（即在0层循环时还要退），那就编译错误了

                //否则是合法退循环

                if(deepn[deep]){deepn[deep]=0; ljcf--;}//如果这一层的时间复杂度为O(n)，在退出这一层循环时就要减去它的复杂度

                if(deep==o1) o1=inf;//这一层循环是进不去的，那么退掉这层循环之后就要清掉o1变量以确保能进入后面的循环

                deep--;//循环深度-1

                usedbl[s.top()]=0;//将这个变量设为未使用

                s.pop();//弹掉循环层

                continue;

            }

            cin>>I>>X>>Y;

            if(CE) continue;//已经编译错误了，该程序中后面的内容输入完后就不用再管了

            deep++;//循环深度+1

            if(usedbl[I-'a']){CE=1; continue;}//如果变量名被使用过，就记录编译错误，但后面输入的程序内容依然是要输入的，所以不能直接退循环

            usedbl[I-'a']=1;//记录变量已使用过

            s.push(I-'a');//记录当前循环层（的变量名）

            if(deep>=o1) continue;//如果循环是进不去的 ，那记录完循环变量信息后就直接过掉 

            //能到这里说明能正常到达该层，那么该层的复杂度需要算

            if(X[0]=='n' && Y[0]=='n') continue;//X=Y=n，相当于O(1)，直接过

            else if(X[0]=='n'){o1=deep; continue;}//X=n>100, Y<100，相当于进不去，记录o1变量，也过

            else if(Y[0]=='n') ljcf++,deepn[deep]=1;//X<100,y=n>100，相当于O(n)（因为n远大于100，从小于100的数到远大于100的n接近需要O(n)的时间），时间复杂度垒上一个n，这一层做复杂度大于O(1)的标记

            else{

                intx=atoi(X),inty=atoi(Y);//把X和Y转成整数，方便判断大小（不要拿字符串直接比！）

                if(intx>inty) o1=deep;//X>Y，相当于进不去，记录o1变量，直接过

				//否则两个常数的复杂度相当于O(1)，直接过

                continue;

            }

            ans=max(ljcf,ans);//对于刚才的第三种情况，复杂度（ljcf）增加了，需要更新最大的时间复杂度

            //cout<<"deep:"<<deep<<" ljcf:"<<ljcf<<'\n';

        }

        //cout<<ans<<' '<<cf<<'\n';

        if(CE || !s.empty()){printf("ERR\n"); continue;}//编译错误或者还有循环层没有退出。（!s.empty()可替换为deep>0）

        if(ans==cf) printf("Yes\n");//判断最大时间复杂度是否跟预期相同

        else printf("No\n");

    }

    return 0;

}

#include<bits/stdc++.h>

#define MAXN 100001

#define MAXM 200001

using namespace std;

inline int read(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	if(!f) return 0-x;

	return x;

}

struct Edge{

    int u, v, w, next;

}e[MAXM];

int n, m, k, head[MAXN], p, d[MAXN], f[MAXN][55], b[MAXN][55], ans;

bool vis[MAXN], flag; //flag在记忆化搜索时用，flag=1表示有零环，即应输出-1 

void spfa() {

    queue<int> q;

    d[1] = 0;

    q.push(1);

    int i,u;

    while (!q.empty()) {

        u = q.front(); q.pop();

        vis[u] = 0;

        for (i = head[u]; i; i = e[i].next) {

            if (d[e[i].v] > e[i].w+d[u]) { //更新最短距离

                d[e[i].v] = d[u]+e[i].w;

                if (!vis[e[i].v]) { //目标点不在队列里，就将它加入队列

                    vis[e[i].v] = 1;

                    q.push(e[i].v);

                }

            }

        }

    }

}

int dfs(int u, int step) {

    if (b[u][step] == 1 || flag) return flag = 1; //如果有零环就退出。这里能这么判零环是因为刚刚已经以dis(1,u)+step的距离到过这个点而还没退回去，现在却又以dis(1,u)+step的距离到这个点，说明走了一遍零环。于是就可以判了

    if (b[u][step] == 2) return f[u][step]; //剪枝，如果一个点曾经到过（注意是曾经，表示它不在当前路径上），就直接返回它的答案

    b[u][step] = 1; //设置该点正在路径上

    for (int i = head[u], w; i; i = e[i].next) {

        w = step+ d[u]-d[e[i].v]-e[i].w; //注意由于图是反向的，这里的有向边(u,v)在原图中实际上是(v,u)，因此dis[u]=dis[v]+w，e[i].w也就跟d[e[i].v]同号了

        if (w > k || w < 0) continue;

        f[u][step] += dfs(e[i].v, w);

        f[u][step] %= p;

    }

    b[u][step] = 2; //设置该点曾经访问过

    return f[u][step]; //回溯答案

}

int main() {

	int T = read(), i;

    while (T--) {

        memset(head, 0, sizeof(head));

        n = read(), m = read(), k = read(), p = read();

        for (i = 1; i <= m; i++) {

            e[i].u = read(), e[i].v = read(), e[i].w = read();

            e[i].next = head[e[i].u];

            head[e[i].u] = i;

        }

        memset(vis, 0, sizeof(vis));

        memset(d, 127, sizeof(d));

        spfa();

        memset(head, 0, sizeof(head));

        for (i = 1; i <= m; i++) { //将图反向连接，dfs要从终点出发

            swap(e[i].u, e[i].v);

            e[i].next = head[e[i].u];

            head[e[i].u] = i;

        }

        memset(f, 0, sizeof(f));

        memset(b, 0, sizeof(b));

        f[1][0] = 1;

        ans = 0, flag = 0;

        for (i = 0; i <= k; i++) { //枚举与最短路径的差

            ans += dfs(n, i); //因为dfs是回溯，所以要从终点先往起点延伸路径，然后把答案回溯回终点

            ans %= p;

        }

        printf("%d\n", flag ? -1 : ans);

    }

    return 0;

}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline long long read(){

    long long x=0; bool f=1; char c=getchar();

    while(!isdigit(c)){if(c=='-') f=0; c=getchar();}

    while(isdigit(c)){x=x*10+c-'0'; c=getchar();}

    if(!f) return 0-x;

    return x;

}

struct cheese{

    long long x,y,z;

}c[1001];

struct edge{

    int to,next;

}e[(1001*1001)<<1];

int head[1001];

bool vis[1001];

int T,n,cnt;

long long c_h,r;

bool calc(long long x1,long long y1,long long z1,long long x2,long long y2,long long z2){

    if(sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)+(z1-z2)*(z1-z2))<=2*r) return 1;

    else return 0;

}

inline void add(int x,int y){

    e[++cnt].to=y;

    e[cnt].next=head[x];

    head[x]=cnt;

}

bool up,down;

bool dfs(int u){

    vis[u]=1;

    if(c[u].z-r<=0 && c[u].z+r>=0) down=1;

    if(c[u].z+r>=c_h && c[u].z-r<=c_h) up=1;

    if(up && down) return 1;

    for(int i=head[u];i;i=e[i].next){

        if(vis[e[i].to]) continue;

        if(dfs(e[i].to)) return 1;

    }

    return 0;

}

int main(){

    int i,j;

    bool ok;

    T=read();

    while(T--){

        memset(head,0,sizeof(head));

        memset(vis,0,sizeof(vis));

        cnt=0; ok=0;

        n=read(),c_h=read(),r=read();

        for(i=1;i<=n;i++) c[i].x=read(),c[i].y=read(),c[i].z=read();

        for(i=1;i<n;i++)

            for(j=i+1;j<=n;j++)

                if(calc(c[i].x,c[i].y,c[i].z,c[j].x,c[j].y,c[j].z)) add(i,j),add(j,i);

        for(i=1;i<=n;i++){

            if(vis[i]) continue;

            up=down=0;

            if(dfs(i)){printf("Yes\n");ok=1;break;}

        }

        if(!ok) printf("No\n");

    }

    return 0;

}

我的得分：100

5.宝藏

题目描述

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋， 也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远， 也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路 则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某 个宝藏屋的通道，通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以 任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路 所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是：L×K

L代表这条道路的长度，K代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

输入输出格式

输入格式：

第一行两个用空格分离的正整数 n 和 m，代表宝藏屋的个数和道路数。

接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏 屋的编号（编号为 1~n），和这条道路的长度 v。

输出格式：

输出共一行，一个正整数，表示最小的总代价。

输入输出样例

4 5

1 2 1

1 3 3

1 4 1

2 3 4

3 4 1 

4

4 5

1 2 1

1 3 3

1 4 1

2 3 4

3 4 2  

5

说明

【样例解释1】

小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路 1→2，挖掘了 2 号宝藏。开发了道路 1→4，挖掘了 4 号宝藏。还开发了道路 4→3，挖掘了 3 号宝 藏。工程总代价为：1×1+1×1+1×2=4

【样例解释2】

小明选定让赞助商打通了 1 号宝藏屋。小明开发了道路 1→2，挖掘了 2 号宝藏。开发了道路 1→3，挖掘了 3 号宝藏。还开发了道路 1→4，挖掘了 4 号宝 藏。工程总代价为：1×1+3×1+1×1=5

【数据规模与约定】

对于 20%的数据： 保证输入是一棵树，1≤n≤8，v≤5000 且所有的 v 都相等。

对于 40%的数据： 1≤n≤8，0≤m≤1000，v≤5000 且所有的 v 都相等。

对于 70%的数据： 1≤n≤8，0≤m≤1000，v≤5000。

对于 100%的数据： 1≤n≤12，0≤m≤1000，v≤500000。

考场上我居然轻易地按照最短路的思想做了这题，对着数据来回搞，最后只搞了40分-_- 居然忘了状压这一回事……

下面是鄙人的题解

聪明的人说：第二天的dp来了（n<=12，不来一发状压dp还想干啥？）。

愚蠢的人说：第二天的暴力来了（n<=12，不来一发暴力还想干啥？）。

通过上面两句，相信大家已经知道，这题肯定跟dp有关系了。

然而你知道这题为什么会放到d2t2吗？

（消息来自知乎）：据出题人还是谁透露，这题本来是放在d2t3的，而列队那题原来放在d2t2，结果验题人一发暴力A了这题（出题人本来是想考察状压dp的），于是两题就被调换位置了。

于是今年的Day2难得可以不写dp了！但这题我想说一下部分分的做法，因为部分分给的不错。

○方法1：状压dp（暂缺代码，码好了就发）

○方法2：dfs

用 dp[i] 来表示状态 i 下的最优方案，dis[j] 表示 j 到根节点的距离（题目中所描述的 K），用 dfs 来更新答案。状压dp就变成了记忆化搜索。

#include<bits/stdc++.h>

#define inf 2147483647

using namespace std;

int dp[1<<13],dis[15],G[15][15],isG[15][15],n,m,ans=inf;

//isG表示x,y之间是否有边

//点只有十二个直接上邻接矩阵即可

void insert(int x,int y,int w){G[x][y]=w;G[y][x]=w;isG[x][y]=1;isG[y][x]=1;}

//插边函数

void dfs(int x){

    for(int i=1;i<=n;i++){

    //枚举你所选点集中的每个点

        if((1<<(i-1)) & x){

            for(int j=1;j<=n;j++){

                if(!(1<<(j-1)&x) && isG[i][j]) //判断能否选

                    if(dp[1<<(j-1)|x]>dp[x]+dis[i]*G[i][j]){ //有没有更新的必要

                        int temp=dis[j];

                        dis[j]=dis[i]+1;

                        dp[1<<(j-1)|x]=dp[x]+dis[i]*G[i][j];

                        dfs(1<<(j-1)|x);

                        dis[j]=temp;

                    }

            }

        }

    }

}

int main(){

    scanf("%d%d",&n,&m);

    memset(G,63,sizeof(G)); //赋较大初值

    for(int i=1;i<=m;i++){

        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);

        if(w<G[x][y])insert(x,y,w);

    }

    for(int i=1;i<=12;i++){

        memset(dis,63,sizeof(dis));

        for(int j=1;j<=(1<<n)-1;j++) dp[j]=inf;

        //每枚举一遍根节点就重置一遍

        dis[i]=1; dp[1<<(i-1)]=0;

        dfs(1<<(i-1));

        ans=min(ans,dp[(1<<n)-1]); //看答案是否能更新

    }

    printf("%d",ans);

    return 0;

}

○方法3：bfs（来自wxj神爷的考场代码，不得不膜拜啊，这年代还手撸队列）

跟dfs差别不大，把挖到的宝藏屋的信息 塞到队列里而已，

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define LL long long

using namespace std;

inline LL read(){

    LL x=0,f=1;char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;

	for(;isdigit(c);c=getchar()) x=x*10+c-'0';

	return x*f;

}

const int INF = 9999999;

const int MAXN = 100001;

LL N,M;

struct data{ //记录宝藏屋信息

	LL ans;

	LL dist[12+1]; //dist[i]表示从起点到i号点经过的宝藏屋数量，即题目中的K

	LL ct; //ct表示宝藏屋编号

}Que[(1<<17)+1];

LL Root[MAXN+1],Node[MAXN+1],Cost[MAXN+1],Next[MAXN+1];

LL cnt, vis[(1<<17)]; //vis数组记录到每个宝藏屋的最低费用 

void insert(int u,int v,int w){ //邻接表 不过跟我的风格差的有点多

	++cnt; Node[cnt]=v; Cost[cnt]=w; Next[cnt]=Root[u]; Root[u]=cnt;

	return;

}

LL ans=INF;

LL BFS(int f){

    int head=1,tail=1;

	for(int i=1;i<=N;i++) Que[tail].dist[i]=INF;

	Que[tail].dist[f]=1; Que[tail].ans=0; //从起点到起点经过1个宝藏屋，且免费开通，无代价

	for(int i=1;i<(1<<N);i++) vis[i]=INF;

	Que[tail].ct=(1<<(f-1)); vis[(1<<(f-1))]=0; //刚开始的状态为只到过起点f

	while(head<=tail)

	{

	    data p=Que[head++];

		if(vis[p.ct]<p.ans) continue; //当前解不比最优解更优，直接退

		for(int k=1;k<=N;k++)

		{

		    if( !(p.ct & (1<<(k-1))) ) continue; //判断当前宝藏屋p.ct是否已到过，如果（在状态中）没到过就退。也就是说只能从到过的宝藏屋出发

			for(int x=Root[k];x;x=Next[x]) //用邻接表找宝藏屋出边

			{

			    int v=Node[x];

				if(p.ct & (1<<(v-1))) continue; //判断当前宝藏屋p.ct是否已到过，如果（在状态中）到过就退

				data t=p;

				t.ans+=(t.dist[k]*Cost[x]); //记录答案

				t.ct=t.ct|(1<<(v-1));

				if(vis[t.ct]<=t.ans) continue;

				vis[t.ct]=t.ans; t.dist[v]=t.dist[k]+1;

				Que[++tail]=t;

			}

		}

	}

	return vis[(1<<N)-1];

}

int main(){

    N=read(),M=read();

	for(int i=1;i<=M;i++){

	    LL u=read(),v=read(),w=read();

		insert(u,v,w); insert(v,u,w);

	}

	for(int i=1;i<=N;i++)

	    ans=min(ans,BFS(i)); //直接枚举起点然后bfs

	printf("%lld\n",ans);

}

我的得分：40

6.列队

题目描述

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

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

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

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

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

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

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

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

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

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

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

输入输出格式

输入格式：

输入共 q+1 行。

第 1 行包含 3 个用空格分隔的正整数 n,m,q，表示方阵大小是 n 行 m 列，一共发生了 q 次事件。

接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x,y，用一个空 格分隔，表示这个离队事件中离队的学生当时排在第 x 行第 y 列。

输出格式：

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学生的编号。

输入输出样例

2 2 3

1 1

2 2

1 2 

1

1

4

说明

【输入输出样例 1 说明】

列队的过程如上图所示，每一行描述了一个事件。 在第一个事件中，编号为 1 的同学离队，这时空位在第一行第一列。接着所有同学 向左标齐，这时编号为 2 的同学向左移动一步，空位移动到第一行第二列。然后所有同 学向上标齐，这时编号为 4 的同学向上一步，这时空位移动到第二行第二列。最后编号 为 1 的同学返回填补到空位中。

【数据规模与约定】

数据保证每一个事件满足 1≤x≤n，1≤y≤m。

没错，这次的boss来了——但为什么是树巨结垢题啊……

考场上我大概留了1h准备手爆这题。但我的基础太菜，很不幸所有部分分都打炸了，不过由于官方数据太水，打错的前30分暴力 居然还搞到了25分……

所以不要再问我考试时爆炸的心态了……这种题一般就要拼部分分，那就开讲部分分吧。

30-pts

直接取出出队点放到右下角，然后平移询问所在的行 和 最后一列。 这是考场必打的辣鸡暴力。

50-pts

也就是说有效的行数（即参与询问的行数）不超过500行。我们把这些行离散化，那么就只需要维护一个q*m大小的方阵了（500*50000=2500W），直接开数组+暴力随便跑。

　　但由于最后一列的平移操作是不能离散化的，因此单开一个数组给最后一列取出询问所在行的点，暴力将后面部分前移，然后把该点放到最后。最后一列的操作 的单次复杂度O(n)，总共做q次，该操作的总复杂度为O(nq)，也随便跑。

　　只能离散化行，列是无法离散化的，多想想就明白了。

80-pts（n≠1，x=1的10分）

所有询问都只对第一行进行操作，看起来跟n=1的20分做法没什么区别。手玩一下就会发现此时只有第一行和最后一列的数会发生变化，再仔细一点就会发现其实只是在第一行后面接上最后一列，然后就跟n=1的20分做法完全无区别了。于是把第一行和最后一列都放入树状数组里，像70-pts一样搞。

　　当然，有人可能并不想把第一行和最后一列接在一起（第一行最后一个数算在最后一列中，这样第一行就只存前m-1个数。这样的存法在100分做法中有实际作用！），那就给第一行和最后一列各单独做一个树状数组和arr数组，每次出队时都在第一行中删去这个点，接到最后一列的尾部，然后把最后一列的第一个数删去，接到第一行的尾部。实际上，这个做法引申了100分做法——因为对于每行你都可以类似这种操作，与最后一列实现快速“平移”呀！

　　****经过一系列的操作之后，其实上面的操作就剩下一个难点：怎么在O（log n）的时间内做到二分查询前缀和为k的最左位置？如果你想到了，再结合上一段说的内容，那恭喜你，你可以做100分做法了。

100-pts

  70/80-pts已经大力提醒你了~

 友情提示：在看下面的方法之前，你要做好仔细研读代码的准备，因为代码挺复杂的，不好理解，需要你缕清每一步在干什么。

○方法1：树状数组（官方标解，个人理解了1天；速度最快，最慢的点跑488ms）

　　 正解概述：给每一行前m-1个数和最后一列各开一个树状数组和arr数组，利用树状数组在log级别的时间内查找出队点，然后快速将其移到最后一列尾部，再将最后一列于本行的数接到本行尾部。

　　但现在还剩下一个棘手的数据结构问题——直接开30w*30w的二维数组会爆！那我们能只用一维数组把他们都存下来吗？能！下面我从头分析整个想法过程：

　　 我们观察到对于本来就在这一行中的元素，我们可以直接算出它的值，而不用存储。

　　怎么算呢？

　　 定义一行中原来的元素为 初始时这一行前 m-1 个元素中，没有离队过的元素。

　　将所有出队点以 横坐标为第一关键字、输入编号为第二关键字 从小到大排序（就是优先以横坐标从小到大排序）。我们发现这时有一些出队点一定是原来的元素，那我们就可以用树状数组预处理出这些原来的元素的答案了。

　　预处理：考虑到x=1的30分的做法中，只有一行（n≠1，x=1时加一列）的数进行出队、加入队尾操作。在这里，每一个出队点都只会对本行 和 最后一列的点造成平移，当两个出队点不在最后一列 且 不在同一行的时候，它们不会不相互影响，因此我们依然可以对每一行用 m-1 位的树状数组，维护一个同70/80-pts中的01序列。但由于现在出队的点是加入了整个队列的右下角，而不是本行的最右侧，因此我们代入了原来的元素这个定义。这样在一行中的一个点出队时，我们只把那一位设成0，而不把这个数放到队尾，即不在队尾添加一个1。此时，由于本行的第m个数平移到了第m-1位，而第m列，也就是最后一列的数由于在每一次操作后都会向上平移一次而不是任何一行原来的元素，这一行的最后就会多出一个非原来的元素，因此我们记录一下本行m-1个数中最后有几个连续的非原来的元素，如果出队点不是原来的元素（即在最后非原来的元素那块）就不预处理。

　 　当两个出队点在同一行的时候，它们之间会相互影响，必须按照输入顺序出队，因此输入编号作为第二关键字排序。

　　其实，不必对每一行都开一个树状数组，只需要开一个一行的树状数组，预处理下一行的时候把树状数组初始化就好了。

　　预处理操作后，要把树状数组清空，下面的操作对树状数组的用法与之前不同！

　　这下我们就预处理完了一部分询问的答案。对于剩下的不是原来的元素，我们发现，由于最多只有q（30w）个点出队，并且这些不是原来的元素一定是从最后一列平移过来的（重点！），我们很容易想到每行有几个点出队，最后一列就有几个点入这行的队尾（记住这个关键词！）。

　　因此我们可以把一个30w位的数组分割出n块，每行对应一块，且每行对应的块的大小为 该行要出队的点的数量。记录相邻两行之间的分割点，把每块都搞成一棵树状数组，这样每行就对应了一棵树状数组。每行对应的树状数组只存储最后一列平移到本行的点，这样本行有几个点出队，最后一列就有几个点入这行，这就是为什么每行对应的树状数组的大小为 该行要出队的点的数量。由于这些非原来的元素是从最后一列平移过来的，因此我们还得单开一个树状数组，用于存储最后一列。注意在开树状数组的时候要同步开arr数组。（其实可以用30w+1个vector来代替这个方法，每行对应一个vector，最后一列再单开一个，就不用考虑每行树状数组要开多大了。但由于时间关系，我就不码这个版本的代码了，下面的代码用的还是把数组分割成n块的方式）

　　做好了每行的树状数组，还得考虑一下它该怎么用。

　　我们可以记录一下每个出队点在本行的位置 的前面 有几个原来的元素，这样这个点的 列数（在本行的位置） - 前面原来的元素的数量，就得到了这个点是本行第几个非原来的元素（不要忘了没有预处理过的点都是非原来的元素）。这样就可以按类似70-pts中叙述的 二分找到第k个数 的思想，使用80-pts方法的最后一段提到的那个要求你想到的方法——在O（log n）时间内二分查询前缀和为k的最左位置，在本行的树状数组中用log级别的时间找到这个点，然后对它进行一系列操作。

　　那怎么操作呢？我们按照输入顺序对每个出队点进行操作：

　　　　如果这个出队点已经预处理过答案，就从本行的队列中直接取出它，接到最后一列的尾部；然后利用最后一列的树状数组，二分找到最后一列在本行的点，将其所在位置删除，并把这个点接到本行的尾部。

　　　　如果这个出队点没有预处理过答案，说明它不是原来的元素。先记录这个点的答案，然后分两种情况：

　　　　　　1.这个点不在最后一列，说明这个点的数是从最后一列平移过来的。利用本行的树状数组，二分找到这个点，将其所在位置删除，并把这个点接到最后一列的尾部。然后利用最后一列的树状数组，二分找到最后一列在本行的点，将其所在位置删除，并把这个点接到本行的尾部；

　　　　　　2.这个点在最后一列，那直接利用最后一列的树状数组，二分找到最后一列在本行的点，将其所在位置删除，并把这个点接到最后一列的尾部。

　　注意：树状数组和arr数组要一直同步更新，因为通过树状数组二分找到的第k个数 要在arr数组中的对应位置找到值！

树状数组版正解的复杂度：

　　时间复杂度 O（q log 玄学）【“玄学”大约为n+m+q这个级别？】

　　空间复杂度 O（n+2q）【所有行的树状数组大小加起来为q，最后一列的树状数组大小为n+q，因此最大的数组（即树状数组和arr数组）都是n+2q位】

 #include<bits/stdc++.h>

 using namespace std;

 inline int read(){

     int x=;bool f=;char c=getchar();

     for(;!isdigit(c);c=getchar()) if(c=='-') f=;

     for(;isdigit(c);c=getchar()) x=(x<<)+(x<<)+c-'';

     if(!f) return -x;

     return x;

 }

 int n,m,q,tot;

 int x[];

 long long a[][];

 vector<long long> que;

 map<int,int> lsh,rlsh;

 struct query{

     int x,y;

 }qr[];

 int main()

 {

     n=read(),m=read(),q=read();

     int i,j;

     for(i=;i<=q;i++) x[i]=qr[i].x=read(),qr[i].y=read();

     sort(x+,x+q+);

     lsh[++tot]=x[], rlsh[x[]]=tot;

     for(i=;i<=q;i++){

         if(x[i]!=x[i-]) lsh[++tot]=x[i];

         rlsh[x[i]]=tot;

     }

     for(i=;i<=tot;i++)

         for(j=;j<=m;j++)

             a[i][j]=(long long)(lsh[i]-)*m+j;

     que.push_back();

     for(i=;i<=n;i++) que.push_back((long long)i*m);

     int tmp,xx,yy;

     for(i=;i<=q;i++){

         xx=rlsh[qr[i].x], yy=qr[i].y;

         printf("%lld\n",a[xx][yy]);

         tmp=a[xx][yy];

         for(j=yy+;j<=m;j++) a[xx][j-]=a[xx][j];

         que.erase(que.begin()+qr[i].x);

         que.push_back(tmp);

         for(j=xx;j<=tot;j++) a[j][m]=que[lsh[j]];

     }

     return ;

 }

 #include<cstdio>

 #include<cctype>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define ll long long

 inline ll read(){

     ll x=;bool f=;char c=getchar();

     for(;!isdigit(c);c=getchar()) if(c=='-') f=;

     for(;isdigit(c);c=getchar()) x=(x<<)+(x<<)+c-'';

     if(!f) return -x;

     return x;

 }

 int q,id[];

 long long n,m,a[],b[];

 int h[],len[],len2[],bit[]; //bit（树状数组）最多用n+q位

 long long arr[],ans[];

 inline bool cmp(int p1,int p2){return a[p1]==a[p2] ? p1<p2 : a[p1]<a[p2];} //按照行从小到大排序

 inline int lowbit(int x){return x&-x;}

 inline void add(int *array,int siz,int i,int x){

     for(;i<=siz;i+=lowbit(i)) array[i]+=x;

 }

 inline int query(int *array,int siz,int x){ //查找树状数组中第一个前缀和为x的位置

     int l=,r,mid,sum,ans;

     while(l<=siz && array[l]<x) l<<=, ans=l; //由于树状数组的第1位、第2位。第4位、第8位等2的倍数位 都直接存前缀和，因此通过它们找到x在哪两个前缀和区间，在这个区间里二分即可。挖槽，学到了，还能这么操作

     r=l; sum=array[l>>=]; //sum预设成树状数组在区间左端位置的前缀和

     while(l<r-){

         mid=l+r>>;

         if(mid>siz || array[mid]+sum>=x) r=mid, ans=mid; //array[mid]+sum=x 说明mid位进了答案x区间

         else l=mid, sum+=array[l];

         /*上一行

         1.这个树状数组前缀和求得太神了！利用二分代替 反向代替lowbit！orz

         2.此时mid明显不是答案，但由于l设成了mid（正常是mid+1），二分结束时l和r差1，此时r是答案x的最左边一位，l是答案x区间的左边一位

         */

     }

     ans=r;

     return ans;

 }

 int stk[],top;

 int main(){

     int i;

     n=read(),m=read(),q=read();

     for(i=;i<=q;i++) a[i]=read(),b[i]=read(),id[i]=i; //a行 b列

     sort(id+,id+q+,cmp);                   //将id按照行（a）从小到大排序

     for(i=;i<=m-;i++) add(bit,m-,i,); //初始化每一位都是原来元素（即未被删除）

     for(i=;i<=n;i++) len[i]=m-;           //此时的len[i]记录第i行有几个 原来的元素

     //预处理部分，方法跟80-pts部分基本相同

     for(i=;i<=q;i++){

         if(a[id[i-]]!=a[id[i]])                   //（a升序排列时）如果相邻两个a不相同

             while(top) add(bit,m-,stk[top--],); //将树状数组初始化（前m-1个点都为1，后面的都为0）。我们只要把上一行做过-1操作的位置都记录下来，这里再把1加回去即可。

         if(b[id[i]]>len[a[id[i]]]) continue;       //b[id[i]]表示第i个询问的列，len[a[id[i]]]表示第i个询问所在行剩余的 原来的元素。意思：如果这个询问的位置不是原来元素就不预处理

         //这个位置是原来元素，直接预处理答案

         int pos=query(bit,m-,b[id[i]]);           //查询这个点到底在本行第几个

         ans[id[i]] = (a[id[i]]-)*m + pos;           //直接根据横纵坐标计算出这个点的值

         add(bit,m-,pos,-);                      //更新这个点为0，即被删除

         stk[++top]=pos;

         --len[a[id[i]]];

     }

     //求剩下的 非原来的元素 的答案

     //tip：数组+q 代表一个指针，指向数组的第q位，即在函数中以第q位为第1位 进行一系列操作

     //bit + h[i]开的是第i行的树状数组，用来存储 最后一列滚来的数（非原来的元素），初始情况下都是0

     //bit + h[n+1]开的是最后一列的树状数组，初始情况下1~n位都是1 

     //初始化h数组，h数组用于记录每行的树状数组的起始位置

     int iter=;

     for(i=;i<=n;i++){

         while(iter<=q && a[id[iter]]<i) ++iter;

         h[i]=iter-; //寻找最大的iter，使第iter个横坐标小于i。意思是寻找前一行最右边的一个离队点，那么 iter+x 就指向了第i行的树状数组的第x个数

     }

     h[n+]=q; //最后一列的树状数组在第q位之后存，前面q位留给每行开树状数组 

     memset(bit,,sizeof bit); //清空树状数组，重新使用它。之后的树状数组存每一行的非原来元素

     for(i=;i<=n;i++) len[i]=, len2[i]=m-; //此时的len[i]记录第i行最后接了几个最后一列滚来的数（非原来的元素）；len2[i]记录第i行有几个原来的元素

     len[n+]=n;

     for(i=;i<=n;i++) add(bit+h[n+],n+q,i,), arr[q+i]=i*m; //arr[q+i]位记录最后一列第i行的数

     for(i=;i<=q;i++){

         if(ans[i]){ //这个点预处理过答案了

             int pos=query(bit+h[n+], n+q, a[i]); //在最后一列的树状数组查询本行（ai）的数所在的位置 

             add(bit+h[n+], n+q, pos, -);          //更新这个点为0，即被删除

             add(bit+h[n+], n+q, ++len[n+], ); //把这个点接到最后一列尾部，在树状数组尾部加一个1（它出队留下的空就不补了）

             arr[h[n+] + len[n+]] = ans[i];     //把这个出队点放入最后一列的最后一位 

             add(bit+h[a[i]],h[a[i]+]-h[a[i]],++len[a[i]],); //将最后一列在本行的点 向左平移一位 至本行的第m-1位，所以要在本行的树状数组最后接一个1，代表接了一个数

             arr[h[a[i]]+len[a[i]]] = arr[h[n+]+pos];           //把数值也搬到本行最后的对应位

             --len2[a[i]];                                       //本行多了一个 非原来的元素

         }

         else{ //没预处理过答案，说明不是原来的元素

             int pos = query(bit+h[n+],n+q,a[i]); //在单独的树状数组查询第ai大的数

             add(bit+h[n+],n+q,pos,-);           //更新这个点为0，即被删除

             add(bit+h[n+],n+q,++len[n+],);     //把这个点接到队尾，在树状数组尾部加一个1（它出队留下的空就不补了）

             if(b[i] != m){ //如果这个点不在最后一列

                 int pos2 = query(bit+h[a[i]], h[a[i]+]-h[a[i]], b[i]-len2[a[i]]);  //b[i]-len2[a[i]]=列数-本行有几个原来的元素=这个点是本行第几个 非原来的元素。意思：求自己在本行树状数组中的第几位

                 add(bit+h[a[i]], h[a[i]+] - h[a[i]], pos2, -);                    //取出这个点，即在树状数组中将其设为0

                 ans[i] = arr[h[a[i]] + pos2];                                         //把这个数的值代入答案

                 add(bit+h[a[i]], h[a[i]+] - h[a[i]], ++len[a[i]], );                 //将最后一列在本行的点 向左平移一位 至本行的第m-1位，所以要在本行的树状数组最后接一个1，代表接了一个数

                 arr[h[a[i]]+len[a[i]]] = arr[h[n+]+pos];                             //把数值也搬到本行最后的对应位

             }

             else ans[i] = arr[h[n+] + pos]; //直接取出最后一列在本行的点，这个点就是出队点

             arr[h[n+] + len[n+]] = ans[i]; //把这个点接到队尾

         }

     }

     for(i=;i<=q;i++) printf("%lld\n",ans[i]); //每一个询问的答案离线查询出答案了

     return ;

 }

该做法最初借鉴于本大佬，感谢他的题解：https://www.luogu.org/space/show?uid=10703。:-)

○方法2：线段树（CCF老爷机严重卡常，因此动态开点）

暂时没写

○方法3：平衡树（splay）（非noip考查内容，理解难度低一点；速度最慢，最慢的点跑1800ms）

2018.10.7 update（好吧，我承认，现在弄题解没以前那么认真，简洁了一些）：

我们观察每一行除了最后一个数之外的数在操作中是如何变化的。

如果出队在 $(x,y)$，那么第$x$行（除了最后一个数）会弹出第$y$个数，它后面的数依次左移，再在最后插入一个数（就是最后一列当前的第$x$个数）；然后，对于最后一列，我们要弹出第$x$个数（插入到第$x$行），再在最后插入一个数（就是刚出队的那个）。

所以，我们无论是对于行还是列，都要执行两种操作：第一，弹出第k个数，第二，在尾部插入一个数。可以用splay来实现。

但是这最多做到了二分优化时间，挨个存点的空间复杂度是$O(nm)$。

那怎么办？

跟用树状数组写的发现一样，我们发现$q$最大只有$300000$，有些人从始至终都是左右相邻的。

但splay是开的是点，而不是区间，所以跟树状数组不一样，不预处理那些始终不动的数。

利用splay的点存优势，我们在维护splay的时候，一段连续的数可以用一个节点维护，记录这个节点表示的区间的左右端点。

如果我们发现要弹出的数在某个节点内部，我们就把它拆成$3$个节点（其中中间那个节点只有一个数，就是我们要的那个数。其余两个节点分别存左半边和右半边），拆点操作这么做：把原节点表示区间的右端点左移，而右边减少的部分可以划为新增节点的表示区间。

时间复杂度还是 O（q log 玄学）【这个“玄学”就带很大的常数了，看你splay的优化和卡常情况】

空间复杂度还是 O（2n+2q）【对于前m-1列，一开始总共n个点（每行1个），每次询问最多会分离出2个点（分离前的点还在用！）；对于第m列，一开始总共1个点，最多被分为n个点】

另外， 这个程序写了垃圾桶优化内存。

 #include<bits/stdc++.h>

 #define ll long long

 #define N 300010

 using namespace std;

 inline int read(){

     int x=; bool f=; char c=getchar();

     for(;!isdigit(c);c=getchar()) if(c=='-') f=;

     for(; isdigit(c);c=getchar()) x=(x<<)+(x<<)+(c^'');

     if(f) return x;

     return -x;

 }

 int fa[N<<],son[N<<][],cnt;

 ll l[N<<],r[N<<],siz[N<<];

 int rub[N],rub_cnt;

 struct Splay{

     int root;

     inline int newNum(){

         if(!rub_cnt) return ++cnt;

         return rub[--rub_cnt];

     }

     inline int newNode(ll L,ll R){

         int x=newNum();

         fa[x]=son[x][]=son[x][]=;

         siz[x]=(r[x]=R)-(l[x]=L);

         return x;

     }

     inline void init(ll L,ll R){

         root=newNode(L,R);

     }

     inline void upd(int x){siz[x]=siz[son[x][]]+siz[son[x][]]+r[x]-l[x];}

     inline int dir(int x){return son[fa[x]][]==x;}

     void rotate(int x){

         int d=dir(x),f=fa[x];

         fa[x]=fa[f];

         if(f==root) root=x;

         else son[fa[f]][dir(f)]=x; //更新点x的爷爷节点的儿子

         if(son[f][d]=son[x][d^]) fa[son[f][d]]=f;

         fa[son[x][d^]=f] = x;

         upd(f), upd(x);

     }

     void splay(int x){

         for(;fa[x];rotate(x))

             if(fa[fa[x]]) rotate(dir(x)==dir(fa[x]) ? fa[x] : x); //判断单双旋

     }

     int splitNode(int x,ll k){ //把节点x分裂，分裂后x的区间里前k个数还在x节点上，第k个及后边的数对应新节点

         k+=l[x];

         int y=newNode(k,r[x]);

         r[x]=k;

         if(son[x][]==) fa[son[x][]=y] = x;

         else{

             int t=son[x][];

             while(son[t][]) t=son[t][];

             fa[son[t][]=y]=t;

             while(t!=x) upd(t),t=fa[t];

         }

         splay(y);

         return y; //返回新分出的节点（后面一段）

     }

     inline void del(int o){ //splay删除

         splay(o);

         fa[son[o][]]=fa[son[o][]]=;

         if(!son[o][]) root=son[o][];

         else{

             int t=son[o][];

             while(son[t][]) t=son[t][];

             splay(t);

             upd(root = fa[son[t][] = son[o][]] = t); //将原根的右儿子更新给新根的右儿子，原根就没了（之前忘了写后面的=t！）

         }

         rub[rub_cnt++]=o;

     }

     ll popKth(ll k){

         int o=root;

         while(){

             if(k<=siz[son[o][]]) o=son[o][];

             else{

                 k-=siz[son[o][]];

                 if(k<=r[o]-l[o]){

                     if(k!=r[o]-l[o]) splitNode(o,k); //出队点不在最右端 才需要分出右边节点

                     if(k!=) o=splitNode(o,k-); //出队点不在最左端 才需要分出左边节点

                     break;

                 }

                 else{

                     k-=r[o]-l[o]; //减去当前节点的大小

                     o=son[o][];

                 }

             }

         }

         del(o); //删除出队点

         return l[o];

     }

     void pushBack(ll k){

         int y=newNode(k,k+);

         if(!root) root=y;

         else{

             int o=root;

             while(son[o][]) o=son[o][];

             splay(o);

             upd(fa[son[o][]=y] = o);

         }

     }

 }s[N];

 int n,m,q;

 int main(){

     n=read(),m=read(),q=read();

     ll i;

     for(i=;i<=n;i++) s[i].init((i-)*m+,i*m);

     s[].init(m,m+);

     for(i=;i<=n;i++) s[].pushBack(i*m);

     int x,y;

     ll p;

     while(q--){

         x=read(),y=read();

         s[x].pushBack(s[].popKth(x));

         printf("%lld\n",p=s[x].popKth(y));

         s[].pushBack(p);

     }

     return ;

 }

该做法最初借鉴于本大佬，感谢他的题解：https://www.luogu.org/space/show?uid=7868。:-)

另外我重申一下：这种splay写法在OJ上交，是卡着2s的时限过的（标题说了最大点1800ms），但是在noip考场上不推荐写这种比较骚的数据结构，他们的老爷机会卡常数，可能导致最后几个点评测TLE了。来了解一下wzj52501神爷两小时打完day2然后最后一题被卡30分常的自闭经历

我的得分：25（哇你肯定很奇怪这是怎么拿的分吧？！没办法我人菜分也菜）

提高组总得分：295（北京省一分数线280+，那5分名义上是惩罚而实际上是人性沦丧，考280分的人招谁惹谁了）

到这里我只有一句话想说了：我好菜，我要加油。

后记

好的，我已经愉快地翻掉了noip2017的车，下面我就要驶向更加残酷的noip2018了~

别以为蒟蒻没有梦想，我也希望有一天我的解题报告能上NOI年鉴的ToT

看完全文的福利（重点！）：

The log：

2018.3.1 本文基础更新完毕时间（即所有题都发了至少一种题解）

2018.9.28 优化部分标题字体颜色

2018.10.7 修复提高组几道题因复制后没清干净格式 而导致的文字数学格式混乱->Math Processing Error