NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#7

NanoApe posted @ 2015年11月23日 20:48 in 蒟蒻不做题提前退役 , 444 阅读

考完NOIP完就突然失去做题的动力了……

接下来是要奋战GDKOI,也就是省选难度

加油吧(说着说着打开了Osu

现在已完成:

50/50

1052: [HAOI2007]覆盖问题

给N个点,用三个边长为x的正方形覆盖全部点,求x的最小值

二分答案+搜索,首先将第一个放在四角,然后第二个也是,最后判断第三个能否全覆盖

1050: [HAOI2006]旅行comf

求“最大比最小比值最小路径”

就跟“最大减最小差最小路径”差不多,也是边排序完一条条加,用并查集维护图的连通性

★1049: [HAOI2006]数字序列

先对数据处理,每个数减去其下标,一问就被弄成求最长不下降子序列

然后二问就要DP了,一问的转移用邻接表保存下来,二问的DP就可以以此转移

对于子序列两个数$A,B(A \le B)$之间的区间的数,要不全部弄成A,要不全部弄成B,要不找个中分点,左边弄成A,右边弄成B。可以证明其中有一种方案是最优的

★2466: [中山市选2009]树

高斯消元解xor方程组

3505: [Cqoi2014]数三角形

一个N*M的网格图,求有多少三角形

$Ans=C^3_{(n+1)(m+1)}-三点共线对数$,斜线上的就神奇的枚举姿势,复杂度$O(n^2)$

1022: [SHOI2008]小约翰的游戏John

胜利条件相反的Nim游戏

假如全部为1,则看1个数(奇数先手败,偶数后手败)

否则看Nim,如果$Nim \neq 0$则后手败,否则先手败(跟原Nim游戏相反

3930: [CQOI2015]选数

求在$[L,H]$的区间中选取n个数使得他们的gcd为k的方案数

容斥原理,设F[i]表示$gcd=k*i$的方案数,$F[i]=(H/i/k-L/i/k)^n-F[2*i]-F[3*i]-F[4*i]……-(H/i/k-L/i/k)$(这步是减去全部数都一样的方案),假如$[L,H]$包含k的话方案数+1

或者用莫比乌斯做也行

2760: [JLOI2011]小A的烦恼

就模拟

2763: [JLOI2011]飞行路线

分层图最短路

★2746: [HEOI2012]旅行问题

给N个串,每次询问指定两个串的前缀,求其最长公共后缀且这个后缀是某个串的前缀

建立AC自动机和Fail树,对于询问的两前缀找到结点,答案就是两结点在Fail树上的Lca

2521: [SHOI2010]最小生成树

给定图和指定边,每次操作可以使某条边边权增加一,询问最少操作次数使得指定边一定会出现在MST中

设指定边边权为mx,将边权大于mx的边删去,其余边的边权改为mx-v[i]+1,然后指定边两端点为源和汇,求最小割

★3627: [JLOI2014]路径规划

分层图最短路

首先,保留加油站的点,其余去掉(第一次分层图最短路

然后第二次分层图最短路(怎么觉得自己一直在口胡

然后在注意一下细节什么的就可以辣(没说到重点好像

4027: [HEOI2015]兔子与樱花

从下往上贪心,能删的子节点就删

2342: [SHOI2011]双倍回文

回文树,建完遍历Fail树,找双倍回文

★4028: [HEOI2015]公约数数列

给你一堆数,每次操作可以修改一个数,每次询问某个前缀(最小下标)能满足gcd*xor=给定值

分块,修改的时候维护块内前缀gcd和前缀xor和整块的gcd和xor。查询的时候假如当前块的前缀gcd都相等,则由公式可以反推出自己所需的块内前缀xor值,二分查找即可;如果前缀gcd在块内有变动的话就直接暴力查询。

3613: [HEOI2014]南园满地堆轻絮

二分答案+贪心

3629: [JLOI2014]聪明的燕姿

搜索。若一个数的质因数分解为$$x=p_1^{a1}+p_2^{a2}+p_3^{a3}+……$$

则约数和为$$x=(1+p_1+p_1^2+……+p_1^{a1})*(1+p_2+p_2^2+……+p_2^{a2})*……$$

可以枚举质数p,采取DFS的方式求出所有值

★3612: [HEOI2014]平衡

整数划分,求n个数划分为m个互不相同的数且最大不超过k的数的方案数

令f[n][m]表示n个数划分为m个互不相同的数且最大不超过k的数的方案数

如果最小的数是1,等价于将最下方一排砍掉的方案数,即f[n-m][m-1]

如果最小的数不是1,等价于将最下方一排砍掉的方案数,即f[n-m][m]

但是这样求出的是最大不超过k+1的方案数,因此我们还要减掉最大等于k+1的方案数

最大等于k+1的方案数等价于将最右一排砍掉后最大不超过k的方案数,即f[n-k-1][m-1]

故有f[n][m]=f[n-m][m]+f[n-m][m-1]-f[n-k-1][m-1]

于是分是否取走中间的质点两种情况讨论,每次枚举左右的总和,枚举左右拿走的质点数即可

2028: [SHOI2009]会场预约

STL题,弄个set就可以维护了,又短又好写

★2744: [HEOI2012]朋友圈

求最大团

建立反图,最大团变成最大独立集。枚举A国选择的人,与A国有相连的B国人去掉;B国人通过xor自动分成两类,建立二分图跑最大独立集

顺便知道了如何通过位运算求一个二进制数的1的个数

3166: [HEOI2013]Alo

可持久化Trie

先建立可持久化Trie(把每个数的二进制看成字符串)然后对于非最大数,查找xor后最大的值,范围从左边比当前值大的第二个数到右边比当前值大的第二个数

3192: [JLOI2013]删除物品

怎么做都可以

1067: [SCOI2007]降雨量

就是各种判断,其中求区间的最小值用log算法

Mistake 区间最小值暴力求TLE了QwQ

1068: [SCOI2007]压缩

区间DP,$F(i,j)$表示前i位且最右边的R的位置为j的最短压缩长度

1072: [SCOI2007]排列perm

数位DP,对于计算重复的数,设某个数字出现了A次,最后除以$A!$就行了

★1079: [SCOI2008]着色方案

状态设置比较神奇,$F(o,s1,s2,s3,s4,s5)$表示剩i格没涂的颜色有$si$种,且上次涂的颜色现在剩o格的方案数

1087: [SCOI2005]互不侵犯King

状压DP

1088: [SCOI2005]扫雷Mine

确认第一二格就能推出剩余的格子

1089: [SCOI2003]严格n元树

设$F(i)$表示深度不大于i的严格n元树,推下公式,$F(i)=F(i-1)^n+1$,答案就是$F(d)-F(d-1)$

Mistake 没注意d=0的情况

1084: [SCOI2005]最大子矩阵

状压DP,手推公式就行

1074: [SCOI2007]折纸origami

对于穿孔位置,求$2^n$个可能的孔的位置,去重后一个个模拟着折,统计一下最后的确出现在穿孔位置的孔的位置,总数即答案

1090: [SCOI2003]字符串折叠

区间DP

1295: [SCOI2009]最长距离

枚举起点跑最短路,不超过T的就是可达的

1263: [SCOI2006]整数划分

高精度,能分3出来就分3出来,直到n<=4就直接乘上去

1085: [SCOI2005]骑士精神

搜索+剪枝

1296: [SCOI2009]粉刷匠

就一遍$O(n^3)$的DP

1853: [SCOI2010]幸运数字

把所有范围内的68数搜出来,结合容斥计算

Mistake DFS计算容斥的时候是从小到大搜索的,TLE,应改成从大到小

1856: [SCOI2010]字符串

n个1m个0的二进制数,任意前缀的1的个数不少于0的个数,求满足条件的二进制数个数

将1看作向量$(1,1)$,0看做$(1,-1)$,起点为$(0,0)$,终点为$(n-m,n+m)$,且移动路径不经过$y=-1$的方案数

合法方案数=总方案数-非法方案数=$C_{n+m}^{n}-C_{n+m}^{n+1}$

1857: [SCOI2010]传送带

华罗庚选优法,三分套三分

1858: [SCOI2010]序列操作

标准线段树

Mistake 维护区间修改和区间取反信息的时候没考虑优先级的差别

1854: [SCOI2010]游戏

二分图匹配

2335: [SCOI2011]飞镖

耗智商脑跑题,我自己算了个两元一次方程的解的范围

Mistake 三个10^9乘在一起爆longlong

1876: [SDOI2009]SuperGCD

更相减损(大数GCD)

分三种情况:如果两数能整除2,则gcd*2,两数/2;其次谁能整除2就/2;最后大数减小数

1878: [SDOI2009]HH的项链

随便莫队

或者离线+树状数组,询问按左端点排序,初始每种颜色的第一个点打标记,当扫过有标记的点时将标记移动到下一个同颜色的点,维护前缀和。

1877: [SDOI2009]晨跑

裸费用流

1875: [SDOI2009]HH去散步

由于不能返回走,则将边的两向各设为点,然后矩阵乘DP

1228: [SDOI2009]E&D

求出子游戏的Sg函数是难点:$Sg(a-1,b-1)=k_Min(((a-1)\;or\;(b-1))and\;2^k=0)$

1227: [SDOI2009]虔诚的墓主人

离散化之后坐标排序完按行(y)统计,需树状数组维护前缀和

1235: [SDOI2009]细胞探索

FloodFill一遍,找出细胞核(四联通且只与一个四联通空块相邻)细胞壁(八联通)细胞质(四联通且只与一细胞核和一细胞壁相邻且不与边界相邻),然后就容易了

1879: [SDOI2009]Bill的挑战

首先先预处理出任意位置选任意字母所能匹配的字符串集(二进制),然后DP,$f(i,S)$表示答案串前i位能匹配的字符串集为S的方案数


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter