A
原题链接
给定一个\(n\times
m\)的矩阵，有0有1，有两个操作：改变（01互换）相邻的两个竖着的地方，或者两个相邻的横着的地方，问最后是否能全部变成1
根据分析可以发现，只要一开始0的个数是偶数就可以全部变成1
做的时候没有发现www，在执着于什么时候用操作一什么时候用操作二wwwwwww
eg：
11111
11010
01000
对第二行：-> 11100 -> 11111
对第三行：-> 10000 -> 11111
所以只用操作二都可以
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m;
char flag[2010][2010];
signed main(){
cin>>t;
while(t--){
cin>>n>>m;
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>flag[i][j];
if(flag[i][j]=='0') cnt++;
}
}
if(cnt%2==0) puts("Yes");
else puts("No");
}
return 0;
}
|
B
原题链接
每个结点有对应的字母，要求从1开始“走”，顺序走过的每个结点的字典序最大
类似于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
| #include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e6 + 10;
int ne[N], to[N], head[N], idx;
string se = "", s;
void add(int a, int b)
{
ne[idx] = head[a], to[idx] = b, head[a] = idx++;
}
queue<int> q;
bool st[N];
int pro[N];
void bfs(int o)
{
q.push(o);
st[o] = true;
se += s[o - 1];
int k = 1;
while (q.size())
{
int cnt = 0;
char x = 'a' - 1;
while (k)
{
int t = q.front();
q.pop(), k--;
for (int i = head[t]; i != -1; i = ne[i])
{
int j = to[i];
if (s[j - 1] > x) cnt = 0, pro[cnt++] = j, x = s[j - 1];
else if (s[j - 1] == x) pro[cnt++] = j;
}
}
if(x != 'a' - 1)
se += s[pro[0] - 1];
for (int i = 0; i < cnt; i++)
q.push(pro[i]), k++;
}
cout << se;
}
signed main()
{
memset(head, -1, sizeof head);
int n;
cin >> n;
cin >> s;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
add(a, b);
}
bfs(1);
return 0;
}
|
D
原题链接
每个结点对应a b
c中的一个，要求从根开始不回溯遍历，得到字符串abc，k表示可以回溯到开始结点再换条路遍历，最终得到abc即可
利用dfs，建立两个数组，一个存储某个节点之前的abc的个数，一个存储该结点之后abc的个数
对于k == 1情况下为什么要ans -= sum：
f[x][0] * g[x][2]表示的是以x或者x的子节点为'b'结点，出现abc的次数，即不一定是以x为结点'b'，所以直接减去- 然后再利用
s[x] == b/c的情况，精准计算以x为'b'的情况
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
| #include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n, k;
string s;
vector<int> v[N];
int p[10], f[N][10], g[N][10];
int ans;
void dfs(int x, int fa)
{
f[x][s[x] - 'a']++;
g[x][s[x] - 'a']++;
for(auto i: v[x])
{
if(i == fa) continue;
memcpy(f[i], f[x], sizeof(f[x]));
dfs(i, x);
for(int j = 0; j < 3; j++)
g[x][j] += g[i][j];
}
int sum = 0;
if(s[x] == 'b')
sum = f[x][0] * g[x][2];
if(k == 0)
ans += sum;
if(k == 1)
{
ans -= sum;
if(s[x] == 'b')
ans += f[x][0] * p[2];
if(s[x] == 'c')
ans += f[x][1] * p[0];
}
}
signed main()
{
cin >> n >> k >> s;
s = " " + s;
for (int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(int i = 1; i <= n; i++)
p[s[i] - 'a']++;
if(k == 2)
cout << p[0] * p[1] * p[2];
else
{
dfs(1, 0);
cout << ans;
}
return 0;
}
|
