部分题解集合
__vector__ · · 个人记录
CF1353E
- Difficulty:
\color{purple}\text{1900} - sol1:
可以枚举最后一个灯的所在位置,进行 dp。
设dp_i 表示最后一个灯在位置i ,且只考虑前i 个位置的最优解。
显然,对于转移,一种情况是前面全是0 ,只有这一位是1 ;另一种情况,是位置i-k 为1 ,i-k+1 到i-1 都是0 ,从dp_{i-k} 转移过来。
复杂度O(n)
提交记录 - sol2
这些灯可以存在的位置模k 同余。
所以可以用O(k) 的时间枚举灯可选的位置。
由题目可知,除了选出了的一些相邻的模k 同余的位置是1 ,其余位置都得是0 。
也就是说选出了一个位置使其为1 ,如果原来就是1 ,可以少改变一次,如果原来是0 ,就要多变一次。
现在就是选出一些连续的模k 同余的位置使得最终改变的次数最小。
成经典贪心题了。
复杂度O(k \cdot \frac{n}{k}) = O(n)
提交记录
然后发现和第一份做法都是 93ms,复杂度一样常数也一样。。。。。
CF1403C
- Difficulty:
\color{black}\text{3}\color{red}\text{200} - sol:
CF3A
- Difficulty:
\color{gray}\text{1000} - sol:
本质上就是可以一次操作中可以改变单个坐标一次,也可以横纵坐标一起改一次。
贪心是很显然的。
提交记录
CF1396C
- Difficulty:
\color{orange}\text{2300} - sol:
设dp_i 表示解决完前i 关的最小代价。
对于每一关,显然都分两种情况:一次解决所有怪;解决所有的小怪后,逃跑,再回来打死 Boss。
想一下,移动路线必然是从1 到n (最后一步可能还有个n 到n-1 )。
对于一次解决所有怪(即不逃跑再回来打)的情况,从dp_{i-1} 转移。
对于需要逃跑一次的情况,最优的方法是移动到相邻的关卡,相邻两关互相横跳再继续往后走(总体上是向后走的,一些关卡因为要打两遍,为了减少时间消耗只往前走一个关卡,然后回来继续向后走)。
所以这种情况也从dp_{i-1} 转移。
注意走到了i-1 再回来,i-1 和i 这样下来都能打两遍,也就是说还可以从dp_{i-2} 转移过来,计算i-1 和i 打两遍的代价。
总体说完了,一些细节要处理。
注意如果是n-1 和n 互相横跳的话,由于不存在没访问过的点了,n 可以直接解决所有怪然后跳到n-1 ,不再回去,这个要特判。
复杂度O(n) 。
提交记录
ABC176F
- Difficulty:
\color{red}\text{2912} - sol:
ZOJ2113
- Difficulty: Unknown
- sol:
CF498E
- Difficulty:
\color{red}\text{2700} - hint: 矩阵乘法
- sol:
ABC144F
- Difficulty:
\color{orange}\text{2189} - sol:
CF8E
- Difficulty:
\color{red}\text{2600} - sol:
CF1140E
- Difficulty:
\color{orange}\text{2200} - sol:
显然只需要分别计算每段连续-1 的方案数,然后乘起来就行了。
进行一些模拟发现,每段连续-1 的方案数和左右两边的值没有关系,有关系的是左右两边的值是否相等。
可以 dp 预处理长度为i 的连续-1 段的方案数。$dp_{i,1}$ 表示长度为 $i$ 且左右两边的定值相等的 $-1$ 连续段。 把 dp 状态对应的图画出来(如 $dp_{i,0}$ 对应 $a,-1,-1,\cdots,-1,b$),就能列出转移方程,即: $dp_{i,1} = dp_{i-1,0} \cdot (k-1) dp_{i,0} = dp_{i-1,0} \cdot (k-2) + dp_{i-1,1} 复杂度
O(n) 。
提交记录
CF1782E
- Difficulty:
\color{orange}\text{2300} - sol:
vjudge Kattis-tetris
- Difficulty: unknown
- sol:
CF1699E
- Difficulty:
\color{red}\text{2600} - sol:
acmicpc.net 12610
- Difficulty: unknown
- translation:
题意:
一年有N 天,其中有T 场比赛。
每一场比赛分为很多轮,且每一轮都分布在比赛开始后的第\cdots (不知道)天。
这些比赛的开始时间随机分布在一年中的一些天。
设一年中一天同时有S 轮,那么这一天所带来的快乐值贡献为S^2 。
求这一年快乐值期望总和(如果某些轮到了下一年,不算)
输入格式:
第一行有一个整数C ,代表有C 组数据。
每组数据第一行是两个整数N,T 。
接下来T 行,第i 行描述第i 场比赛。
每行第一个整数m ,代表这场比赛有m 轮,接下来是d_2,d_3,d_4,\cdots,d_m ,d_i 代表第i 轮在比赛开始之后的第d_i 天进行(第一轮都是在比赛开始的第一天进行,所以没给出)
输出格式:
每组数据输出一行,每行输出一个最简形式的带分数,代表答案(具体看原文)。 - sol:
POJ3623
- Difficulty:unknown
- hint: 贪心利用后缀数组优化
- sol:
CF295D
- Difficulty:
\color{red}\text{2400} - sol:
CF533D
- Difficulty:
\color{black}\text{3}\color{red}\text{000} - sol:
CF1418D
- Difficulty:
\color{orange}\text{2100} - sol:
首先,如果点数小于等于2 ,不用进行操作。
否则,画图可知,答案为最大坐标减最小坐标,再减去(相邻两个点位置差的最大值)。
加上了括号方便断句。
最大坐标和最小坐标用 set 维护就行了,接下来要想的是如何维护相邻两个点位置差的最大值。 - sol.1
用 multiset 维护相邻两个点位置差的最大值。
考虑插入删除操作的影响到底是什么。
对于插入,设插入在位置x ,x 左边最近的点为l ,x 右边最近的点为r ,相当于删除区间[l,r] 的影响,加入区间[l,x],[x,r] 的影响。那只需要在 multiset 里面删掉一个r-l ,加入一个x-l 和一个r-x 。
对于删除,和插入差不多,只不过反过来了。
一个技巧:如果不想分类讨论,可以先插入两个点,分别是+ \infty 和- \infty 。
复杂度O((n+q) \log n) 。
提交记录 - sol.2
用线段树维护相邻两个点位置差的最大值。合并区间的时候,就是左子区间的答案,右子区间的答案,和(右子区间最靠左的点的坐标)减去(左子区间最靠右的点的坐标) 取 max 作为当前区间的答案。 所以线段树需要维护三个值,即当前区间答案,当前区间最靠左的点的坐标,当前区间最靠右的点的坐标。 复杂度 $O((n+q) \log n)$。 [提交记录](https://codeforces.com/contest/1418/submission/189812049)
Luogu P4066
- Difficulty:
\color{purple}\text{省选/NOI} - sol:
CF1520G
- Difficulty:
\color{orange}\text{2200} - sol:
一定只使用一次传送门。
证明:设使用两次或以上的传送门能达最优效果,第一次使用传送门的起点为s ,最后一次使用传送门的终点为t ,显然直接从s 到t 更优。
现在分两种情况统计答案,第一种是不使用传送门,第二种使用一次传送门。
第一种很简单,第二种也只需要找出走的距离和跳的代价总和最小的两个点就行了。
复杂度O(nm) 。
我不知道开了 Ofast 为啥还跑这么慢,提交记录。
POJ1151
- Difficulty: unknown
- sol:
CF845E
- Difficulty:
\color{red}\text{2400} - sol:
二分答案,然后离散化所有矩形,看空隙之间距离就行了。
离散化的时候要把矩阵四个顶点旁边的点也加入离散化,否则空隙可能会被离散化凭空消失掉。
Codeforces 提交记录
这样复杂度O(k^2 log_{n}) ,是最劣解。
为了优化复杂度,可以采用扫描线。
扫描线题解CF1635F
- Difficulty:
\color{red}\text{2800} - sol:
CF1284D
- Difficulty:
\color{orange}\text{2100} - sol:
本质上是问是否不存在两个会议,使得在一个会议场不发生冲突,另一个发生冲突。
一个简单的套路就是对每个会议分配一个随机权值,然后对每个会议,在两个会场分别记录与其不发生冲突的会议的权值的异或和,看两个会场所得结果是否一样就行了。
计算不发生冲突的会议的权值的异或和,前后缀异或和预处理就行了。
这样是复杂度是 O(值域) 的,过不去。
考虑实际上只关心区间端点的相对大小,可以离散化。
复杂度是离散化的O(n \log n) 。
提交记录
CF1132F
- Difficulty:
\color{purple}\text{2000} - sol:
我不会比洛谷题解说得清楚。acmicpc8081
- Difficulty: unknown
- sol:
CF ACM sguru442
- Difficulty: unknown
- sol:
CF482C
- Difficulty:
\color{red}\text{2600} - sol:
https://coursera.cs.princeton.edu/algs4/assignments/baseball/specification.php
- Difficulty: unknown
- sol:
UVA1086
- Difficulty: unknown
- sol:
ABC210F
- Difficulty:
\color{orange}\text{2632} - sol:
HDU-3062
- Difficulty: unknown
- sol:
POJ-3281
- Difficulty: unknown
- sol:
POJ-1149
- Difficulty: unknown
- sol:
POJ-2391
- Difficulty: unknown
- sol:
CF1009G
- Difficulty:
\color{red}\text{2400} - sol:
贪心思想。
从前到后枚举每一位的字母。
优先保证前面的小。
当一位枚举了一个字母之后,可以通过网络流判断后面位是否存在合法方案。
关于网络流:
搞成二分图的形式,左部点是位置,右部点是6 个字母。
右部点向超级汇点连权值为该点在原串中出现次数的边。
当然这不是真正的二分图,可以这样转化成二分图:把每种字母拆成该字母在原串中出现次数个点。
然后枚举右部点6 个字母的子集,hall 定理判定即可。
提交记录
ARC076F
- Difficulty:
\color{red}\text{2819} - sol:
只考虑一个段点限制,然后贪心得计算右端点。CF808F
- Difficulty:
\color{red}\text{2400} - sol:
二分等级。
质数除了2 都是一奇一偶组成的,而2 = 1+1 ,也就是说只能有一个1 。
把1 处理掉之后形成了一个以奇偶分类的二分图,超级源点向左部点连权值为能量的边,右部点向超级汇点连权值为能量的边,然后求最小割。
CF 提交记录
loj3379 【CSP-S2020 儒略日】
- Difficulty:
\color{green}\text{普及+/提高} - sol:
CF Gym100722
这个 gym 比较特殊,可以查看他人代码,只有看数据需要 Coach Mode。
在 UVA/SPOJ/BZOJ 有原题。 - Difficulty: unknown
- B:
把集合编上号,模拟。 - D:
最小斯坦纳树。 - E:
排序,然后 dp。