Blackops

初心易得，始终难守

0%

CF #485 Div.2题解

发表于 更新于 分类于 ，

A.Infinity Gauntlet

水题。

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
map<string, string>st;

int main(void)
{
    st["purple"] = "Power";
    st["green"] = "Time";
    st["blue"] = "Space";
    st["orange"] = "Soul";
    st["red"] = "Reality";
    st["yellow"] = "Mind";
    int n;
    sf(n);
    string s;
    while (n--)
    {
        cin >> s;
        st[s] = "";
    }
    int sz =  0;
    for (auto &x : st)
        if (x.second != "")
            ++sz;
    printf("%d\n", sz);
    for (auto &x : st)
        if (x.second != "")
            printf("%s\n", x.second.c_str());
    return 0;
}

B.High School: Become Human

给定整数$x、y$，求$x^y$和$y^x$的大小关系，首先肯定用log函数取一下对数，然后再设稍微小一点的eps比较一下即可。这里注意用long double提高一下精度，double会出现一些奇奇怪怪的问题。

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
typedef long double LF;
const lf eps = 1e-15;
LF a, b;

int main(void)
{
    while (cin >> a >> b)
    {
        LF xx = b * log10(a), yy = a * log10(b);
        if (xx == yy)
            puts("=");
        else
            puts(xx > yy ? ">" : "<");
    }
    return 0;
}

C.Three displays

题意就是给定长度为$n$的数列$S$和$C$，求三个数满足$i \lt j \lt k，S_i \lt S_j \lt S_k$的情况下$C_i + C_j + C_k$的最小值，对于这种三元之间的关系问题可以考虑枚举中间那个数来优化复杂度至$O(n ^ 2)$。

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 3010;
int n, s[N];
ll c[N];

int main(void)
{
    int i, j;
    sf(n);
    for (i = 1; i <= n; ++i)
        sf(s[i]);
    for (i = 1; i <= n; ++i)
        sfl(c[i]);
    ll inf = 1ll << 60;
    ll ans = inf;
    for (i = 1; i <= n; ++i)
    {
        ll l = inf, r = inf;
        for (j = 1; j < i; ++j)
        {
            if (s[j] < s[i])
                l = min(l, c[j]);
        }
        for (j = i + 1; j <= n; ++j)
        {
            if (s[j] > s[i])
                r = min(r, c[j]);
        }
        if (l != inf && r != inf)
            ans = min(ans, l + r + c[i]);
    }
    printf("%lld\n", ans == inf ? -1ll : ans);
    return 0;
}

D.Fair

题意就是给定$n$个城市和$m$条边权为$1$的无向边，有$k$种商品，每个城市一开始已有一种商品$a_i$，求至少个其他城市的人带自己城市的商品到第$i$个城市，使得城市$i$收集到至少$s$种商品的最小花费。

由于商品的种类数最多$100$个，因此可以考虑已商品为点，枚举商品时把具有当前商品的城市的花费设为$0$，其他为$ +\infty$，做$k$次多源BFS，即用$dis[i][j]$表示运送第$j$种商品到第$i$个城市的最小花费。然后每个$dis[i]$取前$s$小个花费相加即可。

这里有个小优化技巧，求数组的前k大可以用nth_element(begin, begin + k, end)这个函数，而不用每次都sort

代码：

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
#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb push_back
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
int n, m, k, s, a[N], d[N];

struct edge
{
    int to, nxt;
    edge() {}
    edge(int _to, int _nxt): to(_to), nxt(_nxt) {}
} E[N << 1];
int head[N], tot;
vector<int> dis[N];

void init()
{
    clr(head, -1);
}
void add(int s, int t)
{
    E[tot] = edge(t, head[s]);
    head[s] = tot++;
    E[tot] = edge(s, head[t]);
    head[t] = tot++;
}
void bfs(int c)
{
    queue<int>Q;
    clr(d, INF);
    for (register int i = 1; i <= n; ++i)
        if (a[i] == c)
            d[i] = 0, Q.push(i);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for (register int i = head[u]; ~i; i = E[i].nxt)
        {
            int &v = E[i].to;
            if (d[v] > d[u] + 1)
            {
                d[v] = d[u] + 1;
                Q.push(v);
            }
        }
    }
    for (register int i = 1; i <= n; ++i)
        dis[i].pb(d[i]);
}
int main(void)
{
    init();
    int i, x, y;
    sf(n), sf(m), sf(k), sf(s);
    for (i = 1; i <= n; ++i)
        sf(a[i]);
    for (i = 0; i < m; ++i)
    {
        sf(x), sf(y);
        add(x, y);
    }
    for (i = 1; i <= k; ++i)
        bfs(i);
    for (i = 1; i <= n; ++i)
    {    
        nth_element(dis[i].begin(), dis[i].begin() + s, dis[i].end());
    	printf("%d%c", accumulate(dis[i].begin(), dis[i].begin() + s, 0), " \n"[i == n]);
    }
    return 0;
}

E.Petr and Permutations

题意就是存在一个长度为$n$的初始排列，Petr会对一个排列做$3n$次两两元素随机交换，而Um_nik会做$7n + 1$次，现给定排列后的结果，求是Petr做的还是Um_nik做的。

由于题目是结果唯一的，那就是符合所有特殊情况，考虑一种特殊情况——他们两个人运气够好，使得相邻的两次交换总是互相抵消，而交换元素位置会使得逆序数的奇偶发生改变（一开始的初始序列逆序数为$0$），逆序数嘛BIT搞搞，注意开long long就好。

那么只要看交换次数是奇数还是偶数就行了。因此分类讨论一下

  1. 当$n$为奇数时，$3n$为奇数，$7n + 1$为偶数，如果逆序数是奇数则肯定是Petr，否则为Um_nik
  2. 当$n$为偶数时，$3n$为偶数，$7n + 1$为奇数，如果逆序数是奇数则肯定是Um_nik，否则为Petr

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 1e6 + 7;
int n, i, a[N], T[N];

void add(int k, int v)
{
    while (k <= n)
    {
        T[k] += v;
        k += (k & -k);
    }
}
int sum(int k)
{
    int w = 0;
    while (k)
    {
        w += T[k];
        k -= (k & -k);
    }
    return w;
}
int main(void)
{
    sf(n);
    int i;
    ll w = 0;
    for (i = 1; i <= n; ++i)
    {
        sf(a[i]);
        w += ((ll)(i - 1) - sum(a[i]));
        add(a[i], 1);
    }
    if (n & 1)
        puts(w & 1 ? "Petr" : "Um_nik");
    else
        puts(w & 1 ? "Um_nik" : "Petr");
    return 0;
}

F.AND Graph

题意就是给你$n、m$，表示有$m$个数大小在$[0, 2 ^ n - 1]$之间，如果有两个数$a \& b = 0$，那么这两个数之间有一条无向边，求这$m$个数最终分成几个连通块。
自己YY了很久没调出来滚去看题解了。

  1. 显然一个数本身可以和其补码相连；
  2. 补码的任意为$0$的位置可以改为$1$，因为这样再做一次补码后该位会变回$0$，不会改变按位与为$0$的结果；
  3. 补码可以随时和补码的补码相连。
    这样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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define sfl(x) scanf("%lld", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 1 << 22;
int n, m, a[N], vis[N][2], mx, sz, ins[N];

inline int rs(int x)
{
    return (1 << n) - 1 - x;
}
void dfs(const int &u, const int &flag)
{
    if (vis[u][flag])
        return ;
    vis[u][flag] = 1;
    if (flag)
    {
        for (int i = 0; i < n; ++i)
        {
            if (u >> i & 1)
                continue;
            dfs(u | (1 << i), 1);
        }
        if (ins[rs(u)])
            dfs(rs(u), 0);
    }
    else
        dfs(u, 1);
}
int main(void)
{
    sf(n), sf(m);
    mx = 1 << n;
    int i;
    for (i = 0; i < m; ++i)
        sf(a[i]), ins[a[i]] = 1;
    for (i = 0; i < m; ++i)
    {
        if (!vis[a[i]][0])
        {
            ++sz;
            dfs(a[i], 0);
        }
    }
    printf("%d\n", sz);
    return 0;
}