JLOI2010 世界杯租房

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

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

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

O(Tmn^2)

 

 

JLOI2010 铁人双项比赛

我们有一个式子

t_i=\frac{k\left( v_{2i}-v_{1i} \right)}{v_{1i}v_{2i}}+\frac{s}{v_{2i}}

然后把 k 看做 x 轴,把 t 看作 y 轴,就是 n 条直线。

嗯,对于前 n-1 条求半平面交(注意直线对应的半平面是右侧)。

对于最后一条直线,最优的 k 是与这个凸包相切的时候。

而且显然 k 只会在端点处取到,所以直接二分找到斜率最近似的直线然后算一下答案即可。

注意最优的 k 为负的时候要调整为 0 并判定是否有解。

 

JLOI2008 CODES

一天半,唉。。真该AFO了。

首先考虑我们可以DP,设状态 dp[i][j] 表示 第 i 个字符串  还需要匹配长度为 j 的前缀   可以得到的最短答案。

转移:

转移就是枚举一个字符串 i_0 来与之匹配。记忆化搜索非常好写。注意讨论两种情况:

  1. i_0比当前前缀长
  2. i_0比当前前缀短

用 dp[i0][?] + 匹配长度 去更新dp[i][j]。(?是因为我懒得讨论了……代码里有)

数据范围很小,暴力匹配即可。

注意事项:

第一个细节就是字符串可以重复利用;

第二个细节是让dp[i][0]=0 其余为 +\infty

第三个细节就是最后统计答案和DP过程中别忘记比较字典序。

字典序:

 answ[i][j] 保存当前 dp[i][j] 对应的具体方案,

更新 dp[i][j] 顺便更新 answ[i][j] 即可。

每次遇到 dp[i0][?]+len  dp[i][j] 相等的情况,判定字典序,然后更新 answ[i][j] 即可。

最后的答案是 dp[i][len[i]]

O(\text{跑得过})

[题单]搜索及相关

一直有做几个题单的计划,不过好像直到停课了才抽出空来……这是第一个,先试试水吧。

我在洛谷交的第二份代码就是一个DFS,当时写的还是挺魔性的……

以下字体不是纯黑的然而我也懒得一个一个弄了。。将就一下 😥

推荐挨着写。右面目录快速跳转。


洛谷 P1036 选数 

最基础的DFS。每次递归选一个。

code

太早期了……很魔性啊有没

 


洛谷 P1101 单词方阵 

入门向(然而记得当时做了一晚……TAT)

code

当时专门写的题解


洛谷 P1706 全排列问题 

有毒吧……

code

没有!


洛谷 P1958 上学路线_NOI导刊2009普及(6) 

这题我也不知道是BFS还是DFS了 好像都不难写。大致思路是每个格子从前驱格子累加一下

code


洛谷 P1451求细胞数量 

floodfill。

code

代码风格演变史?


洛谷 P1596 [USACO10OCT]湖计数Lake Counting 

唉,不就双倍经验么。

code

不给了……


洛谷 P1605 迷宫 

唉,不就三倍经验么。

code

😕 (说真的我特喜欢这表情


洛谷 P1162 填涂颜色 

唉,不就四倍经验么。

code

🙂  😛   😎   😉   😀


洛谷 P1464 Function 

我本人是忘了。看题解是记搜入门题。。那就放这

code


洛谷 P1012 拼数 

略有代码难度的DFS?相信完成了上面几题的你(我)一定能完成它

code


洛谷 P1219 八皇后

是的,是的,我知道八皇后不应该放在这个位置,但是我就想放在这个位置……

既然写完了上面的题,写到现在的阶段,这题应该一遍过的

code

不放。


洛谷 P1019 单词接龙 

搜索+字符串。题解挺多,我不写了。(懒)

说真的当时特别沉迷做字符串。。

code


洛谷 P1032 字串变换

又一道。

code

代码风格演化史看的好迷啊XD


洛谷 P1141 01迷宫

挺水的。我当时大概从这儿开始的BFS练习。

code


洛谷 P1443 马的遍历

BFS。与上题类似。

code

太水了不给了。


洛谷 P1126 机器人搬重物 

BFS。

code

当时专门写的题解 当时码风还很毒瘤,别学我。


洛谷 P1825 [USACO11OPEN]玉米田迷宫Corn Maze 

哎呀!终于到这题了!我超喜欢这题。

写完你发现这题很棒,对于码力、实现技巧、经验值啥的都提升挺高的。

code

当时专门写的题解 题解里面有幅图丢了。。自己搞个数据看就行。


洛谷 P1644 跳马问题 

好像是多倍经验题?不管了,放这儿了。

code


洛谷 P1135 奇怪的电梯 

傻逼题啊!前面的题都写完了这个不可能不会。

code

不给。


洛谷 P1649 [USACO07OCT]障碍路线Obstacle Course 

也挺喜欢的一道题,有一个实现上的技巧。

code

当时专门写的题解 意识流题解警告。


洛谷 P1025 数的划分

搜索+剪枝。题解见代码。

code


洛谷 P2749 [USACO5.1]夜空繁星Starry Night 

拿这道神题出来祭天……

我和题解中使用的方法不太一样,简单一说就是每次记录每一行及每一列都有几个星星这样来判重。别的好说。细节贼多,看代码吧。

code

当时专门写的题解 写完这道保证恶心你。

我当时哪来的勇气。


洛谷 P1434 [SHOI2002]滑雪 

我记搜过的。。

code


洛谷 P1433 吃奶酪 

是时候做点水题练练手了

code

不给。


洛谷 P1074 靶形数独 

经典题。

code

我觉得没必要放。


洛谷 P1363 幻想迷宫 

貌似是多倍经验。

code

不放


洛谷 P1037 产生数 

来道水题练练手?

code

不放


洛谷 P1092 虫食算 

经典题。

code

不放


洛谷 P1378 油滴扩展

经典题。

code

不放


洛谷 P1312 Mayan游戏、

我怎么觉得试炼场里的都是经典题……

code

不放


洛谷 P1120 小木棍 [数据加强版] 

经典题

code

洛谷 P1514 引水入城

经典题

code

我不放还打上只是为了目录而已……


洛谷 P1460 健康的荷斯坦奶牛 Healthy Holsteins 

反正我记得那段时间奶牛题做得不少……

code


洛谷 P1845 影像之结构化特征_NOI导刊2011提高(12)

唉我有毒吧我当时为啥要去做这题啊

code

我记得当时码风基本成型了。


洛谷 P1560 [USACO5.2]蜗牛的旅行Snail Trails 

那就再来一道

code


洛谷 P3958 奶酪

我不想看见这题……痛苦

code

洛谷 P1379 八数码难题 

这也是个经典题 我觉得这题放这儿不合适……

但是其实不做这题也没啥啊

code

洛谷 P2346 四子连棋

当时跟着g++写的,挺好玩的。

code


洛谷 P3456 [POI2007]GRZ-Ridges and Valleys 

也挺好玩的 。

code

我想写个题解来着,可惜咕了。。


洛谷 P2324 [SCOI2005]骑士精神 

我忘了我写了IDA*还是A*来着……

code


洛谷 P1902 刺杀大使 

好像是当时想颓了然后做的这题……

code

洛谷 P2578 [ZJOI2005]九数码游戏 

新操作。

code

恩,到此为止了,以上。

谢谢大家! 😉

 

 

 

 

 

 

 

 

 

 

[JLOI2009]F1一级方程式大赛

……NOIp提高组难度,hhh

首先这是一道DP……这很显然。。

注意到每次加油一定是加刚好够跑整数圈的油……要不浪费时间。

然后方便起见,我们预处理跑 1 \sim n 圈的耗油和耗时,因为这和你当前在跑哪一圈是无关的。

设为了跑第 i 圈,需要用油 q_i ,每圈空车跑油 s   , 每多一升油多跑油 a , 初中数学解方程可以得到:

q_i = (q_{i-1} + q_i) \cdot a + s

q_i = \frac{s + q_{i-1} \cdot a }{1-a}

时间比较好算……就不说了。

预处理完了,我们开始dp。

设dp[i][j]表示:在第 i 圈起点,准备不加油一口气地跑 j 圈的最小时间。

转移就是(need是跑 i 圈的油量,tim是时间,incost是进加油站,gcost是加油):

然后记录一下转移的前驱,最后输出就行了。

O(n^3)

 

弦图,区间图,完美消除,MCS,TreeDecp,PQTree及其他

BKG:某天晚上和dkw闲聊,然后随机到了一个题(ZOJ1015 Fishing Net)。

想了半天不会做。不久之后dkw说他看了题解……然后我们就找来了这个课件。。


感觉还是挺魔性的。

今天T3也是一个Chord Graph TAT.

行,现在开始抄课件.

 

图的定义

子图

G=(V,E), G'=(V',E'),V' \subseteq V , E' \subseteq E 为图 G 的子图。

诱导子图

G'=(V',E'),V' \subseteq V,E'=\{(u,v)|u,v \in V',(u,v) \in E \} 称为 G 的诱导子图。

G 的一个子图 G',满足 G' 为关于 V' 的完全图。

极大团

一个团是极大团,当它不是其他团的子集。

最大团

点数最多的团。记为 \omega (G) 

最小染色

用最少的颜色给点染色使相邻点颜色不同。色数记为 \chi (G) .

最大独立集

一个点集的最大子集使得任意两个点不连通。记为 \alpha (G) .

最小团覆盖

可以覆盖所有的点的最小团数。团数记为 \kappa (G) .

定理

\omega (G) \leqslant \chi (G) .

\alpha (G) \leqslant \kappa (G) .

弦(Chord)

连接环中的不相邻两个点的边。

弦图

一个无向图,图中任意长度 \geqslant 3 的环都至少有一个弦。

 

定理

弦图的每一个诱导子图一定是弦图。

弦图的任一个诱导子图不同构于 C_n \; (n>3)(?)

弦图判定

单纯点

一个点称为单纯点,当它和与它相连的所有点构成的诱导子图是一个团。

Lemma

任何一个弦图有至少一个单纯点,不是完全图的弦图至少有两个不相邻的单纯点。

完美消除序列

一个点组成的序列 v_1,v_2,v_3,\cdots ,v_n ,满足 v_i \{ v_i,v_{i+1},\cdots,v_n \} 的诱导子图中是一个单纯点。

定理

一个无向图是一个弦图,当且仅当它有一个完美消除序列。

证明:略,详见课件qwq

Lexicographic BFS (LexBFS,字典序BFS)

实现困难又难记,我选择不写。

时间复杂度O(n+m) .

MCS (Maximum Cardinality Search,最大势算法)

这个算法要做的就是按照从 n1 顺序依次给每个点标号。标号为 i 的点是完美消除序列中的第 i 个点。

l[i] 表示第 i 个点与多少个已经标号的点相邻,每次选择一个 l 最大的未标号点进行标号。

😕 这个代码挺好的,但是有一点问题就是如何维护largest label.

有一个做法就是维护一个链表,并维护最大值。这样每次更新 \mathrm{label} 都是 O(1) 左右的。

还要啰嗦一句的是,存在MCS和BFS都得不到的完美消除序列。(但是我不会找……  🙁 )

相邻点判定完美消除序列(判定弦图)

1 \sim n 枚举序列中的每个点。

\{ v_{i+1},\cdots ,v_n \} 中所有与 v_i 相邻的点依次为 v_{j1},\cdots,v_{jk}

每次判断 v_{j1} 是否与 v_{j2},\cdots,v_{jk} 相邻即可。

时间复杂度 O(n+m)算法的正确性证明咕了,等我翻完论文看看有没有给出。

CODE

这份是 BZOJ1242 的代码,这玩意包括了求一个图的 PEO (Perfect Elimination Orderings) 和判定一张图是不是弦图 QAQ

(这段文字和这篇文章的首发差了半年的时间,233

弦图相关

寻找极大团

Lemma

设第 i 个点在弦图的完美消除序列的第 p(i) 个。

N(v)= \{ w | w \text{与} v \text{相邻且} p(w)>p(v) \} ,那么弦图的极大团一定是 v \cup N(v) 的形式。

推论

弦图最多有 n 个极大团。

我们只需要判定每个 v \cup N(v) 是否为极大团。

A = v \cup N(v) , 若存在 B = w \cup N(w) 使得 A \subseteq BA 不是极大团。

首先我们可以得到 p(w)<p(v)

\mathrm{next} (v) 表示 N(v) 中最前的点, w* 表示在所有满足 A \subseteq Bw 中最后的一个点。

可知 \mathrm{next} (w*) = v 。若不是,则 \mathrm{next} (w*) 也是一个满足上述条件的点,得证。

那么, v \cup N(v) \subseteq w \cup N(w) 当且仅当 | N(v) | +1 \leqslant | N(w) |

我们只需要判定是否存在一个 w ,满足 \mathrm{next} (w) = v| N(v) | +1 \leqslant | N(w) | 即可。

时间复杂度 O(n+m)

 

<<此处本应有代码>>

 

弦图点染色

行……我们终于来到了这个题……

HNOI2008 神奇的国度。

用最少的颜色给每个点染色,使得相邻的点染色不同。

有一个神奇的做法:

求出完美消除序列,从后向前给每个点染上可以染的最小色。

团数=色数。证明:比较简单,咕了,看课件吧

O(n+m)

弦图最大独立集,最小团覆盖

最大独立集:完美消除序列从前往后能选就选。

最小团覆盖:最大独立集的每个点都与它的邻点组成一个团,以此求出最小团覆盖。

\alpha (G) = \kappa (G)

区间图

定义

在序列上给定一些区间,定义一个相交图为:

  1. 每个顶点表示一个区间
  2. 两点之间有边,当且仅当对应代表的区间的交集非空。

如果一个图是若干区间的相交图,则它是区间图。

定理

区间图一定是弦图。

证明略,详见课件。

区间图完美消除序列

将所有的区间按照右端点从小到大排序。

没了。。。证明depends on我能不能找到了

区间图最大独立集

问题:给定 n 个区间,求一个选择最多区间的方案,使得所有区间的交集为空。

Sol:最裸的题,最大独立集。完美消除序列上的判定可以做到 O(n\log _2 n)   (线段树或堆),非常优秀。

区间图最小染色

n 个高度均为 1 的积木,第 i 个位于 [L_i,R_i] 的位置   (也就是起点在 L_i ,宽 R_i-L_i )。

求一个积木下落顺序,使得最后积木总高度尽可能小。

就是求一个最小染色,方案则是按照颜色编号从小到大掉落。

一个很意识流的解释就是尽量让不交的区间落在一层上。

更多实现上的细节:我们可以倒过来排序,然后依次处理。也是 O(n \log _2 n) 的。

判定区间图

  • 判定是否为弦图。
  • 找出所有的极大团。
  • 构建一个 顶点-团矩阵 A ,使得 A 的每一行代表 G 的一个顶点,每一列代表 G 的极大团。满足 A_{ij}=\begin{cases} 1 \; \mathrm{if} \; v_i \in C_j \\ 0 \; \mathrm{otherwise} \end{cases}
  • 判断是否存在一个重排方式,即任意交换 A 的各列,使得每行的所有 1 都是连续的。如果这种排列存在,就称这个矩阵具有连续 1 性质。
  • 可以用PQTree来实现(这就是作死)

 

  • 另外一种判定方法
  • 《A new Test for Interval Graphs》


 

Tree Decomposition

一个无向图 G=(V,E) 的 树的分解(Tree Decomposition) 定义为 (X,T) ,\; X= \{ X_1,X_2, \cdots ,X_m \} ,其中 X_iV 的一个子集, T 是一棵树,点集为 X

一些性质

X_1 \cup X_2 \cup \cdots \cup X_m = V

对于 G 中任意一条边 (u,v) \;,\; \exists X_i 使得 u,v \in X_i

对于每个点 v,P(v)= \{ X_i | v \in X_i \} ,则 TP(v) 的诱导子图是联通的。

所以这玩意到底有啥用啊 🙁

Clique Tree

clique tree是一种tree decomposition.

一个无向图 G 为弦图当且仅当存在一个clique tree.

一个无向图为区间图当且仅当存在一个链形态的clique tree

所以这玩意到底又有啥用啊 🙁

构建弦图Clique Tree

感觉这玩意没用。我Bing了一下Clique Tree看到的全是概率学玄学……

愿意学的看课件吧。