Blackops

初心易得，始终难守

0%

CF #475 Div.2 A B C D

发表于 更新于 分类于 ，

A.Splits

题意就是把数$n$用一个不升序列的前一部分和表示，求有几种不同权重的表示，观察一发发现这玩意儿似乎就是除以$2$再加$1$就行了（这题让我知道了交两发只算最晚的那发的2333，原地爆炸）

代码：

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
#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 long long LL;
const double PI = acos(-1.0);
const int N = 1100;

int main(void)
{
    LL n;
    while (cin >> n)
    {
        LL ans = ceil(n / 2.0);
        if (n % 2 == 0)
            ++ans;
        cout << ans << endl;
    }
    return 0;
}

B.Messages

题意就是有$n$个信息，初始价值均为$A$，每个信息在$t_i$的时候会发送给你，你可以选择阅读或者不阅读，不读的话每一分钟会开始扣$B$的价值，读的话就会把总价值加上$A$，然后每分钟总价值还会加上$C\times当前未读信息$，求在$T$分钟之后全部阅读掉的前提下最大的总价值。

如果$C\ge B$的话显然放到最后总是最优的，读了的话一个信息就少了$C-B$的贡献，不读的话还能加上这个贡献。

当$C\le B$时，可以考虑全部放到最后一分钟阅读，这样的总价值是最大的。

代码：

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
#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 long long LL;
const double PI = acos(-1.0);
const int N = 1010;
int t[N];

int main(void)
{
    int n, A, B, C, T, i;
    while (~scanf("%d%d%d%d%d", &n, &A, &B, &C, &T))
    {
        for (i = 1; i <= n; ++i)
            scanf("%d", &t[i]);
        if (C >= B)
        {
            int delay = 0;
            for (i = 1; i <= n; ++i)
                delay += T - t[i];
            printf("%d\n", A * n + C * delay - B * delay);
        }
        else
            printf("%d\n", A * n);
    }
    return 0;
}

C.Alternating Sum

题意就是给你一个循环节为$k$的$S_{0…n}$序列，然后求

$\sum \limits_{i=0}^{n} s_{i} a^{n - i} b^{i}$

答案对$1e9+9$取模。显然把数列写出来，可以发现如果以前$k$项的和作首项的话，刚好是一个模意义下的等比数列求和，公比是$a^{-k}b^k$，然后题目还是很良心的给你的$n+1$是$k$的整数倍，这样刚好让你用等比数列公式算，当然其中有个坑，当公比为$1$的时候，$1-q$会变成$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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#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 long long LL;
const double PI = acos(-1.0);
const LL mod = 1e9 + 9;
const int N = 1e5 + 7;
char s[N];
struct Mat
{
    LL A[2][2];
    void O() {
        A[0][0] = A[0][1] = A[1][0] = A[1][1] = 0;
    }
    void I() {
        A[0][0] = A[1][1] = 1;
        A[0][1] = A[1][0] = 0;
    }
    Mat operator *(Mat b) {
        Mat c;
        c.O();
        for (int i = 0; i < 2; ++i) {
            for (int k = 0; k < 2; ++k) {
                for (int j = 0; j < 2; ++j) {
                    c.A[i][j] = (c.A[i][j] + A[i][k] * b.A[k][j]) % mod;
                }
            }
        }
        return c;
    }
    friend Mat operator^(Mat a, LL b) {
        Mat r;
        r.I();
        while (b) {
            if (b & 1)
                r = r * a;
            a = a * a;
            b >>= 1;
        }
        return r;
    }
    Mat() {}
    Mat(initializer_list<LL> v) {
        register int p = 0;
        for (auto &x : v) {
            A[p / 2][p & 1] = x;
            ++p;
        }
    }
};
inline LL qpow(LL a, LL b)
{
    if (a < 0)
        a = (a % mod + mod) % mod;
    if (b < 0)
        b = (b % mod + mod) % mod;
    LL r = 1;
    while (b)
    {
        if (b & 1)
            r = r * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return r;
}
inline LL mul(LL a, LL b)
{
    if (a < 0)
        a = (a % mod + mod) % mod;
    if (b < 0)
        b = (b % mod + mod) % mod;
    LL r = 0;
    while (b)
    {
        if (b & 1)
            r = (r + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return r;
}
LL inv(LL x)
{
    if (x < 0)
        x = (x % mod + mod) % mod;
    return qpow(x, mod - 2);
}
int main(void)
{
    int n, i, k;
    LL a, b;
    scanf("%d%I64d%I64d%d", &n, &a, &b, &k);
    scanf("%s", s);
    LL a1 = 0;
    LL inv_a = inv(a);
    LL fa = qpow(a, n), fb = 1;
    for (i = 0; i < k; ++i)
    {
        a1 = (a1 + (s[i] == '+' ? 1LL : -1LL) * fa % mod * fb % mod) % mod;
        fa = fa * inv_a % mod;
        fb = fb * b % mod;
    }
    Mat A =
    {
        a1, a1,
        0LL, 0LL
    };
    Mat B =
    {
        1LL, 1LL,
        0LL, qpow(inv_a, k)*qpow(b, k) % mod
    };
    B = B ^ ((n + 1) / k - 1);
    A = A * B;
    printf("%I64d\n", ((A.A[0][1] % mod) + mod) % mod);
    return 0;
}

D.Destruction of a Tree

题意很简单就是让你判断能否通过不停删除偶数度数的点及其连出去的边，最后删完这整颗树。

刚开始感觉哇这不是无脑BFS吗，燃鹅无脑的我并没有考虑到实际上不同的删点顺序会影响能否成功删完这棵树，所以正确的策略是优先删除靠近叶子结点的点，那么一开始用DFS预处理出每个结点的深度，然后用pq按度数大的优先去BFS即可。

代码：

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
90
91
92
93
94
95
96
97
98
99
100
#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 long long LL;
const double PI = acos(-1.0);
const int N = 2e5 + 7;
vector<int>E[N];
int deg[N], n, des[N], p[N];
vector<int>pos;
int dep[N];

void dfs(int u, int f, int d)
{
    dep[u] = d;
    for (auto &v : E[u])
    {
        if (v != f)
            dfs(v, u, d + 1);
    }
}
inline void add(int s, int t)
{
    E[s].pb(t);
}
void bfs()
{
    priority_queue<pii>Q;
    int i;
    for (i = 1; i <= n; ++i)
    {
        if (deg[i] & 1)
            continue;
        Q.push({dep[i], i});
    }
    while (!Q.empty())
    {
        int u = Q.top().second;
        Q.pop();
        if (des[u] || ((deg[u] > 0) && (deg[u] & 1)))
            continue;
        des[u] = 1;
        pos.push_back(u);
        for (auto &v : E[u])
        {
            if (des[v] || (deg[v] <= 0))
                continue;
            --deg[v];
            --deg[u];
        }
        for (auto &v : E[u])
        {
            if (des[v])
                continue;
            if (deg[v] % 2 == 0)
                Q.push({dep[v], v});
        }
    }
}
int main(void)
{
    int i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &p[i]);
        if (p[i])
        {
            add(p[i], i);
            add(i, p[i]);
            ++deg[i];
            ++deg[p[i]];
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        if (!p[i])
            dfs(i, 0, 1);
    }
    bfs();
    int ans = pos.size();
    if (ans != n)
        puts("NO");
    else
    {
        puts("YES");
        for (auto &x : pos)
            printf("%d\n", x);
    }
    return 0;
}