NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#14

NanoApe posted @ 2016年4月22日 18:52 in 蒟蒻不做题提前退役 , 735 阅读

有可能是最后的一篇题解了……

GDOI保佑……

50/50

4326: NOIP2015 运输计划

二分答案,然后将长度大于答案的边提取来,看其交集中有没有长度够长的边可以减掉(这步可以直接树上前缀和修改),$O(nlogn)$

4325: NOIP2015 斗地主

模拟+搜索题,状压也是可以的

3677: [Apio2014]连珠线

十分恶心的树DP……

3205: [Apio2013]机器人

类似斯坦纳树的思路,设 $F(l,r,x,y)$ 表示编号为 $l-r$ 的机器人到了 $(x,y)$ 的最少操作次数,然后就DP+最短路

最短路是单位最短路,所以弄两个单调队列,前者放置已经知道距离的点,后者放遍历过的点,每次拿两个队列的最小值去扩展就行

3206: [Apio2013]道路费用

一开始先求出 $k$ 条边优先级最高的MST,再把 $k$ 条边去掉,缩联通块成点,把原图中没在MST中出现且跨联通块的边取出,然后再枚举 $k$ 条边的修建情况,做 $2^k$ 次MST,每次做完dfs一遍,预处理出原图中将结点分为两个集合时中间边的最小费用,这样就能得到 $k$ 条边的最优费用

4071: [Apio2015]巴邻旁之桥

△这题AC了然而在UOJ被Hack了所以我不打算写题解QwQ

4069: [Apio2015]巴厘岛的雕塑

按位考虑,前四个子任务做 $O(n^3)$ 的DP就可以了,第五个就做个 $O(n^2)$ 的DP

4070: [Apio2015]雅加达的摩天楼

最短路,然而对于移动能力小的doge会有很多重边,所以移动能力小于某个阀值的我们把边先建出来,移动能力大的直接建边

3671: [Noi2014]随机数生成器

按照题目描述建图,然后每次找最小的数并将它左下和右上的全部数删去,这步可以 $O(n^2)$

由于空间限制,两个数组要充分利用,且常数要优化得好……

4542: [Hnoi2016]大数

给一数字串,每次询问 $S$ 的一个子串中有多少子串是素数 $P$ 的倍数

首先预处理出 $F(i)$ 表示把 $S[i+1..n]$ 换成0之后数字串的值(模 $P$)

然后我们就可以莫队啦

(对于 $P=2,5$ 的要特殊处理)

4198: [Noi2015]荷马史诗

裸哈夫曼树

4199: [Noi2015]品酒大会

逆序插入SAM中,建出来的FailTree就是后缀树,然后就容易了

4197: [Noi2015]寿司晚宴

首先我们先将可能在质因数分解中出现两次的数记录下来(才8个)

二进制压一下,然后枚举数判断取不取,$O(500*2^8)$

对于分解后有相同大质数的我们一并解决

4500: 矩阵

看有没有四个约束构成矩形且对角相加不相等

(然而直接dfs就可以了

4546: codechef XRQRS

按二进制建持久化Trie

4547: Hdu5171 小奇的集合

先分类讨论,对于越加越大的就弄个矩阵快速幂

3530: [Sdoi2014]数数

AC自动机+数位DP

4200: [Noi2015]小园丁与老司机

首先弄个DP(顺便记录转移路径(路径居然还有多条简直SXBK

然后再求个有下界的最小可行流

3994: [SDOI2015]约数个数和

求 $\sum \sum d(ij)$,其中 $d(x)$ 是 $x$ 的约数个数

有个结论:$d(nm)=\sum_{i|n} \sum_{j|m} [gcd(i,j)=1]$(因为能一一对应)

然后式子就变成 $$\begin{align} \sum \sum d(ij) & =\sum \sum \sum_{a|i} \sum_{b|j} [gcd(a,b)=1] \\ & =\sum_a \sum_b \lfloor \frac na \rfloor \lfloor \frac mb \rfloor [gcd(a,b)=1] \\ & = \sum_a \sum_b \lfloor \frac na \rfloor \lfloor \frac mb \rfloor \sum_{d|gcd(a,b)} \mu(d) \\ & =\sum_d \mu(d) F(\lfloor \frac nd \rfloor)F(\lfloor \frac md \rfloor) \end{align}$$

其中 $F(n)=\sum \lfloor \frac ni \rfloor=\sum G(i)$,后者是约数个数

3990: [SDOI2015]排序

首先操作序列怎么改顺序都可以,然后就dfs咯

4552: [Tjoi2016&Heoi2016]排序

妈呀BC原题(见BC#76E题)

4551: [Tjoi2016&Heoi2016]树

离线后逆序连边,然后就可以并查集咯

4554: [Tjoi2016&Heoi2016]游戏

求出横竖联通的块然后二分匹配

4553: [Tjoi2016&Heoi2016]序列

求出每个数修改后的最小值和最大值,得到DP转移方程,然后就求三维偏序(CDQ时一半按最大值排序一半按原值排序)

2809: [Apio2012]dispatching

可并堆我选择斜堆

2303: [Apio2011]方格染色

首先这相当于每一行等于上面那行经过一次xor变换得到的结果,xor变换是指所有奇数列取反或偶数列取反

先考虑没有限制的情况,那么方案数等于 $2^m2^{n-1}$

对于同一行有多个列有限制的话,那么也可以推出第一行这两列的关系

因此可以把限制全部推到第一行(而且还要判断合不合法

当然那些在第一行的限制就固定的了

方案数等于 $2^{未限制块数}2^{未限制行数}$

1911: [Apio2010]特别行动队

斜率优化

1179: [Apio2009]Atm

缩环跑拓扑图

1177: [Apio2009]Oil

我们可以枚举三个正方形之间的分割线(就同方向2种+不同方向4种)

1178: [Apio2009]CONVENTION会议中心

第一问可以右端点排序后贪心

第二问我们预处理出 $F[i][j]$ 表示点 $i$ 后面接 $2^j$ 个订单的最小右端点(离散化后倍增求)

然后我们可以按编号从小到大考虑,设之前确定放置的订单中在前面的为 $A$,在后面的为 $B$,若 $Ans(A.Right+1,B.Left-1)=Ans(A.Right+1,Left-1)+1+Ans(Right+1,B.Left-1)$ 则放置

$Ans$ 是指一段区间最多放多少订单,可以通过之前的预处理得到

1912: [Apio2010]patrol 巡逻

找两次最长路(第一次找完之后将路上的边全部取负)(第二次找用树DP)

4576: [Usaco2016 Open]262144

设 $F[i][j]$ 表示第 $i$ 格往右合并出一个 $j$ 时右端的位置

4563: [Haoi2016]放棋子

你把所有障碍移到对角线,就会发现这不是要求错排方案嘛

4562: [Haoi2016]食物链

搜索

4566: [Haoi2016]找相同字符

反向建广义SAM然后就可以求了(每个节点的贡献为 $(Len[x]-Len[Fail(x)])*cnt1*cnt2$

4557: [JLoi2016]侦察守卫

树DP

4567: [Scoi2016]背单词

Trie建出来,将没被标记的点删掉,然后贪心,每次先走小子树

4569: [Scoi2016]萌萌哒

离线做法:建立ST表然后将限制转成两对ST表的限制(就是用并查集来维护每一层的ST表)然后就可以一层层往下推

在线做法:建立ST表然后将限制转成两对ST表的限制然后递归合并(可以发现最多 $nlogn$ 个节点所以最多合并 $nlogn$ 次

4568: [Scoi2016]幸运数字

可以倍增+线性基,可以点分+线性基

点分的话建出重心树,每个节点维护其到祖父重心的线性基,询问就可以找到最深公共重心然后玩一波

4571: [Scoi2016]美味

对于加完才xor的情况我们就拎出权值线段树处理偏移

按位贪心,我们会发现满足条件的 $Ai$ 是在某个区间内的,这就可以线段树了嘛

1508: [NOI2003]Game

搜索

3884: 上帝与集合的正确用法

首先设 $F(p)$ 为当模数为 $p$ 时的值,设 $p=2^ka$,其中 $a$ 为奇数

$$\begin{align} 2^{2^{2^{...}}} \mod p &= 2^{2^{2^{...}}-k} \mod a \\ &= 2^{(2^{2^{...}}-k) \mod {\varphi(a)}} \mod a \\ &= 2^{2^{2^{...}} \mod {\varphi(a)}-k \mod {\varphi(a)}} \mod a \end{align}$$

也就是说 $F(p)=2^{F(\varphi(a))-k \mod {\varphi(a)}} \mod p$

1443: [JSOI2009]游戏Game

二分图匹配,假如能完全匹配则必败,否则找未盖点并随着匹配方案搜索查找可行点

4586: [Usaco2016 Open]Landscaping

算出每个地方的变化情况(该增加还是该减少)然后每次找代价最小的移动方式

update:16.5.24

从Claris那里获得了更不错的解法

这道题本质是费用流,那么退流我们怎么办呢?退流其实相当于取消决策,所以这里我们利用这一点来解决。

我们建立两个堆,往右走的用Q1,往左走的用Q2,然后假如此刻位置上是正的则在Q1中找最小代价,累加进答案并扔到Q2,负的则同理

距离代价我们可以统一减去 $(pos*Z)$,这样就可以处理距离的绝对值问题

1975: [Sdoi2010]魔法猪学院

K短路,建个堆,按“当前已走过的距离+距离终点最近距离”为关键字从小到大排序,每次取最小的一个方案扩展

4570: [Scoi2016]妖怪

右上凸包上的每个点都有可能成为最大值,求出并得到每个点成为最大值时K的范围,统计一下即可

4530: [Bjoi2014]大融合

在线:启发式合并+LCT

离线:对于最后的森林建立树链剖分,维护子树大小和最远祖先,然后倒序删边

4338: BJOI2015 糖果

求 $P^{n}_{C^{m}_{m+K-1}}$

先通过求1-m的逆元算出C,然后乘n次算出P

4550: 小奇的博弈 & 2281: [Sdoi2011]黑白棋

【错题,应该假设白棋只能往右,黑棋只能往左】

将一个“白+黑”的间距设为一堆石子,问题变成Nim-K问题

必败态为将所有堆二进制分位后每个位上1的个数是 $K+1$ 的倍数

Avatar_small
zhouzixuan 说:
Apr 22, 2016 10:26:37 PM

TAT还有一个星期还能怒切50T
简直可怕2333333

bearx 说:
Apr 28, 2016 11:28:27 PM

神犇看来是准备GDOI AK啊

Avatar_small
CreationAugust 说:
May 03, 2016 03:48:27 PM

然后kpm欣然拿下了队长宝座


登录 *


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