1.7k 字 2 分钟

# 或 - 最短路 - 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...
3.9k 字 4 分钟

# 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，所以倒着枚举...
2.2k 字 2 分钟

# 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 # 题解 如果最终，是...
5.6k 字 5 分钟

# 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 >...
6k 字 5 分钟

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（否则无法满足...
3.7k 字 3 分钟

# 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 # 题解 考前缀和，求...
20k 字 18 分钟

# 卷积 # 一维卷积 连续域函数卷积 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) #...
4.1k 字 4 分钟

# 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...
3.8k 字 3 分钟

# A # 题目大意 黑板上有 0→n−10 \to n - 10→n−1 的整数，在一轮游戏中，小 AAA 需要 选取一个 aaa 并擦除 然后小 BBB 选取一个 bbb，满足 a+b≡3(mod4)a+b \equiv 3 \pmod 4a+b≡3(mod4) 并擦除 这个游戏从小 AAA 开始，如果有一方不能操作了，则另一个人赢了，给你 nnn，请问谁能赢？ # 数据范围 1≤n≤1001 \le n \le 1001≤n≤100 # 题解 我们观察有，满足条件的 a b 是 1 2 , 3 4 , 5 6 ... 连续的，而小 BBB...
4.4k 字 4 分钟

写在前面 没抢到名额写个🥚 [补题链接][https://codeforces.com/gym/105901] # A # 题目大意 现在有 nnn 个问题，每个问题的难度是 aia_iai​ 然后有 qqq 个调整，每个调整会给你一个需求 [qi,li,ri][q_i, l_i,r_i][qi​,li​,ri​]，要求把 qiq_iqi​ 问题的难度调整到 [li,ri][l_i, r_i][li​,ri​] 区间，如果不能满足所有需求，则输出 -1 ，能满足则输出最小难度变化代价 # 数据范围 1≤T≤1001 \le T \le...