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;
}