Blackops

初心易得，始终难守

0%

CF #480 Div.2 A B C D E

发表于 分类于 ，

A.Links and Pearls

题意就是给你一个含有$\textbf{O}$和字符$\;—\;$的成环字符串，问你能不能重排一下使得相邻的$\textbf{O}$之间的$\;—\;$的数量相等，显然要相等只要剩余的横杠数量能被$\textbf{O}$均分掉即可，注意特判下没有$\textbf{O}$的情况。

代码：

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
#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 all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#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 = 110;
char s[N];

int main(void)
{
    while (~scanf("%s", s))
    {
        int o = 0, _ = 0;
        int i, len = strlen(s);
        for (i = 0; i < len; ++i)
        {
            if (s[i] == 'o')
                ++o;
            else
                ++_;
        }
        if (o == 0)
            puts("YES");
        else
            puts((_ % o == 0) ? "YES" : "NO");
    }
    return 0;
}

B.Marlin

题意就是给你一个$4\times n$的空地图，放$k$个障碍物，使得从$(1,1)$到$(4,n)$和$(4,1)$到$(1,n)$的最短路数量相同，感觉是个思维题，可以发现肯定不用去考虑具体的最短路数量是多少，而是考虑如何放置这$k$个障碍物使得对两条路线造成的影响相同。

  1. 如果$k$是偶数，显然对称地放即可。
  2. 如果$k$是奇数，
    1. 如果$k \le n-2$，那么显然对称地放到第一行即可。
    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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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 all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#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 = 110;
char s[N][N];

int main(void)
{
    int n, k, i, j;
    while (~scanf("%d%d", &n, &k))
    {
        CLR(s, '.');
        int cnt = k >> 1;
        if (!(k & 1))
        {
            for (i = 0; i < cnt; ++i)
            {
                s[1][i + 1] = '#';
                s[2][i + 1] = '#';
            }
        }
        else
        {
            if (k <= n - 2)
            {
                s[1][n >> 1] = '#';
                for (i = 0; i < (k - 1) / 2; ++i)
                    s[1][(n >> 1) + 1 + i] = s[1][(n >> 1) - 1 - i] = '#';
            }
            else
            {
                int f = 1;
                int g[2] = {1, n - 2};
                for (i = 1; i <= n - 2; ++i)
                    --k, s[1][i] = '#';
                int l = 0, r = 0;
                for (i = 0; i < k; ++i)
                {
                    if (f)
                        s[2][g[f] - r] = '#', ++r;
                    else
                        s[2][g[f] + l] = '#', ++l;
                    f ^= 1;
                }
            }
        }
        puts("YES");
        for (i = 0; i < 4; ++i)
            for (j = 0; j < n; ++j)
                printf("%c%s", s[i][j], j == n - 1 ? "\n" : "");
    }
    return 0;
}

C.Posterized

题意（看了好一会儿才懂）就是给你$n$个颜色用数值$1…256$表示，将他们分配到长度不超过$k$的连续集合中，求最后字典序最小的分配方案。一个分配方案用该连续区间中的任意一个颜色代表（显然优先用最左边的颜色）。

然后感觉这题是个YY题啊，贪心地看看每一个$color_i$往前考虑$k$个位置，贪心地把颜色归靠左的位置去。用并查集判断一下这个颜色是否被归并过，它所在的集合大小是多少，如果还能容纳当前的颜色，当然也是符合条件的。

代码：

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
#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 all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#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, M = 300;
int a[N], belong[N];
int pre[M], sz[M], rev[M];

void init()
{
    for (int i = 0; i < M; ++i)
        sz[i] = 1, pre[i] = i;
}
int fd(int n)
{
    return pre[n] == n ? n : pre[n] = fd(pre[n]);
}
void mg(int a, int b)
{
    a = fd(a), b = fd(b);
    if (a > b)
        swap(a, b);
    if (a != b)
    {
        sz[a] += sz[b];
        sz[b] = 0;
        pre[b] = a;
    }
}
int main(void)
{
    int n, k, i;
    while (~scanf("%d%d", &n, &k))
    {
        init();
        for (i = 0; i < n; ++i)
            scanf("%d", a + i);
        for (i = 0; i < n; ++i)
        {
            if (fd(a[i]) != a[i])
                continue;
            int ch = a[i];
            int fc = fd(a[i]);
            for (int col = a[i]; col >= 0 && col >= a[i] - k + 1; --col)
            {
                int f = fd(col);
                if (f == col && sz[f] + sz[fc] <= k)
                    ch = col;
            }
            for (int col = a[i]; col >= 0 && col >= ch; --col)
                mg(ch, col);
        }
        for (i = 0; i < n; ++i)
            printf("%d%c", fd(a[i]), " \n"[i == n - 1]);
    }
    return 0;
}

D.Perfect Groups

题意就是给你$n$个数，对$n\times (n+1)/2$个子区间都计算出其最小划分的集合数$k_i$，使得子区间被划分之后集合中任意两个数相乘为平方数。

看题解发现解法不难，就是有坑点比较猥琐而且常数比较大的算法容易超时。首先容易想到把数进行质数分解，得到质数底数及其对应指数，显然只要将奇数指数与$1$等价，偶数指数与$0$等价，然后这样每一个数$a_i$可以变换得到新的数$b_i$，然后考虑由这种$b_i$们组成的集合，怎么划分才是最小的，显然要成为平方数只能是双方指数同奇偶性，因此把相等的$b_i$划分到同一个集合中，也就是说这个集合中不同的数就是最小的划分数$k$。那么这样以来就是$O(n^2)$枚举同时维护子区间内不同数的个数，这里需要注意的坑点是如果区间内有$0$且不全为$0$，就不能考虑$0$，因为$0$可以被任意划分。

代码：

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
#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 all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#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 = 5010;

int a[N], ans[N], num[N];
unordered_map<int, int>st;
bitset<N> cnt;

int G(int n)
{
    int neg;
    n < 0 ? neg = -1, n = -n : neg = 1;
    int w = 1;
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            int t = 0;
            while (n % i == 0)
            {
                n /= i;
                t ^= 1;
            }
            if (t)
                w *= i;
        }
    }
    return w * n * neg;
}
int main(void)
{
    register int n, i, j;
    scanf("%d", &n);
    int id = 0;
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
        num[i] = a[i];
        a[i] = G(a[i]);
        if (!st.count(a[i]))
            st.insert(pii(a[i], ++id));
        a[i] = st[a[i]];
    }
    for (i = 1; i <= n; ++i)
    {
        cnt.reset();
        int sz = 0;
        for (j = i; j <= n; ++j)
        {
            if (num[j] == 0)
            {
                ++ans[max(sz, 1)];
                continue;
            }
            else if (!cnt[a[j]])
            {
                cnt[a[j]] = 1;
                ++sz;
            }
            ++ans[sz];
        }
    }
    for (i = 1; i <= n; ++i)
        printf("%d%c", ans[i], " \n"[i == n]);
    return 0;
}

E.The Number Games

题意就是给你$n$个点的树，每一个点$i$的权值为$2^i$，从中删掉$k$个点使得剩下的子图连通，使得最后留下的子图权值和最大，输出删除的点。

一开始感觉这题不就是贪心用pq删掉标号小的拓扑排序吗，实际上并不是这样的简单贪心，由于权值的特殊性，可以发现保留第$i$个点，比删掉剩下的$i-1$个点要优，因此应从大到小去考虑保留哪些点。假设当前要保留点$i$，那么还要保留的点是$i$到子图路径上的所有点（这样才能时刻保持子图连通性），那么就用DFS和倍增预处理一下路径长度和每个节点的$k$倍祖先，每次倍增找到第一个在子图中的祖先，保留路径上的点个数就是$dep[i] - dep[ancestor]$，可以保留的话就暴力把路径上所有点都标记为保留即可。

代码：

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
89
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define all(a) (a).begin(),(a).end()
#define pb(x) push_back(x)
#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)
const int N = 1e6 + 7;
struct edge
{
    int to, nxt;
    edge() {}
    edge(int _to, int _nxt): to(_to), nxt(_nxt) {}
} E[N << 1];
int head[N], tot;
int dep[N], vis[N], fa[N][21];

void init()
{
    CLR(head, -1);
    tot = 0;
}
void add(int s, int t)
{
    E[tot] = edge(t, head[s]);
    head[s] = tot++;
}
void dfs(int u, int f, int d)
{
    fa[u][0] = f;
    dep[u] = d;
    for (int i = head[u]; ~i; i = E[i].nxt)
    {
        int v = E[i].to;
        if (v != f)
            dfs(v, u, d + 1);
    }
}
void del(int x)
{
    if (vis[x] || !x)
        return ;
    vis[x] = 1;
    del(fa[x][0]);
}
int main(void)
{
    int n, k, i, a, b, j;
    init();
    scanf("%d%d", &n, &k);
    for (i = 1; i < n; ++i)
    {
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }
    dfs(n, 0, 0);
    for (j = 1; j <= 20; ++j)
    {
        for (i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
    int res = n - k - 1;
    vector<int>v;
    vis[n] = 1;
    for (i = n - 1; i >= 1 && res > 0; --i)
    {
        if (vis[i])
            continue;
        int x = i;
        for (j = 20; j >= 0; --j)
        {
            if (fa[x][j] && !vis[fa[x][j]])
                x = fa[x][j];
        }
        x = fa[x][0];
        int kpcnt = dep[i] - dep[x];
        if (res < kpcnt)
            continue;
        del(i);
        res -= kpcnt;
    }
    for (i = 1; i <= n; ++i)
        if (!vis[i])
            printf("%d ", i);
    puts("");
    return 0;
}