ABC408

A - Timeout

简单的枚举

#include <bits/stdc++.h>
using namespace std;
int n, s;
int last, now;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> s;
    last = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> now;
        if (now - last > s)
        {
            cout << "No";
            return 0;
        }

        last = now;
    }
    cout << "Yes";
    return 0;
}

B - Compression

排序去重输出，经典的明明的随机数。这里数据范围也很友好，计数排序、其他排序以及 C++ 自带的去重都可以实现。这里把几种写法都给大家看看。

普通排序

这题 $n\le 100$ 其他排序方法都能做

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int n;
int a[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);

    int nn = 1;
    for (int i = 2; i <= n; i++)
        if (a[i] != a[i - 1])
            nn++;
    cout << nn << "\n";

    cout << a[1];
    for (int i = 2; i <= n; i++)
        if (a[i] != a[i - 1])
            cout << " " << a[i];
    return 0;
}

计数排序

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXAI = 100;
int n;
int a[MAXN + 5];
int cnt[MAXAI + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }

    int nn = 0;
    for (int i = 1; i <= MAXAI; i++)
        nn += (cnt[i] > 0);
    cout << nn << "\n";

    for (int i = 1; i <= MAXAI; i++)
        if (cnt[i] > 0)
            cout << i << " ";
    return 0;
}

C++ 自带的去重

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
const int MAXAI = 100;
int n;
int a[MAXN + 5];
int cnt[MAXAI + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // unique 要求对有序数组操作
    // 不会改变数组大小，而是返回去重后的结尾位置（去重后数组不包括结尾）
    // 减去 a 之后再减 1 就能转变为去重后最后一个元素位置的下标
    sort(a + 1, a + n + 1);
    int nn = unique(a + 1, a + n + 1) - a - 1;
    // 简单的输出
    cout << nn << "\n";
    for (int i = 1; i <= nn; i++)
        cout << a[i] << " ";
    return 0;
}

C - Not All Covered

显然就是看哪个城墙被覆盖的炮塔最少，直接暴力枚举去计算覆盖肯定是不行，实际上容易想到就是进行“区间加一”和最终“求解全局最小值”。使用差分数组就能快速搞定了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000;
int n, m;
int d[MAXN + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int l, r;
        cin >> l >> r;
        d[l]++;
        d[r + 1]--;
    }
    for (int i = 1; i <= n; i++)
        d[i] = d[i - 1] + d[i];
    int ans = m; // 炮塔全拆了肯定行
    for (int i = 1; i <= n; i++)
        ans = min(ans, d[i]);
    cout << ans;
    return 0;
}

D - Flip to Gather

这题最大的难点在于题意容易理解错误，at most one interval 如果翻译为最多一个间隔，容易理解为是允许 00011011000 这样的中间留一个位置的。并且按照这个理解很多样例数据都能正确解释。

但最后一组样例数据 00010101 的正确输出是 2，就能让我们知道实际的意思是 1 必须是连续的一段。

那这题就没啥难的了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n;
string s;
int cnt1[MAXN + 5], cnt0[MAXN + 5];
// f[i]：a[1]~a[i] 中只有右边有 1 最少花几次
int f[MAXN + 5];
void work()
{
    cin >> n >> s;
    s = "^" + s;
    // 预处理 cnt*
    cnt1[0] = cnt0[0] = f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cnt1[i] = cnt1[i - 1] + (s[i] == '1');
        cnt0[i] = cnt0[i - 1] + (s[i] == '0');
        // 左边位置要么 0 结尾、要么 1 结尾
        f[i] = min(f[i - 1], cnt1[i - 1]) + (s[i] == '0');
    }
    // 算答案
    int ans = cnt1[n]; // 最坏情况，删掉所有 1
    for (int i = 1; i <= n; i++)
    {
        // a[1]~a[i] 的右边堆积了 1，a[i] 的右边 0 全都删掉
        ans = min(ans, f[i] + (cnt1[n] - cnt1[i]));
    }
    cout << ans << "\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--)
        work();
    return 0;
}

E - Minimum OR Path

首先显然如果最高位为 $0$ 能连通，我们就肯定会选择最高位为 $0$ 的方案。因此容易想到位数从高到低贪心，看看在当前对边的要求下能否连通。

判断连通性可以上并查集或者简单的搜索都行，反正最多只有 $30$ 次检查。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
int n, m;
vector<pair<int, int>> e[MAXN + 5];
// 检测当前 mask 下能否从 u 走到 n、也可以写 bfs 实现
int flag, vis[MAXN + 5]; // int 型 vis 配合 flag 避免每次都要重新清空
bool ok(int u, int mask)
{
    vis[u] = flag;
    if (u == n)
        return true;
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i].first;
        int w = e[u][i].second;
        if (vis[v] == flag)
            continue; // 过滤做过的点
        if ((w & mask) != w)
            continue; // 过滤非法的边
        if (ok(v, mask))
            return true;
    }
    return false;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    int ans = (1 << 30) - 1;
    for (int i = 29; i >= 0; i--)
    {
        // 检查去掉第 i 位的 1 能否从 1 走到 n
        flag++;
        if (ok(1, ans - (1 << i)))
            ans -= (1 << i);
    }
    cout << ans;
    return 0;
}