算法学习专栏——Codeforces——Codeforces Round 934(Div.2)

EducationalCodeforcesRound163

A：Special Characters

Problem - A - Codeforces

思路

​ 这道题目有一个思路其实就是一个字：猜。通过枚举的办法得出一个结论：如果可以构造出这种字符串，那么就这个n一定是一个偶数，具体构造方式可以随意指定一种方式，本人的方式为：AAB为一组。

​ 第二种得出结论的思路就是贡献法：由题意可知，1个相同的连续段都只能贡献2个特殊字符，其他没有任何情况可以共享特殊字符，因此最后的特殊字符数量只可能为2k**(k是连续序列的段数)**，如此特殊字符数量只能为偶数

代码（构造 + 思维）

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
#include <iostream>
#include <algorithm>

using namespace std;
int T;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        if (n % 2 == 0){
            cout << "YES\n";
            for (int i = 1; i <= n * 3 / 2 - 1; i ++) {
                if (i % 3 == 1) cout << "A";
                else if (i % 3 == 2) cout << "A";
                else cout << "B";
            }
            cout << '\n';
        } else {
            cout << "NO\n";
        }
    }
    // (n + 1) / 3 * 2 = k * 3 / 2 - 1
    // }
    // 1 - 0
    // 2 - 2
    // 3 - 2
    // 4 - 2
    // 5 - 4
    // 6 - 4
    // 7 - 4
    // 8 - 6
    // 9 - 6
    // 10 - 6
    // 11 - 8
    // AABAABAABAABAA
    return 0;
}

B：Array Fix

Problem - B - Codeforces

代码（贪心+模拟）

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010;
int a[N];
int t, n;

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin >> t;
    while (t--) {
        int n, flag = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = n; i > 1; i--) {
            if (a[i - 1] <= a[i]) continue;
            string s = to_string(a[i - 1]);
            int len = s.length();
            for (int j = 0; j < len - 1; j++) {
                if (s[j + 1] < s[j]){
                    flag = 1;
                    break;
                }
            }
            if (s[len - 1] - '0' > a[i]) flag = 1;
            a[i - 1] = s[0] - '0';
            if(flag){
                cout << "NO\n";
                break;
            }
        }
        if (!flag) cout << "YES\n";
    }


    return 0;
}

C：Arrow Path

Problem - C - Codeforces

思路

思路一：BFS是这道题目最容易想到的一种思路了，然后就是模拟一下你的走法就OK了，难度不大，但是速度比较慢，630ms左右。但是可以优化，模拟思维更佳。

思路二：本人并没有想到，后面看到了别人代码时才发现的方法：贪心思路。其实你可以设想一下，如果你能够到达当前位置的右边，是不是至少需要右边的位置的2个位置至少有一个是”>”的方向，否则就会向左走从而出现死循环。

代码一（BFS）

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
// 630ms
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

#define x first
#define y second
using namespace std;

const int N = 2e5 + 10;
typedef pair<int, int> PII;
int a[3][N];
int vis[3][N];

bool bfs(int n) {
    memset(vis, 0, sizeof vis);
    int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
    int k = 1;
    queue<PII> q;
    q.push({1, 1});
    while(q.size()) {
        auto t = q.front();
        int x1 = t.x, y1 = t.y;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];
            if (x2 < 3 && x2 > 0 && y2 < n + 1 && y2 > 0 && vis[x2][y2] == 0) {
                vis[x2][y2] = 1;
                y2 += a[x2][y2];
                if (y2 <= 0 && y2 >= n + 1 || vis[x2][y2] == 1) continue;
                q.push({x2, y2});
                vis[x2][y2] = 1;
            }
        }

    }
    return vis[2][n];
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++) {
                char c;
                cin >> c;
                if (c == '>') a[i][j] = 1;
                else a[i][j] = -1;
            }
        }
        if (bfs(n)) cout << "YES\n";
        else cout << "NO\n";
    }
    
    return 0;
}


// 78ms
#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<string> g(3);
    vector<vector<int>> dp(6, vector<int>(n + 10, 0));
    for (int i = 1; i <= 2; i++)
    {
        cin >> g[i];
        g[i] = ' ' + g[i];
    }
    dp[1][1] = 1;
    for (int j = 1; j <= n; j++)
    {
        for (int i = 1; i <= 2; i++)
        {
            if (i == 1)
            {
                if (g[i + 1][j] == '>')
                {
                    dp[i + 1][j + 1] |= dp[i][j];
                }
                else
                {
                    dp[i + 1][j - 1] |= dp[i][j];
                }
                if (g[i][j + 1] == '>')
                {
                    dp[i][j + 2] |= dp[i][j];
                }
            }
            else
            {
                if (g[i - 1][j] == '>')
                {
                    dp[i - 1][j + 1] |= dp[i][j];
                }
                else
                {
                    dp[i - 1][j - 1] |= dp[i][j];
                }
                if (g[i][j + 1] == '>')
                {
                    dp[i][j + 2] |= dp[i][j];
                }
            }
        }
    }
    if (dp[2][n])
    {
        puts("YES");
    }
    else
    {
        puts("NO");
    }
}
 
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

代码二（贪心思路）

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
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
 
void solve() 
{
	int n, flag = 0;
	string s1, s2;
	cin >> n >> s1 >> s2;
	for(int i = 0;i < n - 1;i ++) {
		if(i % 2 == 1 && s1[i] == '<' && s2[i + 1] == '<') {
			flag = 1;
			break;
		} 
		else if(i % 2 == 0 && s2[i] == '<' && s1[i + 1] == '<') {
			flag = 1;
			break;
		}
	}
	if(flag == 0) cout << "YES" << endl;
	else cout << "NO" << endl;
} 
 
signed main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	while(t --) {
		solve();
	}
	return 0;
}

D：Tandem Repeats?

Problem - D - Codeforces

代码

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
#include <iostream>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    string s;
    cin >> s;
    int n = int(s.size());
    int ans = 0;
    for (int len = n / 2; len >= 1; len--) {
      int t = 0;
      for (int i = 0; i + len < n; i++) {
        if (s[i] == s[i + len] || s[i] == '?' || s[i + len] == '?') {
          t ++;
          if (t == len) {
            ans = max(ans, len);
            break;
          }
        } else {
          t = 0;
        }
      }
    }
    cout << 2 * ans << '\n';
  }
  return 0;
}

E：Clique Partition

Problem - E - Codeforces

思路

$$
\begin{flalign}
&这道题目的思路是非常经典的贪心思路类型的题目。\\
&i和j相距越近，abs(i-j)越小，所以应该是一个一个连续的区间中的数为一个团。\\
&(1,2,3,4,5,6),k=5 \\
&abs(1-6)=5,a_1\neq a_2,因此相距5的两个位置数是不可能在1个团里面的。\\
&由此我们就可以如此来进行枚举abs(i-j)<k的数在一个团里面。\\
&当abs(i-j)变大，abs(a_i-a_j)就应该尽可能小才可以，反之大一点无所谓。\\
&比如对于(1,5)，abs(1-5)=4,要想成立就必须abs(a_1-a_5)=1才符合题意。\\
&还需要注意的是你在枚举的过程中可能会出现k不足的情况，所以应该进行一个min(k,n - i + 1)操作&\\
\end{flalign}
$$

代码（dfs + 贪心 + 思维）

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
#include <iostream>

using namespace std;
const int N = 110;
int ans;
int a[N];
int c[N];

void dfs(int i, int n, int k, int id) // i表示从上一团的下一个点出发，n表示顶点数量，k表示限制，id表示当前属于第几团
{
    if (i > n)
    {
        return;
    }
    ans = id; // 当前团中的点数
    int num = min(n - i + 1, k); // 记录我们以 num 个顶点作为一团
    int cur = i; // 记录枚举点开始位置
    // 1 2 3 4
    // 4 3 2 1
    for (int j = i + num / 2 - 1; j >= i; j--)
    {
        a[j] = cur++;
        c[j] = id;
    }
    // 5 6 7 8
    // 8 7 6 5
    for (int j = i + num - 1; j >= i + num / 2; j--)
    {
        a[j] = cur++;
        c[j] = id;
    }
    dfs(i + num, n, k, id + 1);
}

void solve()
{
    int n, k;
    cin >> n >> k;
    dfs(1, n, k, 1);
    for (int i = 1; i <= n; i++)
    {
        cout << a[i] << " \n"[i == n];
    }
    cout << ans << "\n";
    for (int i = 1; i <= n; i++)
    {
        cout << c[i] << " \n"[i == n];
    }
}

int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

后面的题目不是本人可以驾驭的了，See You………!!!!