题面:https://codeforces.com/contest/794/problems
A. Bank Robbery
题意
直接模拟。
解法
直接模拟。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
using namespace std;
map<int, int> loc;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a, b, c, n;
cin >> a >> b >> c >> n;
int ans = 0;
for(int i = 0; i < n; i++)
{
int t;
cin >> t;
if(t > b && t < c)
ans++;
}
cout << ans << endl;
return 0;
}
B. Cutting Carrot
题意
给定一个底为1高为h的三角形。现在给定$h$和$n$，需要将三角形划分为$n$块面积大小相等的部分。需要求出每一部分的高。
解法
其实推个三角公式，算一下就好了。（这篇博客好偷懒哦hhh）1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
const int maxn = 2e5 + 10;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, h;
cin >> n >> h;
double s = h * 1.0 / (2 * n);
for(int i = 1; i < n; i++)
cout << setprecision(10) << sqrt(i * 2 * h * s) << endl;
return 0;
}
C. Naming Company
题意
甲乙两人各有一个长度为$n(n < 3 \cdot 10^5)$的字符串，有两个人要进行博弈。两人每次给出一个字母，可以替换任一字符。甲希望构成的字符串字典序尽可能的小，乙希望字典序尽可能的大。甲先手，两人都会选择最佳策略。最终构成一个长度为$n$的字符串。求最后的字符串。
解法
其实读完题目就知道肯定是个贪心了。
问题在于贪心策略的选取。一开始naive的想法是甲选他最小的字符放在最前面，乙选他最大的字符放在最后面。
但这样贪心是有问题的。比如甲是zzz乙是aaa，显然甲把z放在最后要比放在之前能形成更小的字符串。
所以如果先将两组字符串进行从小到大和从大到小排序。
如果甲中当前最小的大于等于乙中最大的，则甲最小的放在字符串前部。
如果甲中当前最小的小于乙中最大的，则将甲最大的放在字符串后部。
乙的策略同理。
仔细考虑一下，这样满足最优策略。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
using namespace std;
const int maxn = 3e5 + 10;
vector<char> a, b;
char ans[maxn];
int main()
{
char c;
while((c = getchar()) != '\n')
a.push_back(c);
while((c = getchar()) != '\n')
b.push_back(c);
int len = a.size();
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<char>());
int la = 0, lb = 0;
int ra = (len + 1) / 2 - 1, rb = len / 2 - 1;
int l = 0, r = len - 1;
ans[len]= 0;
for(int i = 0; i < len; i++)
{
if(a[la] < b[lb])
{
if(i % 2)
ans[l++] = b[lb++];
else
ans[l++] = a[la++];
}
else
{
if(i % 2)
ans[r--] = b[rb--];
else
ans[r--] = a[ra--];
}
}
cout << ans << endl;
return 0;
}
D. Labelling Cities
题意
给定一个图有$n$个节点$m$条边。现在要对图中的每个点进行标记。要求标记完后满足$|a_i-a_j| \leq 1$当且仅当两个点之间有边相连。输出每个点的标记，若没有满足方案则输出NO。
解法
这道题要注意两点。
- 如果有一个点同时连接了超过两个互不相连的点，则不会有满足的方案。
- 如果有两个点满足所有与其相连的点的集合相同（包括自己）则这两个点可以打同一个标记
知道这两点后题目就变得可做了起来。首先缩点，将所有相连的点的集合相同的点缩成一个点。这里需要用一个哈希，也算是学到的新东西。
这里的哈希函数是对于点$u$所有的与之相连的$v$($v$已经进行了排序)
来找相同点集合的点缩点，然后再重新建图。建完图后判断是否一个点连接另外三个不相连的点，如果有就直接NO。如果没有的话理想条件应该是一条链，看是否存在两个度为1的点确定没有环。然后就通过链首dfs染色就可以啦。做完啦～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
using namespace std;
const int maxn = 3e5 + 10;
vector<int> g[maxn], _g[maxn];
int bas = 1997, col = 1;
int par[maxn], color[maxn];
map<ll, int> q;
vector<int> res[maxn];
ll h[maxn];
ll hsh(int i)//计算哈希值
{
sort(g[i].begin(), g[i].end());
ll v = 0;
for(auto idx: g[i])
v = v * bas + idx;
return v;
}
void dfs(int node, int pre)
{
color[node] = col++;
for(auto idx: _g[node])
{
if(idx == pre)
continue;
dfs(idx, node);
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
g[i].push_back(i);
for(int i = 0; i < m; i++)
{
int u, v; scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 1; i <= n; i++)
h[i] = hsh(i);
int sign = 0;
for(int i = 1; i <= n; i++)
{
if(q[h[i]] == 0)
q[h[i]] = ++sign;
res[q[h[i]]].push_back(i);
}
for(int i = 1; i <= sign; i++)
{
for(auto v: g[res[i][0]])
if(q[h[v]] != i)
_g[i].push_back(q[h[v]]);
sort(_g[i].begin(), _g[i].end());
_g[i].erase(unique(_g[i].begin(), _g[i].end()), _g[i].end());
}
int st = 1;
for(int i = 1; i <= sign; i++)
if(_g[i].size() > 2)
{
puts("NO");
return 0;
}
else if(_g[i].size() == 1)
st = i;
dfs(st, 0);
puts("YES");
for(int i = 1; i <= n; i++)
printf("%d ", color[q[h[i]]]);
putchar('\n');
return 0;
}