0103abc 的网站

正解好像是树上维护懒标记然后下传，~~但是众所周知我不会维护懒标记~~，所以考虑一个相对偏 ds 的做法。 发现题目的查询操作全在修改操作之后，因此考虑离线做法。先记录每一个点 $i$ 的 $1,2$ 两种操作的权值，设其为 $v1i,v2i$。可以发现两个操作之间互相独立，因此考虑分离处理之。...

首先有经典结论：对于一个长度为 $n$ 的数组 $a$，若交换其 $i,j$ 位置的元素的值（$i\neq j$），则其逆序对数必然发生改变。 因此可以证明若 $n\equiv 2,3\pmod 4$，则必然无解。否则可以构造答案使得其存在合法解； 若 $n\equiv 0\pmod...

一个很神经病的做法。显然可以考虑枚举每一段最小单位长度的区间，然后记录有多少种不同的选 $k$ 条线段的方法包含这一段区间。显然这样会计算重复。 问题变为怎么不让答案计算重。考虑从左往右枚举每一个最小单位长度的段，设其左端点为 $l$，则只需要让所有线段不同时覆盖 $l$...

一个很好理解很好写的做法。显然答案的上界是 $n$。 考虑对于一条 $a\sim b$ 的路径，则要么在圆上顺时针走要么逆时针走。考虑定义一条路径的状态 $F(u\to v)$： $F(u\to v)=1$：即维护 $u$ 顺时针走到 $v$ 的路径。 $F(u\to v)=0$：即维护 $u$...

被 $2400$ 击败了，写点水题提提信心（ 考虑什么时候是不合法的。显然，此时 $S$ 串必须为回文串，且必须满足下面三个条件之一： $S$ 串内所有元素均相同。 $S$ 串内只有两个不同的字符，$2\nmid |S|$ 且所有奇数位，偶数位的字符分别相同。 $S$...

第一篇 $3500$ 题解欸（ 一道诈骗题。考虑到对于每一个三元环 $$ ，其都有三条无向边 $,,$ 将其连接。每一次操作是让一条边 $$ 的两个端点的点权同时增加 $v$（ $1\le v\le 4$ ）。那么可以考虑对于上面提到的每一个三元环 $$，考虑给其三条边对应端点的点权分别增加...

首先有一个经典结论：连通性具有传递性。具体来说，图上若 $a$ 可以到达 $b$ ，$b$ 可以到达 $c$ ，那么 $a$ 就必然可以到达 $c$ 。在给定的图中，因为边总是从小编号连向大编号的，因此只需要判断编号相邻的两个点是否都连通，就可以知道是否整个集合内所有点都连通了。 考虑维护两个栈...

首先考虑一条长度为 $n$ 的链上的情况。 对于 $2\nmid n$ 的情况：链上存在编号为 $\frac{n+1}2$ 的中点，直接以这个点为中心，向两边扩展长度染色即可，需要耗费 $\frac {n+1}2$ 次操作。 对于 $2\mid n$ 的情况：此时链上没有中点，因此需要继续分类讨论：...

可以证明下面的等式成立： f(a,b)=f(a/\gcd(a,b),b/\gcd(a,b)) 于是问题就变得简单了。首先先对 $a,b$ 进行操作直到 $\text{gcd}(a,b)=1$ ，然后分类讨论： 若此时 $b=0$，则无需进行任何操作，返回 $0$ 。 若此时...

考虑对 $n$ 的奇偶性分类讨论答案。 I. $n$ 是偶数 此时把上面的 $\frac n2$ 行构造奇数，下面的 $\frac n2$ 行构造偶数。可以证明此时上 $\frac n2$ 行和下 $\frac n2$ 行各自内部相邻两个数的和一定不为质数（都是不为 $2$...