[$O(nk)$ 标算被踩](https://www.luogu.com.cn/article/mdbgb5zz)

贪心题。考虑按起点为第一键、终点为第二键从大到小排序依次考虑，每次取到的点若高于当前区间的终点就取其起点。时间复杂度 $O(n\log n)$。 证明：这些取到点的区间互不相交，必须每个区间都取点，而只有每个区间起点是最优的。其他区间由于被覆盖到不影响结果。 ```python a = sorted(list(map(…

数学题，推出公式即可。先找到 $k$ 节点在哪一层的哪一位置，再找到 $n$ 的，设二者之间层数差为 $x$ 则 $n$ 节点以上层数子树大小为 $\sum_{i=0}^{x-1}m^2$，再根据子树最后一层节点范围和 $n$ 求出最后一层节点数即可。复杂度 $O(T\log_mn)$，在题目数据范围内树最多 $31$…

接近板子的马拉车，求 $1$ 最多的回文串（可以复制最多的 $1$，同时显然该串一定是确定中心时的最长串），注意串中心不能是 $1$，因为奇数长度串中间的位和自己异或一定是 $0$。统计回文串中 $1$ 的数量的方法是：先求出前缀和，尾首相减。答案是总 $1$ 的数量减回文串中 $1$ 的数量的一半。复杂度 $O(n)…

```python import re a = [] for i in range(int(input())): b, c = input().split() a.append((int(b), c.rstrip('/').replace('/*', '(/\w+)') + '$')) a.sort(reverse =…

在讨论《这个问题有可能贪心解吗》回复：

补一句，给出 $x$ 的初始值

有 $n$ 个函数 $f_i(x)=a_{i0}x^0+a_{i1}x^1+...+a_{ik}x^k$ 满足 $a_{ij}$ 为正整数，求 $1$ 到 $n$ 的排列 $p$ 使得 $f_{p_n}(...f_{p_1}(x))$ 最大 我只想到了状压，问 AI 也没给出状压以外的解法 目前的一些可能的思路： -…

经典无向图一笔画问题。每一个连通图结论为奇度数点的一半（特判：如果没有则仍然需要一笔起笔）。 证明：注意到每笔只会对头尾度数奇偶性有影响，所以答案至少为奇度数点的一半。由于只要图联通就一定可以从奇点走到奇点结束，而分割出无奇点的联通部分是不需要担心的（可以直接附在奇点间的路径上），可以找到最优构造。 统计节点度数奇偶性…

在讨论《因大量脚本导致的提交评测现状说明》回复：

@[__Sparkle__](luogu://user/1436448) 我的意思是公开的政策限制 如果是收钱的AI训练或者ddos用户会不遗余力地对抗这些体系，不如把filter收紧

考虑将答案对数化考虑。显然 $\log_2x'$ 需要落在 $[\log_2x-1,\log_2x+1]$ 之间。 注意到 $5\times 10^9$ 略大于 $2^{32}=4294967296$，直接四次二分插眼 $16$ 个覆盖不完，考虑将所有数离散地分段：$[1,4],[5,20],[21,84]$，以此类推…

在讨论《因大量脚本导致的提交评测现状说明》回复：

@[chen_zhe](luogu://user/8457) 请问考不考虑直接限制未实人认证的账号的提交频率？这样既可以筛选可疑的用户也可以对正常用户的异常行为快速追责。

在文章《题解：P12171 [蓝桥杯 2025 省 Python B] 最长字符串【缺少 words.txt】》发表评论：

@TruemanKent 第 $i$ 轮循环表示长度为 $i$ 的还能被扫到的子串，即坚持到最后一轮才有效 以及发现貌似写的是 bfs 说的却是 dfs 致歉

在文章《题解：CF2108B SUMdamental Decomposition》发表评论：

勘误一下，特判是n=1和x=0（不是x=1）

考虑分类讨论。 - $x=0$ 的情况： - $n$ 为偶数时直接 $n$ 个 $1$ 相消即可，答案为 $n$； - $n$ 为奇数时： - $n=1$ 显然无解； - 否则最简单的奇数异或和归零是 $3\oplus 2\oplus 1=0$ ，剩下的 $n-3$ 个 $1$ 相消即可，答案为 $n+3$； - $x…

由于不增顺序操作只禁阻了从低到高的按钮操作，所以找到所有单台机器无法跨越的“谷地”，即连续若干个相同的数比其左右都低，答案为谷地数加一（两边肯定不是谷地，谷地外还有要按的按钮）。复杂度 $O(n)$。 ```python for _ in range(int(input())): n=int(input());a=li…

在讨论《建议加强数据》回复：

@[_Corange_](luogu://user/762117) @[Folden_xiaoming](luogu://user/1393199) 但是是被Python过的（）

[$10^4$ 的数据规模被 $O(m^2)$ 给过了](https://www.luogu.com.cn/article/wu6lwhkr)

先上代码： ```python a,b=map(int,input().split());c=[1<<30]*b;d=[list(map(int,input().split()))for i in range(a)];e=1;from bisect import* while d: for i in range(len…

由于产物序号一定高于原料，可以根据产物序号排序分析每种产物最高人均产量，这样保证后面要调取前面最高人均产量时是正确的。 如果产物可以白嫖那么它的人均产量就是 $w_i$，否则考虑消耗单位人产生的所有底物 $w_s$ 需要的（包括生成底物的单位人）总人数 $n_i=\frac{w_s}{k_i}+1$ 以及这些底物带来的…

Python 的魅力时刻！ 考虑贪心，将所有数想象成无限循环小数的循环节，可以用交换——逐步优化法发现在交换时显然有小数越大越应该靠前的结论，于是排序加和输出即可。 ```python a='';import sys;sys.set_int_max_str_digits(1<<30) for i in sorted((…

看到题第一反应：串这么短，别说暴力 $O(n^2)$ 了，找个放 $O(n^3)$ 甚至常数小点的 $O(n^4)$ 来都能过啊，而且还是 Python 最经典的 ```eval()``` 环节，太简单啦！ 实际一写：诶怎么这里 RE 了？！诶怎么这里又 WA 了！？ 看数据汲取教训： - 首先要套 ```try```…

分类讨论： - 如果 $m$ 和 $n$ 都不能被 $k$ 整除则直接 $1$ 到 $k$ 循环摆 $\frac{mn}k$ 遍然后穿到矩阵里，余数产生的列号位移让相同的数包碰不上的。 - 如果其中一种能被 $k$ 整除（不妨设是 $n$）可以则直接每行 $1$ 到 $k$ 循环摆 $\frac nk$ 遍，每行之间位…

可以先将异或拆成相加再减去二倍的重叠部分，发现相加部分是 $na_k+s$（$s$ 为数列总和），重叠部分可以统计 $a_i$ 每一位的数量，然后逐个逐位比对相减，答案为 $s+\max(na_k-2\sum_{j=0}^{29}2^ja_{kj}s_j)$，其中 $a_{kj}$ 代表 $a_k$ 的二进制第 $j$…

根据题意给每个字符串一个统计属性，dfs 即可。由于长度递增无需设置 vis 数组，集合合并优化即可。 ```python import sys,time;t=time.time();a={};c={(0,)*26};d=set();sys.stdin=open('words.txt','r') for i in ra…

经典结论：两组异或和相等则它们再异或为零，即算整体异或和是否为零即可。复杂度 $O(\sum_{i=1}^T N_i)$。 C/C++ 代码 ```c #include int c,n,m,d; int main() { scanf("%d",&c); while(c--) { m=0; scanf("%d",&n);…

翻转只能连接两个连续子段，于是统计每种数字前两长的连续子段的和，乘以其自身求最大值即可。复杂度 $O(n)$。 ```python from collections import*;input();a=defaultdict(list);b=c=0 for i in map(int,input().split()):…

将串按最长连续非递减子串切段，答案是每段内部所有子串和相连段连续子串的统计值。复杂度 $O(n)$。 ```python a=[0];b=0 for i in map(int,input().strip()): if i==b or i==b+1:a[-1]+=1 else:a.append(1) b=i print(…

所有节点左儿子颜色和自己相同，右儿子颜色和自己不同，求节点编号 $2^{n-1}+k-1$ 二进制表达中 $1$ 的数量（即从根节点到目标节点的路径中向右走了几次）的奇偶性即可，偶数为红色，奇数为黑色。复杂度 $O(mn)$。 ```python for i in range(int(input())):a,b=map…

由于每行左移一位，直接取数列 $2,0,2,5$ 的第 $\lfloor\frac{x+y}4\rfloor$ 项即可。 ```c #include unsigned char h,w,x,y,s[4]={50,48,50,53}; int main() { scanf("%hhu%hhu",&h,&w); for(x…

无论前面的位有多少，只要最后一位从 $0$ 到 $9$ 循环，$0$ 到 $4$ 的余数都是积累两次，共产生 $\lfloor\frac{202504}{5}\rfloor=40500$ 个数，最后的 $202500$ 到 $202504$ 中只有 $202501$ 符合，减去不符合条件的 $0$ 得到答案 $4050…