题意:用左图的图形去填充 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; } return 0; }
|
题意:一个图 *
代表非空,.
代表空,如果图中非空的点是一个连通图并且为十字架型(从一个点向四个方向延伸)就是 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; return 0; }
|
题意:定义“优美的歌词”如下:
- 由两行四个单词组成,每行两个,用空格隔开
- 第一行第一个单词的元音数等于第二行第一个单词的元音数
- 第一行第二个单词的元音数等于第二行第二个单词的元音数
- 每行的最后一个出现的元音相同
给定 n 个单词,保证每个单词含有至少一个元音。每个输入的单词只能使用一次,重复输入按输入次数记。请确定最大可以构造多少段这样的歌词并依次输出
思路:没什么好方法,将所有的单词分为两组,一组是元音数相同且末尾元音相同的单词对,另一组是仅仅是元音数相同的单词对,记第一组大小为 cnt1
,第二组为 cnt2
,如果 cnt1<=cnt2
,那么最多构造 cnt1
段歌词,但是若是 cnt1>cnt2
,让多出来的 cnt1
平均分给 cnt2
还可能构造更多的歌词,剩下的就是模拟了,传说中的脑力不够手指来凑,需要用到两个 vecetor
和 pair
巴拉巴拉一大堆 😵
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; } 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; } return 0; }
|
题意:给定一个无根树,请你找出一个树根使得其所有子树的度数都相同,若果有多个答案输出任意一个,没有输出 -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(); return 0; }
|