noip模拟试题（一）-坤特牌

首先可以想到一种贪心，但如果牌这样传递会出现问题（-> -> <- <-），形成了一个峰形

其实贪心能做，但是我现在不知道怎么做，懒得想了，好像类似记录透支之类的

经过不断画图实验（面向样例编程），发现可以建树再进行拓扑排序（虽然其实树不用拓扑，但是拓扑模板方便）

对于 1~n-1 每个点，若右边缺少牌（设缺少的牌数为k），则向右边节点连一条长度为k的边。如果右边牌多了则由i+1向i连长度为k的边，之后拓扑的时候进行类似dp操作

主要部分：

void topsort(){
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(!d[i]) q[++tt]=i;
    while(hh<=tt){
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            d[j]--;ans=(ans*getc(f[t],w[i]))%mod;
            f[j]+=w[i];f[t]-=w[i];  
            if(!d[j]) q[++tt]=j;
        }
    }
}

还有建边
for(int i=1;i<=n;i++) scanf("%lld",&f[i]),m+=f[i],s[i]=s[i-1]+f[i];
        m/=n;
        for(int i=1;i<n;i++){
            int r=s[n]-s[i],rc=n-i;
            int a2=r-rc*m;
            if(a2<0) add(i,i+1,-a2);
            else add(i+1,i,a2);
        }

2. noip模拟测验（一）-strategy

这dp太水了，都懒得说了。

就正反进行dp，注意不一定非要attack k次，可以<k次

贪心也是csp-j难度

3. noip模拟测验（二）-easy LCA

lca一种非常强的性质：A1,A2,A3……An的lca，必然为其中两个Ai,Aj的lca

也就是如果预处理出 lca(A1,A2),lca(A2,A3),lca(A3,A4)……lca(Ai,Ai+1)……lca(An-1,An)，那么任何区间l,r的lca都一定是l~r所有相邻lca的一个

于是我们反向思维，不是枚举l,r，而是枚举每个lca，求最多这个lca的贡献

可以使用单调栈维护每个i点最多能覆盖到的l,r，使得l~r中所有相邻lca的深度都>枚举的lca。发现可以使用单调栈

具体有很多细节，反正挺恶心（其实我还没调出来）

另外，从这题我还学会了用欧拉序+ST表求lca，O(1)查询，记得复习

4. noip模拟测验（三）-Scarborough Fair

过于恶心，我觉得我这辈子都不配碰这个题