Codeforces Round 495 (Div. 2)

还行吧，但我实在太菜了，水题都不会做

A

Description

数轴上 $n$ 个点，求离最近的点的距离恰好为 $d$ 的点的数目。

Solution

扫一遍，我直接用 set 去重（）

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 110;

long long a[maxn], n, d;

int main()
{
    cin >> n >> d;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    std::set<long long> S;
    a[0] = -5e9, a[n + 1] = 5e9;
    for (int i = 1; i <= n; i++)
    {
        int nxt = a[i] + d;
        if (a[i + 1] - nxt >= d)
            S.insert(nxt);
        nxt = a[i] - d;
        if (nxt - a[i - 1] >= d)
            S.insert(nxt);
    }
    cout << S.size() << endl;
}

B

Description

一个长度为 $n$ 的 $01$ 串，给出 $m$ 个区间，每个区间权值是区间里 $1$ 的数目乘 $0$ 的数目。输出总权值最大的串。

Solution

和同近积大，直接 $0$ 和 $1$ 交替输出就行。

Code

n, m = map(int, input().split())

for i in range(n):
    if i % 2 == 0:
        print(0, end='')
    else:
        print(1, end='')

C

Description

给你 $n$ 个数，从每一个数起向后找一个数，这两个数组成一个数对，求一共有多少个数对。（去掉重复的）

Solution

一个数最优答案肯定在最左面，我们开个桶然后倒着更新答案即可。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;

int a[maxn], n, b[maxn], ans[maxn];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    int sum = 0;
    for (int i = n; i >= 1; i--)
    {
        ans[a[i]] = sum;
        sum -= b[a[i]];
        b[a[i]] = 1, sum++;
    }
    long long res = 0;
    for (int i = 1; i <= 1e5; i++)
        res += ans[i];
    cout << res << endl;    
}

D

Description

定义一种矩阵是菱形矩阵，其大小是 $n\times m$；满足以下条件：有且只有一个格子的值是 $0$，其他格子的值是到值为 $0$ 的格子的曼哈顿距离。

给出 $t$ 个数，问这些数能不能构造出一个菱形矩阵。如果可以，输出其 $n,m$，以及值为 $0$ 的格子的坐标。

$t\leq10^6$。

Solution

首先发现矩阵是可以旋转的，这肯定不影响。

如果矩阵无限大，那每个数的数量是 $4\times n$。

手玩一下样例可以发现第一个不符合上面要求的数（即出到矩阵外了）一定是值为 $0$ 的数的横坐标或纵坐标。

这样我们就确定了 $x$。

证明不写了，懒，挺显然的。

我们可以枚举 $n$，同时也就确定了 $m$。想一想怎么确定 $y$——找找奇怪的性质。

发现最大的数一定在一个角上，那随便算一下就知道 $y=n+m-mx$，$mx$ 是给出的最大的数。

发现我们现在时间复杂度还很充裕，且已经知道了 $x,y,n,m$，只需要 check 一下，那怎么 check 呢？当然是暴力了！（）（）（）

时间复杂度 $O(t)$ 乘上 $t$ 的因数个数，这玩意显然能过。（因为很难跑满）

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <cmath>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e6 + 10;

int cnt[maxn], n, t, m, x, y, mx, tot[maxn];

bool check(int n, int m, int x, int y)
{
    for (int i = 0; i <= mx + 5; i++)
        tot[i] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            tot[abs(i - x) + abs(j - y)]++;
    for (int i = 0; i <= mx; i++)
        if (cnt[i] != tot[i])
            return false;
    return true;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> t;
    for (int i = 0, p; i < t; i++)
        cin >> p, cnt[p]++, mx = std::max(mx, p);
    if (cnt[0] != 1)
    {
        cout << -1 << endl;
        return 0;
    }
    for (int i = 1; i <= t; i++)
        if (cnt[i] != i * 4)
        {
            x = i;
            break;
        }
    for (n = 1; n <= t; n++)
    {
        if (t % n)
            continue;
        m = t / n;
        y = m + n - x - mx;
        if (y > 0 && check(n, m, x, y))
        {
            cout << n << " " << m << endl << x << " " << y << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

E

Description

给出一个 $n$ 个结点的带权树和 $k$，找出一条点数不大于 $k$ 的路径，使得路径外的点到路径的距离的最大值最小。求这个最小的最大值。$n\leq10^5$。

Solution

和树网的核一样。甚至更简单

树上路径、最小、最大，去想一想直径。

能证明这条路径一定在任意一条直径上。

于是对于一条路径分两种情况。到路径距离最大的点可能是直径的两个段点之一，也可能在路径上某个点的子树内。

对前者直接双指针即可，后者搜一遍就行。

时间复杂度 $O(n)$。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;

const int maxn = 1e5 + 10;

struct edge
{
    int y, w;
};
std::vector<edge> e[maxn];
inline void add(int x, int y, int w) { e[x].push_back({y, w}), e[y].push_back({x, w}); }

int n, k;
int dis[maxn], father[maxn], ind[maxn], dep[maxn];

void dfs(int x, int fa)
{
    father[x] = fa, dep[x] = dep[fa] + 1;
    for (auto k : e[x])
    {
        if (k.y == fa || ind[k.y])
            continue;
        int v = k.y;
        dis[v] = dis[x] + k.w;
        dfs(v, x);
    }
}

int find_root()
{
    int res = 0;
    for (int i = 1; i <= n; i++)
        if (dis[i] > dis[res])
            res = i;
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> k;
    for (int i = 1, x, w, y; i < n; i++)
        cin >> x >> y >> w, add(x, y, w);
    dfs(1, 0);
    int root = find_root();
    dis[root] = 0;  
    dfs(root, 0);
    root = find_root();

    int ans = 1 << 30;
    if (n == 1)
    {
        puts("0");
        return 0;
    }
    for (int i = root, j = root; i; i = father[i])
    {
        while (father[j] && dep[i] - dep[j] < k - 1)
            j = father[j];
        ans = std::min(ans, std::max(dis[j], dis[root] - dis[i]));
    }
    for (int p = root; p; p = father[p])
        ind[p] = 1, dis[p] = 0;
    for (int p = root; p; p = father[p])
        dfs(p, father[p]);
    for (int i = 1; i <= n; i++)
        ans = std::max(ans, dis[i]);
    cout << ans << endl;
}

F

Description

有一个长度为 $n$ 的序列，有两种操作。

操作一：将 $a_i$ 修改为 $y$；
操作二：给出 $l,r$，求 $[l,r]$ 内有几个子区间内所有数按位或起来的结果大于等于 $X$（$X$ 在题目一开始给出，为定值）。

$n,m\leq10^5$。

Solution

难，我看了题解。

先考虑如果只有一次询问怎么办。

能（能吗？）想到一个分治算法：把 $[l,r]$ 的询问拆成 $[l,mid],[mid+1,r]$，求出解，然后合并这两个区间。

具体怎么得出大区间的解呢？我们联想区间最长连续子段和的做法，求出每个区间的前缀或和后缀或。

这样我们可以用双指针得到两个区间合并后的解。

单点修改，区间查询，显然我们需要线段树来维护这个东西。

那怎么把上面这个做法推广到线段树上呢？好像直接做不太行，我们显然需要看一看或运算的性质。

一个数或另一个数之后最少只变了 $1$ 位，且不会变回去，也就是说每个区间前缀/后缀或应该是分成至多 $\log a_i$ 段的，我们用 vector 维护这个值，就能做到 $O(\log a_i)$ 合并了。

那我们用线段树维护，把得到的这 $\log n$ 个区间依次合并起来就行。

这时候发现时间复杂度是 $O(m\log n\log a_i)$。

后来我双指针写挂了，一怒之下把双指针换成了暴力合并，复杂度是 $O(m\log n\log^2a_i)$，也能轻松通过。

注意位运算的优先级。

Code

建议把所有函数规划好再写，然后想一些简单的方法来简化代码。

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::cerr;

namespace IO
{
    const int mxsiz = 1 << 20;
    char inbuf[mxsiz], *p1, *p2;
    char outbuf[mxsiz], *op = outbuf;
    struct endio
    {
        endio(){};
        ~endio() { fwrite(outbuf, 1, op - outbuf, stdout); }
    } useless_var;
    inline char gc() { return p1 == p2 && (p2 = (p1 = inbuf) + fread(inbuf, 1, mxsiz, stdin), p1 == p2) ? EOF : *p1++; }
#define isdigit(x) (x >= '0' && x <= '9') // 防止忘记打 <cctype> 头文件
    inline int read()
    {
        int x = 0, f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        return x * f;
    }
    template <typename T>
    inline void read(T &x)
    {
        x = 0;
        int f = 1;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-')
                f = -1;
        for (; isdigit(ch); ch = gc())
            x = x * 10 + ch - '0';
        x *= f;
    }
#undef isdigit
    inline bool ischar(char x)
    {
        return x >= 'A' && x <= 'z';
    }
    inline char readchar()
    {
        char ch = gc();
        while (!ischar(ch))
            ch = gc();
        return ch;
    }
    inline void push(char ch)
    {
        if (op - outbuf == mxsiz)
            fwrite(outbuf, 1, mxsiz, stdout), op = outbuf;
        *op++ = ch;
    }
    template <typename T>
    inline void work_wt(T x)
    {
        if (x > 9)
            work_wt(x / 10);
        push(x % 10 + '0');
    }
    template <typename T>
    inline void write(T x)
    {
        if (x < 0)
            x = -x, push('-');
        work_wt(x);
    }
    inline void writestr(char *s)
    {
        int n = strlen(s);
        for (int i = 0; i < n; i++)
            push(s[i]);
    }
    inline void endln() { push('\n'); }
    inline void space() { push(' '); }
    template <typename T>
    inline void writeln(T x) { write(x), endln(); }
}
using namespace IO;

const int maxn = 1e5 + 10;
typedef long long ll;

int n, X, m;
int a[maxn];

struct seg
{
    int val, len;
    void p() { write(val), space(), write(len), space(), endln(); }
};

struct node
{
    std::vector<seg> l, r;
    ll ans;
    void p()
    {
        writestr("l :\n");
        for (auto k : l)
            k.p();
        writestr("r :\n");
        for (auto k : r)
            k.p();
        writeln(ans);
    }
} t[maxn * 4];
inline int ls(int x) { return x * 2; }
inline int rs(int x) { return x * 2 + 1; }

node merge(const node &ls, const node &rs)
{
    node k;
    k.l = ls.l;
    for (auto p : rs.l)
    {
        if ((k.l.back().val | p.val) == k.l.back().val)
            k.l.back().len += p.len;
        else
            k.l.push_back({k.l.back().val | p.val, p.len});
    }
    k.r = rs.r;
    for (auto p : ls.r)
    {
        if ((k.r.back().val | p.val) == k.r.back().val)
        {
            k.r.back().len += p.len;
        }
        else
            k.r.push_back({k.r.back().val | p.val, p.len});
    }
    k.ans = ls.ans + rs.ans;

// 原先的双指针
    /*
    for (int i = 0, j = (int)rs.l.size() - 1; i < (int)ls.r.size(); i++)
    {
        while (j && ls.r[i].val | rs.l[j].val >= X)
            j--;
        if (j >= 0)
            k.ans += rs.l[j].sum * ls.r[i].len;
    } */
    for (auto i : ls.r)
        for (auto j : rs.l)
            if ((i.val | j.val) >= X)
                k.ans += (ll)i.len * j.len;
    return k;
}

void modify(int l, int r, int x, int v, int k)
{
    if (l == r)
    {
        t[k].ans = v >= X, t[k].l.clear(), t[k].r.clear();
        t[k].l.push_back({v, 1}), t[k].r.push_back({v, 1});
        return;
    }
    int mid = (l + r) / 2;
    if (x <= mid)
        modify(l, mid, x, v, ls(k));
    else
        modify(mid + 1, r, x, v, rs(k));
    t[k] = merge(t[ls(k)], t[rs(k)]);
}

node query(int l, int r, int x, int y, int k)
{
    if (l == x && r == y)
        return t[k];
    int mid = (l + r) / 2;
    if (y <= mid)
        return query(l, mid, x, y, ls(k));
    if (x > mid)
        return query(mid + 1, r, x, y, rs(k));
    return merge(query(l, mid, x, mid, ls(k)), query(mid + 1, r, mid + 1, y, rs(k)));
}

void build(int l, int r, int k)
{
    if (l == r)
    {
        t[k].ans = a[l] >= X, t[k].l.clear(), t[k].r.clear();
        t[k].l.push_back({a[l], 1}), t[k].r.push_back({a[l], 1});
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, ls(k));
    build(mid + 1, r, rs(k));
    t[k] = merge(t[ls(k)], t[rs(k)]);
}

int main()
{
    n = read(), m = read(), X = read();
    for (int i = 1; i <= n; i++)
        a[i] = read();
    build(1, n, 1);

    while (m--)
    {
        int opt = read(), x = read(), y = read();
        if (opt == 1)
            modify(1, n, x, y, 1);
        else
            writeln(query(1, n, x, y, 1).ans);
    }    
}

A¶

Description¶

Solution¶

Code¶

B¶

Description¶

Solution¶

Code¶

C¶

Description¶

Solution¶

Code¶

D¶

Description¶

Solution¶

Code¶

E¶

Description¶

Solution¶

Code¶

F¶

Description¶

Solution¶

Code¶

A

Description

Solution

Code

B

Description

Solution

Code

C

Description

Solution

Code

D

Description

Solution

Code

E

Description

Solution

Code

F

Description

Solution

Code