Blackops

初心易得，始终难守

0%

CF #485 Div.2题解

发表于 更新于 分类于 ， 阅读次数： 25

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，求xy和yx的大小关系，首先肯定用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<j<k，Si<Sj<Sk的情况下Ci+Cj+Ck的最小值，对于这种三元之间的关系问题可以考虑枚举中间那个数来优化复杂度至O(n2)。

代码：

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种商品，每个城市一开始已有一种商品ai，求至少个其他城市的人带自己城市的商品到第i个城市，使得城市i收集到至少s种商品的最小花费。

由于商品的种类数最多100个，因此可以考虑已商品为点，枚举商品时把具有当前商品的城市的花费设为0，其他为+∞，做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,2n−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;
}