cf_566_div2

补题地狱

1182A

1182B Plus from Picture 模拟

找出用*组成的十字,而且其它的格必须是.

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
#include <bits/stdc++.h>
using namespace std;
char s[510][510];
int h,w,cnt;
bool vis[510][510],fin;
bool ok(int x,int y) {
return x >= 0 && x < h && y >= 0 && y < w;
}
void check(int i,int j) {
if(i < 1 || i >= h - 1 || j < 1 || j >= w - 1) return;
int x = i + 1,y = j;
if(s[i + 1][j] != '*' || s[i - 1][j] != '*' || s[i][j - 1] != '*' || s[i][j + 1] != '*') return;
while (ok(x,y) && s[x][y] == '*')
{
vis[x][y] = 1;
--cnt;
x++;
}
x = i - 1,y = j;
while (ok(x,y)&& s[x][y] == '*')
{
vis[x][y] = 1;
--cnt;
x--;
}
x = i,y = j - 1;
while (ok(x,y)&& s[x][y] == '*')
{
vis[x][y] = 1;
--cnt;
y--;
}
x = i,y = j + 1;
while (ok(x,y)&& s[x][y] == '*')
{
vis[x][y] = 1;
--cnt;
y++;
}
fin = 1;
--cnt;
}
int main() {
cin>>h>>w;
for(int i = 0; i < h; ++i) {
cin>>s[i];
for(int j = 0; j < w; ++j)
if(s[i][j] == '*') ++cnt;
}

for(int i = 0; i < h; ++i) {
for(int j = 0; j < w; ++j) {
if(!vis[i][j] && s[i][j] == '*')
if(!fin) check(i,j);
}
}
if(!cnt && fin) puts("YES");
else puts("NO");
return 0;
}

1182C Beautiful Lyrics 模拟

就是个大模拟,然而太菜了没写出来…

就是给一堆单词,选四个组成一组。每组有两行,每行两个单词。其中:

所有行中的第一个单词的元音字母数量相同,所有行中第二个单词的元音字母数量相同。

第一行的最后一个元音字母和第二行的最后一个元音字母是相同的。

从所有单词中尽可能的选出四个单词尽可能多的组成这样的一组,然后输出。

首先,虽然原题里没提顺序,那肯定就是顺序不重要,随便配就行。

把所有的单词分成元音字母相同的集合(s1)和元音字母相同且最后一个元音相同的集合(s2)。

每行第二个单词肯定是必须从s2里选,然后它们尽可能的和s1匹配。

如果s1匹配光了,再从s2选四个匹配。

这个map套map的统计方法有点意思,可以学习一下。

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
#include <bits/stdc++.h>
using namespace std;
isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int cnt1(const string& s) {
int cnt = 0;
for(auto &i:s) {
if(isVowel(i)) ++cnt;
}
return cnt;
}
int lastVow(const string& s) {
for(auto i = s.rbegin(); i != s.rend(); ++i) {
if(isVowel(*i)) return *i - 'a';
}
}
int main() {
ios::sync_with_stdio(false);
int n; cin>>n;
vector<string> v(n);
map<int, map<int,vector<int> > > rec;
for(int i = 0; i < n; ++i) {
cin>>v[i];
rec[cnt1(v[i])][lastVow(v[i])].push_back(i);
}
vector<pair<int,int> > r1,r2;
for(auto &same_cnt : rec) {
for(auto & same_v : same_cnt.second) {
while(same_v.second.size() >= 2) {
int s1 = same_v.second.back();
same_v.second.pop_back();
int s2 = same_v.second.back();
same_v.second.pop_back();
r1.push_back({s1,s2});
}
}

vector<int> Re;
for(auto & same_v : same_cnt.second) {
if(same_v.second.size())
Re.push_back(same_v.second.back());
}

while(Re.size() >= 2) {
int s1 = Re.back();
Re.pop_back();
int s2 = Re.back();
Re.pop_back();
r2.push_back({s1,s2});
}
}
vector<pair<int,int> > ans;

while(r1.size() && r2.size()) {
ans.push_back({r2.back().first,r1.back().first});
ans.push_back({r2.back().second,r1.back().second});
r1.pop_back(),r2.pop_back();
}
while(r1.size() >= 2) {
pair<int,int> s1 = r1.back(); r1.pop_back();
pair<int,int> s2 = r1.back(); r1.pop_back();
ans.push_back({s1.first,s2.first});
ans.push_back({s1.second,s2.second});
}
cout<<ans.size() / 2<<endl;
for(auto i : ans) {
cout<<v[i.first]<<" "<<v[i.second]<<endl;
}
return 0;
}

1182D 树的直径 思维题

给定一棵树,求输出任意一个根,使得其所有相同深度的点的度数都相同。

然而虽然解法并不难,但是始终不是很明白,先放一放。虽然不是直接求树的直径,但跟它有联系。

1182E Product Oriented Recurrence 矩阵快速幂

先放一放…