Fanyi's Blog

一道有趣的题。 查看题目 PDF 3s+O2 原题大概是这道。 看到模 \(3\) 显然是出题人精心构造的。 于是我们打出一张组合数模 \(3\) 的表。 好多 \(0\) 啊～ 于是我们考虑如何快速求出组合数不是 \(0\) 的位置。 先说一下我考场上想到的 \(\log\) 做法： 我们考虑 lucas，对于组合数 \(\binom{m}{n}\)，其实就是 \(\binom{M_i}{N_i}\) 的乘积，其中 \(M_i,N_i\) 表示 \(m,n\) 在 \(3\) 进制下的第 \(i\) 位。 我们发现 \(\binom{M_i}{N_i}\) 只要有一位是 \(0\)，最终结果就是 \(0\)，所以我们只要枚举 \(m\) 后枚举三进制下每一位是比 \(m\) 小的 \(n\) 就行了，这样每次找是 \(\log\) 的，所以复杂度是…

给定一张无向图，要求把边染成黑白两色，要求所有白色边构成的子图没有环，且所有黑色边构成的子图没有环。 多组询问，输出是否有解。 \(n\le 500,m\le 2n,T\le 10\)。 显然，由白边构成的图是一个森林，黑边构成的图也是个森林。 显然森林所有的导出子图也是森林。 那么显然图是一个森林的充要条件为其最大导出子图的 \(|E|-|V|\le -1\)。 我们考虑原问题，如果一张图 \(G\) 要有解，那么 \(G\) 的所有导出子图都要有解，且该图的 \(|E|\le 2(|V|-1)\)，也就是让黑白两种颜色都能是一片森林。 有了这个有理有据的性质，我们就把问题转化成了：对于图 \(G\)，定义 \(\rho_G=|E|-2|V|+2\)，求出一张图所有导出子图 \(\rho?\) 的最大值。 我们考虑网络流，\(S?\) 向所有原图的边（看作点）连边，容量为 \(1?\)，…

一道有趣的贪心题。 查看题目 PDF 给你两种瓷砖 \(a,b\)，每种瓷砖有 \(n\) 块，每块瓷砖有两个属性：高度 \(h\) 和价值 \(p\)。 现在要求你把这些瓷砖重新排成两行（\(2\times n\)）。前一行放瓷砖 \(b\)，后一行放瓷砖 \(a\)。 要求从左到右 \(p\) 递增（单调不减），对于任意一个位置 \(i\)，后面的瓷砖要比前面的瓷砖高。 求一种方案或输出无解。 \(n\le 5\times 10^5\) 对于一段 \(p\) 相同的区间，我们可以将里面的瓷砖随意调换。 考虑如何贪心。 我们发现有两种不同的情况，我们的目的不同： 此时我们是想让匹配完 \(a\) 中 \(p=2\) 情况后，\(b\) 中剩余的 \(p=3\) 的瓷砖的 \(h\) 尽量小。 我们可以将 \(a\) 中 \(p=2\) 的每块瓷砖都找到 \(b\) 中一个恰好比它小的瓷砖…

原题链接 \(n(n\le 10^5)\) 个球排成一排，第 \(i\) 个球有颜色 \(c_i(c_i\le n)\) 和重量 \(w_i(w_i\le 10^9)\)。 Snuke 每次可以选择两个颜色相同，且重量之和不超过 \(x\) 的球，交换他们的位置。 Snuke 每次可以选择两个颜色不同，且重量之和不超过 \(y\) 的球，交换他们的位置。 问可以得到多少种不同的颜色序列。\(1\le x,y\le 10^9\)，答案对 \(10^9+7\) 取模。 我们考虑什么时候连个球能进行交换。 显然如果有三个球 \(a,b,c\)，如果 \(a\) 与 \(b\) 能交换，\(b\) 与 \(c\) 能交换，那 \(a\) 与 \(c\) 一定能通过 \(b\) 的“媒介”交换（\(a\) 先于 \(b\) 交换，\(b\) 与 \(c\) 交换，\(a\) 与 \(b\) 交换）。…

题目链接 有一个长度为 \(L\) 的圆环, 上面有 \(n\) 个蚂蚁, 位置分别为 \(x_i\)，运动方向为 \(d_i\)，\(1\) 表示顺时针，\(2\) 表示逆时针。每只蚂蚁将会同时开始以单位速度运动，如果两只蚂蚁相遇，那么它们会改变自己的方向继续运动。求 \(T\) 秒之后每只蚂蚁的位置。 \(1\le n\le 10^5;1\le L,T\le 10^9;0\le x_1<x_2<\cdots<x_n\le L - 1\)。 显然我们先来看如果没有标号，那么可以把两只蚂蚁的“掉头”无视掉，这样我们就已经知道了蚂蚁的位置。 不难发现每只蚂蚁的相对位置不变，即它左边和右边的蚂蚁是不会变的。 于是我们只要确定其中一只蚂蚁即可。 我们可以记录一下坐标最小的蚂蚁是那只，即越过 \(0\) 坐标的蚂蚁有几只，这样就确定了一只蚂蚁。

题目链接 给出一颗 \(n(n\le 10^5)\) 个节点组成的树，每个节点都可以被染成白色或者黑色。 有高桥（先手）和青木（后手）两个人，高桥可以把任意某个点染成白色，青木则可以把任意一个点染成黑色，每个点只可染色一次。 当所有点都被染色后，只执行一次执行以下操作： 若操作完毕后仍还有白点存在，即高桥（先手）胜，反之则青木（后手）胜。 现在给出这棵树，问当前此树是先手必胜 or 后手必胜。 问题显然就是青木不能让任意一个白点旁边没有黑点。 如果该树有完美匹配，那么显然是后手赢。因为不管先手选什么，后手只要选先手对应的点就可以。 于是我们就来考虑没有完美匹配的情况。 最特殊的应该是叶子节点，因为只有一个点与它相邻。如果叶子节点是白点，那么叶子节点的“父亲”必须是黑点；而如果叶子是黑点，那么叶子节点的“父亲”必须是白点。这里的“父亲”是指它相邻的点。 我们考虑先手先任意一个叶子节点的“父亲…

题目链接 给一个 \(n(n\le 15)\) 个点 \(m\) 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 \(1\) 到 \(n\) 只有 \(1\) 条路径（不经过重复点），问割掉的边权和最小是多少。 问题其实就是需要保留的边权和最大。 问题是有关点集+路径的，不难想到状态：\(f_{i,j}​\) 表示遍历了集合 \(i​\)，这条唯一的路径的已经是从 \(1​\) 到 \(j​\) 的答案。 我们考虑选择路径的形状，大概应该应该是这样的： 就是 \(1\sim n\) 的一条，然后中间许多分叉，连向一些连通块，而这些联通块中所有的边都连上。 于是我们考虑转移。 当 \(j=1\) 时，\(f_{i,j}=E_i\)，其中 \(E_i\) 表示 \(i​\) 集合中所有边的权值和。 可以连下一个链上的点：…

我们定义一棵树的删除序列为：每一次将树中编号最小的叶子删掉，将该节点编号加入到当前序列的最末端，最后只剩下一个节点时将该节点的编号加入到结尾。 例如对于上图中的树，它的删除序列为：2 4 3 1 5。 现在给出一棵 \(n\) 个节点的树，有 \(m\) 次操作： 第一行两个正整数 \(n,q(1 \leq n , q \leq 200000)\) 表示树的点数和操作数。 接下来 \(n-1\) 行每行 \(2\) 个正整数 \(u,v(1 \leq u,v \leq n)\) 表示树上的一条边。 接下来 \(q\) 行每行描述一个操作。 每一个询问输出一行。 对于 when v 询问，输出一个正整数表示 \(v\) 是当前删除序列的哪一个元素。 对于 compare u v 询问，如果 \(u\) 在删除序列中更靠前则输出 \(u\)，否则输出 \(v\)。 显然在任意时刻最大的那个节点…

原题链接 有 \(n\) 个二次函数，第 \(i\) 个形如 \(f_i(x)=a_ix^2+b_ix+c_i\) 你的总收益是 \(\sum_{i=1}^nf_i(x_i)\)，但是有几个限制： 求最大的总收益。 \(n\le 50; m\le 100; |a_i|\le 10;|b_i|,|c_i|\le1000;-100\le l_i\le r_i\le 100;|d_i|\le 200\)。 感觉和刚刚做过一场模拟赛的一道题很类似…… 考虑网络流，对每个函数都建立 \([l_i,r_i]​\) 的点，点 \((i,j)​\) 表示函数 \(f_i​\) 当 \(x_i=j​\) 时的点。 我们考虑最小损失。设一个极大值 \(lim\)（大于所有的 \(f_i(x)\)），将也就是要求 \(lim-f_i(x)\) 的最小值。 我们从点 \((i,j)\) 向点…

原题链接 有 \(m​\) 个猪圈，开始时第 \(i​\) 个猪圈有 \(a_i​\) 头猪，每个猪圈都是锁门的，要是不相同。管理员没有猪圈的钥匙。依次来了 \(m​\) 个顾客，第 \(i​\) 个顾客有 \(A_i​\) 把猪圈钥匙（哪几个都告诉你）话说为什么钥匙会在顾客手中啊，需要至多 \(B_i​\) 头猪。每个顾客打开这几个猪圈，然后管理员可以把打开门的几个猪圈里的猪进行调整（比如把 \(\text{A}​\) 猪圈的其中一头猪带到 \(\text{B}​\) 猪圈）。要求的是管理员最多能卖出多少猪。 \(n\le 100,m\le 1000\)。 一道有趣的网络流建模题…… 首先当然要建超源（\(S\)）和超汇（\(T\)）。 把每个顾客都看成一个点。 每个顾客向 \(T\) 连一条容量为 \(B_i\) 的边，表示每个顾客最多买 \(B_i\) 头猪。 首先是 \(S\) 向…