概述

Div1 的 B、C、D、E 都值得一做。

Div2 A

Description

有一个长度为 $n$​ 的序列，你需要找到一个非零整数 $d$​ 满足：当所有数都除以 $d$​ 之后（可以为小数），正数的个数要大于 $\lceil\dfrac{n}{2}\rceil$​。

Solution

当正数数量足够，$d=1$；当负数数量足够，$d=-1$，否则无解。

Code

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

int cnt = 0, n, cnt2;

int main()
{
    cin >> n;
    for (int i = 1, x; i <= n; i++)
        cin >> x, cnt += x > 0, cnt2 += x < 0;
    int p = ceil(1.0 * n / 2);
    if (cnt >= p)
        puts("1");
    else if (cnt2 >= p)
        puts("-1");
    else
        puts("0");
}

Div2 B

Description

萨沙和迪玛要做两个 $N$​ 层蛋糕，已知一条街上的 $2n$ 个商店 $a_1,a_2….a_{2n}$ ​每家只能提供一个 $a_i$ ​层蛋糕，蛋糕必须按照从 $1\sim n$（从小到大）的顺序购买。最初，萨沙和迪玛位于第一个（最左边）房子附近。输出他们在购买两个蛋糕时必须行走的最小距离。相邻两栋房子之间的距离正好是 $1$。​

Solution

显然两个人并没有什么特殊要求，找距离和最小的走即可。

Code

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

const int maxn = 2e5 + 10;

int a[maxn], b[maxn][2], n;
inline int dis(int x, int y) { return std::abs(x - y); }

int main()
{
    cin >> n;
    for (int i = 1; i <= 2 * n; i++)
    {
        cin >> a[i];
        if (b[a[i]][0])
            b[a[i]][1] = i;
        else
            b[a[i]][0] = i;
    }
    int nowa = 1, nowb = 1;
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = b[i][0], y = b[i][1];
        if (dis(nowa, x) + dis(nowb, y) < dis(nowa, y) + dis(nowb, x))
            ans += dis(nowa, x) + dis(nowb, y), nowa = x, nowb = y;
        else
            ans += dis(nowa, y) + dis(nowb, x), nowa = y, nowb = x;
    }
    cout << ans << endl;
}

Div2 C

Description

有一个 $n\times n$ 的网格，有一些部分是陆地，剩下的是海洋。海洋不能通行。一个人想从一个格子出发到另一个格子。

你可以造至多一个隧道连接两个格子，如果从 $(x_1,y_1)$ 连到 $(x_2,y_2)$，代价是 $(x_1-x_2)^2+(y_1-y_2)^2$。在陆地上行走没有代价。

问最小代价是多少。$n\leq50$。

Solution

因为只能造一个隧道，我们只能在出发点所在陆地和终点所在陆地造一个隧道。

$n$ 这么小，直接最暴力的暴力即可，找到出发地所在联通块所有点和终点所在联通块所有点，直接暴力找最小代价即可。

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

优化其实也可以，我们只求出来每个联通块最外圈的点，这样就是 $O(n^2)$ 的了。

Code

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

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int maxn = 55;

struct point
{
    int x, y;
} s, t;

char ss[maxn][maxn];
int a[maxn][maxn], vis[maxn][maxn], n;

inline bool is_in(int x, int y) { return x >= 1 && x <= n && y >= 1 && y <= n; }

void dfs(std::vector<point> &p, int x, int y)
{
    vis[x][y] = 1;
    p.push_back({x, y});
    for (int i = 0; i < 4; i++)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if (is_in(nx, ny) && !vis[nx][ny] && a[nx][ny] == 0)
            dfs(p, nx, ny);
    }
}

inline int pow_2(int x) { return x * x; }

int main()
{
    cin >> n >> s.x >> s.y >> t.x >> t.y;
    for (int i = 1; i <= n; i++)
        cin >> (ss[i] + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            a[i][j] = ss[i][j] == '1' ? 1 : 0;
    std::vector<point> p, q;
    dfs(p, s.x, s.y), memset(vis, 0, sizeof(vis)), dfs(q, t.x, t.y);
    int ans = 1 << 30;
    for (auto k : p)
        for (auto f : q)
        {
            ans = std::min(ans, pow_2(k.x - f.x) + pow_2(k.y - f.y));
        }
    cout << ans << endl;
}

A

Description

有 $n$ 个站台和一个玩具火车，第 $i$ 个站台单向连向第 $i+1$ 个站台，特殊地，第 $n$ 个站台连向第 $1$ 个站台。

有 $m$ 个糖果，每个糖果初始在 $a_i$ 站台，要被送到 $b_i$​ 站台。

火车经过一个站台时，可以卸下任意数量糖果，但只能往火车上装一个糖果。

问从每个站台出发，把所有糖果运送到指定位置需要的时间。（经过一条边需要 $1$ 的时间）。

Solution

一个站台里的糖果数决定了要经过这个站台的次数。

显然只有最后一次经过拿的糖果的目的地能影响时间，我们贪心地让这个时间最小。

预处理出从 $1$ 出发把每个车站的糖果的都送完的时间加上 $1$。

输出一个车站的答案后，只需要把这个车站的时间都加上 $n$ 并更新答案即可。

Code

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

const int maxn = 5100;

int n, m;

std::vector<int> all[maxn];

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> m;
    int mx = 0;
    for (int i = 1, x, y; i <= m; i++)
    {
        cin >> x >> y;
        all[x].push_back(y < x ? y + n : y);
    }
    for (int i = 1; i <= n; i++)
    {
        std::sort(all[i].begin(), all[i].end(), std::greater<int>());
        int now = 0;
        for (auto &p : all[i])
            p += now, now += n, mx = std::max(mx, p);
    }
    for (int i = 1; i <= n; i++)
    {
        cout << mx - i << " ";
        for (auto &p : all[i])
            p += n, mx = std::max(p, mx);
    }
}

B

Description

给定一个序列 $a$，有 $n$ 个元素，编号从 $0$ 到 $n-1$。求 $\max\limits_{0 \leq l \leq r \leq n-1}(r-l+1)\times\sum\limits_{l\leq i\leq r}a_i$。

有一个错误算法：

```
function find_answer(n, a)
    # Assumes n is an integer between 1 and 2000, inclusive
    # Assumes a is a list containing n integers: a[0], a[1], ..., a[n-1]
    res = 0
    cur = 0
    k = -1
    for i = 0 to i = n-1
        cur = cur + a[i]
        if cur < 0
            cur = 0
            k = i
        res = max(res, (i-k)*cur)
    return res
```

你需要构造一组数据，使这个标准答案减去错误算法得出的答案是 $k$。

$|a_i| \leq 10^6,n \leq 2000$。

Solution

不难发现这个错误做法会在出现负数的时候出错，那么我们先安排一个 $-1$ 进去。

这时候错误做法的答案是 $(\sum a_i+1)(n-1)$，而正确答案是 $n\times\sum a_i$。

那么应该新加进去的数是 $k-\sum a_i+n$（这里的 $\sum a_i,n$ 都是加进去之前的）。

如果这个数比 $10^6$ 大我们就加进去 $10^6$，否则直接加该加的数即可。

Code

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

const int mx = 1e6;

std::vector<int> ans;
int k;

int main()
{
    ans.push_back(-1);
    int sum = -1, n = 1;
    cin >> k;
    while (sum - n + 1 < k)
    {
        if (k - sum + n <= mx)
            ans.push_back(k - sum + n), n++;
        else
            n++, ans.push_back(mx);
        sum += ans.back();
    }
    cout << ans.size() << endl;
    for (int p : ans)
        cout << p << " ";
    cout << endl;
}

C

Description

在摩尔斯电码（以下简称“摩码”）中，字母表中的一个字母被表示为一个长度为$1\sim4$的 01 串。长度为 $1\sim4$ 的 01串共有 $2^1+2^2+2^3+2^4=30$ 个，而字母只有 $26$ 个，所以有 $4$ 个 01 串不表示任何字母——0011、0101、1110、1111，其他 $26$ 个 01 串表示互不相同的 $26$ 个字母。 你有一个 01 串 $S$，初始为空。现在有 $m$ 次添加，每次往 $S$ 的末尾添加一个字符（0 或 1）。对于每一次添加，你都要回答目前的 $S$ 的所有非空子串用摩码所能表示的字母串的总数。由于答案可能巨大，你只需要输出答案模 $10^9+7$ 的结果。

$m\leq3000$。

Solution

$m$ 很小，我们可以考虑用暴力一点的方法草过去这个题。

可以考虑对每个操作计算其对答案的贡献，那么我们就是要计算后缀对答案的贡献。

发现我们的字母串是本质不相同的，使用 Trie 树就可以维护之前的所有前缀。

进行一个操作时，我们在 Trie 树上的所有叶子节点下面都新开一个点，然后找它的 $4$ 个父亲（即枚举新后缀所在摩尔斯电码的长度），直接把方案数加上去就行。

复杂度 $O(m^2)$。

Code

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

const int maxn = 3000 * 3000 + 10, mod = 1e9 + 7;
typedef long long ll;

inline void upd(int &x, int y) { x += y % mod, x %= mod; }

int ans = 0;

struct Tree
{
    int ch[maxn][2], f[maxn], tot, father[maxn], a[maxn];
    void dp(int x)
    {
        int p = x;
        int s = 0;
        for (int i = 0; i < 4; i++)
        {
            int fa = father[x];
            //cout << x << " " << fa << endl;
            int now = ch[fa][1] == x;
            s += now << i;
            x = fa;
            if (i == 3 && (s == 3 || s == 5 || s == 14 || s == 15))
                continue;
            upd(f[p], f[x]);
            if (x == 0)
                break;
        }
        upd(ans, f[p]);
    }
    void insert(int x, int pos)
    {
        a[pos] = 0;
        for (int i = 0; i <= pos; i++)
        {
            int p = a[i];
            if (!ch[p][x])
                ch[p][x] = ++tot, father[tot] = p, dp(tot);
            a[i] = ch[p][x];
        }
    }
} t;

int main()
{
    int m;
    cin >> m;
    t.f[0] = 1;
    for (int i = 1; i <= m; i++)
    {
        int x;
        cin >> x;
        t.insert(x, i);
        cout << ans << endl;
    }
}

D

Description

给出一个长度为 $n$ 的序列，把它划分成若干段，使得每一段中出现过恰好一次的元素个数 $\le k$，求方案数对 $998244353$ 取模后的结果。

Solution

不难想到一个 DP：$f(i)$ 表示前 $i$ 位的答案。$f(i) = \sum\limits_{0 \leq j < i \wedge g(j+1, i) \leq k} f(j)$。其中 $g(i,j)$ 表示区间 $[i,j]$ 中出现过恰好一次的元素个数。

直接转移是 $O(n^2)$ 甚至 $O(n^3)$​ 的，想办法优化。

不会，下文包括代码全是抄题解。

因为恰好一次，我们想办法记录一个 $lst_i$​ 数组表示 $i$​ 上一次出现位置。

我们维护 $g_j=g(j+1,i)$

那么新加入 $a_i$​ 时，我们应该把 $[lst_{lst_{a_i}},lst_{a_i}-1)$​ 里的 $g$​​ 减一，把 $[lst_{a_i},i)$ 里的 $g$ 加上 $1$。

问题变成有一个序列，每个元素有一个权值和键值。我们每次将区间键值 $\pm1$，查询序列中键值 $\leq k$​ 的元素权值和。

对这种莫名其妙的维护我们可以尝试分块。

对序列进行分块，对每个块维护一个 $sum(i,j)$ 表示第 $i$ 个块中 $g_p\geq j$ 的 $f_p$ 之和。并维护一个 $all_i$ 表示块内所有 $f_p$​​​ 之和。

$lzy$ 是块上的加法懒标记。

查询直接遍历所有块把答案加进去即可（用 $all_i-sum(i,k-lzy_i+1)$ 就得到这个块的答案了）。

修改怎么办呢？对于整块，我们直接加懒标记。

对于散点，我们如果要把 $g_j$​​ 加上 $1$​​，那么就相当于把 $sum(i,g_j)$​​ 加上 $f_j$，反之同理。

这样查询和修改就是 $O(1)$​ 的。

时间复杂度 $O(nw+\dfrac{n^2}{w})\geq O(n\sqrt n)$。

Code

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

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

int n, k, len, id[maxn], lst[maxn], tot; 
int f[maxn], sum[410][maxn], lzy[maxn], bl[maxn], cnt[maxn], br[maxn], all[maxn], a[maxn], llst[maxn];

inline void upd(int &x, int y) { x += (y + mod) % mod, x %= mod; }

void add(int l, int r, int v)
{
    if (l > r)
        return;
    if (id[l] == id[r])
    {
        for (int i = l; i <= r; i++)
            if (v == 1)
                upd(sum[id[l]][++cnt[i]], f[i]);
            else
                upd(sum[id[l]][cnt[i]--], -f[i]);
        return;
    }
    for (int i = l; id[i] == id[l]; i++)
        if (v == 1)
            upd(sum[id[l]][++cnt[i]], f[i]);
        else
            upd(sum[id[l]][cnt[i]--], -f[i]);
    for (int i = r; id[i] == id[r]; i--)
        if (v == 1)
            upd(sum[id[r]][++cnt[i]], f[i]);
        else
            upd(sum[id[r]][cnt[i]--], -f[i]);
    for (int i = id[l] + 1; i < id[r]; i++)
        lzy[i] += v;

}

int work()
{
    int res = 0;
    for (int i = 0; i <= tot; i++)
    {
        upd(res, all[i]);
        if (k - lzy[i] + 1 >= 0)
            upd(res, -sum[i][k - lzy[i] + 1]);
        else
            upd(res, -all[i]);
    }
    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n >> k;
    f[0] = 1, len = sqrt(n), tot = n / len + 1;
    for (int i = 1; i <= tot; i++)
    {
        bl[i] = (i - 1) * len, br[i] = std::min(i * len - 1, n);
        for (int j = bl[i]; j <= br[i]; j++)
            id[j] = i;
    }
    sum[1][0] = 1, all[1] = 1;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        add(llst[a[i]], lst[a[i]] - 1, -1), add(lst[a[i]], i - 1, 1);
        llst[a[i]] = lst[a[i]], lst[a[i]] = i;
        f[i] = work();
        upd(sum[id[i]][0], f[i]), upd(all[id[i]], f[i]);
    }
    cout << f[n] << endl;
}

E

Description

这是一道交互题。

有一个 $n$ 个节点的树，你需要通过不超过 $11111$ 次询问得知树的形态。

询问方式为给出两个非空无交点集 $S$ ，$T$ 和一个点 $u$，可以得到满足 $s \in S , t \in T$ 且路径 $(s,t)$ 经过 $u$ 点的二元组 $(s,t)$ 的总数。

$n\leq500$。

Solution

没什么头绪，看看我们能通过询问得到什么。

假设我们以 $1$ 为根，每次询问 $(\{1\},\{2,3,…,n\},i)$ 能得到以 $i$ 为根子树大小。

那么把子树大小按从小到大排序，一个点儿子必定在其左侧，现在我们把问题转化为找儿子了。

设现在还没有确定父亲的点集合为 $S$。

问一次 $(\{1\},S,i)$ 能得到点 $i$ 的儿子个数 $k$，我们接下来二分 $k$ 次，每次找到一个最小的 $p$，使询问 $(\{1\},\{S_1,S_2,…,S_p\},i)$ 的结果非零。

那么这个 $p$​ 就是一个儿子。我们把它删掉接着二分就找到了所有儿子。

找完之后把点 $i$ 加进集合里就行。

时间复杂度 $O(n^2\log n)$，询问次数大概是 $2n+2n\log_2n$。

Code

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

const int maxn = 510;

struct node
{
    int id, siz;
    bool operator<(const node &b) const { return siz < b.siz; }
} a[maxn];

int father[maxn], n;

void get_siz()
{
    a[1].id = 1, a[1].siz = n;
    for (int i = 2; i <= n; i++)
    {
        cout << 1 << endl << 1 << endl << n - 1 << endl;
        for (int i = 2; i <= n; i++)
            cout << i << " ";
        cout << endl << i << endl;
        cin >> a[i].siz;
        a[i].id = i;
    }
    std::sort(a + 1, a + 1 + n);
}

int S[maxn], top;

bool check(int x, int pos)
{
    cout << 1 << endl << 1 << endl << x << endl;
    for (int i = 1; i <= x; i++)
        cout << a[S[i]].id << " ";
    cout << endl << pos << endl;
    int res = 0;
    cin >> res;
    return res > 0;
}

void solve()
{
    //for (int i = 1; i <= n; i++)
    //    cout << a[i].id << " " << a[i].siz << endl;
    for (int i = 1; i <= n; i++)
    {
        if (a[i].siz == 1)
            S[++top] = i;
        else
        {
            //cout << a[i].id << " " << a[i].siz << "!!!\n";
            int times;
            cout << 1 << endl << 1 << endl << top << endl;
            for (int i = 1; i <= top; i++)
                cout << a[S[i]].id << " ";
            cout << endl << a[i].id << endl;
            cin >> times;
            while (times--)
            {
                int l = 1, r = top, ans = -1;
                while (l <= r)
                {
                    int mid = (l + r) / 2;
                    if (check(mid, a[i].id))
                        r = mid - 1, ans = mid;
                    else
                        l = mid + 1;
                }
                father[a[S[ans]].id] = a[i].id;
                int flag = 0;
                for (int i = 1; i < top; i++)
                {
                    if (i == ans)
                        flag = 1;
                    if (flag)
                        S[i] = S[i + 1];
                }
                top--;
            }
            S[++top] = i;
        }
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin >> n;
    get_siz(), solve();
    cout << "ANSWER" << endl;
    for (int i = 2; i <= n; i++)
        cout << father[i] << " " << i << endl;
    return 0;
}