20190206 新生培训期末总结 题解

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 字数： 6.2k

1. A - Multi-Subject Competition CodeForces - 1082C

1.1 题目大意

给定n个考生，每个考生都有唯一选择的科目$s_i$和对应的能力水平$r_i$。同时给定m个考试科目。

求选定若干个科目，并且每个科目参与的考生数目相同的情况下，可以得到的最大能力水平和。

1.2 解题思路

我们首先将对应的考生预处理到对应的考试科目当中，并将其按照能力水平降序排列。

只要我们知道选定k个人的最大能力值和$sum[k]$是多少，我们只需枚举k从1到m，$ans = max{sum[k]}$，我们便可以得到答案。

下面考虑如何获得k个人的最大能力值和

首先对于每一门科目维护一下能力值和，我们可以得到某一门科目选1个人的最大能力值和，选2个人的最大能力值和… …一直枚举到这门科目的所有考生，或者枚举到能力值和小于零。

我们考虑只要第 $i$ 门科目的选取k个人的能力值和大于零，我们在选定考试人数为k人时，将这门科目加入考虑范围一定更优，于是我们可以让$sum[k] += cal(i, k)$

1.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 22时18分43秒
File Name     :A.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
vector<int> v[maxn];
bool cmp(int a, int b){
    return a > b;
}
int sum[maxn];
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n, m; sdd(n, m);
    while(n--){
        int s, r; sdd(s, r);
        v[s].pb(r);
    }
    int mx = 0;
    rep(i, 1, m + 1) {
        int sz = (int)v[i].size();
        if(sz > mx) mx = sz;
        sort(v[i].begin(), v[i].end(), cmp);
        int now = 0;
        rep(j, 0, sz){
            now += v[i][j];
            if(now > 0) sum[j + 1] += now;
        }
    }
    int ans = 0;
    rep(i, 0, mx + 1) ans = max(ans, sum[i]);
    pd(ans);
    return 0;
}
/*


*/

2 B - Minimizing the String CodeForces - 1076A

2.1 题目大意

给定一个由$n$个小写拉丁字母组成的字符串$s$。至多删除一个字符，问删除后字典序最小的字符串是什么。

注意 “aaa” is smaller than “aaaa”, “abb” is smaller than “abc”, “pqr” is smaller than “z”

2.2 解题思路

由于$aaa$小于$aaaa$。我们可以考虑每个字符串后有一个比任何字母都要小的哨兵字符存在。

由于字典序的定义，我们可以知道 $abcda$ 的字符串删除一个字符后最小的字符串为$abca$。

$”abca” < “abcd” < “abcda” < “abda” < “acda” < “bcda”$

因此我们可以将每个字符串看做一个数字序列 a 为 1， b 为 2， … … z 为26， 末尾哨兵为0;

很容易想到，在这个数字序列中，我们删除第一个下降位置的前半部分对应的字母一定可以获得最小字符串。

比如刚刚的 $abcda$ 对应 $123410$ 第一个下降位置为 $41$ 因此我们选择删除 $4$ 对应的字母 $d$ 可以获得最小字符串

2.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 21时15分51秒
File Name     :B.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
char s[maxn];
vector<char> ans;
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n; sd(n);
    ss(s); int len = strlen(s);
    bool ok = false;
    rep(i, 0, len){
        if(i == len - 1 || s[i] > s[i + 1]){
            if(ok) ans.pb(s[i]);
            else ok = true;
            continue;
        } 
        ans.pb(s[i]);
    }
    rep(i, 0, len - 1) printf("%c", ans[i]);
    puts("");
    return 0;
}
/*


*/

3 C - Divisor Subtraction CodeForces - 1076B

3.1 题目大意

给定一个范围在$1$ 到 $10 ^ {10}$ 的数字 $n$

算法将对其重复进行下述操作

如果 n == 0,，算法结束

否则的话，将这个数减去它的最大质因子

这个算法结束时我们进行了多少次减法

3.2 解题思路

如果这个数为偶数，它的最小质因子就是 $2$

在每次减去 $2$ 之后，它将仍然是偶数

也就是说，一个偶数，我们只会将其进行减2操作

所以答案将会是 $ans = \frac{n}{2}$

如果这个数是奇数，那么它的最小质因子一定是个奇数

而在减去这个最小质因子后，也就是 奇数减去奇数 后，我们一定会获得一个偶数

因此答案将会是 $ans = \frac{a - p}{2} + 1$

3.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 21时20分15秒
File Name     :C.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    ll n; sld(n);
    if((n&1) == 0){
        pld(n/2);
        return 0;
    }    
    ll ans = 1;
    ll sn = sqrt(n), p = -1;
    for(ll i = 3; i <= sn; ++i){
        if(n%i) continue;
        p = i;
        break;
    }
    if(p == -1) p = n;
    n -= p;
    ans += n/2;
    pld(ans);
    return 0;
}
/*


*/

4 D - Commentary Boxes CodeForces - 990A

4.1 题目大意

给定n个会场，m个代表团

每个代表团必须分配相同个数的会场（0个也可以）

我们可以花费 a 建设一个会场， m 拆毁一个会场

问满足题意的最小花费是多少

4.2 解题思路

每一次我们都只会拆除，或者只会建设，不会既拆除又建设

这样的话，我们考虑余数$rem = n\%m$，通过建设满足题意的花费$c1 = (m - rem)a$，通过拆除的的花费为$c2 = remb$

这样的话答案将是$ans = min(c1, c2)$

4.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 21时27分15秒
File Name     :D.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    ll n, m; sldd(n, m);
    ll a, b; sldd(a, b);
    ll rm = n%m;
    ll c1 = rm*b, c2 = (m - rm)*a;
    ll ans = min(c1, c2);
    pld(ans);   
    return 0;
}
/*


*/

5 E - Maximum Diameter Graph CodeForces - 1082D

5.1 题目大意

给定n个点，每个点的最大度数为$a_i$

问这个图能否构造出来

能构造出来的话，构造出来的最大直径是多少，它的边是哪些。

5.2 解题思路

如果这个图存在，我们将其所有最大度数大于一的点连成一条线

如果存在度数为1的点，首先在连成的线最左边和最右边的点各放置一个

然后将剩下的度数为1的点连在度数还没超的线上的点即可

如果最后度数为1的点没有连完，那么给定的图一定不存在

5.3 代码实现

写的时候头有点晕，思路有点乱，大家凑合着看叭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
/* ***********************************************
Author        :linxi
Created Time  :2019年02月07日 星期四 10时22分52秒
File Name     :E.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 5e2 + 5;
//head
struct node{
    int a, id;
    bool operator<(const node& nd) const{
        return a > nd.a;
    }
}nd[maxn];
int d[maxn];
int ans = 0;
vector<int> u, v;
void solve(int x, int y){
    u.pb(x), v.pb(y);
    --d[x], --d[y];
    ++ans;
}
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n; sd(n);
    rep(i, 0, n){
        nd[i].id = i + 1;
        sd(nd[i].a);
        d[i + 1] = nd[i].a;
    }
    sort(nd, nd + n);
    if(nd[0].a == 1){
        puts("NO");
        return 0;
    }
    int lst = -1, pos = 0, rt = nd[0].id;
    rep(i, 1, n){
        int now = nd[i].id;
        if(d[now] == 1) break;
        pos = i;
        if(lst != -1) solve(lst, now);
        lst = now;
    }
    ++pos;
    if(lst == -1){
        bool ok = true;
        rep(i, pos, n){
            if(d[rt] <= 0){
                ok = false;
                break;
            }
            int now = nd[i].id;
            solve(now, rt);
        }
        if(!ok){
            puts("NO");
            return 0;
        }
        if(ans > 2) ans = 2;
        printf("YES %d\n", ans);
        int sz = (int)u.size();
        printf("%d\n", sz);
        rep(i, 0, sz) printf("%d %d\n", u[i], v[i]);
        return 0;
    }
    int lf = nd[1].id;
//    printf("%d %d %d\n", lf, lst, rt);
//    pd(pos);
    solve(lst, rt);
    if(pos < n){
        solve(nd[pos++].id, lf);
        if(pos < n) solve(nd[pos++].id, rt);
    }
    int now = 0;
    bool ok = true;
    rep(i, pos, n){
        while(now < n){
            if(d[nd[now].id] > 0) break;
            ++now;
        }
        if(now >= i || now >= n){
            ok = false;
            break;
        }
        solve(nd[i].id, nd[now].id);
        --ans;
    }
    if(!ok){
        puts("NO");
        return 0;
    }
    printf("YES %d\n", ans);
    int sz = (int)u.size();
    printf("%d\n", sz);
    rep(i, 0, sz) printf("%d %d\n", u[i], v[i]);
    return 0;
}
/*
3
2 2 2
*/

6 F - Micro-World CodeForces - 990B

6.1 题目大意

给定n个细菌，一个吞噬阈值k，每个细菌都有一个体积$a_i$

一个细菌能吞噬所有体积小于它但是体积差小于等于k的细菌

你可以规划吞噬顺序，问最后能剩余的最少细菌是多少个

6.2 解题思路

将细菌们按照体积升序排序

考虑每个细菌，二分查找第一个大于它的细菌，如果它们的体积差不大于k，这个细菌将可以被吃掉，顺手统计一下即可

6.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 21时54分11秒
File Name     :F.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int a[maxn];
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int n, k; sdd(n, k);    
    rep(i, 0, n) sd(a[i]);
    sort(a, a + n);
    int ans = n;
    rep(i, 0, n - 1){
        int pos = upper_bound(a + i + 1, a + n, a[i]) - a;
        if(pos != n && a[i] + k >= a[pos]) --ans;
    } 
    pd(ans);
    return 0;
}
/*


*/

7 G - A Blend of Springtime CodeForces - 989A

7.1 题目大意

给定n个花盆，每个花盆种着A、B、C三种花朵，或者为空，花凋零后花瓣会掉入旁边的花盆，此花盆将不再存在这个花瓣

你可以调整花瓣凋零顺序

问是否有某个时刻，某个花盆存在三种颜色的花瓣

7.2 解题思路

根据题意，只要存在ABC连续存在的三个花盆，无论顺序如何，都将满足题意

我们只需在字符串里找一下是否存在连续的ABC子串

7.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 21时31分54秒
File Name     :G.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
char s[maxn];
int cnt[5];
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    ss(s); int len = strlen(s);
    int tot = 0;
    rep(i, 0, len){
//        printf("%d %d\n", i - 1, tot);
//        rep(j, 0, 3){
//            printf("%c %d\n", j + 'A', cnt[j]);
//        }
        if(tot == 3){
            puts("Yes");
            return 0;
        }
        if(s[i] != '.'){
            int& now = cnt[s[i] - 'A']; 
            if(now == 0) ++tot;
            ++now;
        }
        if(i < 3 || s[i - 3] == '.') continue;
        int& lst = cnt[s[i - 3] - 'A'];
        --lst;
        if(lst == 0) --tot;
    }
    if(tot == 3){
        puts("Yes");
        return 0;
    }
    puts("No");
    return 0;
}
/*


*/

8 H - Trial for Chief CodeForces - 37E

8.1 题目大意

给定一个全白色的$n \times m$的板

你每次可以将一个（可以是某个联通子区域）相同颜色的（上下左右四联通的）联通块涂成相反的颜色

问你最少需要几步可以将其涂成给定的颜色模式

8.2 解题思路

如果是一个全白色的板，明显答案是0

否则的话，我们可以枚举所有位置

考虑以某个位置(x, y)作为染色起点，我们所需要的最少花费

这样的话，我们只需将所有位置的花费取一个最小即可

如何计算以某个点为染色起点的最小花费呢

我们可以考虑这样一种染色方式，我们计算出所有点按照距离该位置的层数距离

距离层数的计算可以抽象为同一个颜色的相邻位置移动花费为0，不同颜色的相邻位置移动花费为1，跑一个迪杰斯特拉即可得到

首先将层数距离最远的黑点包含进去涂黑

将除离该位置最远的黑点外的所有点涂白，将包含所有次远黑点以及更近的黑点涂黑

重复上述操作，直至将所有所有点染成相应的颜色

这样的话，我们的花费是，距离此位置的最远的黑点加一

可以证明，这种染色方式一定保证每次染得都是联通块，而且次数是最少的

8.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
/* ***********************************************
Author        :linxi
Created Time  :2019年02月07日 星期四 14时58分01秒
File Name     :H.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
int tox[] = {0, 0, 1, -1};
int toy[] = {1, -1, 0, 0};
char g[55][55];
int n, m, dist[55][55];
bool judge(int x, int y){
    if(x < 0 || x >= n) return false;
    if(y < 0 || y >= m) return false;
    return true;
}
struct node{
    int x, y, t;
    bool operator <(const node& nd) const{
        return t > nd.t;
    }
};
int dijk(int x, int y){
    int ret = 0, t;
    priority_queue<node> q;
    node now; now.t = 1, now.x = x, now.y = y;
    q.push(now);
    dist[x][y] = 1;
    while(!q.empty()){
        now = q.top(); q.pop();
        rep(i, 0, 4){
            int tx = now.x + tox[i], ty = now.y + toy[i], tt = now.t;
            if(!judge(tx, ty)) continue;
            if(g[tx][ty] != g[now.x][now.y]) ++tt;
            if(tt >= dist[tx][ty]) continue;
            node nxt; nxt.x = tx, nxt.y = ty, nxt.t = tt;
            dist[tx][ty] = tt;
            q.push(nxt);
        }
    }
    rep(i, 0, n){
        rep(j, 0, m){
            if(g[i][j] == 'W') continue;
            if(dist[i][j] > ret) ret = dist[i][j];
        }
    }
    return ret;
}

int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    sdd(n, m);    
    bool ok = true;
    rep(i, 0, n){
        ss(g[i]);
        rep(j, 0, m){
            if(g[i][j] == 'W') continue;
            ok = false;
        }
    }
    if(ok){
        puts("0");
        return 0;
    }
    int ans = 0x3f3f3f3f;
    rep(i, 0, n){
        rep(j, 0, m){
            rep(ii, 0, n) rep(jj, 0, m) dist[ii][jj] = 0x3f3f3f3f;
            int now = dijk(i, j);
            if(now < ans) ans = now;
        }
    } 
    pd(ans);
    return 0;
}
/*


*/

9 I - A Tide of Riverscape CodeForces - 989B

9.1 题目大意

给定一个长度为n的01字符串，’.’位置你可以选择填0或者1,

问是否存在一个字符串，满足不以p为循环节

9.2 解题思路

我们只需找到一个位置，它的下p个位置，有可能与这个位置不同

有以下几种情况

此位置是1，它的下p个位置是0

此位置是0，它的下p个位置是1

此位置或者它的下p个位置是’.’

均可满足题意

将对应位置填成相反的数字，其余位置随便填即可

如果不存在这样的位置，即不存在满足题意的字符串

9.3 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
/* ***********************************************
Author        :linxi
Created Time  :2019年02月06日 星期三 21时31分54秒
File Name     :G.cpp
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <bits/stdc++.h>
using namespace std;
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d%d",&n,&m)
#define sddd(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d", n, m)
#define pld(n) printf("%lld\n", n)
#define pldd(n,m) printf("%lld %lld\n", n, m)
#define sld(n) scanf("%lld",&n)
#define sldd(n,m) scanf("%lld%lld",&n,&m)
#define slddd(n,m,k) scanf("%lld%lld%lld",&n,&m,&k)
#define sf(n) scanf("%lf",&n)
#define sff(n,m) scanf("%lf%lf",&n,&m)
#define sfff(n,m,k) scanf("%lf%lf%lf",&n,&m,&k)
#define ss(str) scanf("%s",str)
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define mm(a,n) memset(a, n, sizeof(a))
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair()
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int maxn = 3e5 + 5;
//head
char s[maxn];
int cnt[5];
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    ss(s); int len = strlen(s);
    int tot = 0;
    rep(i, 0, len){
//        printf("%d %d\n", i - 1, tot);
//        rep(j, 0, 3){
//            printf("%c %d\n", j + 'A', cnt[j]);
//        }
        if(tot == 3){
            puts("Yes");
            return 0;
        }
        if(s[i] != '.'){
            int& now = cnt[s[i] - 'A']; 
            if(now == 0) ++tot;
            ++now;
        }
        if(i < 3 || s[i - 3] == '.') continue;
        int& lst = cnt[s[i - 3] - 'A'];
        --lst;
        if(lst == 0) --tot;
    }
    if(tot == 3){
        puts("Yes");
        return 0;
    }
    puts("No");
    return 0;
}
/*


*/