A.Filling Shapes—签到

题意:用左图的图形去填充 3*n 的图形,要求不能重叠不能留有空隙也不能超出边界,问填充的方法有几种

思路:左图的图形每两个可以填充一个 3*2 的就行并且有两种填法,所有对于 3*n 图形如果 n 为奇数没有填法,否则的话就有 2n/2 种方法,注意因为 n 最大为 60 所以答案会爆 longlong

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
while (cin >> n) {
if (n % 2 == 0)
cout << (ll)pow(2, n / 2) << endl;
else
cout << 0 << endl;
}
// system("pause");
return 0;
}

B.Plus from Picture—暴力+DFS

题意:一个图 * 代表非空,. 代表空,如果图中非空的点是一个连通图并且为十字架型(从一个点向四个方向延伸)就是 YES

思路:先找到一个出发点,然后从此点固定的沿四个方向搜索 * 并将遍历的点变为 .,之后如果没有点再是 * 就是 YES

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 505;

char s[maxn][maxn];

void up(int i, int j) {
s[i][j] = '.';
if (s[i - 1][j] == '*')
up(i - 1, j);
}

void down(int i, int j) {
s[i][j] = '.';
if (s[i + 1][j] == '*')
down(i + 1, j);
}

void left(int i, int j) {
s[i][j] = '.';
if (s[i][j - 1] == '*')
left(i, j - 1);
}

void right(int i, int j) {
s[i][j] = '.';
if (s[i][j + 1] == '*')
right(i, j + 1);
}

void dfs(int i, int j) {
s[i][j] = '.';
up(i - 1, j);
down(i + 1, j);
left(i, j - 1);
right(i, j + 1);
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int h, w;
bool flag=false;
cin >> h >> w;
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
cin >> s[i][j];
for (int i = 1; i <= h; i++) {
for (int j = 1; j <= w; j++)
if (s[i][j] == '*' && s[i - 1][j] == '*' && s[i][j - 1] == '*' && s[i + 1][j] == '*' && s[i][j + 1] == '*') {
dfs(i, j);
flag = true;
goto Loop;
}
}
Loop:
for (int i = 1; i <= h; i++)
for (int j = 1; j <= w; j++)
if (s[i][j] == '*')
flag = false;
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
// system("pause");
return 0;
}

C.Beautiful Lyrics—贪心+模拟

题意:定义“优美的歌词”如下:

  • 由两行四个单词组成,每行两个,用空格隔开
  • 第一行第一个单词的元音数等于第二行第一个单词的元音数
  • 第一行第二个单词的元音数等于第二行第二个单词的元音数
  • 每行的最后一个出现的元音相同

给定 n 个单词,保证每个单词含有至少一个元音。每个输入的单词只能使用一次,重复输入按输入次数记。请确定最大可以构造多少段这样的歌词并依次输出

思路:没什么好方法,将所有的单词分为两组,一组是元音数相同且末尾元音相同的单词对,另一组是仅仅是元音数相同的单词对,记第一组大小为 cnt1,第二组为 cnt2,如果 cnt1<=cnt2,那么最多构造 cnt1 段歌词,但是若是 cnt1>cnt2,让多出来的 cnt1 平均分给 cnt2 还可能构造更多的歌词,剩下的就是模拟了,传说中的脑力不够手指来凑,需要用到两个 vecetorpair 巴拉巴拉一大堆 😵

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;
typedef pair<int, int> P;

string s[maxn];
bool vis[maxn];

struct node {
int num, ch, id; //元音数目和最后末尾的元音字母和单词的id
} p[maxn];

bool cmp(node x, node y) {
if (x.num != y.num) return x.num < y.num;
return x.ch < y.ch;
}

signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
int cnt = 0;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
int alpha = 0, gamma;
char beta;
for (int j = 0; j < s[i].size(); ++j) {
if (s[i][j] == 'a' || s[i][j] == 'e' || s[i][j] == 'i' || s[i][j] == 'o' || s[i][j] == 'u')
++alpha, beta = s[i][j], gamma = i;
}
p[cnt].num = alpha, p[cnt].id = gamma, p[cnt++].ch = beta;
}
sort(p, p + cnt, cmp); //按照指定方式排序好
vector<P> vec1, vec2; //分别存储元音数目相同且末尾元音字母相同,元音相同
for (int i = 1; i < cnt; ++i) { //先找第一组的单词对
if (!vis[i] && !vis[i - 1] && p[i].num == p[i - 1].num && p[i].ch == p[i - 1].ch)
vec1.push_back(P(p[i - 1].id, p[i].id)), vis[i] = vis[i - 1] = 1;
}
vector<node> vc;
for (int i = 0; i < cnt; ++i) //再在剩余的单词中寻找另一组单词对
if (!vis[i]) vc.push_back(p[i]);
sort(vc.begin(), vc.end(), cmp);
memset(vis, 0, sizeof vis);
for (int i = 1; i < vc.size(); ++i) {
if (!vis[i] && !vis[i - 1] && vc[i].num == vc[i - 1].num)
vec2.push_back(P(vc[i - 1].id, vc[i].id)), vis[i] = vis[i - 1] = 1;
}
int cnt1 = vec1.size(), cnt2 = vec2.size();
if (cnt1 > cnt2) { //贪心的平均分让构造的歌词段数最多
int cha = (cnt1 - cnt2) / 2;
for (int i = 0; i < cha; ++i) {
P temp = vec1[cnt1 - 1];
vec1.pop_back();
vec2.push_back(temp);
--cnt1, ++cnt2;
}
}
int ans = min(cnt1, cnt2); //确定答案并输出
cout << ans << endl;
for (int i = 0; i < ans; ++i) {
cout << s[vec2[i].first] << ' ' << s[vec1[i].first] << endl;
cout << s[vec2[i].second] << ' ' << s[vec1[i].second] << endl;
}
// system("pause");
return 0;
}

D.Complete Mirror—树的重心+思维

题意:给定一个无根树,请你找出一个树根使得其所有子树的度数都相同,若果有多个答案输出任意一个,没有输出 -1

思路 参考博客  题目也就是让找到一个答案节点以它为树根其所有子树都是对称的,那么如果这个答案节点有多个子节点那么这个答案就是树的重心,如果这个答案节点有一个子节点,那么这个答案节点到树的重心肯定是一条直线没有分叉,即答案节点和树的重心之间是一条链

  • 先找出图的树的重心并判断是否可以作为答案
  • 再找出和树的重心之间是一条链的节点判断是否可以作为答案,并且对于到树的重心同一个深度的点,我们只需要考虑一次就行(原理不好描述但是画几个图即可得知其正确性)
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 100;

int n;

int ans = 0x3f3f3f3f, rt;
int sz[maxn];

vector<int> G[maxn];
bool vis[maxn];

void dfs_rt(int x, int from) { //树的重心的模板
sz[x] = 1;
int max_part = 0;
for (int nex : G[x]) {
if (nex == from) continue;
dfs_rt(nex, x);
sz[x] += sz[nex];
max_part = max(max_part, sz[nex]);
}
max_part = max(max_part, n - sz[x]);
if (max_part < ans) ans = max_part, rt = x;
}

bool dfs(int x, int from, int depth) {
if (!sz[depth])
sz[depth] = G[x].size();
else if (G[x].size() != sz[depth])
return 0;
for (int nex : G[x]) {
if (nex == from) continue;
if (!dfs(nex, x, depth + 1)) return 0;
}
return 1;
}

bool check(int x) { //判断树是否对称
memset(sz, 0, sizeof sz);
return dfs(x, 0, 0);
}

int line(int x, int from, int depth) { //判断当前的点到树的重心是否是一条链,是的话返还深度
if (x == rt) return depth;
if (G[x].size() > 2) return 0;
for (int nex : G[x]) {
if (nex == from) continue;
return line(nex, x, depth + 1);
}
}

void solve() {
scanf("%d", &n);
int u, v;
for (int i = 1; i < n; ++i) { //无向图存边
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs_rt(1, 0); //先寻找树的重心
if (check(rt)) {
printf("%d\n", rt); //判断树的重心是否为答案
return;
}
for (int i = 1; i <= n; ++i) { //在树的重心的子链上的点寻找答案
if (G[i].size() == 1) { //可能在链上的单
int d = line(i, 0, 0);
if (d && !vis[d]) { //判断当前深度的点是否已经作为答案过
vis[d] = 1;
if (check(i)) {
printf("%d\n", i); //尝试用当前点作为答案
return;
}
}
}
}
printf("-1\n");
}

signed main() {
solve();
// system("pause");
return 0;
}