NOI前-我爱学习-解题报告

· · 个人记录

CF981H

拆开式子后发现可以对每个点分治NTT维护，然后我们想想暴力枚举重叠路径的长度，不是直上直下的链，树形DP一下即可；是直上直下的链，发现我们需要做多项式除法！？如何保证复杂度？

法一：对于度数分类讨论，度数少的暴力，度数大的，注意到不同的数字最多\sqrt{N}种，用另一种形式的暴力。

法二：分治+pushup

CodeChef - SSPLD(S Semi-palindromic)

唔，好题。FWT+快速幂。

很容易构造出转移矩阵，但是直接矩乘会T的很惨。事实上，我们可以手动矩乘！记A[i][S]表示\mod S余i，奇偶性为S的方案数，第二维是FWT之后的值。

CodeChef - BICONT(Edge Addition)

给定一棵树，每条未出现的边有1/2概率出现，求每个边双个数的概率。

我们定义树上的边$(u,v)$联通，当且仅当u,v在一个边双。那么，有i个边双等价于断开了i-1条边。于是我们设$f[x][i][j]$表示点x子树中，至少断开i条边，与j通过联通的边连接的点有j个。枚举两组i,j，转移： 1.断开这条边：记得乘上$2^{(j-1)(j-2)/2}$，因为这些边可以任意连。 2.连接这条边，j相加即可。 然后二项式反演一下就好啦！ ```cpp void dfs(int x,int _fa) { sz[x]=1; f[x][0][1]=1; for(solid v:E[x]) { if(v==_fa) continue; dfs(v,x); for(ri i=sz[x]-1; i>=0; --i) for(ri j=sz[x]; j>=1; --j) { int &w=f[x][i][j]; if(!w) continue; for(ri k=0; k<sz[v]; ++k) for(ri h=1; h<=sz[v]; ++h) { const int p=mul(w,f[v][k][h]); if(!p) continue; // cut the edge inc(f[x][i+k+1][j],mul(p,pw2[C2(h-1)])); // link the edge inc(f[x][i+k][j+h],p); } w=0; } sz[x]+=sz[v]; } } ``` ## 【数论出题组-02】劳动节纪念赛 ### T1 好菜啊降智了。 求是m的倍数的，$\le n$的，没有平方因子个数。$m\le 10^9,n/m\le 10^9

如果没有m的倍数的限制，设n=n/m，计算方法是

\sum_i\mu(i)\lfloor n/i^2\rfloor

有了m的倍数限制，那么新的数不能包含m的质数。然后我到这就降智了，这就是数字和m互质！然后用另一个反演解决即可。

T2

法一（自己YY的）：

把多项式用牛顿表示法表示，然后设S_k=\sum _i {i\choose k}r^i，可以用组合数错位相减得到递推式。

或者直接硬把=\sum _i i^kr^i错位相减。

法二：

又长见识啦！！！

shadowice1984出给高一的毒瘤题。

给定一棵树，点有点权，求两两点对之间的路径的权值，定义为：设路径的点权按位与为x，则贡献为x^x。设叶子个数为d，要求O(nd)，值域\le 2^{30}

这道题...不要往“合并子树”和“按位考虑性质”的方面考虑，因为它真的没有性质...

考虑点x的贡献的来源，可以归给d个方向。

如果我们以一个叶子为根开始dfs到x，那么x的这个叶子方向的贡献，就是这个路径的每个后缀的按位与的值（可能会算重，判断一下即可），由于只有30位，所以这个路径上最多有30种权值，我们每个点维护一个队列一样的东西，到了每个点就暴力从父亲那里继承队列，然后暴力修改。

奇奇怪怪获得的zzt雅礼讲课课件

起名字太难了

（p是质数）

Evenpath

见到k\le 32这种不上不下的数据范围，应该联想到折半。

我们按照拓扑序将k个点分成AB两个集合，我们枚举A集合中 障碍点，让每条路径在最后一个经过的不是障碍点的A集合点处统计到（特判一个都不经过），这样做的好处是我们把路径分成了两个阶段，而且第二个阶段和A的状态无关了。我们求出从0到每个A的奇偶性。

我们另外枚举B的障碍点，求出A中每个点不经过其他A，到达1的方案的奇偶性。

把这两个合并起来即可，我们把每个点的奇偶性状压起来，前后方案数相乘，也就是做&卷积。

String

给定 n 个串，有 m 次询问，每次询问给定串 a, b，问 n 个串中有多少个能表示为 axb，其中 x 为任意字符串。

像这种有两个限制的题，往往可以转成二维平面上的点，限制就表示一个矩形！ 相当于查有多少点同时在两棵树里某两个点的子树里。

如何减掉长度不足的？直接枚举长度！复杂度O(s\log s)

最长次连续子串

容易发现最长次连续子串一定是前缀或后缀。考虑最长次连续子串长度 ≤ w，意味着开头的 l − w 个字符互不相同且末尾的 l − w个字符互不相同。

平方串

我们定义一个串为平方串当且仅当这个串非空而且它可以由两个相同串连接而成。例如 naivenaive 和 aaaaaa 为平方串，而naiveevian 和 aaaaa 不是。

现在 zzq 拿到了一个很长的数字串（每个字符为 0 ∼ 9），他想要随机地取出一个非空子串，如果这个子串没有前导零且为平方 串，那么它的价值就为它的数值，否则它的价值为 0。

zzq 想知道他取出子串价值的期望，mod666623333 输出。n ≤ 5 × 10^5

见到形如AA的串，使用插眼法！！！

分治，考虑过中心的串，我们枚举平方串长度2p，分靠左、靠右、中间考虑。

本质不同双回文串划分

PAM，对每个位置相当于把前缀回文串和后缀回文串对应搭上标记，线段树合并+O(1)LCA即可。

BZOJ4962 简单的字符串

哇，神仙结论题。

我们枚举子串的中心，然后把两边的字符交替的写下来，那么新串每个长度为2L的前缀，如果可以表示成两个（可空）偶回文串的和，那么它就唯一对应一个可行的子串。还有一个性质：如果一个串S可以表示为两个偶回文串u,v的和，要么u是S的最长回文前缀，要么v是S的最长回文后缀。

LOJ6400 连通块计数

给定带点权的树，求满足所有点的点权的 \gcd=s1 且所有点的点权的 \operatorname{lcm}=s2的树上联通块个数。

挖掘性质的好题。这道题的关键就在于s1|a_i|s2，且s2无平方因子！

于是一个显然的方法时把gcd的限制用\mu反演，设f[i][S]表示以i为根的联通块，状态为S，同时加一些剪枝可得60分。但是好像不能继续优化了

我们考虑，每个质因数只有3种状态：只取到gcd，只取到lcm，gcd和lcm都取到（因为无平方因子），所以有一个O(n3^n)状压。

进一步思考，我们可以只把状态中gcd和lcm都取到的位设成1，其余位一定是和a[x]的状态相同！但是合并两个状态的时候记得补全，其实就是v的数组都|a[x]^a[v]。复杂度O(n2^n)

void dfs(int x,int _fa)
{
    vis[x]=1;
    for(ri i=0; i<(1<<cntp); ++i) f[x][i]=1;
    for(solid v:E[x])
    {
        if(v==_fa) continue;
        dfs(v,x);
        int ex=a[x]^a[v];
        ifwt(1<<cntp,f[v]);
        for(ri i=(1<<cntp)-1; i>=0; --i)
            if((i|ex)>i) inc(f[v][i|ex],f[v][i]),f[v][i]=0;
        fwt(1<<cntp,f[v]);
        for(ri i=0; i<(1<<cntp); ++i)
            f[x][i]=mul(f[x][i],f[v][i]+1);
    }
    for(ri i=0; i<(1<<cntp); ++i) inc(tot[i],f[x][i]);
}

CSA Expected Tree Degrees

？？？为啥zzq给的做法用到了double的精确度？？？

这不是DP平方的期望的套路题吗。

Topcoder AppleTrees

这个转化的套路值得学习：

|b_{i}-b_j|\ge \max(a_i,a_j)

等价于把b数组从小到大排序之后，

|b_i-b_{i-1}|\ge \max(a_{order(i)},a_{order(i-1)}) 假设我们已经枚举了order（1-n的排列），方案数就是盒子放球，但是有下界，这个很好算。 那么我们发现方案数只和$\sum \max(a_{order(i)},a_{order(i-1)})$有关，考虑DP出和为s的方案。 相邻两数的最大值，我们可以从小到大填，贡献只和相邻的情况有关，我们可以DP连续段个数。 ### Topcoder SetAndSet ![捕获.png](https://i.loli.net/2019/06/27/5d14086120bd369563.png) 不错，努力思考是有收获的，自己做出来了。 注意到如果某一位在所有数字上的值都相同，那么这一位就没有意义了；否则，最终按位与的值一定为0，也就是每边各有一个0。现在相当于我们把数字取反，然后让两边的按位或都是$2^m-1

我们可以容斥至少几位不合法，那么不合法的位只能出现在一边，我们用并查集找联通块：每次dfs时添加一个数，就把上一个的并查集复制过来，然后把第i位是1的合并进去。最后的数量是2^c-2

NOI.AC

第三场

强连通分量

我TM以后不能看题解！

可能想到了K氏法，想到分治找边但是还是去看题解的只有我一个吧...

DFS一遍只用找n-1条搜索树的边就行了！！！不用每条边都找出来！！！这也是O(n+n^2/32)的算法的核心！！！要不然那个32是咋来的！

二分图最大权匹配

猜到了正解...但是非常显然的证明不会了...

最优解一定可以表示成kx+b的形式，而k只有n种取值，所以我们可以对每种情况，二分出左右边界。

T3是原题...

第四场

数数

简单的DP题，从小到大填数即可。有一个方便的转化：令a为单位排列，然后把答案乘上n!

立方体

TonyFang打算送你一些立方体。

你需要在[1,n]中选择一个整数k。在送你的立方体的体积和不超过k的情况下，TonyFang会不断给你一个边长为正整数且尽可能大的立方体。

你需要求出最多能得到多少个立方体，以及在此条件下，kk的最小值和最大值。

首先这道题的前两问很好解决，我们打表发现最优解一定是在上一个最优解的基础上加上最小的x_i^3使得\sum_j^i x_j^3<(x_i+1)^3

那么最大值怎么求呢？

从高到低按位确定！！！

我们发现一个数的限制条件之和比它小的数的和有关。那么我们找到一个最大的可行的高位数，对递归的子问题是没有影响的，那么我们就从高到低枚举，确定最大的可行位即可。

可以事先把最优最小解处理出来，这样更快。

#define pil pair<int,LL>
pil solve1(LL n)
{
    if(n<=7) return mp(n,n);
    int ans=7,mx=1; LL sum=7,t;
    while(1)
    {
        while((t=(LL)mx*mx*mx+sum)<=n&&t>=(LL)(mx+1)*(mx+1)*(mx+1)) ++mx;
        if(t>n) break;
        ++ans,sum+=(LL)mx*mx*mx;
    }
    return mp(ans,sum);
}
LL calcmx(LL n,int cnt)
{
    for(ri i=pow(n,1/3.0);i;--i)
    {
        pil res=solve1(min(n,(LL)(i+1)*(i+1)*(i+1)-1)-(LL)i*i*i);
        if(res.fi==cnt-1) return (LL)i*i*i+calcmx(min(n,(LL)(i+1)*(i+1)*(i+1)-1)-(LL)i*i*i,cnt-1);
    }
    return 0;
}
LL n;
signed main()
{
#ifdef M207
    freopen("in.in","r",stdin);
#endif
    in(n);
    pil res=solve1(n);
    out(res.fi);
    out(res.se);
    LL ans=calcmx(n,res.fi);
    out(ans);
    return 0;
}

追捕大象

哇原来是这样，强！

我做这道题时很疑惑：怎么保证大象不会被砸中？大象哪里都可以跑，但是步数确定，所在格子的奇偶性也就确定了，我们可以每次删掉不同奇偶性的格子！但是我们要保证剩下的块是联通的，所以我们需要一圈一圈的删，删的步数就是从这个点到四个角的最大曼哈顿距离。除了第一步，我们肯定蓄力时间是偶数，第一步需要特判。

雅礼集训

这题好苟啊...限制二就是让选择的边尽量少，那么我们把边权减掉正无穷，然后跑上下界网络流

「JOI Open 2017」高尔夫

这道题关键的性质是路径的转折点一定在某两个矩形的边的延长线的交点。于是我们可以求出所有延长线的线段，然后从起点开始bfs，每条横向的线段可以到达的纵向的线段可以排序后线段树优化。

JOI Port Facility

这道题显然的做法是把相交的区间之间连边，然后判二分图、连通性。但是边数是O(n^2)的，怎么办？

这里我们有一个讨巧的办法，我们肯定要离线，按左端点排序。

我们可以维护一个数据结构，储存所有左端点在当前区间之前的区间的信息，支持查询和当前区间相交的区间编号（线段树可以，set的复杂度不对）。

与当前区间连边的区间的右端点是一个区间，我们把这些区间拿出来，我们可以把“内部区间”相邻的连上0边，然后删掉，因为我们知道它们的颜色是一样的；端点处和当前区间连1边。

LOJ 503 ZQC的课堂

关键的一点：两位分开考虑

然后我们可以容斥一下，变成统计\min(a_i,a_{i+1})>0,\max(a_i,a_{i+1})<0的个数

那么移动指针=插入删除，集体修改=打标记，查询=lower_bound，用set即可。

LOJ 完美的队列

神题预定。看另一篇博客吧。

「2017 山东三轮集训 Day1」Fable

求k轮冒泡后的序列。

有这样一个性质：如果一个位置前边有\ge k个位置比它大，那么a_i最终的位置是i-k

否则，对于剩下的数，它们一定是按照大小排好序的。

cheese

有 n 对pair (vi, mi)，你能最多分割两对pair，即将 (v, m) 分成(pv, pm) 和 ((1 − p)v, (1 − p)m)。

分割后你希望将所有pair分成两组使得 v 之和相同且 m 之和相同。

这道题的转化思路很强。

这是一种二维的等比例划分，我们可以把(v_i,m_i)视为矩形(v_i,m_i/v_i)，这样问题就转化为了选择一个矩形的子集，使得宽为V/2，面积为M/2（大写字母表示总和）

我们可以把矩形按照高(m/v)排序，然后我们要切两刀，使得两刀中间的宽和面积满足要求。我们可以二分左端点，因为高递增，所以固定宽后，左端点越大，面积越大，于是就可以做了，也就证明一定有解了。

atcoder Piling Up

有一个非常自然的想法就是f[i][j]表示操作了i次，红球数量为j，但是这样做我们的方案会非常严重的算重。考虑去重，我们在红球数量最小时统计答案，也就是中间过程需要出现一次红球数量为0的情况，于是DP状态多加一维0/1即可。

某题

一张 n ≤ 100 个点没有边的无向图，每次随机加一条边，问联通的期望步数，对大质数取模。

我们可以计算i条边不联通的方案数。设f[i][j][k]表示i个点，至少有j个联通块，联通块内部的边数为k的方案数，转移的话枚举最后一个联通块大小，计算答案需要容斥。

某题

求有多少 n 个点的环套树，满足第 i 个点的度数为给定的 di。答案对 10^9 + 7 取模。

我们建一个超级点，把环上的点统领起来，就变成树的计数问题了。

ARC081F

W × H 的矩阵，每个格子为黑色或者白色。你可以进行任意次操作，每次操作将某一行或者某一列颜色取反。问可以得到的最大全黑子矩形的面积。

经过观察可以发现对于一个 2 × 2 的矩形，若黑色个数为奇数则无论怎么变化都不能全黑，否则可以全黑。 令 ai, j 表示 (i, j), (i, j + 1), (i + 1, j), (i + 1, j + 1) 的黑色个数就行。问题转化为最大的全 0 矩形。

CF1055G

这道题的转化很神仙：如果不能完美穿过两个障碍物之间，那么在这两个点之间连一条边，如果ST不联通那么有解，跑最小割即可。

GDSOI2019

T1

超级Lucas定理？

T2

有n个a类点和m个b类点。要选择若干个圆，使得包含住的点的价值减去使用圆的花费这个值最大。n+m\le 16

有一个显然的O(2^nn+3^n)的最小圆覆盖+状压的做法。

注意到做法的瓶颈在于枚举子集，而且有用的（极大的）子集应该不多。事实上优化方法就是这样的，我们只需要把

  1. 以每个点为圆心
  2. 1 .中两个圆的交点

这O(n^2)个圆找出来，然后O(2^nn^2)即可。

T3

题解写的看不懂...不过应该可以用广二那道AC自动机+fhq的做法，就是空间带log有点尴尬

有一个所有串长\le 100的部分分，是小串暴力，大串发现如果长度>100，那么每个左端点的贡献就独立了，于是就可以贪心了。

CF1149D Abandoning Roads

这个n=70的数据范围很尴尬，果然做法也很怪...虽然都见识过。

首先我们只加入a边，然后形成若干联通块，我们要用b边的生成树连接这些联通块。但是b边不能形成环，这个限制我们需要状压DP。我们可以类比斯坦纳树式最短路DP，记f[x][S]表示当前在点x，经过的A联通块集合为S的最短路。

优化复杂度要用到一个性质：如果一个联通块的大小\le3，离开这块再回来至少要走两条b边，而它们之间至少可以走两条a边到达，所以即使我们不强制，最优解也不会在这个点形成环。复杂度O(2^{n/4}m)（BFS型最短路）

SDOI2012 集合

一道很好的题，但是因为数据太水被mq日穿了。

首先考虑树如何做？我们对每个点的儿子维护三种集合的set，再维护一个全局set就可以了。

注意这道题的特殊性质：两点之间最多有3条不相交的路径。这等价于两点之间最大流为3.这等价于这张图可以被分为3棵生成森林！我们在这3棵树上做这些事就行了。

为什么？因为求出图的生成树后，两点之间路径至少-1条。

题答题的做法

不要在这种题上浪费太多时间，也不要不花时间，往往前一半的分是比较好拿也比较赚的。

小数据直接手玩，要善于发现数据的特殊性。可以用一些暴力做法跑很长时间。多试试爆搜。

要抓紧时间，拼手速。很多题需要码很多东西。

实在不会了随机化也是很好的方法。

再不济也要交一个合法答案。

题目经常会给出网格图。

upd on 19.7.15

[北京省选集训2019]生成树计数

我们要计算生成树权值的和的k次方，但是矩阵树定理求的是积？二项式展开，我们求的其实是：

(w_1+w_2+\cdots +w_m)^k = k![z^k]\prod_{i=1}^m \mathrm{e}^{w_iz}

这样，我们就用exp的乘积凑出了和的k次方