Blackops

初心易得，始终难守

0%

CF #447 Div.2题解

发表于 更新于 分类于 ，

A.QAQ

题意就是找出所有构成”QAQ”三个字母的子序列个数，听说还有统计什么的，果然蒟蒻选手只知道三个for……

代码：

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
#include <bits/stdc++.h>
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 fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
char s[110];

int main(void)
{
    while(cin >> s)
    {
        int len = strlen(s);
        int ans = 0;
        for(int i = 0; i < len; ++i)
        {
            for(int j = i + 1; j < len; ++j)
            {
                for(int k = j + 1; k < len; ++k)
                {
                    if(s[i] == 'Q' && s[j] == 'A' && s[k] == 'Q')
                        ++ans;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

B.Ralph And His Magic Field

题意就是给你$n$、$m$和$k$，问你构造出每一行每一列的乘积都是$k$的方案数有多少种，由于智商感人，比赛的时候没想出来
显然那每一个格子只能放$1$或$-1$，然后只要考虑$k==-1$和$k==1$两种情况即可，然后用$n*m$个元素的乘积和每行每列之间的乘积之间的关系，可以得到：

  1. $k==1$时答案为$2^{(n-1)*(m-1)}$，这里用费马小定理和快速乘法处理一下即可。
  2. $k==-1$，当$n$和$m$奇偶性不同，则答案为$0$；否则答案还是$2^{(n-1)*(m-1)}$。

代码：

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>
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 fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const LL mod = 1000000007LL;

inline LL qpow(LL a, LL b, LL m)
{
    LL r = 1;
    while(b)
    {
        if(b & 1)
            r = r * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return r;
}
inline LL mul(LL a, LL b, LL m)
{
    LL r = 0;
    while(b)
    {
        if(b & 1)
            r = (r + a) % m;
        a = (a + a) % m;
        b >>= 1;
    }
    return r;
}
int main(void)
{
    LL n, m, k;
    while(cin >> n >> m >> k)
    {
        if(k == 1)
            cout << qpow(2LL, mul(n - 1, m - 1, mod - 1), mod) << endl;
        else
        {
            if((n + m) & 1)
                puts("0");
            else
                printf("%I64d\n", qpow(2LL, mul(n - 1, m - 1, mod - 1), mod));
        }
    }
    return 0;
}

C.Marco and GCD Sequence

题意就是给你$n$个数组成的集合，这个集合就是某个序列的所有区间$gcd$所构成的集合，构造这个数列。
Naive地以为只要相互之间$gcd$不为$1$就可以了，到最后用$ST$表暴力判断还是错的，正解就是看每一个数是不是那个最小数的倍数，如果有一个数不是的话无法构造；否则只要在两两之间插入一个最小的数就是所要构造的序列了

代码：

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>
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 fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1010;
int arr[N];
int vis[1000010];

int main(void)
{
    int n, i;
    while(~scanf("%d", &n))
    {
        CLR(vis, 0);
        for(i = 1; i <= n; ++i)
            scanf("%d", &arr[i]);
        int flag = 1;
        for(i = 1; i <= n; ++i)
        {
            if(arr[i] % arr[1])
            {
                flag = 0;
                break;
            }
        }
        if(!flag)
            puts("-1");
        else
        {
            printf("%d\n", n << 1);
            for(i = 1; i <= n; ++i)
                printf("%d %d%c", arr[1], arr[i], " \n"[i==n]);
            puts("");
        }
    }
    return 0;
}

D.Ralph And His Tour in Binary Country

题意就是给你一个完全二叉树（比赛的时候看了几眼还是选择去做E了，弱比我既没看出来题目所给的就是完全二叉树，也忘记去打表了找规律了），然后每一个树边都有权值（走过路径就要减去这条路径的权值），询问从某一个点$A_i$开始，拥有初始值为$H_i$，问那些点可以在$H_i$不被扣成负数前提下能走到，并求到这些点的时候所有剩余$H_i$的和。
完全不会写，还好大佬们的代码看得懂……感觉非常巧妙的一道题，做法就是先对树上的所有节点求出它子树内的节点（记得算自己）到自己的路径长度，记录到这个节点的信息中，对于询问：考虑候选点只能来自与子树内部或子树外部，因此先处理$A_i$子树，然后再处理$A_i$的兄弟子树，然后再往上走，单独处理父亲，依次循环，直到走到整棵树的根节点$1$为止。对于子树的处理，显然在上面排好序的路径长度中二分一下最后的位置，然后哪个位置的前缀和就是所要扣掉的总值，为了避免老是作前缀和，再用一个数组再预处理的时候顺便记录下前缀和就可以了。然后记录子树路径长度的时候用归并排序和代替暴力$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
87
88
#include <bits/stdc++.h>
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 fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e6 + 7;
LL L[N];
vector<LL>dis[N], presum[N];
int n, m;
LL tl[N], tr[N];

inline LL Getsubsum(int u, LL v)
{
    if (v <= 0 || u < 1 || u > n)
        return 0;
    int pos = upper_bound(dis[u].begin(), dis[u].end(), v) - dis[u].begin() - 1;
    return (pos + 1LL) * v - presum[u][pos];
}
int main(void)
{
    int i, j;
    scanf("%d%d", &n, &m);
    for (i = 1; i < n; ++i)
        scanf("%I64d", L + i);
    for (i = n; i >= 1; --i)
    {
        dis[i].emplace_back(0);
        int ls = LC(i), rs = RC(i);
        int lsz = 0, rsz = 0;
        if (ls <= n)
        {
            LL w = L[ls - 1];
            lsz = dis[ls].size();
            for (j = 0; j < lsz; ++j)
                tl[j] = dis[ls][j] + w;
        }
        if (rs <= n)
        {
            LL w = L[rs - 1];
            rsz = dis[rs].size();
            for (j = 0; j < rsz; ++j)
                tr[j] = dis[rs][j] + w;
        }
        int u = 0, v = 0;
        while (u < lsz && v < rsz)
        {
            if (tl[u] < tr[v])
                dis[i].emplace_back(tl[u++]);
            else
                dis[i].emplace_back(tr[v++]);
        }
        while (u < lsz)
            dis[i].emplace_back(tl[u++]);
        while (v < rsz)
            dis[i].emplace_back(tr[v++]);
        LL sum = 0;
        for (auto &d : dis[i])
            presum[i].emplace_back(sum += d);
    }
    while (m--)
    {
        int A;
        LL H;
        scanf("%d%I64d", &A, &H);
        LL ans = 0;
        ans += Getsubsum(A, H);
        while (A != 1)
        {
            if (H < L[A - 1])
                break;
            H -= L[A - 1];
            ans += H;
            int other = (A & 1) ? A - 1 : A + 1;
            ans += Getsubsum(other, H - L[other - 1]);
            A >>= 1;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}

E.Ralph and Mushrooms

题意就是给你一个有向可能带环的图，每一条边都有一个所能得到的蘑菇数量，设初始蘑菇为为$w$，第$i$次走这条路，蘑菇数量会减掉$i-1$，比如一开始蘑菇有$4$个，那么这条路可被采集的蘑菇数量依次为$4,3,1,0$，然后从一个给定起点$s$出发，求最多能采集到多少蘑菇。路可以来回走，但是蘑菇一旦为$0$就不能再采集了。
说起这题很痛心，没有预处理+智商低导致终测$TLE$，做法就是先缩点成多个连通分量目的是得到一个新的$DAG$，然后根据每一条输入边连接的端点，来更新新图的边权或者新图的点权，用二分或数学的方法把连通分量（即环）里的可采集蘑菇数量求出来作为点权（用到自然数前n项和的求和公式），然后然后做一遍$dfs$记忆化搜索（用spfa没必要且容易超时）求$DAG$上的点边均带权的最长路即可。最好预处理一下自然数的前$n$项和$S_n$的前$n$项和$T_n$，否则可能会超时

代码：

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>
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 fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 1e6 + 7;
struct edge
{
    int to;
    int pre;
};
struct Edge
{
    int to, pre;
    LL w;
};
edge E[N];
Edge e[N];
int head[N], tot, h[N], Tot;
int dfn[N], low[N], st[N], belong[N], ins[N], sc, ts, top, scnum[N];
int node[N][2];
LL w[N];
bitset<N>vis;
LL sumofsum[20010];

LL d[N], sum[N];

void init()
{
    CLR(head, -1);
    CLR(h, -1);
    sc = ts = top = 0;
    tot = Tot = 0;
}
inline void Add(int s, int t, LL w)
{
    e[Tot].to = t;
    e[Tot].pre = h[s];
    e[Tot].w = w;
    h[s] = Tot++;
}
inline void add(int s, int t)
{
    E[tot].to = t;
    E[tot].pre = head[s];
    head[s] = tot++;
}
LL dfs(int u)
{
    if (d[u])
        return d[u];
    LL nxt = 0;
    for (int i = h[u]; ~i; i = e[i].pre)
    {
        int v = e[i].to;
        nxt = max<LL>(dfs(v) + e[i].w, nxt);
    }
    d[u] = sum[u] + nxt;
    return d[u];
}
void Tarjan(int u)
{
    dfn[u] = low[u] = ++ts;
    ins[u] = 1;
    st[top++] = u;
    int v;
    for (int i = head[u]; ~i; i = E[i].pre)
    {
        v = E[i].to;
        if (!dfn[v])
        {
            Tarjan(v);
            if (low[v] < low[u])
                low[u] = low[v];
        }
        else if (ins[v])
        {
            if (dfn[v] < low[u])
                low[u] = dfn[v];
        }
    }
    if (dfn[u] == low[u])
    {
        ++sc;
        do
        {
            v = st[--top];
            ins[v] = 0;
            belong[v] = sc;
            ++scnum[belong[v]];
        }
        while (u != v);
    }
}
inline LL calcxiang(LL x)
{
    LL l = 0, r = x;
    LL mid = 0;
    LL ans = 0;
    while (l <= r)
    {
        mid = (l + r) >> 1;
        if ((mid * (mid + 1) >> 1) <= x)
        {
            l = mid + 1;
            ans = mid;
        }
        else
            r = mid - 1;
    }
    return ans;
}
int main(void)
{
    for (LL i = 1; i <= 20000LL; ++i)
        sumofsum[i] = sumofsum[i - 1] + ((i * (i + 1)) >> 1);
    int n, m,  i;
    scanf("%d%d", &n, &m);
    init();
    for (i = 0; i < m; ++i)
    {
        scanf("%d%d%I64d", &node[i][0], &node[i][1], &w[i]);
        add(node[i][0], node[i][1]);
    }
    for (i = 1; i <= n; ++i)
        if (!dfn[i])
            Tarjan(i);
    for (i = 0; i < m; ++i)
    {
        int u = node[i][0], v = node[i][1];
        if (belong[u] == belong[v])
        {
            LL nn = calcxiang(w[i]);
            LL dsum = sumofsum[nn];
            sum[belong[u]] += w[i] * (nn + 1LL) - dsum;
        }
        else
            Add(belong[u], belong[v], w[i]);
    }
    int s;
    scanf("%d", &s);
    printf("%I64d\n", dfs(belong[s]));
    return 0;
}