比赛地址：Dashboard – Codeforces Round #495 (Div. 2) – Codeforces
官方题解：Codeforces Round #495 (Div. 2) — Editorial – Codeforces

1004A Sonya and Hotels

题意简述

一维空间坐标轴上有$n$个整点位置修建了酒店，现在想在一个未建酒店的整点位置修一个新酒店，要求新酒店离最近的酒店的距离等于$d$，求新酒店可以选择的坐标数量。
数据范围：$1 \leq 100, 1 \leq d \leq 10^9$

思路

枚举每两个酒店之间的距离，$距离=2d$的时候对答案有1的贡献，$>2d$的时候有2的贡献，首尾各有1的贡献，统计一下就好。
复杂度$O(n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#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();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 105;

int n, d, x[MAXN];

int main() {
    n = readint(); d = readint();
    for(int i = 1; i <= n; i++) {
        x[i] = readint();
    }
    int ans = 2;
    for(int i = 2; i <= n; i++) {
        if(x[i] - x[i - 1] == 2 * d) ans++;
        if(x[i] - x[i - 1] > 2 * d) ans += 2;
    }
    printf("%d", ans);
    return 0;
}

1004B Sonya and Exhibition

题意简述

要放$n$盆花成一排，每个位置有两种选择，有$m$个人参观这些花，他们会参观一个连续区间的花，参观的美丽度定义为区间两种花的个数的乘积，求安排方案使得美丽度之和最大。
数据范围：$1 \leq n, m \leq 10^3$

思路

$$ n^2 > (n+1)(n-1) > (n+2)(n-2) > \cdots $$
因此我们可以直接输出一个类似0101010101010101这样的序列就好了。
复杂度$O(n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#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();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1005;

int n, m, l[MAXN], r[MAXN];

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= m; i++) {
        l[i] = readint(); r[i] = readint();
    }
    LL sum1 = 0, sum2 = 0;
    for(int i = 1; i <= m; i++) {
        int cnt1[2] = {0, 0}, cnt2[2] = {0, 0};
        for(int j = l[i]; j <= r[i]; j++) {
            cnt1[j & 1]++;
            cnt2[(j & 1) ^ 1]++;
        }
        sum1 += 1ll * cnt1[0] * cnt1[1];
        sum2 += 1ll * cnt2[0] * cnt2[1];
    }
    if(sum1 > sum2) {
        fprintf(stderr, "%lld\n", sum1);
        for(int i = 1; i <= n; i++) {
            putchar('0' + (i & 1));
        }
    } else {
        fprintf(stderr, "%lld\n", sum2);
        for(int i = 1; i <= n; i++) {
            putchar('0' + ((i & 1) ^ 1));
        }
    }
    return 0;
}

1004C Sonya and Robots

题意简述

有一个长为$n$的序列，两个机器人从序列的两段开始相向而行，遇到第一个与机器人中存储的数字相同的数字时就在该位置停下，你可以给机器人写入不同的数字，求让它们不相遇的数字对数。
数据范围：$1 \leq n \leq 10^5$

思路

我们从左向右扫这个序列，对于一个之前没有出现过的数字，显然它会与后面的不重复数字产生贡献，那么答案就是这些贡献的和。我们只需要知道一个位置的后面是否还有与这个位置相同的数字，动态地维护后面的不重复数字种数以及前面出现过哪些数字就可以了。
复杂度$O(n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#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();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

int n, a[MAXN], nxt[MAXN], head[MAXN];
bool vis[MAXN];

int main() {
    n = readint();
    int cnt = 0;
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
        if(!vis[a[i]]) {
            vis[a[i]] = true;
            head[a[i]] = i;
            cnt++;
        } else {
            nxt[head[a[i]]] = i;
            head[a[i]] = i;
        }
    }
    memset(vis, 0, sizeof(vis));
    for(int i = 1; i <= n; i++) {
        if(!nxt[i]) {
            cnt--;
        }
        if(!vis[a[i]]) ans += cnt;
        vis[a[i]] = true;
    }
    printf("%lld", ans);
    return 0;
}

1004D Sonya and Matrix

题意简述

有一个矩阵，矩阵中有1个权值为0的格子，而其他格子的权值为到0权格子的曼哈顿距离。现在给你一个长为$t$的序列，是一个包含某一个矩阵里面的所有权值的乱序可重排列。现在你要求出原来矩阵的大小$n \times m$以及0权的位置$(x, y)$。
数据范围：$1 \leq t \leq 10^6$

思路

首先，我们可以用序列统计每个数字出现的次数。在完整的图形中，我们会发现每个数字形成了菱形或者说正方形的形状，如下所示。

          5
        5 4 5
      5 4 3 4 5
    5 4 3 2 3 4 5
  5 4 3 2 1 2 3 4 5
5 4 3 2 1 0 1 2 3 4 5
  5 4 3 2 1 2 3 4 5
    5 4 3 2 3 4 5
      5 4 3 4 5
        5 4 5
          5

我们可以求出序列中的最大数字以及最大的在矩阵中完整地出现了它的菱形的数字，显然，最大数字应该在角上，由于图形的对称性，四个角是等价的，我们暂且让它在左上角$(1, 1)$。
当我们发现矩形的大小并无法让0与最大数共存的时候，显然情况不合法，这种情况的判断，我们可以使用对角线曼哈顿距离（即图形中的最长曼哈顿距离）来判断，即$n+m-2 < mx$时不合法。
另外的不合法情况就是当确定了$n, m, x, y$以后，我们可以计算出最大的整个菱形都包含进来的数字，这个数字是$\min \{ x-1, y-1, n-x, m-y \}$，再把不合法的情况扔掉就好。
剩下的合法情况已经很少了，我们直接暴力$O(t)$地验证就好。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>
#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();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 1000005;

int t, mx, cnt[MAXN], cnt2[MAXN];

inline int border(int n, int m, int x, int y) {
    return std::min(std::min(x - 1, y - 1), std::min(n - x, m - y));
}

inline bool check(int n, int m, int x, int y) {
    memset(cnt2, 0, sizeof(cnt2));
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            cnt2[abs(x - i) + abs(y - j)]++;
        }
    }
    for(int i = 1; i <= t; i++) {
        if(cnt2[i] != cnt[i]) return false;
    }
    return true;
}

int main() {
    t = readint();
    for(int i = 1; i <= t; i++) {
        int a = readint();
        cnt[a]++;
        mx = std::max(mx, a);
    }
    int lim = 0;
    for(int i = 1; i <= t; i++) {
        if(cnt[i] != i * 4) {
            lim = i - 1; break;
        }
    }
    for(int n = 1; n * n <= t; n++) {
        if(t % n) continue;
        int m = t / n;
        if(n + m - 2 < mx) continue;
        for(int j = 1; j <= n; j++) {
            int k = mx - j + 2;
            if(k > m || k < 1) continue;
            if(border(n, m, j, k) != lim) continue;
            if(check(n, m, j, k)) {
                printf("%d %d\n%d %d", n, m, j, k);
                return 0;
            }
        }
    }
    puts("-1");
    return 0;
}

1004E Sonya and Ice Cream

题意简述

给你一棵$n$个点的树，要求从中选出一条不超过$k$个点的路径，使得树的其他点到这条路径的最短距离最大值最小。
数据范围：$1 \leq k \leq n \leq 10^5$

思路

首先，我们可以证明，这条路径在包含树的中心点的时候比较优，中心点定义为到这个点最远的点距离最小的点，显然，这个点应该在直径的中心位置，可以$O(n)$求出来。
答案具有二分性质，所以我们二分答案，接着考虑如何验证。我们可以从中心点开始DFS，每次扩展出去一个点，如果发现一个点的子树中最远的点到它的距离大于答案，则这个点一定要被加入路径。如果一个点有多个儿子一定要被加入路径（中心点特殊考虑，它允许有2个儿子必须被加入路径）则不合法。如果必须被加入路径的点数多于$k$则不合法，判断一下就好。
复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

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();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 100005;

struct Edge {
    int to, w;
};
std::vector<Edge> gra[MAXN];

int n, k, du, dv, ct, fa[MAXN], dis[MAXN];

inline void dfs_dis(int u) {
    for(auto e : gra[u]) {
        if(e.to == fa[u]) continue;
        dis[e.to] = dis[u] + e.w;
        fa[e.to] = u;
        dfs_dis(e.to);
    }
}

inline void diameter() {
    dfs_dis(1);
    for(int i = 1; i <= n; i++) {
        if(dis[i] > dis[du]) du = i;
    }
    dis[du] = 0;
    memset(fa, 0, sizeof(fa));
    dfs_dis(du);
    for(int i = 1; i <= n; i++) {
        if(dis[i] > dis[dv]) dv = i;
    }
}

inline void center() {
    for(int i = dv; i; i = fa[i]) {
        if(std::max(dis[ct], dis[dv] - dis[ct]) > std::max(dis[i], dis[dv] - dis[i])) {
            ct = i;
        }
    }
}

int cnt;
bool success;

inline int dfs_check(int u, int fa, int lim) {
    int res = 0, big = 0;
    for(auto e : gra[u]) {
        if(e.to == fa) continue;
        int dis = dfs_check(e.to, u, lim);
        if(dis != -1 && dis + e.w > lim) {
            cnt++; big++;
        }
        if(dis == -1) big++;
        else res = std::max(res, dis + e.w);
    }
    if((u == ct && big > 2) || (u != ct && big > 1)) {
        success = false;
    }
    if(big || u == ct) {
        cnt++; return -1;
    }
    return res;
}

inline bool check(int mid) {
    cnt = 0; success = true;
    dfs_check(ct, 0, mid);
    return success && cnt <= k;
}

int main() {
    n = readint(); k = readint();
    for(int i = 1, u, v, w; i < n; i++) {
        u = readint(); v = readint(); w = readint();
        gra[u].push_back(Edge {v, w});
        gra[v].push_back(Edge {u, w});
    }
    diameter(); center();
    int l = -1, r = 1e9, mid;
    while(r - l > 1) {
        mid = (l + r) >> 1;
        if(check(mid)) r = mid; else l = mid;
    }
    printf("%d", r);
    return 0;
}

1004F Sonya and Bitwise OR

题意简述

维护一个长为$n$的序列，有$m$次操作，支持两种操作

1. 单点修改
2. 区间询问有多少连续子序列的异或和不小于$x$（对于所有的询问$x$都相同）

数据范围：$1 \leq n, m \leq 10^5$

思路

咕咕咕。

代码

咕咕咕。