BZOJ 1478 | 1488 | 1815 无标号无向完全有色图计数

给定一个无向完全图,边有颜色,求所有不同构的图的数量。

这里我们考虑所有边的置换,边的置换太大了,发现边的置换和点的置换是有关的,而且点的置换和图的同构是有关的,所以我们枚举所有点的置换。

但是这样是 n! 的复杂度。我们发现对于两个置换,如果对于每一个大小的轮换,他们都具有相同的轮换个数,那么对于答案的贡献就是等价的。

那么我们就可以枚举整数拆分了。复杂度变成点数的拆分数了。

这样我们对于每一置换都求一下对答案的贡献,然后乘一下轮换个数就好了。

轮换个数怎么算呢……首先是根据拆分组合数搞一下

其中 div_num 是拆分数组。

然后考虑假设大小为 x 的轮换有 y 个,那么我们还要除以 y!

然后注意到每个循环排列方式只和第一个点有关,或者说,因为这是个圆排列所以要去重 (除掉 div\_num[i]),所以我们还要挨个乘 (div\_num[i]-1)!

然后后面就是考虑怎么算边的轮换大小了,见这里:

https://fancydreams.ink/2018/12/01/%E4%BB%8E%E5%B0%8F%E5%AD%A6%E5%BC%80%E5%A7%8B%E7%9A%84%E6%95%B0%E6%95%B0/

代码:

 

BZOJ 3632 | 蒙特卡罗随机化

大概就是让你求一般图的最大团。

直接随机化。然后我们把点序当 PEO 打乱,假装第一个点在最大团里。

然后就判一下其余点的连通就好了。

 

BZOJ2532 | CERC2010 Casting Spells

首先跑马拉车。

然后对于每个位置 i 我们求出他的回文对称半径 r_i 。比如说图上假设 i 是回文子串的中心(如果是偶数长度那就是中心的右侧),然后红色位置是子串的右末端,那么 r_i 就是:

然后有了 r_i 之后我们考虑合法的串长什么样子:

于是我们的任务就是找到满足以下条件的 j

  •  j+r_j \geqslant i
  •  j \geqslant i-\frac{r_i}{2}

然后就可以了。那么这里有一个 O(n \log n) 的搞法:从左到右枚举 i ,并同时维护两个集合:一个是当前所有满足条件 [1] 的 j 的位置集合,这个集合以 r_j+j 排序,并记录每个 r_j+j 对应的 j

另一个集合维护所有当前的合法位置 j ,并按照 j 排序。

每次扫到一个 i 只需先清空位置集合所有 r_j+j < ir_j+j 和合法集合对应的 j

然后求合法集合里 i - \frac{r_i}{2} 的后继即可。

 

BZOJ3895 取石子

这题思路不错。

首先考虑对于一个 >1 的堆,如果合并他对先手有利,那么这堆石子在取完之前一定会被先手合并。同理如果对后手有利也是。

既然合并这个动作要不就是对先手有利要么就是对后手有利,那肯定这堆石子最后会被合并。

并且在取完之前,合并这个动作无论在何时发生,都等同于在对这堆石子操作时的前两步内发生。

那么我们就可以把充裕堆 ( 大小 >1 的堆 ) 先提前合并了,然后在 DAG 游戏图上记搜 \mathrm{SG} 值。

操作分为几种:

  • 拿走一个孤单堆
  • 拿走充裕堆的一个石子
  • 把一个孤单堆合并到充裕堆内
  • 把两个孤单堆合并,成为充裕堆的一部分

然后就写个代码就好了。复杂度大概是 O(T \cdot \sum{a_i}) 的。

 

[Zzz]趁着不太清醒赶紧把题解补完 | JLOI2014

[JLOI2014]天天酷跑

某优雅的DP题。

dp[i][j][k]表示在位置 (i,j) 并且用了 k 次连跳的答案。

转移分三种:一是如果 j=0 也就是在地面那可以跑一格

或者 k<q 可以跳一下

或者如果可以的话,下落。

可以枚举跳跃高度和次数然后记搜。

[JLOI2014]松鼠的新家

年代久远了。如果我没记错应该是一个树上差分问题。

好像是什么树上差分的板子……随便写写。

这是我元旦那天做的第一题,或者也可以说18年第一道题。

[JLOI2014]路径规划

这题劲啊!这题可劲了

考虑对 k 也就是过红绿灯的次数分层。

然后还是不好搞,没有办法之后我们可以分第二层。

k 分层之后,对于每一层,枚举所有加油站,计算出这个加油站 i 分别到 所有层 的 所有加油站 的最短路。

然后这样建新图,直接在加油站-加油站之间连边。然后跑对于 k 的分层图最短路。

SPFA 不会被卡。

期望等待长度是 \frac{R^2}{2 \cdot (R+G)}

[JLOI2014]镜面通道

hhh如果想知道证明可以评论

可以证明如果透气就一定透光。

不会构造出虽然透气,但是光线一直循环地反射,从而出不去的情况。

 

简单计算几何+最小鸽

每个几何图形做一个点,连边双向边。

圆与正方形交的时候,如果解方程,注意精度。

首先对于一个数字 x 的唯一分解式设为 \prod _{i=1} ^{n} p_i^{a_i}

那么约数和就是 \prod _{i=1} ^{n} \sum _{j=0} ^{a_i} p_i^j , 这个非常显然 (?)

那么……我们可以猜出 xS 是同级的。

那么显然 p_i \leqslant \sqrt{S}

那么可以暴搜。枚举 p_ia_i

一个特判是如果当前的剩余数字 S_i 减去 1 之后为一个质数,并且不小于当前枚举到的最大质数,那么也要算进答案。

需要证明请在评论区留言。

QAQ (一瓶咖啡灌下去) 差不多清醒了…

JLOI2010 世界杯租房

数据很水,偷偷看了下好像 T \leqslant 100

嗯,DP+输出方案。记得为了字典序最小我们要倒着DP。。

然后没了。。别写龊了写炸复杂度就好。

O(Tmn^2)

 

 

BZOJ3083 遥远的国度

遥远的行星? 神奇的国度?

NO,遥远的国度.

这题真皮OVO

考虑换根之后只有两种情况答案会变

一是根与询问点重合 答案整棵树

二是在询问点的子树内,这时候需要……枚举子树树根!

然后用dfs序来判断,这玩意是连续的(嗯……?),而且在每个子树内也是连续的(!)

锁定在哪颗子树内!

然后你抓着这个子树的根节点把它拎起来,这整棵树其余的部分就耷拉到下面了

然后你就会发现这时候实际是询问这个红色的部分

然后就行了。

画风奇怪??

 

BZOJ4196 | NOI2015 软件包管理器

呀,我又来骗访问了QAQ

其实就是刨的模板题,不过题面真tm长

 

BZOJ3158&3275 [双倍经验] Number|千钧一发

这俩是一个题。

拿「千钧一发」说吧,你会发现显然如果对于一个i,如果a_i是偶数的话,他一定满足条件2,反过来如果a_i是奇数的话,他一定满足条件1,很好证明,就不说了。

然后你会发现这样一件事情:二分图

我们考虑补集转化,求最少的必须不选的b_i们,这大概……就是一个最小割。

最小割。怎么建图?源点汇点分别连所有奇数/偶数,边权b_i,然后奇偶之间互相连边,边权\rm{INF}

为什么是\rm{INF}?

因为……呃……表示这条边一定不会被割掉,那我们假设他连接了u \; , \; v两个结点,你需要挑一个,把他和源点或者汇点的边割掉。也就意味着最小割增加了b_u或者b_v的权,也就是不选其中一个。

然后这样就形成了超级复杂的关系网络然后就瞎跑Dinic就可以过了

注意!邻接表要开很大,而且两个题范围不一样!

(但是奇怪的是范围较大的\rm{Number}却跑得快

 

BZOJ1016 | JSOI2008 最小生成树计数

题面不放

这是道好题 一开始还以为是\rm{Matrix Tree}定理,后来发现不是QAQ

其实暴搜可过

先一遍Kruskal,顺便把权值相等的边们分到一个块里面,随便怎么实现都行 记录一下每个块有多少边在MST中出现过

然后重置一下并查集,枚举块,每个块跑DFS选哪些边(注意连通性,如果这条边加入成环就不能选,这很显然qwq),答案是所有块的方案数的乘积。

这里用了一个性质就是不同的MST中边权相等的边出现次数相等,证明?

开始时,每个点单独构成一个集合。

首先只考虑权值最小的边,将它们全部添加进图中,并去掉环,由于是全部尝试添加,那么只要是用这种权值的边能够连通的点,最终就一定能在一个集合中。

那么不管添加的是哪些边,最终形成的集合数都是一定的,且集合的划分情况一定相同。那么真正添加的边数也是相同的。因为每添加一条边集合的数目便减少1.

那么权值第二小的边呢?我们将之间得到的集合每个集合都缩为一个点,那么权值第二小的边就变成了当前权值最小的边,也有上述的结论。

因此每个阶段,添加的边数都是相同的。我们以权值划分阶段,那么也就意味着某种权值的边的数目是完全相同的。

上文不是我写的。引用一下。

然后就能愉快的切掉这个水题。

 

点击图片跳转原题

 

 

 

 

 

哦,还有,这段代码BZOJ编译会CE,不知道为什么她就是不支持C++11   [摊手]