Codeforces Round 509 题解

发表于 2018-09-17 更新于 2018-10-07 分类于 Codeforces 阅读次数：

A Heist

排序得到左右边界，即为原编号的左右边界，减去序列的长度即可。

B Buying a TV Set

求满足 $x_0 \le a, y_0 \le b$ 且 $\frac{x_0}{y_0}=\frac{x}{y}$ 的 $(x_0, y_0)$ 方案数，将 $\frac{x}{y}$ 约分，答案为 $max(\frac{a}{x}, \frac{b}{y})$。

C Coffee Break

自闭题T^T。

维护一个 set 存放所有咖啡时间点和在原序列中的下标，每次选 set 的第一个元素 $x$ 放在某一天的第一个，之后二分第一个大于等于 $x+d+1$ 的元素放在同一天并将他从 set 中删除，直到没有元素可以放在这一天。

D Glider

注意到这样一个结论：如果我们从 $x+1$ 处下落，当 $x+1$ 位于上升气流外，假如 $x+1$ 处下落经过的气流和 $x$ 处经过的气流相同，那么他们滑翔的距离也相同，但是对于x轴的一个位置，$x+1$ 下落总比 $x$ 下落高一个单位，因此有可能经过 $x$ 未经过的气流，所以 $ans(x+1) \ge ans(x)$ ；同样的，如果 $x+1$ 位于上升气流内，$ans(x+1) \le ans(x)$。因此可以得出，最长距离一定会在某个上升气流的左端点出取到。

考虑枚举每个左端点的答案，如果直接计算显然这是 $O(n^2)$ 。

我们还发现，高度下降只会发生在上升气流之间，落地前必定高度下降 $h$ ，在上升气流之间水平移动 $h$ ，加上在经过的所有上升气流的长度和。因此，预处理上升气流长度的后缀和，上升气流之间距离的后缀和。

假设枚举到第 $i$ 个位置，如果当前高度大于当前间隔后缀和，那么表示可以滑翔到最后一个上升气流之后，那么答案就是 $len(i) + h$；如果当前高度小于等于当前间隔后缀和，我们需要找到从 $i$ 开始多少个连续间隔距离加起来大于等于 $h$，也就是后缀和小于等于 $h-delta(i)$，因为是后缀和所以满足单调性，二分即可。

时间复杂度 $O(n+n\log n)$。

阅读全文 »

Dinic算法

发表于 2018-09-16 更新于 2019-03-20 分类于图论，网络流阅读次数：

struct Edge {
    int from, to; ll cap, flow;
    Edge(int u, int v, ll c, ll f): from(u), to(v), cap(c), flow(f) {}
};

struct Dinic {
    int n, m, s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int dep[maxn], cur[maxn];
    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; i++) G[i].clear();
        edges.clear();
    }
    void adde(int from, int to, ll cap) {
        edges.emplace_back(from, to, cap, 0);
        edges.emplace_back(to, from, 0, 0);
        m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
    bool bfs() {
        ms(vis, 0); ms(dep, 0);
        queue<int> q; q.push(s);
        dep[s] = 0; vis[s] = 1;
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = 0; i < G[x].size(); i++) {
                Edge& e = edges[G[x][i]];
                if (!vis[e.to] && e.cap > e.flow) {
                    vis[e.to] = 1;
                    dep[e.to] = dep[x] + 1;
                    q.push(e.to);
                }
            }
        }
        return vis[t];
    }
    ll dfs(int x, ll a) {
        if (x == t || a == 0) return a;
        ll flow = 0, f;
        for (int& i = cur[x]; i < G[x].size(); i++) { 
            //从上次考虑的弧
            Edge& e = edges[G[x][i]];
            if (dep[x] + 1 == dep[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
                e.flow += f;
                edges[G[x][i] ^ 1].flow -= f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
    ll get(int s, int t) {
        this->s = s, this->t = t;
        ll flow = 0;
        while (bfs()) {
            ms(cur, 0);
            flow += dfs(s, inf);
        }
        return flow;
    }
} f;

阅读全文 »

Codeforces Manthan18 题解

发表于 2018-09-04 更新于 2018-10-07 分类于 Codeforces 阅读次数：

A Packets

将n枚硬币分成几块，要求能够每次拿出几块组成任意1到n的整数，块数最小。

考虑多重背包的二进制优化，计算n的二进制位数即可。

B Reach Median

给一个序列，每次对一个数加1或减1，求使得中位数等于x的最小操作数。

将原序列排序，二分找到第一个大于x的位置，如果在中位数后则这一部分全部加成中位数，反之亦然。

C Equalize

给两个01串，对第一个串操作，交换两个位置，花费是下标之差的绝对值，翻转一个位置，花费是1。

显然除非两个错误位置时相邻的不同数，否则都使用翻转操作。

将原序列处理成一个012序列，0表示位置正确，12表示错误，1表示错位的是0，2表示错位的是1。

第一遍扫一下这个序列，把相邻的12取出来，第二遍扫一下这个序列加上剩余的12个数。

D Valid BFS?

给一棵树，判断给的序列是否为合法的BFS序列。

合法BFS序列第一个一定是1，然后直接遍历给定的序列。

记录一下每次遍历的一个点时，他的子节点的位置应该在哪。

使用set对比真正的子节点和序列中的子节点。

更新子节点位置，也就是加上当前点的子节点个数。

E Trips

n个人，m天，每天加一条边，询问一次，当天加边之后，在图中选取一个子图，这些点度数都大于k，输出这个子图的最大大小。

先考虑一个静态的问题，m条边全部给定，那么考虑迭代，直到图上剩余点度数都大于等于k，每次迭代将所有度数小于k的点删除，连接他的边也删除。

优化一下迭代过程，考虑维护一个队列，记录所有度数小于k的点，遍历这个队列，每次遍历到一个点时进行删点和删边，如果使得一个点度数恰好小于k就入队（防止重复入队）。

回到原题，可以反过来处理，变加边为删边，建好整个图之后，每次当天加的边没有删除，就把他删除。

算法复杂度来源于第一次遍历原图。

阅读全文 »

HDu6438 Buy and Resell

发表于 2018-08-27 更新于 2018-09-18 分类于题解阅读次数：

原题：codeforces867E

不考虑每天实际是否持有股票。

使用一个最小堆，维护每天可能会买进的股票价格，扫一遍整个序列，如果当前的股票价格大于堆顶的价格，那么我们可以买入这个股票，相当于更新最终答案ans，弹出堆顶。

再将新的价格入两次堆，第一次入堆代表卖出的是当前可以买入的，如果后面在购买这支股票，考虑股价之间的差值，使当前股票变为一个中转站，并不会影响最终答案。第二次入堆代表的是购买当前的股票，前一次入堆实际上只是一次中转，并没有实际在此处购买。

两次入堆之间不会相互影响，如果当前入堆的两个后来被卖出了，那么第一次相当于在这个位置做了中转，第二次又买了这个位置则是忽略了那次中转进行再次卖出。

对于记录操作的次数，对于每次买进操作都会对应一个卖出操作，为节点增加一个维度，表示是否是中转站，对于每次真实的买进都会更新操作数量。

阅读全文 »

高精度整数和整数乘法

发表于 2018-08-22 更新于 2019-03-05 分类于乱七八糟阅读次数：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 100000 + 5;

int n;

int a[maxn], cnt = 1;
void mul(int k){
    int g = 0, tmp = 0;
    for (int j = 0; j < cnt; j++){
        tmp = a[j] * k + g;
        a[j] = tmp % 10000;
        g = tmp / 10000;
    }
    while (g){
        a[cnt++] = g % 10000;
        g /= 10000;
    }
}
void print(){
    printf("%d", a[cnt - 1]);
    for (int i = cnt - 2; i >= 0; i--){
        printf("%04d", a[i]);
    }
    puts("");
}

int main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d", &n);
        a[0] = 1; cnt = 1; // init
        for (int i = 1; i <= n; i++){
            mul(2);
        }
        print();
    }
    return 0;
}

最远曼哈顿距离

发表于 2018-08-22 更新于 2018-09-18 分类于乱七八糟阅读次数：

HDu6435 CSGO

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const ll inf = 1ll << 62;
const int maxn = 100000 + 5;

int n, m, k;
ll x[maxn][5], y[maxn][5], a[maxn], b[maxn];

int main(){
    int T; scanf("%d", &T);
    while (T--){
        scanf("%d%d%d", &n, &m, &k);
        int ss = 1 << k;
        for (int i = 0; i < n; i++){
            scanf("%lld", &a[i]);
            for (int j = 0; j < k; j++){
                scanf("%lld", &x[i][j]);
            }
        }
        for (int i = 0; i < m; i++){
            scanf("%lld", &b[i]);
            for (int j = 0; j < k; j++){
                scanf("%lld", &y[i][j]);
            }
        }

        ll ans = -inf;
        for (int s = 0; s < ss; s++){
            ll ma = -inf, mi = inf;
            for (int i = 0; i < n; i++){
                ll t = 0;
                for (int j = 0; j < k; j++){
                    if (s & (1 << j)) t += x[i][j];
                    else t -= x[i][j];
                }
                ma = max(1ll * a[i] + t, ma);
            }
            for (int i = 0; i < m; i++){
                ll t = 0;
                for (int j = 0; j < k; j++){
                    if (s & (1 << j)) t += y[i][j];
                    else t -= y[i][j];
                }
                mi = min(-1ll * b[i] + t, mi);
            }
            ans = max(ans, ma - mi);
        }
        printf("%lld\n", ans);
    }
    return 0;
}

HDu6430 TeaTree 题解

发表于 2018-08-22 更新于 2019-03-05 分类于题解阅读次数：

维护一串线段树 + 线段树合并。

首先，注意到小于1e5的整数最多只有100多个因子。

那么我们先预处理小于1e5的所有整数的因子。

对于每个输入的权值，将他的所有因子插入到第i颗线段树上，线段树本身里面没有维护任何值，只是维护了左右儿子的存在性。

之后，我们从后往前扫描整个数组，因为从后面开始的由于输入格式一定是叶子结点，对于每个节点将以他为根的线段树合并到父亲节点上。

合并时，将当前父节点的答案更新为最大值。

合并的意义在于，以他为lca的节点的所有因子合并在一起，并找到最大相同因子。

阅读全文 »

HDu6393 Traffic Network in Numazu 题解

发表于 2018-08-21 更新于 2018-09-18 分类于题解阅读次数：

题目给的是一个n条边的连通图，容易知道他是一个基环树，断掉基环树的一条边。

考虑树链剖分维护路径的权值和，每次询问拆成三次，分别是直接到达和两种通过环边到达的路径距离最小值即为答案。

注意：树链剖分的写法和边的记录，边权和点权的转化（边权转化为子节点的点权）。

阅读全文 »

组合数预处理

发表于 2018-08-19 更新于 2019-03-05 分类于组合数学阅读次数：

int f[maxn], inv[maxn], finv[maxn];
void init(){
    inv[1] = 1;
    for (int i = 2; i < maxn; i++) inv[i] = (mod - mod / i) * 1ll * inv[mod % i] % mod;
    f[0] = finv[0] = 1; 
    for (int i = 1; i < maxn; i++) {
        f[i] = f[i - 1] * 1ll * i % mod;
        finv[i] = finv[i - 1] * 1ll * inv[i] % mod;
    }
}
int C(int n, int m){
    if (m < 0 || m > n) return 0;
    return f[n] * 1ll * finv[n - m] % mod * finv[m] % mod;
}

Prim

发表于 2018-08-18 分类于图论阅读次数：

struct edge{
    int to, nxt, d;
    bool operator<(const edge& b)const {
        return d > b.d;
    }
}f[20 * maxn];
int head[maxn], tot = 0;
void add(int x, int y, int d){
    f[++tot].to = y; f[tot].d = d; f[tot].nxt = head[x]; head[x] = tot;
}

int p, r, vis[maxn];
int prim(){
    ms(vis, 0); vis[1] = 1;
    priority_queue<edge> q;
    int ans = 0;
    for (int i = head[1]; i; i = f[i].nxt){
        q.push(f[i]);
    }
    while (!q.empty()){
        edge t = q.top(); q.pop();
        if (vis[t.to]) continue;
        vis[t.to] = 1;
        ans += t.d;
        for (int i = head[t.to]; i; i = f[i].nxt){
            q.push(f[i]);
        }
    }
    return ans;
}