2016 ACM/ICPC Asia Regional Qingdao Online

2016年10月8日8531

大部分都是队友写的代码QAQ

我主要是填坑个题解

1001 I Count Two Three

定义『I Count Two Three Number』为\(2^a3^b5^c7^d\)

问超过n的最小的这种数字

显然这样的数字数量是很少的,其质因数个数不会超过30个

dfs出所有数字,二分查询

1002 Cure

求\(\sum\limits_{k=1}^n \frac{1}{k^2}\)

\(\lim_{n \rightarrow \infty}\) \(\sum\limits_{k=1}^n \frac{1}{k^2}=\frac{\pi^2}{6}\)

n超过十几万之后就达到精度上限

1003 Family View

把一个文本串的所有匹配模式串的子串变为’*’

AC自动机模板

1004 Tea

给定一个装有体积为[L,R]的茶壶,给两个杯子

每次操作可以往茶杯中倒定量的茶,返回操作是否成功

要求最终两个茶杯的茶体积差小于1,茶壶剩余的茶小于1

问至少需要多少步,能处理体积区间内的任一情况

把边界情况特判完后,一边放L/2+0.5,一边放L/2+1.5

然后每次倒 2

1005 Balanced Game

问n种手势的『石头剪刀布』游戏是否存在公平的玩法

每种手势与其它手势有n-1种关系

如果n-1是奇数,就不存在公平玩法,否则可以构造出公平的玩法

1006 The Best Path

给定一张无向图,求一条欧拉路,使得路上所有点权异或和最大

奇度点为0或2存在欧拉路,每个结点贡献可以由度数算出,如果没有奇度点的话,就枚举起点

1007 Sort

给定n个数,每次将其中k个合并,代价为他们的和,并将和放入队列,最后合并为一个数,要求总代价不超过T,求最小的K值

答案满足二分性质,K叉哈夫曼树

1008 Tower Defence

给定一棵边权树,随机删一条边,求两条直径中较大一条的期望

先dfs出原树直径,并从直径两端分别做一次dp,预处理以其为根时所有子树的直径

如果删掉的边与直径无交,直径不变

否则把求所有切出来的子树的最大直径

1010 Herbs Gathering

n个物品,每个物品有体积和价值,问总体积不超过m的最大价值。

注意到m,t,v纯随机,那么不会选太多的草药,而耗时较少的草药有很大概率存在于最优解中

用这些性质优化搜索

1011 Barricade

无向图,要求选择最少的边,使得1到n的最短路一定经过其中的边

求最短路图的最小割,模板题

1012 Eighty seven

给定一些数字,每次询问删去其中的某三个数,剩下的数能不能选出10个凑成87

先求一组解,询问和解没交直接输出Yes,bitset优化背包预处理其它询问的答案