fuck
Atcoder ABC394游记
A.22222
题目描述
给你一个字符串，把所有非2字符删掉并输出。
思路
感觉不用讲
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int cnt = 0;
cin >> s;
for (int i = 0; i < s.length(); i++) {
cnt += (s[i] == '2');
}
while (cnt--) {
cout << 2;
}
return 0;
}
|
B.cat
题目描述
给你N个字符串，把他们按照长度从小到大排序，然后从前到后拼起来，输出。
思路
感觉不用讲
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include<bits/stdc++.h>
using namespace std;
bool cmp(const string &a1, const string &b1)
{
return a1.length() < b1.length();
}
int main()
{
vector<string> v;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string tp;
cin >> tp;
v.push_back(tp);
}
sort(v.begin(), v.end(), cmp);
for (int i = 0; i < n; i++) {
cout << v[i];
}
return 0;
}
|
C.Debug
题目描述
给你一个字符串S。
重复进行这个操作直到S中不包含字串WA：
把字符串最左边的WA改成AC
思路
每次操作的时候看一下会不会产生新的WA，然后把位置记一下就好了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| #include<bits/stdc++.h>
using namespace std;
int main()
{
string s;
int cnt = 0;
cin >> s;
for (int i = 0; i < s.length(); i++) {
cnt += (s[i] == '2');
}
while (cnt--) {
cout << 2;
}
return 0;
}
|
D.Colorful Bracket Sequence
题目描述
给你一个字符串S，只包含’(’,’)’,’[’,’]’,’<’,’>’。
一个字符串T被称为彩色括号序列，则它满足这些条件：
可以通过若干次下面的操作把T变成一个空字符串：
- 如果T存在’()‘或’<>‘或’[]'的字串，选择其中一个并删掉。
- 如果删除的子字符串在T的开头或者结尾，其余部分就会成为新的T.
- 否则，将删除后的子字符串之前的部分与删除的子字符串的部分连接起来，并成为新的T。
判断S是不是彩色括号序列。
思路
其实你读懂题之后就是个括号匹配问题。
代码
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
| #include<bits/stdc++.h>
using namespace std;
string s;
int main(){
cin >> s;
stack<char> st;
bool flag = 1;
for (int i = 0; i < s.length(); i++){
char c = s[i];
if(c=='(' || c=='[' || c=='<'){
st.push(c);
} else {
if(st.empty()){
flag = 0;
break;
}
char tp = st.top();
st.pop();
if((c==')' && tp!='(') ||
(c==']' && tp!='[') ||
(c=='>' && tp!='<')){
flag = 0;
break;
}
}
}
if(!st.empty()) {
flag = 0;
}
cout << (flag ? "Yes" : "No");
return 0;
}
|
E.Palindromic Shortest Path
题目描述
我们有一个有N个顶点的有向图，编号为1,2,...N。
关于边的信息由N2个字符C1,1,C1,2,...,C1,N,C1,N,C2,1,...,CN,N给出。这里，Ci,j表示编号为i的顶点和编号为j的顶点之间的一条边，如果为’-'表示它们之间没有边，否则则为它们边上的标签。
对于每个对于(i,j)满足1≤i,j≤n，输出这个问题：
从顶点i到顶点j的所有路径，其边缘形成了一个回文，最短路径的长度是多少？如果不存在，请输出-1。
思路
第一眼f比e简单结果树形dp写了半个小时写挂了，结果写e，感觉是弗洛伊德有感觉是BFS，结果又写半个多小时的双向BFS最后喜提AC35 WA23 时间不够实在调不出来了。
(什么？你们都是用换根dp做f的？？？)
后来赛后写了半天终于肝出来了正确的！！！
我们定义fi,j为(i,j)的答案，所以fi,i就等于零。对于所有有边的(i,j)，他们之间就那条边就完全可以满足，所以答案就是1。
那我们怎么转移呢？我们知道，回文数就是中间向两边同时增加两个相同的字符构成的。
所以按照这种思路我们就可以考虑转移了，所以对于每个已经确定答案的(i,j)，我们就可以枚举扩展出去的起点和终点，如果起点和i与终点和j都存在边并且字符相同，我们就可以把这个中心往外扩展，转移答案。
我们知道N最大到100，所以我们用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
| #include<bits/stdc++.h>
using namespace std;
int n;
char edges[111][111];
int f[111][111];
int main()
{
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> edges[i][j];
}
}
memset(f, -1, sizeof(f));
queue<pair<int, int>> que;
for (int i = 1; i <= n; i++) {
f[i][i] = 0;
que.push({i, i});
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i != j && edges[i][j] != '-'){
f[i][j] = 1;
que.push({i, j});
}
}
}
while (que.size()) {
int x = que.front().first;
int y = que.front().second;
que.pop();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (edges[i][x] != '-' && edges[y][j] != '-' && edges[i][x] == edges[y][j] && f[i][j] == -1) {
f[i][j] = f[x][y] + 2;
que.push({i, j});
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << f[i][j] << ' ';
}
cout << '\n';
}
return 0;
}
|
死因
我对着以前的代码干瞪眼了114514年之后，终于找到了问题！
我们初始化f数组的时候有的是0有的是1，为了保证答案尽量小，我们bfs要尽量先处理0的那类的。
死就死在这里了！！！我原本代码是类似这种写法
1
2
3
4
5
6
7
8
9
10
11
| for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
f[i][j] = 0;
que.push({i, j});
} else if (edges[i][j] != '-'){
f[i][j] = 1;
que.push({i, j});
}
}
}
|
这个代码没有把初始化为0和1给分开，所以处理的顺序根本不是正确的！这个水样例根本看不出来，简直就是歌姬！！！FUCK
总结
洛谷是骗人的，说好了今天中吉呢？
哦，今天真的掉大分了
