Zorr noob @zyf || 洛谷关注 Ivan422 谢谢喵喵喵
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
在讨论《问正式赛#pragma,不玄关》回复：
不允许
在讨论《警告：在此帖之后跟风发帖的，将禁言一年。》回复：
差点发出去了
考虑一个动态规划。设 $f_{i,j,0/1}$ 为前 $i$ 个教室换了 $j$ 个（第 $i$ 个是否换了）的期望最小距离，距离显然可以 Floyd 求。我们发现显然要考虑上一个的状态，转移如下： 1. 考虑都不换教室，也就是 $f_{i-1,j,0}+dis_{c_i,c_{i-1}}\to f_{i,j,0}$…
你首先考虑到 $n\times m$ 为奇数的情况，显然这个时候点 $x$ 个为奇数的话就可以补全剩余的，否则就补齐本身。容易得出这样任意解都是对的。然后考虑剩余的，直接组合数可以得出公式 $\frac{(r-l+1)^{nm}+(r-l+1)\bmod 2}{2}$。 ```cpp #include using na…
你考虑一个不停 $\times 2$ 的方法，来取得最高位。然后你就发现 $\times 2$ 再 $-1$ 就可以做到不停不变为 $1$，显然直接发现只要奇偶性相同就可以。然后你考虑如何最小化操作次数。这个的话你发现在前面放可以被后面的 $\times 2$ 多次放大，于是找到需要调整的值类似二进制去做就可以了。还有…
练习贪心中。首先你发现一辆车一定要等齐站点内所有人再出发。然后你考虑到加速的限度：不能让车等人。这样就可以预处理出**一个站点的人数（$s$）**，**一个站点最后人什么时候到（$w$）** 这两个信息。然后考虑一段区间的情况。显然预处理出当前 $d$ 下的到站时间 $l$。然后我们考虑如何使用加速器。我们考虑一些乘客…
嗯其实是因为一个性质：一个数的前缀和要是有两位 $\bmod 3$ 相同，或者有一位 $\bmod 3=0$ 就一定是你干的。然后根据这个定理显然容斥得三位数一定可以。然后就结束了。和一位我赛时没有过？？ ```cpp #include using namespace std; #define ull unsigned…
我用的是神秘最劣 $\mathcal O(n^3)$ 做法，直接冲过去了。少量打表可以得出结论：答案一定是一个 $1\sim n^2$ 的排列。所以你考虑用链表维护然后直接暴力即可。因为 $n$ 只开了 $1000$ 所以随便冲。正解是用二次剩余，但是这题做法很多。 ```cpp #include using name…
哦终于开始改这个题了。首先看到最大值最小就考虑一个二分的做法。然后就需要使用树形 DP 来 check 了。状态设计是 $f_i$ 为以 $i$ 为根的子树是否有方案合法，如果有就存储父亲边的使用次数。显然可以考虑一个背包转移。然后代码是不困难的。 ```cpp #include using namespace std…
你首先考虑把合并变为分裂。然后就可以分治去做，把矩形集合分为两部分。因为问题问的是**是否有方案**，所以切多少刀都是无所谓的。所以就有一个 $n^2$ 的做法是不停递归并判定是否可以切割成功。这个东西如何优化呢？你会发现你不一定每一次都要找到所有分割线，所以就考虑使用链表维护这个东西。然后就成为了一坨答辩，但是代码还…
哦赛时就差一点过了，使用 $n^3$ 冲过部分 $n=1000$ 的点，脏脏 $70$ 分。（预计 $40$）然后我们考虑转化问题。你会发现无论树的结构怎么变叶子的相对顺序都不会变，所以考虑一个转化为线段合并问题，到这里就可以直接 $n^3$ 区间 DP。设 $f_{i,j}$ 为合并这个区间后合并的数值。最后显然需要…
``` f[i][j][k] 前 i 行，j 列 1 个，k 列 2 个 f[i][j][k] f[i-1][j][k] f[i][j][k] f[i-1][j+1][k-1]*(j+1) f[i-1][j-1][k]*(m-(j-1)-k) f[i][j][k] f[i-1][j-2][k]*C(m-(j-2)-k,…
其实这是一道好题。首先考虑数据范围提示您 $n^2$ 轻松拿捏。然后我们考虑如何设计状态。$f_{i,j}$ 为操作前 $i$ 个数，已经完成了 $j$ 的部署的不同方案数。显然答案为 $f_{n,n}$。我们考虑如何转移。你发现有这样的转移：$f_{i,j}\leftarrow f_{i-1,j}$。也就是考虑一个不…
我们发现从一个点开始钦定一个特殊点往后走一定是最优的，具体原因就是多选多错，直接这样做然后优化一下就正确了。 ```cpp #include using namespace std; const int N=2e5+10,M=5; int n,d,k,a[N][5],l,r,ma; int t[M*N],tc; int…
哦不其实是直接左右缩着然后直接最优化区间即可。然后注意要固定左右侧都要跑一遍。 ```cpp #include using namespace std; const int N=1e6+10,V=26+5; int n,ans; char a[N]; stack stk[V]; int solve(){ for(int…
如此成绩，何以 PION。你首先考虑一个无限的情况是怎么样的。你会发现在强连通分量里面有完全なるの黄金回旋エネルギー，可以无限传递。当这个 SCC 内的边数与点数相等时就显然有每个点最大为他们的和。要是边数更多一点，就显然有无限传递。缩点后这就显然是一个 DAG，直接做即可。注意判断 $0$，也就是没有病毒的情况。 `…
感觉这题放 NOIP T1 超级合适。这是一道状压 DP 的好题。首先看数据范围 $n\le 24$ 直接起飞。然后考虑如何状压。直接转移比较困难，考虑 $f_i$ 为前 $i$ 个物品最少使用包数，然后设一个辅助转移的数组 $g_i$ 为前 $i$ 个物品目前开的最大背包。然后你发现 $g$ 的定义不一定是对的。所以…
如何呢类 NOIP2024T1 题为什么这么多。那我没制作出来又是和一位啊。你发现序列排列问题都是一个套路：显然找到一个最优策略直接做即可。那个 T1 就是按照固定 2 个 / 1 个 / 无固定三个方面去做。然后这个题就是： 1. 不要选相交区间，这可以合并。 2. 不要让开头结尾被交换，因为这样区间会更长。 根据这…
打得最好的一集，这题秒切。你发现有点边容斥连通块个数为点数减去边数。然后我们随便搜索一次给每一个点定义一个父亲，你发现当一个点与父亲都被选中时可以直接把贡献扔到父亲上，自己就没用贡献。所以考虑一个点被包括的所有矩阵，然后减去与父亲同在的矩阵，计算是容易的。 ```cpp #include using namespace…
你就发现一个点要是选了行就只能选同列其他点。显然这个关系可以把 $x,y$ 轴当做二分图两点连边 $x\to y$ 然后染色就做完了。结论为后手必胜当且仅当该二分图存在一个完美匹配。 ```cpp #include using namespace std; const int N=1e4+10; int n; bool…
你发现做完差分后操作其实变成了单点修改。然后线段树维护哈希值即可。要注意的是传入时 $-c+k$ 以及区间长度限制了查询哈希的时候要动态修改区间端点，不然会搞到错误的区间长度导致哈希匹配失败。 ```cpp #include using namespace std; #define ull unsigned long…
我们考虑如何使用组合数学来做这道生成函数。你首先知道这是一个错排问题。考虑一个组合方案是 $f_{i,j}$ 为有 $i$ 对情侣 $j$ 对在一起的方案数。我们显然有一个排列为 $\binom{i}{j}$ 为选择 $j$ 个对在一起。然后我们考虑这些人的顺序，有 $A_{i}^j$ 的方案。然后左右互换是 $2^j…
T3，随便可以推出一个矩阵快速幂的转移方案。 $$ f=\begin{bmatrix} x & 1 \\ y & 0 \end{bmatrix}\\ f^{-1}=\begin{bmatrix} 0 & \frac{1}{y} \\ 1 & -\frac{x}{y} \end{bmatrix} $$ 也就可以容易计算出…
显然边只选一条，所以会有最短路为： $$ dis(1,u)+w(u,v)+dis(v,n) $$ 求这个的最小值，由于 $w(u,v)=w_i-kt_i$，一次函数，以 $w_i$ 为横坐标即可。所以这是一个凸包。考虑一个维护凸包的东西做即可。但是我不会 Slope。 ```cpp #include using nam…
构造不太容易但是思路是不困难的。你发现显然是需要一次异或对齐 $a,b$ 才好修改 $a$ 最高位为 $c$。然后不停右移异或使得 $a=c$ 让 $b$ 为 $0$ 一次异或既可以解决，最劣情况 $64$ 次操作计算完成呢。 ```cpp #include using namespace std; #define l…
为什么是一个神人构造题。你会发现这个东西有点像前几天做的 P11313，但有本质不同。你可以把格子分为三种来考虑。然后你就会发现这个东西出现了一个对角线的环。摆一个大佬的图。其中颜色深浅表示黑白。嗯其实具体看 CF1586I 呢。 $，超时。发现数据范围不是人 $2\times 10^9$ 有…
h1w 我赛时为什么为什么没做出来怎么会是呢。考虑直接 dp。设 $f_{0/1,i,j}$ 为区间 $i,j$ 顺序 / 逆序能获得的最大收益，简单做。$g_{i,j}$ 为前 $i$ 个有 $j$ 次修改的情况。计算是简单的。 反思：赛事没有往区分方向这方面想，一直在思考正确策略。然后 dp 状态也设计过，问题是状…