题面:http://codeforces.com/contest/1131/problems
上 蓝 了！
嗨森，A了四道题。除了A题5分钟，其他都是20分钟左右过一题。
而且都是1A。由于都是做出来的题，简单写题解。赛后补D
A. Sea Battle
题意
给定两个长方形，要你求出包裹它的面积。如下图绿色所示。
解法
直接模拟就好了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
ll w1, h1, w2, h2;
cin >> w1 >> h1 >> w2 >> h2;
ll ans = 0;
ans += w1 + 2;
ans += h1 + h2 + 1;
ans += w2 + 1;
ans += h2;
ans += (w1 - w2);
ans += h1;
cout << ans << endl;
return 0;
}
B. Draw!
题意
给定n个时刻的比分，求在比赛过程中最多会出现多少次平局。
解法
首先考虑如果只有一个比分$m:n$, 中间会出现的平局次数最多为$min(m, n) + 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
using namespace std;
const int maxn = 2e5 + 10;
struct pii
{
int l, r;
};
pii a[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i].l >> a[i].r;
int mmin = min(a[0].l, a[0].r), mmax = max(a[0].l, a[0].r);
int cnt = mmin + 1;
int p;
if(a[0].l < a[0].r)
p = 0;
else
p = 1;
for(int i = 1; i < n; i++)
{
if(p == 0)
{
if(a[i].l >= mmax)
{
cnt += min(a[i].l, a[i].r) - mmax + 1;;
if(a[i - 1].l == a[i - 1].r)
cnt--;
if(a[i].l < a[i].r)
p = 0;
else
p = 1;
}
mmax = max(a[i].l, a[i].r);
mmin = min(a[i].l, a[i].r);
}
else
{
if(a[i].r >= mmax)
{
cnt += min(a[i].l, a[i].r) - mmax + 1;
if(a[i - 1].l == a[i - 1].r)
cnt--;
if(a[i].l < a[i].r)
p = 0;
else
p = 1;
}
mmax = max(a[i].l, a[i].r);
mmin = min(a[i].l, a[i].r);
}
}
cout << cnt << endl;
return 0;
}
C. Birthday
题意
给定$n$个数，要求你构造一个序列。使得最大的$| a_i - a_{i+1}|$最小(包含$|a_n - a_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
using namespace std;
const int maxn = 1e4 + 10;
int a[maxn];
int seq[maxn];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n, greater<int>());
seq[n / 2] = a[0];
int ptr = 1;
for(int i = 1; i <= n / 2; i++)
{
seq[n / 2 - i] = a[ptr++];
if(n / 2 + i < n)
seq[n / 2 + i] = a[ptr++];
}
int ans = -1;
for(int i = 0; i < n; i++)
cout << seq[i] << ' ';
cout << endl;
// ans = max(ans, abs(seq[i] - seq[(i + 1) % n]));
// cout << ans << endl;
return 0;
}
D. Gourmet choice
题意
给定一个$n \times m$的矩阵，$a_{ij}$分别可能是$>, =, <$三种
分别表示第一天的第$i$道菜和第二天的第$j$道菜的好吃关系程度。
现在需要你用”美味度”来刻画这两天每一道菜。
若存在输出YES并给出美味度，否则输出NO
解法
相同的点用并查集进行缩点，然后拓扑排序
如果存在拓扑序则输出，否则输出NO
tips：以后遇到有大小关系的题目可以试着想想拓扑序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
86
87
88
using namespace std;
const int maxn = 2e3 + 10;
vector<int> g[maxn];
int deg[maxn];//入度
int par[maxn];
char s[maxn][maxn];
int res[maxn];
int getf(int node)
{
if(par[node] == node)
return node;
return par[node] = getf(par[node]);
}
void unite(int a, int b)
{
a = getf(a);
b = getf(b);
par[a] = b;
}
void add_edge(int a, int b)
{
g[a].push_back(b);
deg[b]++;
}
void init(int n)
{
for(int i = 0; i <= n; i++)
par[i] = i;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++)
cin >> s[i];
init(n + m);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
if(s[i][j] == '=')
unite(i, n + j);
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(s[i][j] == '<')
add_edge(getf(i), getf(n + j));
else if(s[i][j] == '>')
add_edge(getf(n + j), getf(i));
}
for(int i = 0; i < n + m; i++)
add_edge(n + m, getf(i));
memset(res, -1, sizeof(res));
res[n + m] = 0;
queue<int> q;
q.push(n + m);
while(q.size())
{
int u = q.front();
q.pop();
for(auto v: g[u])
{
res[v] = max(res[v], res[u] + 1);
if(--deg[v] == 0)
q.push(v);
}
}
for(int i = 0; i < n + m; i++)
{
if(res[getf(i)] == -1 || deg[getf(i)] != 0)
{
cout << "NO" << endl;
return 0;
}
}
cout << "YES" << endl;
for(int i = 0; i < n; i++)
cout << res[getf(i)] << ' ';
cout << endl;
for(int i = 0; i < m; i++)
cout << res[getf(n + i)] << ' ';
cout << endl;
return 0;
}
F. Asya And Kittens
题意
有$n$个房间每个房间里都有一只猫，一开始这n个房间都是用门隔开的。
然后每一天都会有一只猫和另一只猫成为朋友，那么这两个房间间的门就会被打开。
打开后两个房间就会联通，看作是一个房间。
现在给定每天的成为朋友的两只猫，让你求出一个初始房间排列可以满足这个顺序。
解法
并查集。
每个点用一个vector进行维护其房间里当前的人。
每次读入一个点对，就将其用并查集合并。
房间人数少的点向房间人数多的点连边，并且将人数少vector合并至人数多的vector
最后输出即可。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
using namespace std;
const int maxn = 2e5 + 10;
struct node{
int a, b;
};
int par[maxn];
vector<int> pp[maxn];
int F(int node)
{
if(par[node] == node)
return node;
return par[node] = F(par[node]);
}
void unite(int a, int b)
{
a = F(a);
b = F(b);
if(pp[a].size() > pp[b].size())
{
par[b] = a;
for(auto idx: pp[b])
pp[a].push_back(idx);
pp[b].clear();
}
else{
par[a] = b;
for(auto idx: pp[a])
pp[b].push_back(idx);
pp[a].clear();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i <= n; i++)
{
par[i] = i;
pp[i].push_back(i);
}
for(int i = 1; i < n; i++)
{
int a, b;
cin >> a >> b;
unite(a, b);
}
for(auto idx: pp[F(1)])
cout << idx << ' ';
cout << endl;
return 0;
}