The 2020 ICPC Asia Macau Regional Contest

如何读对题意，如何调对代码，这些真的都是硬伤啊。。。

以后一定要一道题有两个人读题才行。

[A Accelerator]

solution

题面：给定长度为的数组，对于的所有排列，计算的期望。

做法：稍微观察下每个的贡献，就能发现求的正是，然后每一项可以通过组合意义得知乘上一个系数加起来。那么直接分治算下就好了，不懂为什么启发式合并会 T？时间复杂度。

[B Boring Problem]

solution

题面：ACAM 上随机游走。

做法：链剖后主元法消元。

[C Club Assignment]

solution

题面：有个数，现要拆分成两个集合，最小化两个集合内的两两元素的异或的最小值的较小值。

做法：这等价于从小到大贪心，每次把异或和小的那个拆开来放在两边，直到不能放了。这样是以上的复杂度。

发现这个过程类似，考虑搞出了最小异或生成树，那么树上有边的点肯定都不能在一个集合了，于是就直接结束了。而最小异或生成树太经典了，最简单的做法就是加上维护下即可。时间复杂度。

[D Artifacts]

solution

题面：

做法：听说是原神题+大模拟，队友写的，我不知道。

[E Mountain]

solution

题面：

做法：

[F Fixing Networks]

solution

题面：个点，要求构造一张图，使得每个点的度数为，且被分成了个连通块。

做法：先判断为奇数的情况，然后搞一堆完全图，最后一些点搞一个环，每个点向两边延伸，如果要求奇数度数就再向对角的点连边。这一定有解，因为度数为奇数的话点数一定为偶数，所以对角的点是惟一的。

[G Game on Sequence]

solution

题面：A 和 B 在玩一个游戏，这个游戏一开始在一根轴上有个位置，每个位置上都有一个数，每个数的大小在之间。游戏一开始有个小人在这个位置上，每个人需要轮流将小人向右移动到另一个位置上，要求位置上的数和当前位置上的数在二进制上最多只能有一位不同，当轮到一个人不能移动时，这个人便输掉了这轮游戏。在游戏开始之前，游戏可以重复的增加一个数放在数轴的最右边，对于每次询问需要回答谁会赢得这场游戏。（假设两人都足够聪明，会采用最优策略）

做法：容易发现只跟最右边的点有关，看下数据范围，直接暴力做就过了。时间复杂度。

[H Fly Me To The Moon]

solution

题面：

做法：

[I Nim Cheater]

solution

题面：博弈，每次可能加入一堆或撤销上一次操作。Alice 先手，但 Bob 可以先拿走若干堆石子。每堆石子都有一个代价，每次操作后，问 Bob 必胜所要花费的最小代价。

做法：的结论告诉我们要求石子异或为，有撤销操作，注意到撤销仅对相邻的起效，于是无需线段树分治，可以直接搞出一棵树。设表示异或为时的最大代价，每个点的答案是它到根的路径上的值。直接暴力则要求每个点求一遍，空间复杂度是。考虑类似的做法，只记录重链信息，即先递归算轻链，最后算重链，并保留重链信息，这样由于一个点到根的路径上只有条轻边，所以空间复杂度降到，时间仍然是。

//2021.10.25 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e4+10;
namespace MAIN{
    int n;
    char str[10];
    int fa[N],cnt,sxor[N];
    Pair a[N];
    vector<int> G[N];
    int id[N];
    LL ans[N];
    LL f[14][16384],g[16384];
    int sz[N],son[N];
    void dfs_sz(res x){
        sz[x]=1;
        for(auto tox:G[x]){
            dfs_sz(tox),sz[x]+=sz[tox];
            if(!son[x]||sz[son[x]]<sz[tox])son[x]=tox;
        }
    }
    void dfs(res x,res dep){
        ans[x]=f[dep][sxor[x]];
        if(!son[x])return;
        for(auto tox:G[x]){
            if(tox==son[x])continue;
            for(res S=0;S<16384;S++)f[dep+1][S]=min(f[dep][S],f[dep][S^a[tox].fi]+a[tox].se);
            dfs(tox,dep+1);
        }
        for(res S=0;S<16384;S++)g[S]=min(f[dep][S],f[dep][S^a[son[x]].fi]+a[son[x]].se);
        for(res S=0;S<16384;S++)f[dep][S]=g[S];
        dfs(son[x],dep);
    }
    inline void MAIN(){
        n=read();
        res now=0;
        for(res i=1;i<=n;i++){
            scanf("%s",str+1);
            if(str[1]=='A'){
                res x=read(),y=read();
                a[++cnt]=mp(x,y),fa[cnt]=now,sxor[cnt]=sxor[now]^x,G[now].pb(cnt),id[i]=(now=cnt);
            }
            else id[i]=(now=fa[now]);
        }
        for(res i=1;i<16384;i++)f[0][i]=INF;
        dfs_sz(0),dfs(0,0);
        for(res i=1;i<=n;i++)printf("%lld\n",ans[id[i]]);
    }
}