Atcoder ABC408游记

405~407有事情没打所以没写文章

Atcoder ABC408游记（A~E）

A.Timeout

题目描述

beat会立即睡着。具体地说，如果从上次拍打beat的肩膀到现在已过去 $S+0.5$ 秒或更长时间，beat就会睡着。

目前，beat是醒着的，一个人刚刚拍了拍beat的肩膀。

从现在开始，这个人会准确地拍打beat的肩膀 $N$ 次。 $i$ 次拍肩将在 $T_i$ 秒后进行。

判断beat从现在开始到 $T_N$ 秒后是否一直保持清醒。

思路

阅读理解题，水

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n, s;
    cin >> n >> s;
    vector<int> a(n + 1);
    a[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] - a[i - 1] > s) {
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
}

B.Compression

题目描述

给出长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ 。

按升序输出 $A$ 中包含的数字，去掉重复的数字。

思路

set解决即可

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    set<int> s;
    while (n--) {
        int x;
        cin >> x;
        s.insert(x);
    }
    cout << s.size() << '\n';
    auto it = s.begin();
    while (it != s.end()) {
        cout << *it << ' ';
        it++;
    }
    return 0;
}

C.Not All Covered

题目描述

beat王国里有$N$个城堡，排成一行，编号从$1$~$N$。

有$M$个炮塔，第$i$个炮塔可以保护从第$l_i$到第$r_i$个城堡。

邪恶beat问你最少移除多少个炮塔可以使至少一个城市没有炮塔守护！

思路

差分呀哥们 用线段树和树状数组的走开

代码

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<int> s(n + 2, 0);
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        s[l] += 1;
        if (r + 1 <= n) {
            s[r + 1] -= 1;
        }
    }
    int sum = 0;
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n; i++) {
        sum += s[i];
        if (sum < ans) {
            ans = sum;
        }
    }
    cout << ans;
    return 0;
}

D.Flip to Gather

题目描述

给你一个长度为 $N$ 的字符串 $S$ ，它由 0 和 1 组成。

您可以执行以下操作任意次数（可能为零）：

• 选择一个满足 $1 \leq i \leq N$ 的整数 $i$ ，并将 $S_i$ 从 0 改为 1，或从 1 改为 0。

你的目标是使 $S$ 中的 1 最多形成1个区间。求实现目标所需的最少运算次数。

更准确地说，目标是使 $S$ 中存在一对满足以下两个条件的整数 $(l,r)$ 。求实现目标所需的最小运算次数。

• $1 \leq l \leq r \leq N+1$ .
• $S_i=$ 对于满足 $1 \leq i \leq N$ 的每个整数 $i$ 来说，1 和 $l \leq i \leq r$ 是等价的。

可以证明，目标总是可以用有限次的运算来实现。

给出了 $T$ 个测试用例，请逐一求解。

思路

贪心，我们只保留最长的一段1，其他的删了即可

代码

#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n;
    string s;
    cin >> n >> s;
    int cnt1 = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '1') {
            cnt1++;
        }
    }
    int maxx = 0;
    int cnt2 = 0;
    for (int i = 0; i < s.length(); i++) {
        int b = (s[i] == '1') ? 1 : -1;
        maxx = max(b, maxx + b);
        if (maxx > cnt2) {
            cnt2 = maxx;
        }
    }
    cout << (cnt1 - cnt2) << '\n';
}
int main()
{
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

E.Minimum OR Path

题目描述

给你一个有 $N$ 个顶点和 $M$ 条无自循环边的连通无向图，其中顶点的编号从 $1$ 到 $N$ ，边的编号从 $1$ 到 $M$ 。边 $i$ 双向连接顶点 $u_i$ 和 $v_i$ ，其权值为 $w_i$ 。

在从顶点 $1$ 到顶点 $N$ 的简单路径（不多次访问同一顶点的路径）中，求路径中所有边的权值的 $\mathrm{OR}$ 的最小值。

什么是比特 $\mathrm{OR}$ 操作？

非负整数 $A$ 和 $B$ 的位运算 $\mathrm{OR}$ , $A\ \mathrm{OR}\ B$ 的定义如下：

• 如果二进制表示的 $A$ 和 $B$ 的 $2^k$ 位中至少有一位数字是 $1$ ，则 $A\ \mathrm{OR}\ B$ 的 $2^k$ （ $k \geq 0$ ）位中的数字是 $1$ ，否则是 $0$ 。

例如， $3\ \mathrm{OR}\ 5 = 7$ （二进制表示为： $011\ \mathrm{OR}\ 101 = 111$ ）。
一般来说， $k$ 非负整数 $p_1, p_2, p_3, \dots, p_k$ 的比特 $\mathrm{OR}$ 定义为 $(\dots ((p_1\ \mathrm{OR}\ p_2)\ \mathrm{OR}\ p_3)\ \mathrm{OR}\ \dots\ \mathrm{OR}\ p_k)$ ，可以证明这与 $p_1, p_2, p_3, \dots p_k$ 的阶数无关。

思路

按位操作即可。

数据范围告诉你$w_i$最大到$2_30 - 1$。

我们考虑贪心，$ans$初始化肯定是所有$w_i$的$\mathrm{OR}$，然后对于二进制里的第$29$到第$0$位，判断一下如果$ans$的这一位可不可以为$0$。

那判断的方法无脑BFS即可，看一下能不能走到$N$这个结点就可以了。

我居然会想到dijkstra

代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<pair<int, int>>> edges;
bool check(int x)
{
    vector<bool> vis(n + 1, 0);
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    while (!q.empty()) {
        int tp = q.front();
        q.pop();
        for (int i = 0; i < edges[tp].size(); i++) {
            int v = edges[tp][i].first;
            int w = edges[tp][i].second;
            if ((w & x) != w) {
                continue;
            }
            if (v == n) {
                return 1;
            }
            if (!vis[v]) {
                vis[v] = 1;
                q.push(v);
            }
        }
    }
    return 0;
}

int main()
{
    cin >> n >> m;
    edges.resize(n + 1);
    int cnt = 0;
    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        edges[u].push_back({v, w});
        edges[v].push_back({u, w});
        cnt |= w;
    }
    int ans = cnt;
    for (int i = 29; i >= 0; i--) {
        if (!(ans & (1 << i))) {
            continue;
        }
        int x = ans & ~(1 << i);
        if (check(x)) {
            ans = x;
        }
    }
    cout << ans;
    return 0;
}