NOI前作业-解题报告

· · 个人记录

Part 1 图论

CF1054F Electric Scheme

ri，好像自己犯傻了，明明50行的事，我的方法足足有200行...

这种不能相交的限制，联想到最小割。我们的线段肯定是连接相邻的点，我们可以把这些边找出来，把横竖相交的用最小割表示出来，然后跑网络流即可。

注意：时刻区分两种方向的边！！！最小割输出方案不能看流量，要从S开始dfs一遍！！！

CF1009G Allowed Letters

不会做提高组题目了...

输出最小字典序，我们选择按位确定。二分图一侧只有6种点，可以用霍尔定理判断有无完美匹配！

CF590E Birthday

建出AC自动机，边为fail边和Trie树上父子边，求最大独立集即可。

然而最长反链的求法挺恶心的，不如网络流最小割（

「2017 山东一轮集训 Day7」养猫

貌似想到把区间作为点，这道题就做出来了。

但是建出来的图可能会有正环（跑最长路），那么需要手动消圈！

有挺多细节的，而且需要注意“循环流”也是可以的。

upd on 19.6.11：有了优秀的消负环方法，可以很方便地解决啦

貌似正常人的写法：类似最长k可重区间集，我们先建立一条主链来限制不选择的最大次数，然后加一些[i,i+k]的边表示一次选择，注意开头部分不要做限制就行了。然后跑最小费用最大流。

CF704D Captain America

水题。对行列建点，因为每个点的两种权值都一样，争取选权值大的。

CF786E ALT

树剖+最小割。因为树的形态固定，所以可以倍增优化建图

CF986F Oppa Funcan Style Remastered

对质因数个数分类讨论，1和2特判，剩下的跑剩余系最短路。

CF757F

最短路DAG+支配树。

未知题目

一个无向图，你需要找两个点s, t，使得s到t有三条不相交的简单路径。判断是否有解并输出方案。

首先两点一定在一个点双里，然后对于一个点双，如果这个点双是一条边，或者整个点双是一个简单环，那么这个点双中是无解的；否则一定有解。

构造？环+一条弦组成3条路。

Part 2 计数

Atcoder Dark Horse

哇，好题好题，只能想到O(4^n)的做法...

首先有一个简化思考的步骤：游戏可以看作一棵满二叉树，叶子的中序遍历是这个序列，每个非叶节点表示子树内的最小值。那么根据对称性，1在任何地方的答案都和1在第一个位置的答案一样。

然后限制就变成：有n个不相交区间，每个区间的最小值都不能是这m个数，问方案数。有一个显然的从小到大填数，状压DP记录几个区间内有数。但是复杂度过不去？这就要用计数的好方法——容斥！

我们枚举至少几个区间不符合要求，我们从大往小填数，为了使得最小值就是我们希望的数，我们每次填就把整个区间填满，中间的系数可以用阶乘算出来。

for(ri i=m; i>=1; --i)
    for(ri S=U-1; S; --S)
        for(ri j=0; j<n; ++j)
            if((S>>j)&1)
                inc(dp[S],mul(dp[S^(1<<j)],C(U-a[i]-(S^(1<<j)),(1<<j)-1),fac[1<<j]));

AT3576 Popping Balls

见另一篇博客。

AT2000 Leftmost Ball

啊啊啊感觉降智了...填一个序列，除了从前往后填，还可以一种一种（从小到大）填，有时这样不容易算重！

AT2371 Placing Squares

见另一篇博客...一道小水题。

CF889E Mod Mod Mod

好像只会做到O(V\log V)？如何筛选出可能成为最优解的数字？

好题！见另一篇博客。

HDU 5181

Trick掌握的不够，看了一眼提示才做出来。

遇到卡特兰数+限制——括号序、出栈序，尝试建出来一棵树，对区间进行“树形DP”

对于这道题，我们可以把数字x从入栈到出栈的这一段看成点x的子树，那么有性质：

  1. 这棵树的先序遍历是1-n
  2. 每个点比它的后代晚出栈

于是我们可以直接DP符合要求的树的个数——也就是区间DP！枚举区间划分的中点，只考虑区间内部的限制条件。

Part 3 树上问题

CF860E Arkady and a Nobody-men

对BFS序的每一层建立虚树统计答案。每个点的答案可以从父亲处继承过来。

CF772E Verifying Kingdom

正确与错误的区别很迷？不知道咋就对了。

在树上定位一个点的最好方法是点分治

我们在树上点分治，向哪个方向走可以通过询问重心的两个儿子得到。

洛谷博客关停了

AT3912 Antennas on Tree

这道题我的思路大题是对的，但是细节理解的很不透彻。

首先这道题的切入点在叶子。对于一个点，如果有k个儿子，那么至少要有k-1个儿子有观察点，然后我就自己YY了一个队列的做法，挂掉了。看了一下zzt的题解，发现可以这么理解：我们选出的k个点符合要求，当且仅当这k个点构成的斯坦纳树，之外的点，组成一条条链，且每个点最多只和一条额外的链相连。

哦好像自己原来瞎写的贪心是对的，就是while循环continue的时候忘做一件事了。

【UTR #1】ydc的大树

树形DP统计每个黑点到最远黑点的路径的交即可，然后树上差分。

AT2377 Blue and Red Tree

感觉自己的思路很好，发一篇题解

AT4504 Wandering TKHS

单独发一篇

Part 4 DP

DP=计数+贪心...

AGC030F Permutation and Minimum

这道题的大致思路很好想，但是到了具体细节和思路就卡住了。

首先我们肯定是按照大小顺序填数，然后记录有多少对未完成。我原本想的是从小到大填数，需要记录有多少pair没填、有多少pair填了一个、有多少原本就有的pair还差一个，于是复杂度就炸了。

正解是从大往小填数，这样一对数只有被填完后才有贡献，更加自由。只需要记录有多少pair填了一个，有多少原本就有的pair还差一个。

这样做的好处是当我们填了一个固定的数，我们可以拉一个填了一半的pair过来！而我们想要新建一个pair的时候永远可以新建一个：因为不合法的方案无法到达最终答案。还有一个好处是，我们最后再乘以cnt[(-1,-1)]!，这样就不用区分每个填了一半的pair了！

CF1067E Random Forest Rank

这个题就是考你一句话：树的邻接矩阵的秩=最大匹配数×2

51nod 1947 栈的代价和

这谁顶得住啊...只会O(n^2)

f[i]表示1~i的入栈的种类数。

g[i]表示1~i入栈的对于每种情况栈内元素个数的和求sigma 。

h[i]表示1~i入栈的对于每种情况栈内元素值的和求sigma 。

容易得到转移：

f[0]=1；

f[i]=sigma(f[j-1]*f[i-j]) j=1~i-1；

g[i]=sigma(f[j-1]g[i-j]+(g[j-1]+jf[j-1])*f[i-j]) j=1~i-1；

h[i]=sigma(f[j-1](h[i-j]+g[i-j]j)+(h[j-1]+f[j-1]j+g[j-1])f[i-j]) j=1~i；

h[n]即为所求。

观察发现f,g,h均可写成母函数形式，且递推式为卷积。

经过计算可以得到h的通项公式h[n]=n4^(n-1)/2+binomal(2n-1,n-1))/2n

预处理阶乘即可。

UOJ 428【集训队作业2018】普通的计数题

这谁顶得住啊...首先题意转化就非常神仙：把0号操作看成叶子，1号操作看成非叶节点；要求：父亲编号大于儿子编号；每个非叶节点要么与x(x\in B)个叶子相连，要么与至少一个非叶节点，以及x(x\in A)个叶子相连。

式子大概是

F'=B+A(\exp(F-x)-1)

牛顿迭代！

具体看另一篇博客吧。

UOJ 424【集训队作业2018】count

这谁顶得住啊...

shadowice1984的清晰题解

首先要意识到这道题要我们求的就是不同的笛卡尔树的个数。

具体看另一篇题解吧。

UOJ 449【集训队作业2018】喂鸽子

肯定要min-max容斥，然后可以NTT优化DP，或者换一种理解方式，直接DP。

具体看另一篇博客吧。

UOJ 422【集训队作业2018】小Z的礼物

min-max容斥+插头DP。我们不能直接状压子集，注意到计算答案，只和“没有任何覆盖集合中的点的pair数”有关，我们可以f[k][S]表示pair数为k，上一行的选择情况为S的带系数贡献和，然后插头DP转移即可。（好写好调？

北大集训 点分方案数

求一棵树的点分治方案数，两个方案不同指点分树不同。

树形DP考虑合并子树。

假如合并p,q，其中q是p的儿子。那么如果某一次的重心选择的是p,q，这两部分就断开了。而每次选择一个重心，这个重心的子树的方案数也都确定了。事实上，合并产生的新方案数就是把p,q在点分树上的祖先合并起来！

所以我们只要记录点分树上的深度即可。所以式子大概是：

f(p,i)f(q,j){k-1\choose i-1}\to f'(p,k),k\le i+j

维护后缀和即可。

void dfs(int x,int _fa)
{
    for(solid v:E[x]) if(v!=_fa) dfs(v,x);
    sz[x]=1,dp[x][1]=1;
    for(solid v:E[x])
    {
        if(v==_fa) continue;
        static int f[N];
        for(ri i=1; i<=sz[x]; ++i)
            for(ri j=0; j<=sz[v]; ++j)
                inc(f[i+j],mul(C(i+j-1,i-1),dp[x][i],dp[v][j]));
        sz[x]+=sz[v];
        for(ri i=1; i<=sz[x]; ++i) dp[x][i]=f[i],f[i]=0;
    }
    for(ri i=sz[x]; i>=0; --i) inc(dp[x][i],dp[x][i+1]);
}

北大集训 矩形面积周长

你可以在平面上任意画出长宽都是正整数的矩形。有 T 次询问，每次询问是否存在一种画矩形的方案满足周长之和为 C，面积之和为 S。 T, C, S ≤ 10^5

哇，这道题的优化真的强。

考虑暴力的DP状态f[i][j]表示周长为i面积为j是否可行。

首先我们有一个O(n^3\log n)的做法：枚举n\log n种矩形转移。

优化一：

考虑矩形a\times b+a\times c;a\le b,c，可以等价为a\times (b+c-1)+1\times a，也就是说，对于每一个短边a，至多有一个矩形，剩下都是1\times 1的矩形。那么我们可以枚举短边a\le \sqrt{n}，然后用新数组辅助DP：g[i][j]表示周长为i面积为j且至少有一个短边为a的矩形是否可行，转移：

f[i][j]\to g[i+4a][j+a^2];g[i][j]\to g[i+2][j+a]

优化二：

注意1\times 1的矩形形成了一个“同余关系”：(i,j)\Leftrightarrow (i+4,j+1)

我们可以设dp[i]表示满足4S-C=i的情况下S的最小值。

于是状态O(n)，转移O(n\sqrt{n})

#define N 100005
// 4S-C = i, min S
const int n=100000,z=N,inf=0x3f3f3f3f;
int f[N*5],g[N*5];
void prework()
{
    mem(f,0x3f);
    f[z]=0;
    for(ri w=1; w*w<=n; ++w)
    {
        mem(g,0x3f);
        for(ri i=-n; i<=4*n; ++i)
        {
            if(f[z+i]==inf) continue;
            int S=f[z+i],C=4*S-i+4*w;
            S+=w*w,C=4*S-C;
            if(C<=4*n) ckmin(g[z+C],S);
        }
        for(ri i=-n; i<=4*n; ++i)
        {
            if(g[z+i]==inf) continue;
            ckmin(f[z+i],g[z+i]);
            int S=g[z+i],C=4*S-i+2;
            S+=w,C=4*S-C;
            if(C<=4*n) ckmin(g[z+C],S);
        }
    }
}
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
    // freopen("ot.out","w",stdout);
#endif
    prework();
    int T,C,S; in(T);
    while(T--)
    {
        in(C,S);
        out(f[z+4*S-C]<=S?1:0);
    }
    return 0;
}

Part 5 匹配与流

Problem Buyer

为啥10^7带\log 能过...写线段树还拿了第3优解...

转化题意：求最大的区间集合，使得不能和需求有完美匹配。

根据霍尔定理，我们只要让某个需求的集合有交的区间个数小于集合大小即可，也就是

\min(cross(l,r)-(r-l))

扫描线+线段树即可。

注意，虽然这道题最小值的位置单调不降，但是不能维护一个指针扫！

上面的解法是错的！

因为霍尔定理要求的是所有子集，而这道题，所有区间并不是最严格的限制！

比如这个例子：

看任何区间都是合法的，但是选\{1,3\}就不合法。

正解是这样的：

对每个位置，求出有多少区间不包含它，设为c个，那么如果我们选了c+1个区间，就一定能覆盖它。

那么我们还要考虑这个位置占用了一个区间对后面的影响。我们的最优决策是从前往后扫，每次选择经过它的右端点最靠前的删除！

这个证明依旧十分感性，事实上我们每次计算的值不一定有意义，但是我们可以保证有意义的答案一定被统计了。

这个博客说的挺真的

GYM101194J

感觉也不难想...就是这个套路确实是没想到...

首先网络流建图，最困难的就是解决“分流”问题，我们想让某个点“要么选择a，要么同时选择b和c”，很难保证不会选a和c这样的。

这就要用到题目的特殊性质了，对于这道题，我们将网格黑白染色，规定黑色的流纵向进，横向出；白色反之。然后每个点再设一个上下界，跑最小费用最大流即可。

最小费用最大流的消负环方法

Topcoder Farmville

见“对偶型”博客。

Topcoder ColorfulPath

哇哦，好题！又是我不会的对偶定理

ri，这道题调了我半天...判无解是大于等于inf不是等于！网络流流量为LL！

这道题一个重要的性质就是边的区间不相交。如果我们把边的包含关系建出一棵树来，那么这棵树的割对应原图中的一条路径！

一般我们是把最小割转为对偶图最短路，但是这次我们反着做！这样做的好处是可以通过最小割的建图方法，满足更多的限制，而这些限制要想在最短路上体现出来，往往需要状压。

建出来一棵树，点x对应的父亲边的流量为这条边的权值，叶子连向T，我们把“区间左端点为同一个颜色”的点x的父亲之间互相连边（画图可以知道为什么），但是这样可能出现祖先后代同时被割的情况，那么我们每个点向fa连inf边就行了。

BZOJ 3593

ri，如果我早点看到这个课件，昨天考试的T2就是原题了...

首先考虑没有“神奇药水”怎么做。这个DP一定是一个后缀更新，我们可以用平衡树维护差分。

现在考虑神奇药水：

？？？为啥我O(n^2)暴力过不去，写O(n\log n)就能过？？？：暴力写错了...

如果使用者在最优解集合内，一定是给b_i最大的服用；

否则一定是给不在最优集合的a_i最小的服用（毕竟b_i的大小无所谓了，a_i更小肯定更优）。

Part 6 计算几何

见计算几何-学习笔记/个人总结

Part 7 杂题

CF494C

见另一篇博客。

POJ 1322 Chocolate

这**题，因为只保留3位小数，所以只计算前1000次即可。

哦，这道题是有n\le 10^9,m\le 10^5的做法的，（其实我一开始也在推生成函数，后来可能是哪里算重了就弃了），类似CTS珍珠的做法，我们分奇偶生成函数。

然后式子大概是

可以看作关于e^x的多项式，用FFT计算系数。

如何把n!去掉？e^x展开式的有/n!，所以不用管。

Topcoder LongPalindromes

求一个字符串的回文子序列个数：

dp[l,r]=dp[l+1][r]+dp[l][r-1]-[s[l]\not =s[r]]dp[l+1][r-1]

理解：如果s[l]\not =s[r]，那么要减去算重的部分。否则可以在这些方案两边加上s[l],s[r]构成新方案。

我们发现长度为len的区间的方案仅由len-1,len-2转移过来，我们可以暴力矩乘！

AT1148

二分，二维前缀和。

hihocoder 1286

以为这道题很神仙，看了题解之后发现要找出一个小Trick就能做这道题：

假设我们当前选择的矩形的sum为s，那么把矩形向右下平移一格后，sum变为s+nm，所以我们可以枚举矩形属于哪一个“斜线”，然后exgcd算一下位置即可。

UR#2 跳蚤公路

感觉和51nod地铁环线那道题很像啊，对每个SCC找负环的区间，感觉挺真的，我写写试试。

是对的，但是WA的不明不白的...把环上总边权=0时的返回值特判不对，返回1不对，返回0就对了...还有一个很神奇的Hack数据，都输出0，我有的输出了-1？而且spfa确实没有跑出负环？不太清楚，特判过了。

hihocoder 1414 Rikka with Grid

这道题挺强。

首先，对于矩形匹配问题，可以求出每个位置向上向左延伸的极长长度，然后与矩形的长和宽比较

对于这道题，我们维护n种bitset数组表示(i,j)位置向上/向左能否延伸p格，求解的话枚举矩形的下边界，然后&一下即可。

但是O(n^3/w)的空间过不去，怎么办？我们建立ST表，区间查询是可重的！

Part 8 概率与期望

CF258D

动态维护f[i][j]表示i位置上的数<j位置上的数的概率。

CF446D

关键是如何快速求出从i号关键点到j号关键点的概率。感觉自己好久没做高斯消元概率DP题了...这道题的方程是这样的：

我们给每个关键点设一个虚点，规定到这个关键点的边都连到对应的虚点，这样就可以区分这个点回到自己的方案了。

其实这样说也不太对，我们可以认为我们同时在进行多个高斯消元，常数项是一个向量，进行按位加减乘除！

ri，数组开小调了20min...

CF618G Combining Slimes

还是CQ_Zhangyu写的题解清楚。不过像这些题目，都是利用浮点数误差来做的，对于\bmod 998求期望的题没啥用。

设a[i][j]表示用i个格子凑出数字j的概率，那么显然有a[i][j]=a[i][j-1]\times a[i-1][j-1]，表示先用i个格子凑出j-1，然后还剩下i-1个格子，再凑出i-1。

为了方便转移，我们再设b[i][j]，限制最左边必须是2.其余和a[i][j]一样。

但是DP完之后，这个还不是最终的概率，事实上，最终的概率应该是a'[i][j]=a[i][j](1-a[i-1][j])，这样才能保证不合并。

**注意上边我们的DP都是从右往左DP，换句话说，总格子数为i** 当项数$>50$，我们可以认为$a$近似不变了，也就是转移系数不变了，那么我们可以矩乘。 ### CF913F Strongly Connected Tournament 好题！不过自己做出来了！ 这道题难点在于边的方向是有概率的，于是每一部分的贡献都要乘上概率，往往这一块比较恶心。 见到SCC这方面的题，可以类比《射命丸文的笔记》，我们枚举拓扑序最小的SCC。 设$f[i]$为大小为i的**未定向**图的答案，$e[i]$为**已定向**图的答案，$g[i]$为i个点组成SCC的概率，$h[i][j]$表示左边有i个点，右边有j个点，之间的所有边都指向右边的概率。 $$f[n]=1+\sum_{i=1}^n{n\choose i}g[i]h[n-i][i](f[i]+e[n-i])$$ 其他的转移式类似。 ### Gym - 101981F Frank 幸好有wxh的题解...神题神题！ 我们设$f(i,j)$表示从i到j的期望步数，$g(i)$表示从i走一圈回到i的期望步数，那么有转移： $$f(i,j)=1+\sum_{(i,k)\in E} f(k,j)/du[i]-[i=j]g(i)$$ **我们又可以把$f(i,*)$看成一个向量来高斯消元！** 我们先考虑如何求$g(i)$：设$p(i)$表示走无限步之后到i的概率，那么$g(i)=1/p(i) $$p(i)=\sum_{(j,i)\in E}p(j)/du[j]$$ 注意是找i的所有入点！ 直接解解不出来，**似乎因为邻接矩阵的秩是n-1！**，我们任意去掉一个等式，补上$\sum_ip(i)=1

同样的，f(i,*)的矩阵秩也是n-1，也就是说我们无法直接解出来答案，只能解出一组特解。

但是我们知道f(i,i)=0，可以用这个调整。

比方说解出来f(i,i)=x，带入到式子：

f(i,i)=1+\sum_{(i,k)\in E} f(k,i)/du[i]-g(i)

因为1和g(i)是常数不能动，那么只有一种可能：f(*,i)都多加了x，我们减去即可。