AT_agc005_d [AGC005D] ~K Perm Counting 题解
AT_agc005_d [AGC005D] ~K Perm Counting 题解 题目链接:AT_agc005_d [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 缩小社交圈 题解 题目链接:P5464 缩小社交圈 题意: 社交圈子里有 \(n\) 个人,每个人都有一个 SAN 值范围 \([l_i,r_i]\)。当两个人的 SAN 值交集不为空时,这两个人有 PY 关系。 现在希望从社交圈子里面挑选出一些人组成一个集合 \(S\),如果将所有集合内的人中有 PY 关系的那一对人都连上边,则 \(S\) 刚好成为一个树(森林不行哦)。 请问,有多少种可以选择的方案?由于答案可能很大,请对 \(10^{9}+7\) 取模。 输入格式: 第一行一个整数 \(n\)。 接下来 \(n\) 行,每行 2 个整数,表示这个人的 SAN 值区间。 输出格式: 一行一个整数,表示答案。 数据范围: 满足 \(n \leq 2000,1 \leq l_{i} <r_{i} \leq 4000\) 。 首先把所有线段按右端点升序排序,这样我们可以依次考虑每条线段。 注意到答案的树形如一条长链,其中一些节点挂了几个单点。 考虑设 \(f(i,j)\) 表示编号最右侧的线段是 \(i\) ,次右的是 \(j\) 时的合法方案数。 记 \...
洛谷P2481 [SDOI2010] 代码拍卖会 题解
洛谷P2481 [SDOI2010] 代码拍卖会 题解 题目链接:P2481 [SDOI2010] 代码拍卖会 题意: 随着 qry 在 P++ 语言上的造诣日益提升,他形成了自己一套完整的代码库。猪王国想参加 POI 的童鞋们都争先恐后问 qry 索要代码库。qry 不想把代码库给所有想要的小猪,只想给其中的一部分既关系好又肯出钱的小猪,于是他决定举行了一个超大型拍卖会。 在拍卖会上,所有的 \(N\) 头小猪将会按照和 qry 的好感度从低到高,从左到右地在 qry 面前站成一排。每个小猪身上都有 \(9\) 猪币(与人民币汇率不明),从最左边开始,每个小猪依次举起一块牌子,上面写上想付出的买代码库的猪币数量(\(1\) 到 \(9\) 之间的一个整数)。大家都知道,如果自己付的钱比左边的猪少,肯定得不到梦寐以求的代码库,因此从第二只起,每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪(们)会得到 qry 的代码库真传,向着保送 PKU(Pig Kingdom University)的梦想前进。 qry 对自己想到的这个点子感到十分满意,在去现场的路上,qry 就...
洛谷P4657 [CEOI2017] Chase 题解
洛谷P4657 [CEOI2017] Chase 题解 题目链接:P4657 [CEOI2017] Chase 题意: 在逃亡者的面前有一个迷宫,这个迷宫由 \(n\) 个房间和 \(n-1\) 条双向走廊构成,每条走廊会链接不同的两个房间,所有的房间都可以通过走廊互相到达。换句话说,这是一棵树。 逃亡者会选择一个房间进入迷宫,走过若干条走廊并走出迷宫,但他永远不会走重复的走廊。 在第 \(i\) 个房间里,有 \(F_i\) 个铁球,每当一个人经过这个房间时,他就会受到铁球的阻挡。逃亡者手里有 \(V\) 个磁铁,当他到达一个房间时,他可以选择丢下一个磁铁(也可以不丢),将与这个房间相邻的所有房间里的铁球吸引到这个房间。这个过程如下: 逃亡者进入房间。 逃亡者丢下磁铁。 逃亡者走出房间。 铁球被吸引到这个房间。 注意逃亡者只会受到这个房间原有的铁球的阻拦,而不会受到被吸引的铁球的阻挡。 在逃亡者走出迷宫后,追逐者将会沿着逃亡者走过的路径穿过迷宫,他会碰到这条路径上所有的铁球。 请帮助逃亡者选择一条路径,使得追逐者遇到的铁球数量减去逃亡者遇到的铁球数量最大化。 输入格式: ...
AT_agc013_d [AGC013D] Piling Up 题解
AT_agc013_d [AGC013D] Piling Up 题解 题目链接:AT_agc013_d [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...
AT_agc002_f [AGC002F] Leftmost Ball 题解
AT_agc002_f [AGC002F] Leftmost Ball 题解 题目链接:AT_agc002_f [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\) 种球里选一种放...
洛谷P6669 [清华集训2016] 组合数问题 题解
洛谷P6669 [清华集训2016] 组合数问题 题解 题目链接:P6669 [清华集训2016] 组合数问题 题意: 给定 \(n,m\) 和 \(k\),对于 \(0≤i≤n,0≤j≤\min(i,m)\) 求有多少对 \((i,j)\) 满足 \(\dbinom{i}{j}\) 是 \(k\) 的倍数。答案对 \(10^9+7\) 取模。 输入格式: 第一行有两个整数 \(t,k\),其中 \(t\) 代表该测试点总共有多少组测试数据。 接下来 \(t\) 行每行两个整数 \(n,m\)。 输出格式: 共 \(t\) 行,每行一个整数代表所有的 \(0≤i≤n,0≤j≤\min(i,m)\) 中有多少对 \((i,j)\) 满足 \(C^j_i\) 是 \(k\) 的倍数。 数据范围: \(1≤n,m≤10^{18}\),\(1≤t,k≤100\),且 \(k\) 是一个质数。 根据 Lucas 定理 \[ \binom{n}{m} \equiv\binom{\left\lfloor n/k\right\rfloor}{\left\lfloor m/k\right\rf...
CF1733E Conveyor 题解
CF1733E Conveyor 题解 题目链接:Conveyor 题意: 有一个 \(120\) 行,\(120\) 列的棋盘,行列编号均为 \(0,1,\cdots,119\),\(i\) 行 \(j\) 列的格子的坐标为 \((i,j)\),左上角的格子坐标为 \((0,0)\)。每一个格子上都有一个传送带,初始方向为右。 一开始,有一个史莱姆在 \((0,0)\),其他格子都什么也没有,每一秒传送带的方向都会如下变化: 所有的史莱姆随着传送带的方向移动一格。 如果传送带的方向没有格子,史莱姆就会离开棋盘; 如果两个史莱姆到了同一个格子上,就会合并为一个史莱姆。 所有有史莱姆的传送带的方向都会改变,向右的会变成向下的,向下的会变成向右的。 \((0,0)\) 处会出现一个史莱姆。 给定 \(q\) 个询问,问在第 \(t\) 秒,\((x,y)\) 格是否有史莱姆。 输入格式: 第一行,一个整数 \(q\)( \(1\le q\le10^4\) ),表示询问个数。 每一行询问依次有三个整数 \(t,x,y\)(\(0\le t\le10^{18},0\le x,y...
CF843D Dynamic Shortest Path 题解
CF843D Dynamic Shortest Path 题解 题目链接:Dynamic Shortest Path 题意: 有一张 \(n\) 个点 \(m\) 条边的有向带权图,你需要回答如下的 \(q\) 个问题: 1 v 询问以 \(1\) 为起点到 \(v\) 的最短路 2 c l_1 l_2 ... l_c 对于 \(l_1, l_2, \ldots, l_c\) 的边的边权增加 \(1\)。 对于询问2,保证 \(l_i\) 互不相同。 不存在输出 -1。 数据范围: \(1 \leq n, m \leq 10^5,~1 \leq q \leq 2000,~\sum l_i \le 10^6\)。边权 \(\le 10^9\) ,时限 10s 。 注意到边权虽然很大,但是增量极为有限,这使得我们考察与增量/值域相关的做法。 首先先跑一遍 Dijkstra ,得到每个点的最短路 \(d_u\) ,然后令每条边的新边权为 \[ w(u,v) \gets d_u +w(u,v) - d_v \] 那么此时 \(u \leadsto v\) 的路径的意义就变为了 \...
CF280D k-Maximum Subsequence Sum 题解
CF280D k-Maximum Subsequence Sum 题解 题目链接:k-Maximum Subsequence Sum 题意: 给定长度为 \(n\) 的数列和 \(m\) 个询问,要求支持: 修改某个位置的值。 询问区间 \([l,r]\) 里选出至多 \(k\) 个不相交的子段和的最大值。 数据范围: \(1 \le n,m \le 10^5,~|a_i| \le 500,~0\le k \le 20\) 。 初学模拟费用流,好像没想象中那么难懂。 考虑以下费用流模型: \(S\) 向每个 \(i\) 连边,容量为 \(1\) ,费用为 \(0\) ,其中 \(1 \le i \le n\) 。 每个 \(i\) 向 \(i + 1\) 连边,容量为 \(1\) ,费用为 \(a_i\) ,其中 \(1 \le i < n\) 。 每个 \(i\) 向 \(T'\) 连边,容量为 \(1\) ,费用为 \(0\) ,其中 \(1 \le i \le n\) 。 \(T'\) 向 \(T\) 连边,容量为 \(c\) ,费用为 \(...
洛谷P3978 [TJOI2015] 概率论 题解
洛谷P3978 [TJOI2015] 概率论 题解 题目链接:P3978 [TJOI2015] 概率论 题意: 为了提高智商,ZJY 开始学习概率论。有一天,她想到了这样一个问题:对于一棵随机生成的 \(n\) 个结点的有根二叉树(所有互相不同构的形态等概率出现),它的叶子节点数的期望是多少呢? 判断两棵树是否同构的伪代码如下: \[ \begin{array}{ll} \hline \textbf{算法 1}&\text{Check}(T_1,T_2) \\ \hline 1&\textbf{Require: }\text{ 两棵树的节点 }T_1,T_2\\ 2&\qquad\textbf{if}\ \ T_1=\text{null}\textbf{ or }T_2=\text{null}\textbf{ then }\\ 3&\qquad\qquad\textbf{return}\ \ T_1=\text{null}\textbf{ and }T_2=\text{null}\\ 4&\qquad\textbf{else}\\ 5&a...
AT_agc018_c [AGC018C] Coins 题解
AT_agc018_c [AGC018C] Coins 题解 题目链接:AT_agc018_c [AGC018C] Coins 题意: 有 \(x+y+z\) 个人,第 \(i\) 个人有 \(A_i\) 个金币,\(B_i\) 个银币,\(C_i\) 个铜币。 要选出 \(x\) 个人获得其金币,选出 \(y\) 个人获得其银币,选出 \(z\) 个人获得其铜币。在不重复选某个人的情况下,最大化获得的币的总数。 数据范围: \(1\le x+y+z\le 10 ^ 5,1 \le A_i,B_i,C_i \le 10^9\) 。 做法和 P5470 [NOI2019] 序列 类似,经典套路了。 我们可以先凑满 \(x,y,z\) 人,然后开始反悔贪心。 将一个 \(x\) 放到 \(y\) 去,再从 \(y\) 中拿一个到 \(x\) 。 将一个 \(x\) 放到 \(z\) 去,再从 \(z\) 中拿一个到 \(x\) 。 将一个 \(y\) 放到 \(z\) 去,再从 \(z\) 中拿一个到 \(y\) 。 将一个 \(x\) 放到 \(y\) 去,再从 \(y\) ...
![AT_agc005_d [AGC005D] ~K Perm Counting 题解](/qwq/img/p143.webp)

![洛谷P2481 [SDOI2010] 代码拍卖会 题解](/qwq/img/p1.webp)
![洛谷P4657 [CEOI2017] Chase 题解](/qwq/img/p162.webp)
![AT_agc013_d [AGC013D] Piling Up 题解](/qwq/img/p95.webp)
![AT_agc002_f [AGC002F] Leftmost Ball 题解](/qwq/img/p197.webp)
![洛谷P6669 [清华集训2016] 组合数问题 题解](/qwq/img/p212.webp)



![洛谷P3978 [TJOI2015] 概率论 题解](/qwq/img/p94.webp)
![AT_agc018_c [AGC018C] Coins 题解](/qwq/img/p152.webp)

![洛谷B3869 [GESP202309 四级] 进制转换 题解](/qwq/img/p184.webp)

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p214.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p230.webp)