CFR-840(Div.2)解题报告
比赛传送门
C. Another Array Problem
题意：给你一个数组 aaa，每次可以选两个位置 i,j(i
0%
CF553C. Love Triangles题解
发表于
分类于
题解
题目传送门
题意：有一个 nnn 个点的无向完全图，边权为 0/10/10/1，钦定 mmm 条边的边权，求填剩下的边的边权的方案数，满足：不存在一个三元环全为 000 或二 111 一 000。
观察第二条性质。首先显然有，如果 a−b,b−ca-b,b-ca−b,b−c 为 111，则 a−ca-ca−c 为 111，所以 111 的关系具有传递性：只要两个点在同一个 111 的连通块内，这两点之间也必然为 111。于是每个 111 的连通块必为一个边权全为 111 的完全图。于是，可以先处理钦定的边权为 111 的边，用并查集维护，对于一个钦定边权为 000 的边，如果两边连通则无解
ABC-282解题报告
发表于
比赛传送门
C. String Delimiter
题意：有一个包含字母、双引号（保证有偶数个，相邻两个匹配）和逗号的字符串，将在双引号外的逗号改为句号。
维护当前在双引号里还是外，遇到双引号更改即可。
By SSRS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include
using namespace std;
int main(){
int N;
cin >> N;
string S;
cin >> S;
bool c = false;
for (int i = 0;
CFR-838(Div.2)解题报告
比赛传送门
A. Divide and Conquer
题意：给你一个数组，每次操作可以将一个数变为它除以二下取整，求将数组的和变为偶数的最小次数。
显然如果数组本来就是偶数，则为 000，否则一定是选一个数一直除到改变，而其他数不动（动了显然更劣）。于是对于每个数求改变奇偶的最小次数，模拟即可。
By jiangly
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include
u
一些有用的tricks
发表于
分类于
学习笔记
图论
* 边的形式统一的完全图用虚点。
* 边权按端点信息生成的图求最小生成树，考虑 Boruvka 算法。
数学
* 异或比大小考虑 trie 树。
* 质因数分解朴素 O(n)O(\sqrt{n})O(n)；预处理 n\sqrt{n}n 以内的质数（假设有 cntcntcnt 个）后可以做到 O(cnt)≈n10O(cnt)\approx\frac{\sqrt{n}}{10}O(cnt)≈10n；预处理 nnn 以内每个数的最小质因子后可以做到 O(log(n))O(\log(n))O(log(n))。
ABC-281解题报告
发表于
分类于
解题报告
B. Sandwich Number
题意：给你一个字符串，判断是否满足：首先为一个大写英文字符；然后为 666 位数字，组成 [100000,999999][100000,999999][100000,999999] 之间的数（即不能有前导零）；最后为一个大写英文字符。
对照题意模拟即可。实现上可以通过函数来简化重复步骤。
By yokozuna57
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool f(char c){
return 'A'<=c&&c<='Z';
}
bool g(char c){
两道区间DP题目总结
发表于
分类于
题解
CF1132F. Clear the String
题目传送门
题意：有一个字符串，每次可以删除一段连续的相同字母的子串，求删完的最小次数。
做法一
设 f[l][r]f[l][r]f[l][r] 表示 [l,r][l,r][l,r] 删完的最小次数，则显然转移为枚举分两段加起来取最小值。由于可以删除连续一段相同的字母，所以如果左右两端相同，无论分的两段内部如何取，一定可以钦定左边的段将左端点留到最后，右边的段将右端点留到最后（钦定最后删端点答案不变），一起删，所以答案会 −1-1−1。于是转移为 f[l][r]=minkf[l][k]+f[k+1][r]−[sl=sr]f[l][r]
NEERC2009解题报告
B. Business Center
有 mmm 个电梯，每个电梯有两个权值 a,ba,ba,b，初始在第 000 层。你可以选择一个电梯，进行恰好 nnn 次操作，每次要么升高 aaa 要么下降 bbb。要求最终在第一层以上且尽可能低。
对于每个电梯 a,ba,ba,b，考虑进行几次上几次下。由于要求在第一层以上，所以上的层数大于下的层数，即 ax>b(n−x)ax>b(n-x)ax>b(n−x)。解一下不等式即可。
By Waterloo Black
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include
u
NEERC2002解题报告
发表于
分类于
解题报告
比赛传送门
A. Amusing Numbers
题意：定义 nnn 以内 kkk 的排名为，数字大小在 1∼n1\sim n1∼n 的数字中，字典序小于等于 kkk 的数字个数。给定 k,mk,mk,m，求最小的 nnn，使得 nnn 以内 kkk 的排名为 mmm。m,k≤109m,k\le 10^9m,k≤109。无解输出 000。
直接找 nnn 可能不是很好找，于是可以考虑二分答案。对于一个 midmidmid，比较 midmidmid 以内 kkk 的排名与 mmm 的大小关系即可。问题转换为如何找排名。
查找 nnn 以内字典序小于等于 kkk 的数字个数显然可以使用数位
Gym100753D-Carpets题解
发表于
分类于
题解
题目传送门
题意：有一个 H×WH\times WH×W 的地板和 nnn 个矩形地毯，问是否能不重不漏地填满地板。H,W≤100,n≤7H,W\le 100,n\le 7H,W≤100,n≤7。
考虑朴素的搜索，每次考虑最左上角的没填的位置，枚举用哪块地毯覆盖（因为这个格子肯定需要被覆盖，而不可能被更左上的格子覆盖）。先检查是否可以用这块地毯，如果可以用则把这块地毯填上，继续搜索，回溯时撤销操作。
这样虽然可以通过本题，但速度比较慢，考虑剪枝。思考可以发现，大多数情况下面积根本无法凑到恰好 H×WH\times WH×W，所以可以提前枚举用哪些地毯，如果这个地毯集合能凑到恰好 H×WH