Tinkoff Challenge - Final Round (Codeforces Round #414, rated, Div. 1 + Div. 2)

发表于 | 分类于 | 0
字数统计: 1.4k | 阅读时长 ≈ 6

题面: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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
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$块面积大小相等的部分。需要求出每一部分的高。https://codeforces.com/predownloaded/81/2f/812f82e202c6b817652566904440d771ad4dd7ea.png

解法

其实推个三角公式，算一下就好了。（这篇博客好偷懒哦hhh）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
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。

解法

这道题要注意两点。

  1. 如果有一个点同时连接了超过两个互不相连的点，则不会有满足的方案。
  2. 如果有两个点满足所有与其相连的点的集合相同（包括自己）则这两个点可以打同一个标记

知道这两点后题目就变得可做了起来。首先缩点，将所有相连的点的集合相同的点缩成一个点。这里需要用一个哈希，也算是学到的新东西。
这里的哈希函数是对于点$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
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
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;
}

来发评论吧~
Powered By Valine
v1.5.2