其实连按部就班也比想象中难

# C # 题目大意 一排有 NNN 个格子（初始时全部是白色） 有 QQQ 个查询，每个查询给出一个 aia_iai​，你需要 翻转从左数，第 aia_iai​ 个格子的颜色，之后，统计当前所有连续的黑色格子区间的数量 # 数据范围 1≤N,Q≤5×1051 \le N, Q \le 5 \times 10^51≤N,Q≤5×105 # 题解 注意，题目是翻转 如果是涂黑 如果左边右边均没有，那答案就 +1+1+1 如果只有一边有，答案不变 如果两边都有，答案 −1-1−1 如果是涂白 如果左边右边均没有，答案 −1-1−1 如果左边右边都有 答案...

# D # 题目大意 给定 nnn 个点 mmm 条边的有向图，第 iii 条边从结点 AiA_iAi​ 连向结点 BiB_iBi​，权值为 WiW_iWi​ 求，从 1→n1 \to n1→n 的路径中（可以重复走），路径权值异或的最小值 # 数据范围 2≤n≤1032 \le n \le 10^32≤n≤103 0≤m≤1030 \le m \le 10^30≤m≤103 0 \le w_i \le 2^ # 题解 # 错解 这个错解，明显忽略了在 a1⊕...⊕ana_1 \oplus ... \oplus...

# 或 - 最短路 - ABC-408-E # 题目大意 现有一个 nnn 个点 mmm 条边的无向连通图，请你求出，顶点 1→1 \to1→ 顶点 nnn 的路径中，所有边的权值或 OROROR 最小值 可能存在重边 # 数据范围 2≤N≤2×1052 \le N \le 2 \times 10^52≤N≤2×105 N−1≤M≤2×105N - 1 \le M \le 2 \times 10^5N−1≤M≤2×105 0 \le w_i \le 2^ # 题解 此处不另附 DSUDSUDSU...

# B # 题目大意 给定 nnn 个数 a1,...,ana_1,...,a_na1​,...,an​，求最大的非负整数 xxx，xxx 需要满足 ∑i=1n[ai≥x]≥x\sum\limits_{i=1}^{n} [a_i \ge x] \ge xi=1∑n​[ai​≥x]≥x # 数据范围 1≤n≤1001 \le n \le 1001≤n≤100 0≤ai≤1090 \le a_i \le 10^90≤ai​≤109 # 题解 xxx 最大不会超过 nnn，因为是计数问题，最多个数也只能是 nnn，所以倒着枚举...

# D # 题目大意 给你一个长度为 nnn 的，只有 0,10,10,1 构成的字符串 sss，你可以执行以下操作若干次 选择任意一个字符，Si←1−SiS_i \leftarrow 1-S_iSi​←1−Si​ 请问，至少经过多少次操作，字符串的 111 连续或不存在 111 # 数据范围 1≤T≤2×1041 \le T \le 2 \times 10^41≤T≤2×104 1≤∣S∣≤2×1051 \le |S| \le 2 \times 10^51≤∣S∣≤2×105 # 题解 如果最终，是...

# C # 题目大意 你现在有一个空字符串 ttt，给定一个字符串 sss，你可以对 ttt 做任意顺序的任意次的以下两种操作 在 ttt 的末尾加一个 0 循环移位一位（往后移 +1 ） 请问，最少要多少步能使得 ttt 变得和 sss 一样？ # 数据范围 1≤∣S∣≤5×1051 \le |S| \le 5 \times 10^51≤∣S∣≤5×105 # 题解 数据范围到了 5×1055 \times 10^55×105，肯定就不能暴力了 如果 Si>Si−1S_i >...

nnn 个球放入 ddd 个盒子中，一共有多少种放置方案？ # 球可区分 盒子可区分 多球同盒 允许空盒 方案数 约束条件 1 是 是 是 是 dnd^ndn 无 2 是 是 是 否 ∑k=0d((−1)k⋅Cdk⋅(d−k)n)\sum\limits_{k=0}^{d}((-1)^k·C_d^k·(d-k)^n)k=0∑d​((−1)k⋅Cdk​⋅(d−k)n) d≥1d\ge1d≥1 且 n≥dn\ge dn≥d（否则无法满足...

# C # 题目大意 给定一个数列 A=(a1,...,an)A=(a_1, ..., a_n)A=(a1​,...,an​) 求 ∑i≤i<j≤N(ai⋅aj)\sum_{i \le i < j \le N} (a_i·a_j)∑i≤i<j≤N​(ai​⋅aj​) # 数据范围 2≤N≤3×1052 \le N \le 3 \times 10^52≤N≤3×105 1≤Ai≤1041 \le A_i \le 10^41≤Ai​≤104 # 题解 考前缀和，求...

# 卷积 # 一维卷积 连续域函数卷积 g(x)=f(x)∗k(x)=∫−∞+∞f(t)⋅k(x−t)⋅dtg(x)=f(x)*k(x)=\int_{-\infty}^{+\infty}{f(t)·k(x-t)·dt} g(x)=f(x)∗k(x)=∫−∞+∞​f(t)⋅k(x−t)⋅dt 离散函数卷积 g(i)=f(i)∗k(i)=∑lf(l)⋅k(i−l)g(i)=f(i)*k(i)=\sum\limits_{l}f(l)·k(i-l) g(i)=f(i)∗k(i)=l∑​f(l)⋅k(i−l) #...

# B # 题目大意 有两个网格 S,TS, TS,T，每个网格都是 NNN 行 NNN 列 每个单元格都被涂成白 / 黑色，单元格是 . 就是白色，是 # 就是黑色 你可以进行下面两种操作任意次 选中 SSS 中的一个格子，反转颜色 将 SSS 顺时针旋转 90°90°90° 请问至少要多少次操作，才能使 SSS 和 TTT 变成一样的？ # 数据范围 1≤n≤1001 \le n \le 1001≤n≤100 # 题解 考虑四种旋转后，与 TTT 图的差异即可，需要注意的是，这四次旋转需要的 222...