Special Characters
A
题意
给定一个整数 n ，需要建立一个只包含大写字母的、有 n 个特殊字符的字符串。
特殊字符定义：一个字符只与其相邻的一个字符相等。
解题思路
- 第一眼想多了，按题意AAA这样只有2个特殊字符，所以构造如AABBCC这样的字符串才是最佳的。
- 自己想的是AACBBDCC这样，后来想想，感觉真的脑子有点糊了，该加睡了。
- 而因为特殊字符都是成对出现，所以 n 只能是偶数。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n;
cin >> n;
if (n % 2) {
cout << "NO" << endl;
return ;
}
cout << "YES" << endl;
char ch = 'A';
for (int i = 1; i <= n / 2; i ++ ) {
cout << ch << ch;
ch = ch + 1;
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Array Fix
B
题意
给定一个长度为 n 的数组，可以将多位的数字拆成数个个位数。
可以将数组变为非降序数组
解题思路
- 完蛋的开端，wa2+6，太美了。
- 现实自信正着扫，然后wa，然后倒着扫，wa。再然后找到了正解，可是忘了break，一直wa2，笑死了。
从右至左找到第一个左大于右的数对，因为此时左边的数拆成了数个个位数，所以再左的数都应拆分成数个个位数。最后判断即可。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++ ) {
cin >> a[i];
}
int idx = -1;
for (int i = n - 1; i > 0; i -- ) {
if (a[i] < a[i - 1]) {
idx = i - 1;
break;
}
}
if (idx == -1) {
cout << "YES" << endl;
return ;
}
vector<int> v;
for (int i = 0; i <= idx; i ++ ) {
int x = a[i];
if (x >= 10) {
v.pb(x / 10), v.pb(x % 10);
} else {
v.pb(x);
}
}
for (int i = idx + 1; i < n; i ++ ) {
v.pb(a[i]);
}
for (int i = 0; i < v.size() - 1; i ++ ) {
if (v[i] > v[i + 1]) {
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Arrow Path
C
题意
2行n列的网络，每行一个字符串，包含字符 “<” 和 “>” 。
初始从 (1,1)开始，每次移动如下：
- 首先，上下左右移动一格
- 然后根据所在位置的箭头移动
解题思路
- 初见 dp，可是wa2，虽然直觉也感觉不对。(赛后证明确实可以dp，只是自己写错了)
- 找到的题解就是BFS，因为每个格子不会重复经过，所以时间复杂度是线性的。
代码
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
void solve() {
int n;
cin >> n;
vector<string> s(2);
cin >> s[0] >> s[1];
queue<PII> q;
q.push({0, 0});
vector st(2, vector<bool>(n));
while (q.size()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i ++ ) {
int a = x + dx[i], b = y + dy[i];
if (a < 0 || a >= 2 || b < 0 || b >= n) continue;
if (st[a][b]) continue;
if (s[a][b] == '>') b ++ ;
else b -- ;
if (a < 0 || a >= 2 || b < 0 || b >= n) continue;
if (st[a][b]) continue;
st[a][b] = 1;
q.push({a, b});
}
}
if (st[1][n - 1]) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Tandem Repeats?
D
题意
给定一个字符串，由小写字母和问号构成。
需要将问号替换成小写字母，使得串联重复的最长子串长度最大。
串联重复是一个偶数长度回文串。
解题思路
数据范围不大，可以接受O(n^2) ，那就遍历长度和初始点即可。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e6 + 10, inf = 1 << 30;
void solve() {
string s;
cin >> s;
int n = s.size();
int ans = 0;
s = " " + s;
for (int len = 1; len <= n / 2; len ++ ) {
int cnt = 0;
for (int i = 1; i + len <= n; i ++ ) {
if (s[i] == s[i + len] || s[i] == '?' || s[i + len] == '?') {
cnt ++ ;
} else {
cnt = 0;
}
if (cnt == len) {
ans = len;
break;
}
}
}
cout << ans * 2 << endl;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
Clique Partition
E
题意
给定两个数n 和 k 。图中 n 个顶点，编号1到n，初始没有边。
现在要给每个顶点分配一个整数 (1 到 n 的不同整数)，然后对于每一对顶点，如果满足$\vert i - j\vert+\vert a_i-a_j\vert <= k$ ，则需要连边。
现在需要给每个点赋值，使得连通块数量最小。
需要输出每个点的赋值 ，连通块的数量，以及每个点所属的连通块。
解题思路
数据范围很小，注定了dfs爆搜之路()。
如何划分呢。当k=4，那么i =1, j > 4的时候，无论如何赋值都会连边。而边界 i = 1, j = 4的时候，则需要保证值相差很小，例如 3 和 2。
手写几个样例，就能发现最合理的分配：
1 2 3 4
3 4 1 2
- 简单赘述一下，如果两边刚好卡到 k - 1，那么向内，i - j就会减少2，此时 左右的差值可以增加2。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define endl '\n'
#define db double
#define pb push_back
typedef long long ll;
typedef pair<int,int> PII;
const int N = 1e2 + 10, inf = 1 << 30;
int ans;
int a[N];
int c[N];
void dfs(int n, int k, int i, int id) {
if (i > n) {
return ;
}
int cur = i;
int num = min(k, n - i + 1);
ans = id;
for (int j = i + num / 2 - 1; j >= i; j -- ) {
a[j] = cur ++ ;
c[j] = id;
}
for (int j = i + num - 1; j >= i + num / 2; j -- ) {
a[j] = cur ++ ;
c[j] = id;
}
dfs(n, k, cur, id + 1);
}
void solve() {
int n, k;
cin >> n >> k;
dfs(n, k, 1, 1);
for (int i = 1; i <= n; i ++ ) {
cout << a[i] << " \n"[i == n];
}
cout << ans << endl;
for (int i = 1; i <= n; i ++ ) {
cout << c[i] << " \n"[i == n];
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t; cin >> t; while (t -- )
solve();
return 0;
}
