高考故事

在失落和自责中,我离开 OI,返回学校,进行文化课的学习。

10个月后,高考落下帷幕。没什么遗憾。目标也许会达成,也许不能达成,已经不重要了。

重要的是我走过了这一段路。

Read More

[NOI 2017] 蚯蚓排队

初始有 n 个分离的字符,字符集为数字 1-6。m 次操作:

  • 1 i j 连接 i 号字符和 j 号字符,使 j 排在 i 后面。保证 i 是一个字符串的末尾,j 是另一个字符串的开头。
  • 2 i 在 i 号字符的后面切开。保证 i 不是字符串的末尾。
  • 3 k s 给出一个长度不小于 k 的字符串 s,对 s 的每个长度为 k 的子串 t,求出向后 k 字符串为 t 的字符的个数,输出乘积模 998244353。定义某个字符的向后 k 字符串为:从该字符往后数,最近的 k 个字符依次连接得到的字符串(包括它本身)。

(n ≤ 2e5,m ≤ 3e5,k ≤ 50,Σ|s| ≤ 1e7,第 2 类操作的次数 c ≤ 1e3)

Read More

Burnside 引理

阅读了 <Pólya 计数法的应用> 一文, 对里面的例题做一下笔记. >_<

  • [UVA 10601] Cubes 用 12 根有颜色的等长棍子搭立方体, 旋转后颜色相同的方案算一种, 求方案数.
  • [SPOJ 419] [SPOJ 422] Transportation is fun 给一个 2^a 2^b 的矩阵, 在内存中从上往下, 从左往右连续存放. 用交换操作求它的转置矩阵, 存储方式相同, 求最小步数.
  • [SGU 282] Isomorphism 染色图是边带颜色的无向完全图. 求 N 个顶点, M 种颜色 (不必用完), 两两不同构的染色图个数模质数 P. (1 ≤ N ≤ 53, 1 ≤ M ≤ 1000, N < P ≤ 10^9)

    Read More

[USACO2008 Nov]toy 玩具

D 天, 第 i 天需要 ti 个物品. 购买一个物品花费 c 元, 消毒后才能再次使用. 两种消毒方式: 收取 c1 元, n1 天后可以再次使用; 收取 c2 元, n2 天后可以再次使用. 储存是免费的, 且不会弄脏物品. 求最小花费. (1 ≤ n1,n2 ≤ D, 1 ≤ c1,c2,c ≤ 60, 1 ≤ ti ≤ 50, 1 ≤ D ≤ 10^5)

Read More