Q779’s Blog

CSS 实现自定义动态光标效果 虽然本文的方案理论上是没什么问题的，但是在不同的设备或浏览器下效果不一样 甚至同一台电脑上不同时间都可能效果不同，这源于浏览器本身并不支持动态光标效果 反正我电脑开了几天没关机就有点渲染问题，重启完了又好了，真奇怪。以下是原文。 本博客暂时先关闭这个功能，毕竟在一些比较长的文章下会导致严重卡顿。 CSS 本身并不支持动态光标效果，尽管你可以给它一个 gif 文件 cursor: url('default.gif'), auto !important; 坏消息是在除了 Safari 外的浏览器上并不会动起来，而 Safari 上也非常不稳定。 好消息是，CSS 还有一个 @keyframes 属性，这使得我们可以创建动画。 既然 gif 不能播放，那么我们把 gif 拆成若干个 png 再用 @keyframes 播放不就可以了吗 qwq 对了，差点忘了，如果你只有 ani 文件，或者你不会拆分，那可以去 这个网站 。 下面是部分代码： /* 这里的*表示应用样式到页面中的所有元素 */ * { animation: defau...

洛谷P5665 [CSP-S2019] 划分 题解 题目链接：P5665 [CSP-S2019] 划分 题意： 2048 年，第三十届 CSP 认证的考场上，作为选手的小明打开了第一题。这个题的样例有 \(n\) 组数据，数据从 \(1 \sim n\) 编号，\(i\) 号数据的规模为 \(a_i\)。 小明对该题设计出了一个暴力程序，对于一组规模为 \(u\) 的数据，该程序的运行时间为 \(u^2\)。然而这个程序运行完一组规模为 \(u\) 的数据之后，它将在任何一组规模小于 \(u\) 的数据上运行错误。样例中的 \(a_i\) 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和，小明将让新数据的规模能够递增。 也就是说，小明需要找到一些分界点 \(1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n\)，使得 \[ \sum_{i=1}^{k_1} a_i \leq \sum_...

洛谷P2605 [ZJOI2010] 基站选址 题解 题目链接：P2605 [ZJOI2010] 基站选址 题意： 有 \(N\) 个村庄坐落在一条直线上，第 \(i(i>1)\) 个村庄距离第 \(1\) 个村庄的距离为 \(D_i\)。需要在这些村庄中建立不超过 \(K\) 个通讯基站，在第 \(i\) 个村庄建立基站的费用为 \(C_i\)。如果在距离第 \(i\) 个村庄不超过 \(S_i\) 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 \(i\) 个村庄没有被覆盖，则需要向他们补偿，费用为 \(W_i\)。现在的问题是，选择基站的位置，使得总费用最小。 输入格式： 输入文件的第一行包含两个整数 \(N,K\)，含义如上所述。 第二行包含 \(N-1\) 个整数，分别表示 \(D_2,D_3,\cdots,D_N\) ，这 \(N-1\) 个数是递增的。 第三行包含 \(N\) 个整数，表示 \(C_1,C_2,\cdots,C_N\)。 第四行包含 \(N\) 个整数，表示 \(S_1,S_2,\cdots,S_N\)。 第五行包含 \(N\) ...

洛谷P3226 [HNOI2012] 集合选数 题解 题目链接：P3226 [HNOI2012] 集合选数 题意： 《集合论与图论》这门课程有一道作业题，要求同学们求出 \(\{ 1, 2, 3, 4, 5 \}\) 的所有满足以下条件的子集：若 \(x\) 在该子集中，则 \(2x\) 和 \(3x\) 不能在该子集中。 同学们不喜欢这种具有枚举性质的题目，于是把它变成了以下问题：对于任意一个正整数 \(n \le 10^5\)，如何求出 \(\{1,2,\ldots ,n\}\) 的满足上述约束条件的子集的个数（只需输出对 \(10^9+1\) 取模的结果），现在这个问题就交给你了。 输入格式： 只有一行，其中有一个正整数 \(n\)。\(30 \%\) 的数据满足 \(n \le 20\)。 输出格式： 仅包含一个正整数，表示 \(\{1,2,\ldots ,n\}\) 有多少个满足上述约束条件的子集。 数据范围： 对于 \(100 \%\) 的数据，\(1 \le n \le 10^5\)。 考虑构造如下系数矩阵 \[ \begin{matrix} 1&2&a...

洛谷P7115 [NOIP2020] 移球游戏 题解 题目链接：P7115 [NOIP2020] 移球游戏 题意： 小 C 正在玩一个移球游戏，他面前有 \(n + 1\) 根柱子，柱子从 \(1 \sim n + 1\) 编号，其中 \(1\) 号柱子、\(2\) 号柱子、……、\(n\) 号柱子上各有 \(m\) 个球，它们自底向上放置在柱子上，\(n + 1\) 号柱子上初始时没有球。这 \(n \times m\) 个球共有 \(n\) 种颜色，每种颜色的球各 \(m\) 个。 初始时一根柱子上的球可能是五颜六色的，而小 C 的任务是将所有同种颜色的球移到同一根柱子上，这是唯一的目标，而每种颜色的球最后放置在哪根柱子则没有限制。 小 C 可以通过若干次操作完成这个目标，一次操作能将一个球从一根柱子移到另一根柱子上。更具体地，将 \(x\) 号柱子上的球移动到 \(y\) 号柱子上的要求为： \(x\) 号柱子上至少有一个球； \(y\) 号柱子上至多有 \(m - 1\) 个球； 只能将 \(x\) 号柱子最上方的球移到 \(y\) 号柱子的最上方。 小 C 的目标...

洛谷P4317 花神的数论题 题解 题目链接：P4317 花神的数论题 题意： 花神的题目是这样的： 设 \(S_i\) 表示 \(i\) 的二进制表示中 \(1\) 的个数。 给出一个正整数 \(N\) ，花神要问你 \(\prod_{i=1}^{N}S_i\) 模 \(10000007\) 的值。 输入格式： 一个正整数 \(N\)。 输出格式： 一个数，答案模 \(10000007\) 的值。 数据范围： 对于 \(100\%\) 的数据，\(1\le N\le 10^{15}\)。 数位dp还是写的太少了…… 注意到 \(N\) 不是特别大，大约 \(2^{50}\) 左右。 考虑枚举二进制下 \(1\) 的个数 \(i\) ，并统计 \([1,N]\) 中有多少个这样的数（显然他们的 \(S_i\) 是一样的）。 这个可以通过数位dp得到，设有 \(k_i\) 个这样的数，则答案为 \(\prod_{i=1}^{50} i^{k_i}\) 时间复杂度 \(\mathcal{O}(\log^4N)\) 代码： #include <bits/stdc++.h> u...

[AGC005D] ~K Perm Counting 题解 题目链接：[AGC005D] ~K Perm Counting 题意： 如果一个排列 \(P\) 满足对于所有的 \(i\) 都有 \(|P_i-i|\neq k\)，则称排列 \(P\) 为合法的。 现给出 \(n\) 和 \(k\)，求有多少种合法的排列。 由于答案很大，请输出答案对 \(924844033\) 取模的结果。 数据范围： \(2\leq n\leq 2\times 10^3\)，\(1\leq k\leq n-1\)。 如果我们把每个点不能放的位置画成一行，那么可以得到下图（\(n=7,k=2\) ，图来自参考文献1） 图中阴影部分是不可以放的，并且每行每列都只能有一个格子被选中（可以认为是放 \(n\) 个互不攻击的车） 正难则反，考虑容斥。设 \(f_i\) 为钦定 \(i\) 个阴影格子放车。答案为 \[ \sum_{i=0}^n(-1)^if_i\cdot (n-i)! \] 那么 \(f_i\) 怎么求呢？根据定义，\(f_i\) 的选择要求车之间互不攻击。 如果我们把每个阴影格子与其...

洛谷P5464 缩小社交圈 题解 题目链接：P5464 缩小社交圈 题意： 社交圈子里有 \(n\) 个人，每个人都有一个 SAN 值范围 \([l_i,r_i]\)。当两个人的 SAN 值交集不为空时，这两个人有 PY 关系。 现在希望从社交圈子里面挑选出一些人组成一个集合 \(S\)，如果将所有集合内的人中有 PY 关系的那一对人都连上边，则 \(S\) 刚好成为一个树（森林不行哦）。 请问，有多少种可以选择的方案？由于答案可能很大，请对 \(10^{9}+7\) 取模。 输入格式： 第一行一个整数 \(n\)。 接下来 \(n\) 行，每行 2 个整数，表示这个人的 SAN 值区间。 输出格式： 一行一个整数，表示答案。 数据范围： 满足 $n ,1 l_{i} <r_{i} $ 。 首先把所有线段按右端点升序排序，这样我们可以依次考虑每条线段。 注意到答案的树形如一条长链，其中一些节点挂了几个单点。 考虑设 \(f(i,j)\) 表示编号最右侧的线段是 \(i\) ，次右的是 \(j\) 时的合法方案数。 记 \(S(i,j) = \sum_{1 \le j &...

洛谷P2481 [SDOI2010] 代码拍卖会 题解 题目链接：P2481 [SDOI2010] 代码拍卖会 题意： 随着 iPig 在 P++ 语言上的造诣日益提升，他形成了自己一套完整的代码库。猪王国想参加 POI 的童鞋们都争先恐后问 iPig 索要代码库。iPig 不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又肯出钱的小猪，于是他决定举行了一个超大型拍卖会。 在拍卖会上，所有的 \(N\) 头小猪将会按照和 iPig 的好感度从低到高，从左到右地在 iPig 面前站成一排。每个小猪身上都有 \(9\) 猪币（与人民币汇率不明），从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代码库的猪币数量（\(1\) 到 \(9\) 之间的一个整数）。大家都知道，如果自己付的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪（们）会得到 iPig 的代码库真传，向着保送 PKU（Pig Kingdom University）的梦想前进。 iPig 对自己想到的这个点子感到十分满意，在去现场的路...

洛谷P4657 [CEOI2017] Chase 题解 题目链接：P4657 [CEOI2017] Chase 题意： 在逃亡者的面前有一个迷宫，这个迷宫由 \(n\) 个房间和 \(n-1\) 条双向走廊构成，每条走廊会链接不同的两个房间，所有的房间都可以通过走廊互相到达。换句话说，这是一棵树。 逃亡者会选择一个房间进入迷宫，走过若干条走廊并走出迷宫，但他永远不会走重复的走廊。 在第 \(i\) 个房间里，有 \(F_i\) 个铁球，每当一个人经过这个房间时，他就会受到铁球的阻挡。逃亡者手里有 \(V\) 个磁铁，当他到达一个房间时，他可以选择丢下一个磁铁（也可以不丢），将与这个房间相邻的所有房间里的铁球吸引到这个房间。这个过程如下： 逃亡者进入房间。 逃亡者丢下磁铁。 逃亡者走出房间。 铁球被吸引到这个房间。 注意逃亡者只会受到这个房间原有的铁球的阻拦，而不会受到被吸引的铁球的阻挡。 在逃亡者走出迷宫后，追逐者将会沿着逃亡者走过的路径穿过迷宫，他会碰到这条路径上所有的铁球。 请帮助逃亡者选择一条路径，使得追逐者遇到的铁球数量减去逃亡者遇到的铁球数量最大化。 输入格式： ...

[AGC013D] Piling Up 题解 题目链接：[AGC013D] Piling Up 题意： 一开始有 \(n\) 个颜色为黑白的球，但不知道黑白色分别有多少。 \(m\) 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球， 最后拿出的球按顺序排列会形成一个颜色序列，求颜色序列有多少种。 答案对 \(10^9+7\) 取模。 数据范围： \(1 \le n, m \le 3000\) 。 考虑设黑球初始有 \(x_0\) 个，则白球有 \(n - x_0\) 个。 记 \(x_i\) 为 \(i\) 次操作后的黑球数量，考察 \(i+1\) 的每种情况： 两次都取黑球，要求 \(x_i > 0\) ，有 \(x_{i+1} = x_i -1\) 。 先黑球后白球，要求 \(x_i > 0\) ，有 \(x_{i+1} = x_i\) 。 先白球后黑球，要求 \(x_i < n\) ，有 \(x_{i+1}=x_i\) 。 两次都取白球，要求 \(x_i < n\) ，有 \(x_{i+1} = x_i + 1\) 。 那么对于一...

[AGC002F] Leftmost Ball 题解 题目链接：[AGC002F] Leftmost Ball 题意： 给你 \(n\) 种颜色的球，每种颜色的球有 \(k\) 个，把这 \(n\times k\) 个球排成一排， 把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列。 答案对 \(10^9+7\) 取模。 数据范围： \(1\leq n, k\leq 2000\)。 可以看作 \(n\) 个白球和 \(n\) 种颜色的各 \(k-1\) 个球。特判 \(k=1\) 。 设 \(f(i,j)\) 为放了 \(i\) 个白球和 \(j\) 种其他颜色的球的合法方案数。 这里规定 \(j \le i\) ，称每个白球右侧到下一个白球前的位置为空位。考虑转移。 在左侧第一个空位放一个白球，从 \(f(i-1,j)\) 处转移； 在左侧第一个空位放至少一个其他颜色的球，然后放完该颜色的球， 即从 \(f(i,j-1)\) 处转移。考虑转移系数。首先从剩下 \(n-j+1\) 种球里选一种放， 然后在剩下的 \(nk-i-(j-1)(k-...