AtCoder Beginner Contest 446

A

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
signed main() {
25
    // ios::sync_with_stdio(0);
26
    // cin.tie(0);
27
    // cout.tie(0);
28
    string s;
29
    cin >> s;
30
    cout << "Of";
31
    for(auto x : s) {
32
        if(x < 'a' || x > 'z') cout << (char)(x - 'A' + 'a');
33
        else cout << x;
34
    }
35
    cout << endl;
36
    return 0;
37
}

B

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 105;
25
int n, m, a[N];
26
signed main() {
27
    // ios::sync_with_stdio(0);
28
    // cin.tie(0);
29
    // cout.tie(0);
30
    cin >> n >> m;
31
    for(int i = 1;i <= m;i++) a[i] = i;
32
    for (int i = 1; i <= n; i++) {
33
        int x;
34
        cin >> x;
35
        vector<int> p;
36
        for(int j = 1;j <= x;j++) {
37
            int y;
38
            cin >> y;
39
            p.push_back(y);
40
        }
41
        int fg = 0;
42
        for(auto t : p) if(a[t]) {
43
            cout << t << endl;
44
            fg = 1;
45
            a[t] = 0;
46
            break;
47
        }
48
        if(!fg) cout << 0 << endl;
49
    }
50
    return 0;
51
}

C

抽象一下发现维护一个双端队列即可。我们先把每天买入的鸡蛋数量压入队列，然后不短取出队头来消耗。用不完的重新入队。这样每个 $a_i$ 在每一天开始入队 1 次，被使用完后出队 1 次，用不完再放回去的次数，所有 $a_i$ 均摊 $O(1)$ 次。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int T, n, D, a[N], b[N];
26
void solve() {
27
    cin >> n >> D;
28
    ll ans = 0;
29
    deque<PII > q;
30
    q.clear();
31
    for(int i = 1; i <= n; i++) {
32
        cin >> a[i];
33
    }
34
    for(int i = 1;i <= n;i++) {
35
        cin >> b[i];
36
    }
37
    for(int i = 1;i <= n;i++) {
38
        q.push_back({a[i], i});
39
        while(q.size() && q.front().second + D < i) {
40
            q.pop_front();
41
        }
42
        int d = b[i];
43
        while(q.size() && d) {
44
            PII x = q.front();
45
            q.pop_front();
46
            if(d >= x.first) {
47
                d -= x.first;
48
                continue;
49
            } else {
50
                q.push_front({x.first - d, x.second});
51
                d = 0;
52
            }
53
        }
54
    }
55
    while(q.size()) {
56
        PII x = q.front();
57
        q.pop_front();
58
        if(x.second + D <= n) continue;
59
        ans += x.first;
60
    }
61
    cout << ans << endl;
62
}
63
signed main() {
64
    ios::sync_with_stdio(0);
65
    cin.tie(0);
66
    cout.tie(0);
67
    cin >> T;
68
    while(T--) solve();
69
    return 0;
70
}

D

用std::map或者std::unordered_map就水过去了。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 2e5 + 5;
25
int n, a[N];
26
map<int, int> f;
27
signed main() {
28
    ios::sync_with_stdio(0);
29
    cin.tie(0);
30
    cout.tie(0);
31
    cin >> n;
32
    for(int i = 1;i <= n;i++) cin >> a[i];
33
    f[a[1]] = 1;
34
    int ans = 1;
35
    for(int i = 2;i <= n;i++) {
36
        if(!f.count(a[i])) f[a[i]] = 1;
37
        if(!f.count(a[i] - 1)) continue;
38
        f[a[i]] = max(f[a[i]], f[a[i] - 1] + 1);
39
        ans = max(ans, f[a[i]]);
40
    }
41
    cout << ans << endl;
42
    return 0;
43
}

E

看起来是个很神秘的题。

在模 $M$ 意义下考虑吧，这样数列中就不允许出现 $0$ 。

对于 $(x, y) \in Z_M^2$ ，都会得到 $\big(y, (Ay + Bx) \bmod M \big) \in Z_M^2$ 。那么序列中这样的数对数量是平方的，可以预处理。

序列中出现 $0$ ，说明存在 $(0, x), x \in Z_M$ 或者 $(x, 0) x \in Z_m$ 。由于数列无限递推，所以能到达它们的点就不允许出现其中，这就变成了一个可达性问题。对上述关系连边，得到一张挺稀疏的图。由于起点不固定，但终点（非法点）可以确定，所以建反边，从非法点开始搜，答案就是 $M^2$ 减掉非法点所在的连通块大小之和。

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 1e6 + 5;
25
int n, A, B, res;
26
bool v[N];
27
vector<int> p[N];
28
int id(int i, int j) {
29
    return i * n + j;
30
}
31
void dfs(int x) {
32
    v[x] = 1;
33
    res++;
34
    // cout << x << endl;
35
    // puts("Haha");
36
    for(auto y : p[x]) if(!v[y]) {
37
        dfs(y);
38
    }
39
}
40
signed main() {
41
    ios::sync_with_stdio(0);
42
    cin.tie(0);
43
    cout.tie(0);
44
    cin >> n >> A >> B;
45
    for(int x = 0; x < n; x++) {
46
        for(int y = 0; y < n; y++) {
47
            int ty = (A * y % n + B * x % n) % n;
48
            int tx = y;
49
            // 反向边
50
            // printf("[%d, %d] -> [%d, %d]\n", x, y, tx, ty);
51
            p[id(tx, ty)].push_back(id(x, y));
52
        }
53
    }
54
    for(int y = 0; y < n; y++) if(!v[id(0, y)]) {
55
        dfs(id(0, y));
56
    }
57
    for(int x = 0; x < n; x++) if(!v[id(x, 0)]) {
58
        dfs(id(x, 0));
59
    }
60
    cout << n * n - res << endl;
61
    return 0;
62
}

F

这题神了。

为了满足条件，必须要考虑 $1$ 到 $x$ 的路径，显然让最大编号最小化总是最优的，因为只考虑从 $1$ 出发的可达性。能设 $f(x)$ 为从 $1$ 出发到 $x$ ，且最小化路径最大节点编号，所对应的那个编号。

这样，由于我们要且只要到达 $[1,x]$ 中所有节点，所以如果 $\max_{i = 1} ^x \{f(i)\} > x$ ，那么必然经过编号更大的点，就无解了。

有

f(y) = \min_{x \rightarrow y} \Big\{ \max\big(f(x), y\big) \Big\}

这个显然是有环的，不能直接做。考虑当前有一个已经确定的 $f(x)$ ，由于最大值的性质，通过环不能将它更新得更小，所以可以放到Dijkstra上转移。

这样就判掉无解的情况了。

如果去想只到达 $[1,x]$ 中节点需要删掉多少个点，信息就不太够，感觉找不到什么好做法。因为这时候容易求的最值类信息已经用不上了。

考虑一个点 $x$ 什么时候应该被删除。

如果 $[1, x - 1]$ 中存在某个点 $y$ ，无论如何选择 $1$ 到 $y$ 的路径，一定能中途易辙走到 $x$ ，此时 $x$ 必须删掉。

并且由于这个可达性要求是个前缀，如果点 $y'$ 能到达 $x$ ，那么对于 $y'' \in [y', x)$ ，由于其一定要能到达 $y'$ ，所以也一定能走到 $x$ 。所以一定存在一个节点 $p$ ，满足走到 $[1, p)$ 中节点不需要删掉 $x$ ，但是走到 $[p, x)$ 必须删。

于是问题就变成了如何求出这个 $p$ 。

好像只要一个节点能够到达 $x$ 就需要删掉 $x$ 啊…

但这显然不是最优解，我们只需要断掉与 $x$ 的路径，并不一定要删掉 $x$ 。这就有了一种微妙的展开——对于每个 $x$ ，我们都求这个临界的 $p$ 。具体的，考虑到达 $x$ 的所有路径，这个 $p$ 一定是路径上的某个点，同时，在考虑 $[1,p)$ 中节点的时候，不需要删除 $x$ ，删除 $p$ 即可保证不可达性。

于是这个 $p$ 就是路径中不包含 $x$ 的最小瓶颈编号。因为无法到达 $p$ ，也就无法前往 $x$ 。同样其他到 $x$ 的路径存在更大的编号，也一样不可达。

这样能避开无效删除吗？首先不会删得更多，因为冗余删除的情况就是本来已经不可到达 $x$ 时删掉 $x$ ，我们考虑了所有路径，小于 $p$ 时不存在走向 $x$ 的路径，也就不会多删。会漏掉吗？显然更不会。

维护一个 $g(x)$ 为到达 $x$ 所有路径中，不含节点 $x$ 的最小瓶颈编号，求法与 $f(x)$ 类似。

影响范围是一个区间，差分维护即可。如果 $g(x) < x$ ，就让 $[g(x), x - 1]$ 要删点的数量加上 $1$ 。

复杂度 $O(n \log n)$

1
#include<bits/stdc++.h>
2
using namespace std;
3
typedef long long ll;
4
typedef unsigned long long ull;
5
typedef pair<int,int> PII;
6
#define MP make_pair
7
#define fi first
8
#define se second
9
#define pb push_back
10
#define eb emplace_back
11
#define SET(a,b) memset(a,b,sizeof(a))
12
#define CPY(a,b) memcpy(a,b,sizeof(b))
13
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
14
#define per(i,j,k) for(int i=(j);i>=(k);--i)
15
int read() {
16
   int a=0, f=1; char c=getchar();
17
   while(!isdigit(c)) {
18
       if(c=='-') f=-1;
19
       c=getchar();
20
   }
21
   while(isdigit(c)) a=a*10+c-'0', c=getchar();
22
   return a*f;
23
}
24
const int N = 3e5 + 5;
25
int n, m, f[N], g[N], pre[N], ans[N];
26
int c[N];
27
bool v[N];
28
vector<int> p[N], pq[N];
29
void dijkstra() {
30
    priority_queue<int, vector<int>, greater<int> > q;
31
    for(int i = 1; i <= n; i++) f[i] = g[i] = n + 1;
32
    f[1] = 1;
33
    q.push(1);
34
    while(q.size()) {
35
        int x = q.top();
36
        q.pop();
37
        if(v[x]) continue;
38
        v[x] = 1;
39
        for(auto y : p[x]) {
40
            int t = f[y];
41
            f[y] = min(f[y], max(f[x], y));
42
            g[y] = min(g[y], max(f[x], x));
43
            if(f[y] < t) {
44
                q.push(y);
45
            }
46
        }
47
    }
48
}
49
signed main() {
50
    ios::sync_with_stdio(0);
51
    cin.tie(0);
52
    cout.tie(0);
53
    cin >> n >> m;
54
    for(int i = 1;i <= m;i++) {
55
        int x, y;
56
        cin >> x >> y;
57
        p[x].pb(y);
58
        pq[y].pb(x);
59
    }
60
    dijkstra();
61
    for(int i = 1;i <= n;i++) {
62
        if(f[i] <= n && g[i] < i) {
63
            c[g[i]]++;
64
            c[i]--;
65
        }
66
    }
67
    pre[0] = 0;
68
    for(int i = 1;i <= n;i++) {
69
        c[i] += c[i - 1];
70
        pre[i] = max(pre[i - 1], f[i]);
71
        if(pre[i] > i) cout << "-1" << endl;
72
        else cout << c[i] << endl;
73
    }
74
    return 0;
75
}

Nanami^2

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

觉得这篇文章怎么样？

分享这篇文章

评论区