Codeforces Round #476 (Div. 2) [Thanks, Telegram!] 赛后总结
![Codeforces Round #476 (Div. 2) [Thanks, Telegram!] 赛后总结](https://ksmeow.moe/wp-content/uploads/2018/04/180426c.jpg)
965A Paper Airplanes
题意简述
一张纸可以做s个纸飞机，现在有k个人，每个人要做n个纸飞机，而一包纸有p张，他们想买若干包然后把纸分给每个人让他们做纸飞机，求他们应该买多少包纸才能满足条件。
思路
没什么难度，按照题目的意思求即可。答案是
[eq display=”1″] \lceil \frac{\lceil \frac{n}{s} \rceil k}{p} \rceil [/eq]
打CFR的时候看一眼1A的那种题。
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
int k, n, s, p;
int main() {
scanf("%d%d%d%d", &k, &n, &s, &p);
printf("%d", int(ceil(ceil(double(n) / s) * k / p)));
return 0;
}
965B Battleship
题意简述
给你一个n*n的地图，有的格子可能属于一条船，有的不属于。一条船的长度为k，体现在地图上就是横向或者纵向连续的k个是船的格子。求可能属于的船的数量最多的格子。
数据范围：n 100
思路
枚举每个格子，然后暴力找到它可能属于的船的数量。具体来说，就是上下/左右找一通连通块，注意延伸出去不能超过k-1格不然不能把这个格子包含进去。然后答案就是这个连通块的大小减去k-1。
写了一会，由于当时CFR就写的很丑emm
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <algorithm>
int n, k;
char mmp[105][105];
int ax, ay, ans = -1;
inline int count(int x, int y) {
if(mmp[x][y] == '#') return 0;
int cnt = 0, tcnt = 1, bcnt = 0;
for(int i = x - 1; i >= 1; i--) {
if(mmp[i][y] == '#') break;
tcnt++;
}
if(tcnt > k) tcnt = k; cnt += tcnt; tcnt = 1;
for(int i = x + 1; i <= n; i++) {
if(mmp[i][y] == '#') break;
tcnt++;
}
if(tcnt > k) tcnt = k; cnt += tcnt - 1; tcnt = 1;
bcnt += std::max(cnt - (k - 1), 0); cnt = 0;
for(int i = y - 1; i >= 1; i--) {
if(mmp[x][i] == '#') break;
tcnt++;
}
if(tcnt > k) tcnt = k; cnt += tcnt; tcnt = 1;
for(int i = y + 1; i <= n; i++) {
if(mmp[x][i] == '#') break;
tcnt++;
}
if(tcnt > k) tcnt = k; cnt += tcnt - 1; tcnt = 1;
bcnt += std::max(cnt - (k - 1), 0); cnt = 0;
return bcnt;
}
int main() {
scanf("%d%d%d%d", &n, &k);
for(int i = 1; i <= n; i++) {
scanf("%s", mmp[i] + 1);
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
int cnt = count(i, j);
if(cnt > ans) {
ans = cnt; ax = i; ay = j;
}
}
}
printf("%d %d", ax, ay);
return 0;
}
965C Greedy Arkady
题意简述
k个人想分n块糖。分糖的规则是这样的，先确定每个人每次分到的糖x，先给第一个人x个，然后第二个，一轮给完以后再轮到第一个人，直到剩下的糖数不足x，剩下的糖会直接扔掉。但是有限制每个人最多不能分到糖D次，且x也不能大于M。求第一个人分到糖的最大数目。
数据范围：n: 1e18，M: ≤n，D: 1e3
思路
我们看到D的范围很小，因此我们可以枚举每个人分到的糖的最多次数i。我们可以根据i计算出一个x的范围，而实际上我们肯定想要最大的x，因为第一个人分到糖的数量实际上是xi。这个x很好求：
x = \lfloor \frac{n}{k(i-1)+1} \rfloor
求出x以后看一下超没超M，超了就直接设成M检查x是否能满足i的要求。然后对于x直接计算答案即可。对于一个确定的x，它的答案是xi。
CFR的时候，一没看见剩下的糖扔掉，二没看见D的范围小，而且对数据范围并不敏感，直接导致没想到枚举D。想到了以后应该是很好做的吧。
当时打了个表，发现如果不管剩下的糖扔掉这条，答案在n的两个因数之间是单峰的，写了个找因数+三分找峰，复杂度O(\sqrt{n} + \log^2 n)，直接TLE。
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cmath>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
LL n, k, M, D;
int main() {
n = readint(); k = readint(); M = readint(); D = readint();
LL ans = 0;
for(LL i = 1; i <= D; i++) {
LL lg = log(i - 1) / log(10) + log(k) / log(10); // 会爆LL，log处理一下
if(lg > log(n) / log(10)) continue;
LL x = std::min(M, n / ((i - 1) * k + 1));
if(!x) continue;
LL ri = ceil(n / x / double(k));
if(ri != i) continue;
ans = std::max(ans, x * i);
}
printf("%I64d", (long long) ans);
return 0;
}
965D Single-use Stones
题意简述
河宽w，一只青蛙最多能跳l这么远。给你河中每个位置的石头数，每个石头只能用一次，用完了就沉入水中了，求最多能让多少青蛙过河。
数据范围：w, l: 1e5
思路
最开始想了个网络流的模型，拆点限流石头个数，然后从i向[i+1, i+l]中的每个石头连出边，但是这样的边数是O(n^2)的空间开不下。
其实我们来想一下，S的出边到[1, l]，而[1, l]的出边到[2, l+1]，依次类推，我们可以把这样一个区间内的点合起来看做最大流的限制啊！也就是说，\min_{i=l}^{w-1} \{sum_i - sum_{i-l}\}就是答案。
其实CF官解的解释是这样的：二分答案k，对于确定的k，首先当从近到远第i块石头到第i+k块的距离大于l的时候，k只青蛙是过不去的。因为最左边那只就跳不过去了，所以就可以O(n)验证确定的k。简化这个过程也能得到上面的解法。
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
int w, l, a[100005];
int main() {
w = readint(); l = readint();
for(int i = 1; i < w; i++) {
a[i] = readint() + a[i - 1];
}
int ans = 1e9;
for(int i = l; i < w; i++) {
ans = std::min(ans, a[i] - a[i - l]);
}
printf("%d", ans);
return 0;
}
965E Short Code
题意简述
把n个字符串用它的一个前缀不重复地代表，求最小的代表串长度和。
数据范围：字符串总长: 1e5
思路
如果放在Trie树上看这个问题，就是把一些word标记给提到这个节点的某个父亲的位置，且每个节点只能有一个word标记。考虑一个节点的子树内的word标记全都提前过，现在这个节点上本来就有word标记，那么这个节点的子树的提前也已经完成了，而如果没有word标记，就要从子树中选择一个提前，我们显然应该选择子树中深度较大的那个。逐子树递归完成这个操作，每个子树维护一个可并堆，最后把堆里的元素加个和就完事了。
复杂度O(n \log n)。
代码
用了下pb_ds的可并堆，其实好像普通堆O(n \log n)合并也没事？
// Code by KSkun, 2018/4
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
typedef __gnu_pbds::priority_queue<int, std::less<int>,
__gnu_pbds::pairing_heap_tag> priority_queue;
const int MAXN = 100005;
int ch[MAXN][26], tot = 1;
bool wrd[MAXN];
inline void insert(char *s) {
int p = 1;
for(int i = 0; s[i]; i++) {
int c = s[i] - 'a';
if(!ch[p][c]) ch[p][c] = ++tot;
p = ch[p][c];
}
wrd[p] = true;
}
inline void dfs(int u, priority_queue &q, int dep) {
for(int c = 0; c < 26; c++) {
if(ch[u][c]) {
priority_queue p;
dfs(ch[u][c], p, dep + 1);
q.join(p);
}
}
if(!wrd[u]) q.pop();
q.push(dep);
}
int n;
char s[MAXN];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
scanf("%s", s);
insert(s);
}
int ans = 0;
for(int c = 0; c < 26; c++) {
if(ch[1][c]) {
priority_queue q;
dfs(ch[1][c], q, 1);
while(!q.empty()) {
ans += q.top();
q.pop();
}
}
}
printf("%d", ans);
return 0;
}
