Q779’s Blog

洛谷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 题解 题目链接：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 题解 题目链接：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 题解 题目链接：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] 概率论 题意： 为了提高智商，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...

[AGC018C] Coins 题解 题目链接：[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\) 中拿一个到 \(z\) ，最后从 \(z\) 中...

CF730I Olympiad in Programming and Sports 题解 题目链接：Olympiad in Programming and Sports 题意： 有 \(n\) 个学生每人有两种技能，分别是 \(a,b\) 表示编程能力和运动能力。你需要将他们分为两个团队分别参加编程比赛和体育比赛，编程团队有 \(p\) 人，体育团队有 \(s\) 人，一个学生只能参加其中一项。每个团队的力量是其成员在对应领域能力总和，请问如何分配能使得两个团队的实力和最大？ 输入格式 共三行，第一行包含三个正整数 \(n,p,s\)。 第二行有 \(n\) 个整数 \(a_1,a_2\cdots a_n\)，第三行，有 \(n\) 个整数\(b_1,b_2\cdots b_n\)。 输出格式 第一行输出整个团队最大的实力，然后给出一种构造方案即可。 数据范围： \(2\le n\le 3\times 10^3,~1\le p+s\le n,~1\le a_i,b_i\le 3000\)。 经典的多个堆维护反悔贪心。做完这题可以去做一下 CF436E 和 P5470 考虑将最...

洛谷P3545 [POI2012] HUR-Warehouse Store 题解 题目链接：P3545 [POI2012] HUR-Warehouse Store 题意： 现在有 \(n\) 天。第 \(i\) 天上午会进货 \(A_i\) 件商品，中午的时候会有顾客需要购买 \(B_i\) 件商品，可以选择满足顾客的要求，或是无视掉他。 如果要满足顾客的需求，就必须要有足够的库存。问最多能够满足多少个顾客的需求。 输入格式： 第一行包含一个整数 \(n\)，表示有 \(n\) 天。 第二行有 \(n\) 个整数 \(a_i\)，表示第 \(i\) 天上午进货 \(a\) 件商品。 第三行包含 \(n\) 个整数 \(b_i\)，表示在第 \(i\) 天中午有顾客来买 \(b\) 件商品。 输出格式： 第一行一个整数，表示最多能满足几天中顾客的需求。 第二行输出满足这么哪些天顾客的需求。 数据范围： \(1\le n\le 2.5\times 10^5,~0\le a_i,b_i \le 10^9\)。 考虑反悔贪心。每次直接选 \(b_i\) 。 如果发现库存不够了，就从之...

洛谷P2107 小Z的AK计划 题解 题目链接：P2107 小Z的AK计划 题意： 在小 Z 的家乡，有机房一条街，街上有很多机房。每个机房里都有一万个人在切题。小 Z 刚刷完 CodeChef，准备出来逛逛。 机房一条街有 \(n\) 个机房，第 \(i\) 个机房的坐标为 \(x_i\) ，小 Z 的家坐标为 \(0\)。小 Z 在街上移动的速度为 \(1\)，即从 \(x_1\) 到 \(x_2\) 所耗费的时间为 \(|x_1 - x_2|\)。 每个机房的学生数量不同，ACM 题目水平也良莠不齐。小 Z 到达第 \(i\) 个机房后，可以花 \(t_i\) 的时间想题，然后瞬间 AK；当然，也可以过机房而不入。 小 Z 现在只有 \(m\) 个单位时间，之后他就该赶着去打 Codeforces 了。现在他想知道自己最多能在多少个机房 AK，希望你帮帮他。 输入格式： 第一行包含两个整数 \(n,m\)。 接下来 \(n\) 行，每行包含两个整数 \(x_i,t_i\)。 输出格式： 第一行包含一个整数，表示小 Z 最多能 AK 的机房数量。 数据范围： \(1 \le...

[AGC006D] Median Pyramid Hard 题解 题目链接：[AGC006D] Median Pyramid Hard 题意： 给出一个 \(N~(1 \le N \le 10^5)\) 层的方格金字塔，自顶向下依次标号为第 \(1\) 到第 \(N\) 层。 其中第 \(i~(1 \le i \le N)\) 层有 \(2i - 1\) 个方格（具体形态见下面的图） 第 \(N\) 层有一个 \(1\) 到 \(2N-1\) 的排列，其他层的数字按以下规则生成： 方格 \(b\) 中填写的整数，是方格 \(b\) 正下方、左下方和右下方方格中所写整数的中位数。 现在给出第 \(N\) 层的数字，请你求第一层的数字。 考虑二分最上层这个数 \(\ge x\)，然后令 \(\ge x\) 的数为 \(1\) ，\(<x\) 的的数为 \(0\) 。 那么原题可以转化为，每次操作对于相邻的三个数， 如果 \(1\) 的个数 \(\ge 3\) 则为 \(1\) ，否则为 \(0\) ，最终最上面的那个数是 \(0\) 还是 \(1\) 。 这样问题就变...

CF73D FreeDiv 题解 题目链接：FreeDiv 题意： 你要执行以下两步操作： 在图中任意连边 在第一步操作后得到一张新图，在新图中继续连边。 要求每个点只能在这步中连一条边，每个新图中的连通块只能连 \(k\) 条边 要求在这两步操作后图是连通的，求第一步中最少要连多少边 数据范围： \(1 \le n,k \le 10^6,~0 \le m \le 10^6\) 显然这个第一步操作实际上是由第二步的决策决定的。 注意到要使得图连通，我们可以用两个连通块连一条边这样的方式合并 考虑把原图的连通块看作一个点，设有 \(d\) 个连通块。 由于让这 \(d\) 个点连通至少需要 \(d-1\) 条边，则当且仅当 \[ \sum_{i=1}^d \min \left(a_i, k\right) \geq 2(d-1) \] 时，我们可以通过操作二完成合并。 而第一个操作实际上在减少 \(d\) ，同时左侧如果加的边不好可能会让左侧减小。 考虑用小根堆维护每个连通块的大小，每次取最小的两个连通块合并，直到上述不等式成立即可。 时间复杂度 \(\mathcal{O}(...

模拟赛题讲解[35] 题目链接：noi.ac #3714 （让 mygr 巨佬帮我交的隐藏题） 一、题面 菜汪酱发现了 \(n\) 个宝箱，编号为 1 到 \(n\)。 这些宝箱被 \(m\) 条铁链绑在了一起。每条铁链连接两个宝箱。 菜汪酱希望拿走尽可能多的宝箱。但是宝箱不能乱拿，否则会触发机关。经过解密，菜汪酱知道一种方案是安全的当且仅当： 拿走的宝箱两两之间有铁链连接。 没有拿走的宝箱两两之间没有铁链连接。 菜汪酱希望在保证安全的情况下拿走尽可能多的宝箱。这个问题的解决方案交给你了。 输入格式 第一行两个整数 \(n\) 和 \(m\)。 接下来 \(m\) 行每行两个整数 \(u\) 和 \(v\)，表示一条铁链连接宝箱 \(u\) 和 \(v\)。 保证不会有两条铁链连接相同的宝箱。 保证存在一种安全的方案。 输出格式 第一行输出一个整数 \(\rm ans\)，表示拿走的宝箱个数。 第二行输出 \(\rm ans\) 个整数，表示选择的宝箱编号。 输入输出样例 输入： 7 9 2 5 3 5 5 7 7 1 1 4 1 2 5 4 7 4 1 5 输出： 4 5...