论如何手玩5h果冻运输得到 AC

最近在大力练习提答颓提答，听说果冻运输很好玩就来试试。

然后玩的停不下来 QAQ ...

于是开一篇博客写一下每个点的解法。(一个个手玩出来的。。)

首先我们每次都算什么下一步完后会发生什么在大脑中演算什么的太不友好了 QAQ ..

所以我们需要一个可视化的界面来手玩。。

只要改一改 Checker 我们就得到了一个可视化实时反馈的程序 >_<...

Checker 最后会附上的 QAQ..

Test 1:

0 . . . . . 1 . 0
|               |
0 . . . . 0-0 . 0
|               |
0 . . 3 . . 1 2 0
|               |
0-0 2 0 3 . 0-0-0
| |   |     | | |
0-0-0-0-0-0-0-0-0

略

Test 2:

0 . . 2 . . . 2 0 : 4
|               |
0 1 . 1 . . . 1 0 : 3
|               |
0-0 . 0 . 0 . 0-0 : 2
| |   |   |   | |
0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9

我们发现最后一共要合成两堆.

但是地上有三个坑?

那么我们搭一个桥来连通所有就好了。

所以我们可以先 $(4,4,0)$

然后 $(2,3,1)$ 就搭好桥了，把 $(8,4)$ 的 $2$ 送过去就好了.

Test3:

0 . . . 3 2 . 0 2 . . 0 : 5
|             |       |
0-0-0 . 0-0 1 0-0 . . 0 : 4
|                     |
0 . . . . . 3 . . . . 0 : 3
|                     |
0-0-0 . 0-0 1 0-0-0-0-0 : 2
| | |   | |   | | | | |
0-0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11 12

可以发现 $(7,x)$ 这一列必须要有人顶着.

不然中间就过不去了。

如果直接进行 $(6,5,0)$ 的话那么就必须要把两个 $2$ 放到 $3$ 的同一侧.

所以此时在把左侧的 $2$ 退下去代替中间的 $3$ 顶着 $1$

然后让被替代的 $3$ 去右边,让右上的 $2$ 落在 $3$ 的左边。

然后一路向左推就好了

Test 4:

0 . . . . . 1 . . . 0 : 8
|                   |
0 . . . . . 2 . . . 0 : 7
|                   |
0 . . . . . 0 . . . 0 : 6
|                   |
0 2 . 1 . . . . . . 0 : 5
| |   |             |
0 2 . 1 . . . . . 2 0 : 4
|                   |
0-0 . 0 . . . . . 0-0 : 3
| |   |           | |
0-0-0-0 . 0-0-0-0-0-0 : 2
| | | |   | | | | | |
0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11

让 $(7,7)$ 和 $(10,4)$ 的 $2$ 在下平台搭一个传送带。

先把 $(4,4)$ 的块运到 $(10,4)$ 上，然后把 $(7,8)$ 的 $1$ 运到 $(3,3)$

剩下的就很明显了 QAQ ...

Test 5:

0 1 2 . 2-2 . . . . . 0 : 6
|                     |
0-0-0 . 0-0 . 0-0 . . 0 : 5
|                     |
0 1 2 . . . . . . . . 0 : 4
|                     |
0-0-0-0 . . 0 . . . 0-0 : 3
| | | |     |       | |
0-0-0-0-0 . 0 . . 0-0-0 : 2
| | | | |   |     | | |
0-0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11 12

比较明显的一个点.

$(6,6)$ 的块肯定是从右边下去了在运到左边。

那么就必须有两个块填在 $(9,3),(9,2)$ 上。

可以先让 $(3,6)$ 到 $(4,4)$ 然后再搭在 $(5,3),(6,3)$ 上。

然后就可以把 $(2,4)$ 和 $(2,6)$ 搭在 $(9,3),(9,2)$ 上啦.

Test 6:

0-0-0-0 . 3 . . . . 0 : 8
|                   |
0 . . . . 0-0 . . . 0 : 7
|                   |
0 1 . 2 . . . . . . 0 : 6
|                   |
0 0 . 0 . 0 . 3 . . 0 : 5
|                   |
0 . . . . . . 0 . 2 0 : 4
|             |     |
0 . . . . 1 . 0-0-0-0 : 3
|             | | | |
0 . . 0-0-0-0-0-0-0-0 : 2
|     | | | | | | | |
0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11

能发现 $(10,4)$ 的 $2$ 肯定出不来。

那么就需要把 $(4,6)$ 的 $2$ 送过去.

所以知道必须要可以让 $(5,3),(5,4),(5,5)$ 都被填满。

因为 $(5,5)$ 这个点肯定是不能通过左右平移填满的，所以一定是 $(6,8)$ 落下来。

所以需要一个高为 $2$ 的块。

所以可以用 $(8,5)$ 的 $3$ 垫在 $(3,2)$ 上得到 $(2,6)$ 的 $1$.

用它和 $(6,3)$ 的 $1$ 组合成高为 $2$ 的块，然后事情就简单了...

Test 7:

0 . . . . . . . . . 1 0 : 7
|                     |
0 . . . . 2 . . . 2 0-0 : 6
|                     |
0 . . . . 0 . . 1-1 . 0 : 5
|                     |
0 . . . . . . . . 0 . 0 : 4
|                 |   |
0-1 . . 2-0 . 0 . 0 . 0 : 3
| |     | |   |   |   |
0 0 . . 0-0 . 0 . 0 . 0 : 2
| |     | |   |   |   |
0-0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11 12

这个点也好明显QAQ.

先把 $1$ 做成宽度为 $3$ 的块塞到左边去

然后再把 $2$ 放过去.

Test 8:

0 . . . 1 . . 2 . . . 0 : 7
|                     |
0 . . . 0 . . 0 . . . 0 : 6
|       |     |       |
0 . . . 2 . . 1 . . . 0 : 5
|                     |
0 1 . . . . . . . . 2 0 : 4
|                     |
0-0 1 . . . . . . 2 0-0 : 3
| |                 | |
0-0-0 . . . . . . 0-0-0 : 2
| | |             | | |
0-0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11 12

感觉这个点比较难，，当时打了好久 QAQ..

可以发现上面挂着两个果冻，一般给人的直觉是要做两个高度 $3$ 的块去够。

不过需要同时交换位置。。

所以就怎么玩都玩不出来。。。

其实够到它不一定要三连块，，可以造出一个弯曲的形状。。

给出中间和最终局面，，应该就比较明显了。。

0 . . . 1 . . 2 . . . 0 : 7
|                     |
0 . . . 0 . . 0 . . . 0 : 6
|       |     |       |
0 . . . 2 . . 1 . . . 0 : 5
|                     |
0 . . . . . 2 . . . . 0 : 4
|                     |
0-0 . . . 1-1 . . . 0-0 : 3
| |                 | |
0-0-0 . . . 2 . . 0-0-0 : 2
| | |             | | |
0-0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11 12

0 . . . . . . . . . . 0 : 7
|                     |
0 . . . 0 . . 0 . . . 0 : 6
|       |     |       |
0 . . . 2 . . 1 . . . 0 : 5
|       |     |       |
0 . . . 2 . . 1 . . . 0 : 4
|       |     |       |
0-0 . . 2 . 1-1 . . 0-0 : 3
| |     |           | |
0-0-0 . 2 . . . . 0-0-0 : 2
| | |             | | |
0-0-0-0-0-0-0-0-0-0-0-0 : 1
1 2 3 4 5 6 7 8 9 10 11 12

剩下的点留坑

Checker

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define rep(i,a,n) for(int i=(a);i<=(n);++i)
#define SZ(x) ((int)(x).size())
typedef pair<int,int> pii;
const int DX[]={-1,1,0,0},DY[]={0,0,1,-1};
const int N=55,M=111111;
FILE * input_data;
int l,m,n,t,C,x,y,z;
int a[N][N],tmp[N][N],sv[N][N];
enum MODENUM{Full,Score}MODE;
FILE *msg; 
void get(int &p){
    int x;for(x=fgetc(input_data);(x<'0'||x>'9')&&x!='|'&&x!='-'&&x!='.'&&x!=' ';x=fgetc(input_data));
    if(x=='|'||x=='-')p=1;else if(x=='.'||x==' ')p=0;else if(x=='0')p=-1;else p=x-'0';
}
queue<pii>Q;
int bo,err;
void dfs1(int x,int y,int z){
    if(x<1||x>2*n-1||y<1||y>2*m-1)return;if(!a[x][y])return;
    if(a[x][y]==-1)bo=0;
    tmp[x+DX[z]*2][y]=a[x][y];a[x][y]=0;
    rep(i,0,3)dfs1(x+DX[i],y+DY[i],z);
    if(a[x+DX[z]*2][y])Q.push(mp(x+DX[z]*2,y));
}
void dfs2(int x,int y){
    if(x<1||x>2*n-1||y<1||y>2*m-1)return;if(!a[x][y])return;
    if(tmp[x][y])return;tmp[x][y]=1;
    rep(i,0,3)dfs2(x+DX[i],y+DY[i]);
    dfs2(x,y+2);
}
void move(int x,int y,int z){
    if(!a[2*x-1][2*y-1]){puts("No block in this place!");err=1;return;}
    bo=1;
    rep(i,1,2*n-1)rep(j,1,2*m-1)tmp[i][j]=0,sv[i][j]=a[i][j];
    while(Q.size())Q.pop(); 
    dfs1(x*2-1,y*2-1,z);
    while(Q.size()){pii k=Q.front();Q.pop();dfs1(k.X,k.Y,z);}
    if(!bo){rep(i,1,2*n-1)rep(j,1,2*m-1)a[i][j]=sv[i][j];puts("Move Error!");err=1;return;}
    rep(i,1,2*n-1)rep(j,1,2*m-1)if(tmp[i][j])a[i][j]=tmp[i][j];

    while(1){
        rep(i,1,2*n-1)rep(j,1,2*m-1)tmp[i][j]=0;
        rep(i,1,2*n-1)rep(j,1,2*m-1)if(a[i][j]==-1)dfs2(i,j);
        int bo=0;
        rep(j,1,2*m-1)rep(i,1,2*n-1)if(a[i][j]&&!tmp[i][j])bo=1,a[i][j-1]=a[i][j],a[i][j]=0;
        if(!bo)break;
    }
    rep(i,1,2*n-1)rep(j,1,2*m-1)if((i&1)&&(j&1))
        rep(k,0,3)if(a[i][j]>=1&&a[i][j]<=5&&a[i][j]==a[i+DX[k]*2][j+DY[k]*2]){
            a[i+DX[k]][j+DY[k]]=1;
        }
    if(MODE!=Score)puts("Successs!");
}
void print(FILE *x=stdout){
    rep(i,1,2*m-1){
        rep(j,1,2*n-1) if((i&1)&&(j&1)){
            if(a[j][2*m-1-i+1]==0)fprintf(x,".");
            else if(a[j][2*m-1-i+1]==-1)fprintf(x,"0");
            else fprintf(x,"%c",a[j][2*m-1-i+1]+'0');
        }else{
            fprintf(x,"%c",a[j][2*m-1-i+1]?i&1?'-':'|':(i&1)&&(j&1)?'.':' ');
        }if(i&1) fprintf(x," : %d",m-(i>>1));
        fprintf(x,"\n");
    }
    rep(j,1,2*n-1){
        if(j&1) fprintf(x,"%d",(j>>1)+1);
        else fprintf(x," ");
    }fprintf(x,"\n");
}
set<int>S[9];
void dfs3(int x,int y,int z){
    if(x<1||x>2*n-1||y<1||y>2*m-1)return;if(a[x][y]<1||a[x][y]>5)return;
    if(tmp[x][y])return;tmp[x][y]=1;
    S[a[x][y]].insert(z);
    rep(i,0,3)if(a[x+DX[i]*2][y+DY[i]*2]==a[x][y])dfs3(x+DX[i]*2,y+DY[i]*2,z);
}
int par;
int check(){
    par=0;
    rep(i,1,5)S[i].clear();int cnt=0;
    rep(i,1,2*n-1)rep(j,1,2*m-1)tmp[i][j]=0;
    rep(i,1,2*n-1)rep(j,1,2*m-1)if((i&1)&&(j&1)&&a[i][j]>=1&&a[i][j]<=5)dfs3(i,j,++cnt);
    cnt=0;rep(i,1,5)if(SZ(S[i]))cnt+=SZ(S[i])-1;
    if(cnt==1)par=1;
    return cnt==0;
}
int work(string IN,string OUT){
    err=0;
    input_data = fopen(IN.c_str(),"r");
    fscanf(input_data,"%d%d",&m,&n);rep(i,1,2*m-1)rep(j,1,2*n-1)get(a[j][2*m-1-i+1]);
    rep(i,1,2*n-1)rep(j,1,2*m-1)if((i&1)&&(j&1))
        rep(k,0,3)if(a[i][j]>=1&&a[i][j]<=5&&a[i][j]==a[i+DX[k]*2][j+DY[k]*2]){
            a[i+DX[k]][j+DY[k]]=1;
        }
    FILE *out_data = fopen(OUT.c_str(),"w");
    C=0;msg = stdout;
    printf("Testing %s %s\n",IN.c_str(),OUT.c_str());
    print(msg);

    while(scanf("%d%d%d",&x,&y,&z)==3){
        if(x == 0 && y == 0 && z == 0) break;
        fprintf(out_data,"%d %d %d\n",x,y,z);
        ++C;if(MODE!=Score)printf("operation %d: ",C);
        fprintf(msg,"after operation %d:\n",C);
        if(x<1||x>n||y<1||y>m||z!=0&&z!=1){puts("Argument Error!");return 0;}
        move(x,y,z);
        if(err) return 0;
        print(msg);
        if(check())break;
    }fclose(out_data);
    rep(i,1,3)fprintf(msg,"\n");
    if(MODE!=Score){
        puts("");
        if(check()){printf("Congratulations!\nYou completed the game in %d steps.\n",C);return 0;}
        else if(par)printf("WA but you can get 1 score.\n");
        else printf("WA\n");
        puts("\nFinal State:");
        print();
    }else{
        if(check())printf("OK, step:%d\n",C);
        else if(par)puts("Scored 1pt");
        else printf("WA\n");
    }
}
int main(int argc,char **argv){
    msg=fopen("report.out","w");
    if(argc==1){
        assert(0);
        MODE=Score;
        rep(i,1,20){
            stringstream sin,sout;sin<<"C"<<i<<".in";sout<<"C"<<i<<".out";
            printf("test %d: ",i);
            work(sin.str(),sout.str());
        }
    }
    if(argc==2){
        MODE=Full;
        stringstream sin,sout;sin<<"C"<<argv[1]<<".in";sout<<"C"<<argv[1]<<".out";
        work(sin.str(),sout.str());
    }
    if(argc==3){
        assert(0);
        MODE=Full;
        work(argv[1],argv[2]);
    }
    return 0;
}

运行的时候需要传入测试点编号，然后在终端输入即可得到反馈.

输入的所有信息会自动保存到对应的 .out 文件里.

QAQ 刚刚求助完就发题解感觉有点滑稽呢 >_<

然后发现早就有人写过题解了...

Test 1:

发现是一个字母表的映射

把 $'a' \to 'z'$ 打进去找出映射就好了QAQ .

Test 2:

刚刚求助的点。。

答案是 : $2016x^2 + 4x + 10 (\bmod 233333)$

Test 3:

把给的数列输进 $OEIS$ 里。

发现是 : $\lfloor\sqrt{\frac{n}{\pi}}\rfloor$

Test 4:

发现给的是个图?

随便输几个数据进去发现只与连通性有关。

再进一步分析，发现是连通块大小的平方之和。

... ...

Test 5:

带权的树 ?

下面给的 $m$ 个点对是啥？

询问？输出怎么只有一个数？

把询问数改成 $1$...还是输出一个数。。

好像是路径长度？

询问两次相同的？

输出变成零了！！！！

询问三次？

又变回来了。。。

把所有询问得到的结果 $xor$ 输出。。。

Test 6:

怎么跟上一个点这么像。。。

询问改成了路径上最小边权？

其他的一点都没变？

。。。 。。。

Test 7:

输入两个数。。输出一个数？

对于所有的 $(i,1) , (1,i)$ 类型的询问的输出都是 $i$ ?

把这个 $n\times m$ 的表打出来。。

好像似曾相识。。。

怎么好象是 : $\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)$ 啊。。。

打了一下发现还真是。。。

反演一波.

Test8:

这个序列好神奇啊 QAQ ...

怎么我连续输出两个相同的序列得到的答案不一样啊。。。

。。。 。。。

只有数据组数不超过一组时，保证lost的输出正确。

。。。 。。。

$*&@)#(*!($^)(!@#(&!@#!(@&#(!@&(#)(!@)#!)@($(*&!@^#*(!@()!@&*(#^!@(*$

然后搞了一波发现是本质不同的子串数目。。。

Test9:

随便扔几个点进去发现是平面最近点对。。

写了一个都说是 $O(n\log n)$ 实际上跑的死慢死慢的东西跑了十几分钟跑出来了。

Test10:

输出 "invalid input!"

#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
    x=0;static char ch;static bool flag;flag = false;
    while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
    while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
namespace work1{
    char mp[] = {'y','f','r','b','k','g','i','m','u','j','v','p','h','a','t','d','s','n','e','l','o','z','c','x','w','q'};
    char s[100010];
    int main(){
        int n;read(n);
        while(n--){
            scanf("%s",s);
            int m = strlen(s);
            rep(i,0,m-1){
                s[i] = mp[s[i] - 'a'];
            }
            printf("%s\n",s);
        }
        return 0;
    }
}
namespace work2{
    inline void work(){
        int n;read(n);
        printf("%lld\n",(2016LL*n%233333*n%233333+4LL*n+10) % (233333));
    }
    int main(){
        int T;read(T);
        while(T--) work();
        return 0;
    }
}
namespace work3{
    const double pi = acos(-1);
    inline void work(){
        int n;read(n);
        printf("%lld\n",(ll)sqrt((double)n/pi));
    }
    int main(){
        int T;read(T);
        while(T--) work();
    }
}
namespace work4{
    const int maxn = 100010;
    int fa[maxn],siz[maxn];
    int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
    inline void Union(int u,int v){
        int x = find(u),y = find(v);
        if(x == y) return ;
        fa[x] = y;siz[y] += siz[x];
    }
    int main(){
        int T;read(T);
        while(T--){
            int n,m;read(n);read(m);
            rep(i,1,n) fa[i] = i,siz[i] = 1;
            int u,v;
            while(m--){
                read(u);read(v);
                Union(u,v);
            }
            ll ans = 0;
            rep(i,1,n){
                int x = find(i);
                ans += 1LL*siz[x]*siz[x];
                siz[x] = 0;
            }printf("%lld\n",ans);
        }
    }
}
namespace work5{
    const int maxn = 100010;
    struct Edge{
        int to,next,dis;
    }G[maxn<<1];
    int head[maxn],cnt;
    void add(int u,int v,int d){
        G[++cnt].to = v;
        G[cnt].next = head[u];
        head[u] = cnt;
        G[cnt].dis = d;
    }
#define v G[i].to
    int fa[maxn],son[maxn],siz[maxn],dep[maxn];
    int top[maxn],n;ll dis[maxn];
    void dfs(int u){
        siz[u] = 1;
        for(rg i = head[u];i;i=G[i].next){
            if(v == fa[u]) continue;
            fa[v] = u;dep[v] = dep[u] + 1;
            dis[v] = dis[u] + G[i].dis;
            dfs(v);siz[u] += siz[v];
            if(siz[son[u]] < siz[v]) son[u] = v;
        }return ;
    }
    void dfs(int u,int tp){
        top[u] = tp;
        if(son[u]) dfs(son[u],tp);
        for(rg i = head[u];i;i=G[i].next){
            if(v == fa[u] || v == son[u]) continue;
            dfs(v,v);
        }return ;
    }
#undef v
    inline int lca(int u,int v){
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u,v);
            u = fa[top[u]];
        }return dep[u] < dep[v] ? u : v;
    }
    inline ll query(int u,int v){
        return dis[u] + dis[v] - 2*dis[lca(u,v)];
    }
    inline void init(){
        memset(head,0,sizeof head);
        memset(son,0,sizeof son);
        memset(top,0,sizeof top);
        cnt = 0;
    }
    inline void work(){
        init();
        int m;read(n);read(m);
        int u,v,d;
        rep(i,2,n){
            read(u);read(v);read(d);
            add(u,v,d);add(v,u,d);
        }dfs(1);dfs(1,1);
        ll ans = 0;
        rep(i,1,m){
            read(u);read(v);
            ans ^= query(u,v);
        }printf("%lld\n",ans);
    }
    int main(){
        int T;read(T);
        while(T--) work();
        return 0;
    }
}
namespace work6{
    const int maxn = 100010;
    struct Edge{
        int to,next,dis;
    }G[maxn<<1];
    int head[maxn],cnt;
    void add(int u,int v,int d){
        G[++cnt].to = v;
        G[cnt].next = head[u];
        head[u] = cnt;
        G[cnt].dis = d;
    }
#define v G[i].to
    int fa[maxn],son[maxn],siz[maxn],dep[maxn];
    int top[maxn],dfn[maxn],dfs_clock,w[maxn];
    int seq[maxn],n;
    void dfs(int u){
        siz[u] = 1;
        for(rg i = head[u];i;i=G[i].next){
            if(v == fa[u]) continue;
            fa[v] = u;dep[v] = dep[u] + 1;
            w[v] = G[i].dis;
            dfs(v);siz[u] += siz[v];
            if(siz[son[u]] < siz[v]) son[u] = v;
        }return ;
    }
    void dfs(int u,int tp){
        top[u] = tp;dfn[u] = ++ dfs_clock;
        seq[dfs_clock] = u;
        if(son[u]) dfs(son[u],tp);
        for(rg i = head[u];i;i=G[i].next){
            if(v == fa[u] || v == son[u]) continue;
            dfs(v,v);
        }return ;
    }
#undef v
    int T[maxn<<2];
    void build(int rt,int l,int r){
        if(l == r){
            T[rt] = w[seq[l]];
            return ;
        }
        int mid = l+r >> 1;
        build(rt<<1,l,mid);
        build(rt<<1|1,mid+1,r);
        T[rt] = min(T[rt<<1],T[rt<<1|1]);
    }
    int query(int rt,int l,int r,int L,int R){
        if(L <= l && r <= R) return T[rt];
        int mid = l+r >> 1;
        if(R <= mid) return query(rt<<1,l,mid,L,R);
        if(L >  mid) return query(rt<<1|1,mid+1,r,L,R);
        return min(query(rt<<1,l,mid,L,R),query(rt<<1|1,mid+1,r,L,R));
    }
    inline void init(){
        memset(head,0,sizeof head);
        memset(w,0,sizeof w);
        memset(son,0,sizeof son);
        memset(top,0,sizeof top);
        memset(dfn,0,sizeof dfn);
        memset(seq,0,sizeof seq);
        cnt = 0;dfs_clock = 0;
    }
    inline int query(int u,int v){
        int res = 1987654321;
        while(top[u] != top[v]){
            if(dep[top[u]] < dep[top[v]]) swap(u,v);
            res = min(res,query(1,1,n,dfn[top[u]],dfn[u]));
            u = fa[top[u]];
        }
        if(dep[u] > dep[v]) swap(u,v);
        if(u != v) res = min(res,query(1,1,n,dfn[u]+1,dfn[v]));
        return res;
    }
    void work(){
        init();
        int m;read(n);read(m);
        int u,v,d;
        rep(i,2,n){
            read(u);read(v);read(d);
            add(u,v,d);add(v,u,d);
        }dfs(1);dfs(1,1);w[1] = 1987654321;
        build(1,1,n);
        ll ans = 0,x;
        rep(i,1,m){
            read(u);read(v);
            ans ^= (x = query(u,v));
        }printf("%lld\n",ans);
        return ;
    }
    int main(){
        int T;read(T);
        while(T--) work();
        return 0;
    }
}
namespace work7{
    const int maxn = 1000010;
    bool vis[maxn];int pri[maxn],cnt;
    ll f[maxn];
    inline void liner(int n){
        f[1] = 1;
        rep(i,2,n){
            if(!vis[i]) pri[++cnt] = i,f[i] = i - 1;
            rep(j,1,cnt){
                ll x = 1LL*i*pri[j];
                if(x > n) break;
                vis[x] = true;
                if(i % pri[j] == 0){
                    f[x] = f[i]*pri[j];
                    break;
                }f[x] = f[i]*f[pri[j]];
            }
        }
        rep(i,1,n) f[i] += f[i-1];
    }
    inline void work(){
        int n,m;read(n);read(m);
        if(n > m) swap(n,m);
        ll ans = 0;
        for(rg i = 1,j;i <= n;i = j+1){
            j = min(n/(n/i),m/(m/i));
            ans += (f[j] - f[i-1])*(n/i)*(m/i);
        }
        printf("%lld\n",ans);
    }
    int main(){
        liner(1000000);
        int T;read(T);
        while(T--) work();
        return 0;
    }
}
namespace work8{
    const int maxn = 1000010;
    struct Node{
        int nx[21];
        int len,fa;
    }T[maxn<<1];
    int last,nodecnt,num[maxn<<1];
    inline void init(){
        last = nodecnt = 0;
        T[0].fa = -1;T[0].len = 0;
        rep(i,1,20) T[0].nx[i] = 0;
    }
    inline void insert(int c){
        int cur = ++ nodecnt,p;
        rep(i,1,20) T[cur].nx[i] = 0;
        T[cur].len = T[last].len + 1;
        for(p = last;p != -1 && !T[p].nx[c];p = T[p].fa) T[p].nx[c] = cur;
        if(p == -1) T[cur].fa = 0;
        else{
            int q = T[p].nx[c];
            if(T[q].len == T[p].len + 1) T[cur].fa = q;
            else{
                int co = ++ nodecnt;
                T[co] = T[q];T[co].len = T[p].len + 1;
                for(;p != -1 && T[p].nx[c] == q;p=T[p].fa) T[p].nx[c] = co;
                T[cur].fa = T[q].fa = co;
            }
        }last = cur;++ num[last];
    }
    int c[maxn],a[maxn],cnt;
    void work(){
        init();int n;read(n);
        rep(i,1,n) read(a[i]),c[i] = a[i];
        sort(c+1,c+n+1);cnt = unique(c+1,c+n+1) - c - 1;
        rep(i,1,n) a[i] = lower_bound(c+1,c+cnt+1,a[i]) - c;
        rep(i,1,n) insert(a[i]);
        ll ans = 0;
        rep(i,1,nodecnt) ans += T[i].len - T[T[i].fa].len;
        printf("%lld\n",ans);
        return ;
    }
    int main(){
        int T;read(T);
        while(T--) work();
        return 0;
    }
}
namespace work9{
    const int maxn = 1000010;
    struct Point{
        int x,y;
        Point(){}
        Point(const int &a,const int &b){
            x = a;y = b;
        }
    }p[maxn];
    inline double dis(const Point &a,const Point &b){
        return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
    }
    inline bool cmpx(const Point &a,const Point &b){
        return a.x == b.x ? a.y < b.y : a.x < b.x;
    }
    inline bool cmpy(const Point &a,const Point &b){
        return a.y < b.y;
    }
    Point tmp[maxn];int n;
    double solve(int l,int r){
        if(l == r) return 1e10;
        if(l == r-1) return dis(p[l],p[r]);
        int mid = l+r >> 1;double d = 1e10;
        d = min(solve(l,mid),solve(mid+1,r));
        int cnt = 0;
        rep(i,1,n) if(abs(p[i].x - p[mid].x) < d) tmp[++cnt] = p[i];
        sort(tmp+1,tmp+cnt+1,cmpy);
        rep(i,1,cnt){
            rep(j,i+1,cnt){
                if(abs(tmp[i].y - tmp[j].y) >= d) break;
                d = min(d,dis(tmp[i],tmp[j]));
            }
        }return d;
    }
    inline void work(){
        read(n);
        rep(i,1,n){
            read(p[i].x);read(p[i].y);
        }sort(p+1,p+n+1,cmpx);
        printf("%.3lf\n",solve(1,n));
    }
    int main(){
        int T;read(T);
        while(T--) work();
    }
}
namespace work10{
    inline void work(){
        puts("invalid input!");
    }
    int main(){
        int T;read(T);
        while(T--) work();
    }
}
int main(){
    int n;read(n);
    if(n == 1) work1::main();
    if(n == 2) work2::main();
    if(n == 3) work3::main();
    if(n == 4) work4::main();
    if(n == 5) work5::main();
    if(n == 6) work6::main();
    if(n == 7) work7::main();
    if(n == 8) work8::main();
    if(n == 9) work9::main();
    if(n == 10) work10::main();
    return 0;
}

求助各位dalao..

消失的源代码的 test2 到底是什么啊。。

搞得我不知所措啊 QAQ ...

遇到了一个问题，向各位dalao求助.

给定一个长为n的序列(数字大小两两不同),老师想把这个序列排序。
他会掷一枚均匀硬币.如果正面朝上,他就会选择一对满足左边的数比右边大的相邻元素进行交换,否则选中一对满足左边的数比右边小的相邻元素进行交换.
如果无法进行交换,他就再扔一次硬币.如果序列按递增顺序排好序,那么操作结束.问期望的操作次数
(n <= 3000)

这道题我写出了一个算法，但是发现算出来的所有的答案都是整数。 是不是这个题的性质就决定了答案一定是整数？

本苣表示不理解，希望各位dalao能够解答一下。 感激不尽。。。

我不知道谁给我发的博客。。。

反正我们全机房共用一个IP..

Day 0:

联赛前一天，收拾行装准备出发了！
大家都激动了，那个早上闹的可欢了，拿着胶带扔来扔去。
   一堆一堆没吃完的苹果和蜂蜜都分了下来，都装不下了。。
但是闹的这么欢的时候居然还有人躲了起来，一副(你们这群愚蠢的人类)的样子
藏到了南楼梯口上，不过还是被我发现了(你们火星人也聪明不到哪去)
临走的时候叫上了(ZS)，然后我们抱着(衡水老白干？)出发了！

大巴车，高铁上，一切都很浪。
还见到了高一的学弟(学妹?)我们的学妹呢？

晚上分到了鱼蛋蛋,味道还不错啊。

大晚上的没睡觉看饥饿游戏看到了12点多。

Day 1:

早上吃了早饭(黄焖鸡米饭)就早早地在考场前面等着了。
一边希望着这次的题不要太简单也不要太难，恰好我都会就行了。
进考场，拉键盘，开编译器，然后... ...
WTF,不能动电脑！？
被你们打败了，，，干坐了半个小时～！@#￥%……&×（）——+，
一开包：
    T1:
        哎呀，水题。
       T2:
        。。。 。。。
        没有什么思路，一会想一想应该能想出来吧
       T3:
        WOC,概率期望，，，你们这是要翻天了啊！
   花了10mins左右打完了第一题，开始看第二题，结果怎么想也没有思路，怎么想也没有思路，再怎么想也没有思路。
看来还是拿部分分吧，这道题貌似有很高的部分分，不过就是程序难写一点，先放放，去想想第三题。
第三题完全有思路，状态秒出，转移也秒出。20mins敲完，调了半小时还没调出来。

时间过去一个多小时了，不行，先把暴力程序都打上！
于是先把第三题的暴力打上了，过去了40mins左右搞出来了，还加了几个小剪枝。
返回去敲第二题的暴力，我敲了1h多，敲出来了80分的，放下了。
发现时间不够了！
赶紧检查文件名，检查各种的低级错误and数组大小。
最后给T3加了一种情况。交了上去。
从考场出来，感觉要废！

虽然感觉自己要废了吧，，但该浪还是得浪！
浪了一下午！
MC + 饥饿游戏 + 黑乐谱 + bilibili
非常感动、感激、感谢爸妈，在这个时候赶了过来。
让我这要废的心灵受到了抚慰

Day 2:

早上依旧去吃早饭，不过这次去吃饭和Day 1不同了。
这次是带上了一个活宝(ZS)去吃饭。
终于可以找一个人和我一起浪了。

开考：
    T1:
        水题啊！
    T2:
        直接骗分60啊
    T3:
        状压Dp骗分70啊
       0 mins
    开始码T1,码完了，样例都不过，发现自己的方法错了，，，
    想了一会才想出可以直接推过去。。。
    30mins
    T2直接上堆，去骗分，骗完了就没有管他。
    1h 10mins
    T3推二元一次不等式推了半天，，
    其实主要是一直以为是自己推错了，过不了自己手算的数据，最后才发现是自己手算的数据算错了
    然后开始状压，为什么我想到的是枚举两个集合啊，，，这是O(4^n)的啊，直接枚举子集的子集就可以做到O(3^n)啊，，，
    O(3^n)就80了！这样我只打到了60分。
    2h 30 mins
    然后打了打对拍，把三个程序都拍了一遍。

    出考场，直接被爸妈带到了海边去。
    好冷啊！

After Ended

我们坐车连夜回到了衡水。
在NOIP倒计时上挂上了-1，终于结束了啊。