AtCoder Beginner Contest 442

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
string s;
25
signed main() {
26
    ios::sync_with_stdio(0);
27
    cin.tie(0);
28
    cout.tie(0);
29
    cin >> s;
30
    int ans = 0;
31
    for(auto x : s) if(x == 'i' || x == 'j') ans++;
32
    cout << ans << endl;
33
    return 0;
34
}

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
int n, c, p;
25
signed main() {
26
    ios::sync_with_stdio(0);
27
    cin.tie(0);
28
    cout.tie(0);
29
    cin >> n;
30
    while(n--) {
31
        int type;
32
        cin >> type;
33
        if(type == 1) c++;
34
        else if(type == 2 && c > 0) c--;
35
        else if(type == 3) {
36
            p ^= 1;
37
        }
38
        if(c >= 3 && p) cout << "Yes" << endl;
39
        else cout << "No" << endl;
40
    }
41
    return 0;
42
}

C

一开始读错题，浪费了点时间。

对于一个 $i$ ，答案是 $\binom{n - a_i}{3}$ ，其中 $a_i$ 为与 $i$ 有冲突的人数。

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, m, a[N];
26
PII e[N];
27
ll u;
28
signed main() {
29
    ios::sync_with_stdio(0);
30
    cin.tie(0);
31
    cout.tie(0);
32
    cin >> n >> m;
33
    u = n * (n - 1) / 2 - m;
34
    for(int i = 1;i <= m;i++) {
35
        cin >> e[i].fi >> e[i].se;
36
        a[e[i].fi]++;
37
        a[e[i].se]++;
38
    }
39
    for(int i = 1;i <= n;i++) {
40
        ll res = 1ll * (n - 1 - a[i]) * (n - 1 - a[i] - 1) * (n - 1 - a[i] - 2) / 6;
41
        cout << res << " ";
42
    }
43
    cout << endl;
44
    return 0;
45
}

D

懒得动脑子了，树状数组暴力维护，写得飞快跑得有点慢。

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, m, a[N];
26
struct BIT {
27
    int c[N];
28
    void add(int x, int d) {
29
        for(int i = x;i <= n;i += (i & -i)) c[i] += d;
30
    }
31
    int query(int x) {
32
        if(x == 0) return 0;
33
        ll res = 0;
34
        for(int i = x;i;i -= (i & -i)) res += c[i];
35
        return res;
36
    }
37
} T;
38
signed main() {
39
    // ios::sync_with_stdio(0);
40
    // cin.tie(0);
41
    // cout.tie(0);
42
    cin >> n >> m;
43
    for(int i = 1;i <= n;i++) {
44
        cin >> a[i];
45
        T.add(i, a[i]);
46
    }
47
    while(m--) {
48
        int type;
49
        cin >> type;
50
        if(type == 1) {
51
            int i;
52
            cin >> i;
53
            T.add(i, -a[i]);
54
            T.add(i + 1, -a[i + 1]);
55
            swap(a[i], a[i + 1]);
56
            T.add(i, a[i]);
57
            T.add(i + 1, a[i + 1]);
58
        } else {
59
            int l, r;
60
            cin >> l >> r;
61
            cout << T.query(r) - T.query(l - 1) << endl;
62
        }
63
    }
64
    return 0;
65
}

E

场上我选择了求极角结果被卡，估计改成比斜率就行了。

F

这题挺有意思的。

先进行一些基本的观察：

如果 $(i,j)$ 为白色，那么以 $(1,1)$ 为左上角， $(i, j)$ 为右下角的矩形都必须是白色。
对于一个合法的矩形，从上到下每一行开头的白色点数量是单调不增的。否则一定与上一条矛盾。

也就是说我们要维护对这个不增的轮廓线。

设 $f(i, j)$ 为处理完了前 $i$ 行，其中第 $i$ 行的白色点数量为 $j$ 的方案数。

显然有

f(i, j) = \min_{k \in [j, n]} \Big\{ f(i - 1,k) + S(i,j)\Big\}

其中 $S(i, j)$ 为把第 $i$ 行搞成前 $j$ 个格子是白色，后面是黑色的代价，是个定值且容易计算。

于是乎

f(i, j) = \min_{k \in [j, n]} \Big\{ f(i - 1,k) \Big\} + S(i,j)

发现转移是个后缀min的形式，维护一下 $O(1)$ 即可转移。

还有一种 DP 方法是设 $g(i,j,0/1)$ 为把以 $(i,j)$ 为右下角的矩形搞合法的最小代价，其中 $(i,j)$ 分别为白色/黑色，这个也能做，但是维护的东西很麻烦，主要是丢掉了轮廓线的信息。而且你确定了一行的白色块延伸到哪里，这一行就确定了，状态信息是不够明显的。

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 = 5e3 + 5;
25
int n, cnt[N][N];
26
string s[N];
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++) {
33
        cin >> s[i];
34
        s[i] = " " + s[i];
35
    }
36
    for(int i = 1;i <= n;i++) {
37
        for(int j = 1;j <= n;j++) {
38
            cnt[i][j] = cnt[i][j - 1] + (s[i][j] == '.');
39
        }
40
    }
41
    vector<vector<int> > f(n + 5, vector<int>(n + 5, 0x3f3f3f));
42
    for(int i = 0;i <= n;i++) f[0][i] = 0;
43
    for(int i = 1;i <= n;i++)  {
44
        for(int j = 0;j <= n;j++) {
45
            f[i][j] = f[i - 1][j] + j - cnt[i][j] + cnt[i][n] - cnt[i][j];
46
        }
47
        for(int j = n - 1;~j;j--) f[i][j] = min(f[i][j], f[i][j + 1]);
48
    }
49
    cout << f[n][0] << endl;
50
    return 0;
51
}

G

没做捏。

Nanami^2

A

B

C

D

E

F

G

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

A

B

C

D

E

F

G

觉得这篇文章怎么样？

分享这篇文章

评论区