xixike

# Visits S 手玩一遍样例，找找最优决策，不难发现一个环中最优情况瞎只有一个点不能选。 并且题目给出的关系是一个基环树森林。 所以先求一下总和， 然后 Tarjan\text{Tarjan}Tarjan 找每一个环上的最小值，用总和减去即可。 另外要判一下环的大小大于等于 2 时才能减（一个点时显然是可以加上的）。 #include <bits/stdc++.h>#define pb push_back#define ll long longusing namespace std;namespace IO{ inline int...

# Description Luogu 传送门 # Solution 一直以为这是道数学题，结果是 dp\text{dp}dp…… 观察题目给的式子，不难发现，这就是个长为 ai+aja_i + a_jai​+aj​，宽为 bi+bjb_i + b_jbi​+bj​ 的矩阵，让你求从左下角走到右上角的方案数。 转移方程也非常简单： dpi,j=dpi−1,j+dpi,j−1dp_{i, j} = dp_{i - 1, j} + dp_{i, j - 1} dpi,j​=dpi−1,j​+dpi,j−1​ 但是转移完之后我们还是要 O(n2)O(n^2)O(n2)...

说是游记其实就是在在机房里考的啦。 全程摸鱼警告 10:55 的时候就开始新建文件夹了，58 分的时候发现没登录，赶紧登录了一波。 11:00 准时开题，发现这题面怎么都巨大长啊，看到了叫做 “THUPC” （后来改成 “画图” 了）的题目，感觉可能是签到题，点进去看了一眼，发现是个毒瘤模拟，让你判断输入的线段是否构成 THUPC 字样，果断放弃。 这时机房里几个 dalao 已经开始切 K 了，是模拟题，输入一个字符矩阵让你求正方体个数头顶标数法应用，感觉也是非常的毒瘤。 开考 6 分钟的时候首 A 诞生了，切的是 A 题，于是滚去看 A。听到旁边 qq 已经搜到 A...

# Description Luogu 传送门 # Solution （感谢 @Acestar 提供的思路） 初始情况下，每头奶牛匹配一个礼物，所以我们把奶牛和礼物当作一个点。 如果奶牛 iii 非常不要脸的去抢奶牛 jjj 的礼物（iii 向 jjj 连单向边），而且不幸的是奶牛 jjj 还打不过奶牛 iii，那么 jjj 就被迫去抢别人的礼物 qwq，所以 jjj 就必须向它能抢到的别的奶牛连边。 因此我们这个图就建出来了，找一组解只需要跑一遍传递闭包即可，顺便拿个 bitset\text{bitset}bitset 优化一下，时间复杂度 O(n3ω)O(\frac...