Blackops

初心易得，始终难守

0%

CF #448 Div.2题解

发表于 更新于 分类于 ，

A.Pizza Separation

题意就是给你一个环形的披萨，已经切成很多个扇形， 要分成连续的两部分大扇形，求最小的扇形角度和的差值。
既然是环形的，当然是把原数组复制一份接到后面然后用前缀和或者暴力枚举某一半的开始和结束位置，更新答案，特判一下$n==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
#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 = 800;
int arr[N], pre[N];

int main(void)
{
    int n, i;
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        cin >> arr[i];
        arr[n + i] = arr[i];
    }
    if (n == 1)
    {
        cout << arr[1] << endl;
        return 0;
    }
    for (i = 1; i <= (n << 1); ++i)
        pre[i] = pre[i - 1] + arr[i];
    int ans = INF;
    for (i = 1; i + n - 1 < (n << 1); ++i)
    {
        int r = i + n - 1;
        int l = i;
        for (int j = l; j < r; ++j)
        {
            int ll = i, lr = j;
            int rl = j + 1, rr = r;
            ans = min(ans, abs(pre[lr] - pre[ll - 1] - (pre[rr] - pre[rl - 1])));
        }
    }
    cout << ans << endl;
    return 0;
}

B.XK Segments

题意就是让你在给定数列里找两个数$a_i$和$a_j$，使得$a_i \le a_j$且$[a_i,a_j]$区间中可以被$x$整除的数有恰好$k$个，求符合此条件的数对的数量
$O(n)$枚举$a_i$，设$a_i=t*x+b$，然后分类讨论：

  1. $k==0$, $a_i \le a_j \le tx+x-1$
  2. $a_i\%x==0$, $tx+kx \le a_j \le tx+(k+1)x-1$
  3. $a_i\%x!=0$, $a_i+(k-1)x \le a_j \le a_i+kx-1$

这样做两次二分查找，找到符合$a_j$的区间，答案加上这段区间的长度即可
具体如何推导出来打个草稿画一画就知道了。

代码：

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
#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 = 1e5 + 7;
LL arr[N];

int getl(int l, int r, LL key)
{
    int ans = -1;
    while (l <= r)
    {
        int mid = MID(l, r);
        if (arr[mid] >= key)
        {
            r = mid - 1;
            ans = mid;
        }
        else
            l = mid + 1;
    }
    return ans;
}
int getr(int l, int r, LL key)
{
    int ans = -1;
    while (l <= r)
    {
        int mid = MID(l, r);
        if (arr[mid] <= key)
        {
            l = mid + 1;
            ans = mid;
        }
        else
            r = mid - 1;
    }
    return ans;
}
int main(void)
{
    int n, i;
    LL x, k;
    while (cin >> n >> x >> k)
    {
        for (i = 1; i <= n; ++i)
            cin >> arr[i];
        sort(arr + 1, arr + 1 + n);
        LL ans = 0;
        for (i = 1; i <= n; ++i)
        {
            if (k == 0)
            {
                if (arr[i] % x)
                {
                    LL l_lim = arr[i], r_lim = arr[i] / x * x + x - 1LL;
                    int l = getl(1, n, l_lim), r = getr(1, n, r_lim);
                    if (l > r || l == -1 || r == -1)
                        continue;
                    ans += (LL)(r - l + 1);
                }
                continue;
            }
            if (arr[i] % x)
            {
                LL l_lim = arr[i] / x * x + k * x, r_lim = arr[i] / x * x + (k + 1) * x - 1LL;
                int l = getl(1, n, l_lim), r = getr(1, n, r_lim);
                if (l > r || l == -1 || r == -1)
                    continue;
                ans += (LL)(r - l + 1);
            }
            else
            {
                LL l_lim = arr[i] + (k - 1) * x, r_lim = arr[i] + k * x - 1LL;
                int l = getl(1, n, l_lim), r = getr(1, n, r_lim);
                if (l > r || l == -1 || r == -1)
                    continue;
                ans += (LL)(r - l + 1);
            }
        }
        cout << ans << endl;
    }
    return 0;
}

C.Square Subsets

题目就是给你一个数列，从中选出不为空的一些数，使得这些数的乘积为一个平方数。
考虑将所有的数质数分解，实际上题目条件变成了将一些数用其分解出来的质数和对应的指数代表，相加之后指数均为偶数，由于$1-70$内的数只有$19$个，因此用状压来求。
将一个数分解之后第$i$的因子的指数如果为奇数，那么这个位置的值为$1$，否则为$0$
设$dp[i][j]$代表从只考虑范围为数列中值为$0 \sim i$的数所能组合出来的状态为$j$，那么有：

为什么是$2^{cnt[i]-1}$,因为第一个式子$j$被改变了，只需要奇数个数$i$即可，那么选奇数个的情况实际上就是二项式展开的奇数项之和，刚好是所有情况的一般，偶数项同理，因此两个式子虽然后一项是一样的，但是意义上不一样。最后答案减去一个都不选的方案即可。

代码：

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
#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 = 1e5 + 7;
const LL mod = 1e9 + 7;
int st[N], cnt[71], POW[N];
LL dp[2][(1 << 19) + 10];
vector<int>P;

inline bool prime(int x)
{
    for (int i = 2; i * i <= x; ++i)
        if (x % i == 0)
            return 0;
    return 1;
}
int main(void)
{
    int n, i, j;
    for (i = 2; i <= 70; ++i)
        if (prime(i))
            P.push_back(i);
    POW[0] = 1;
    for (i = 1; i < N; ++i)
        POW[i] = POW[i - 1] * 2LL % mod;
    for (i = 1; i <= 70; ++i)
    {
        int x = i;
        for (j = 0; j < 19; ++j)
        {
            if (x % P[j] == 0)
            {
                int up = 0;
                while (x % P[j] == 0)
                {
                    ++up;
                    x /= P[j];
                }
                if (up & 1)
                    st[i] |= (1 << j);
            }
        }
    }
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        int x;
        scanf("%d", &x);
        ++cnt[x];
    }
    dp[0][0] = 1LL;
    int pre = 0, cur = 1;
    for (i = 1; i <= 70; ++i)
    {
        CLR(dp[cur], 0);
        if (!cnt[i])
        {
            for (j = 0; j < (1 << 19); ++j)
                dp[cur][j] = dp[pre][j];
        }
        else
        {
            for (j = 0; j < (1 << 19); ++j)
            {
                dp[cur][j ^ st[i]] = (dp[cur][j ^ st[i]] + dp[pre][j] * POW[cnt[i] - 1] % mod) % mod;
                dp[cur][j] = (dp[cur][j] + dp[pre][j] * POW[cnt[i] - 1] % mod) % mod;
            }
        }
        swap(cur, pre);
    }
    printf("%I64d\n", (dp[pre][0] - 1LL + mod) % mod);
    return 0;
}

D.String Mark

题意就是给你字符串$a$和$b$，求用$a$的重排列中字典序严格大于$a$但小于$b$的方案数。
如果我们可以写一个函数$F(s)$仅计算出小于某个字符串的方案数的话，那么答案就是$F(b)-F(a)-1$。
那么可以这样按位考虑：首先令前$i$个字符与$s$相等，然后后续的字符显然就是剩下的可重集的全排列，设这个可重集大小为$n$，每一个元素的个数为$s_i$，其方案数为

那么这样固定好之后，把方案数加上这个数值，然后将当前位置的字符置为跟目标串该位置一样的字符，即从可重集中去掉该字符的一个贡献表示该字符已经被使用，然后继续考虑下一个位置。
若当前位置已经不能和目标串的位置“对齐”时，说明后面的字符的全排列已经包含了所有剩下的情况了， 不需要再计算了。
可以发现枚举位置、枚举小于当前目标串的字符、对可重集的求连乘操作，这样做的复杂度是$n*k^2$的，基本上是超时的，但是显然可以发现求连乘的操作可以预处理优化成$O(1)$获得，因为每一次我们都只会更新一个$cnt[j]$，因此先预先获得$
1 \over {\prod{s_i!} }$的模意义下的值，由于每一次分母中的一项要变，那么直接乘上原来该项的值，再“除以”该项现在的值就可以了，其中除法均用逆元代替。
最后这里还学习到了一个线性求阶乘逆元的方法，先预处理出阶乘，然后计算逆元的最后一项，再逆序地乘得到逆元的每一项，这是显然的，因为

代码：

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
#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;
const LL mod = 1e9 + 7;
char s1[N], s2[N];
int fac[N], invfac[N], cnt[26], buc[26];

inline int qpow(int a, int b)
{
    int r = 1;
    while (b)
    {
        if (b & 1)
            r = (LL)r * a % mod;
        a = (LL)a * a % mod;
        b >>= 1;
    }
    return r;
}
LL calc(char s[], char t[], int len)
{
    memcpy(cnt, buc, sizeof(buc));
    LL ans = 0;
    LL down = 1LL;
    for (int i = 0; i < 26; ++i)
        down = (LL)down * invfac[cnt[i]] % mod;
    for (int i = 0; i < len; ++i)
    {
        for (int j = 0; j < t[i] - 'a'; ++j)
        {
            if (cnt[j])
            {
                --cnt[j];
                LL temp = (((LL)down * fac[len - 1 - i]) % mod) * (((LL)fac[cnt[j] + 1] * invfac[cnt[j]]) % mod) % mod;
                ans = (ans + temp) % mod;
                ++cnt[j];
            }
        }
        if (!cnt[t[i] - 'a'])
            break;
        --cnt[t[i] - 'a'];
        down = (LL)down * fac[cnt[t[i] - 'a'] + 1] % mod * invfac[cnt[t[i] - 'a']] % mod;
    }
    return ans;
}
int main(void)
{
    int i;
    fac[0] = 1;
    for (i = 1; i < N; ++i)
        fac[i] = (LL)fac[i - 1] * i % mod;
    invfac[N - 1] = qpow(fac[N - 1], mod - 2);
    for (i = N - 2; i >= 0; --i)
        invfac[i] = (LL)invfac[i + 1] * (i + 1) % mod;
    while (~scanf("%s%s", s1, s2))
    {
        for (i = 0; i < 26; ++i)
            buc[i] = 0;
        int len = strlen(s1);
        for (i = 0; i < len; ++i)
            ++buc[s1[i] - 'a'];
        LL A = calc(s1, s2, len);
        LL B = calc(s1, s1, len);
        printf("%I64d\n", (LL)(A - B - 1LL + mod) % mod);
    }
    return 0;
}

E.Eyes Closed

题意就是给你两个操作，一个是随机地交换区间$[l_1,r_1]$和$[l_2,r_2]$中的两个数，另一种就是问你$[l,r]$区间的和的期望值是多少
一眼线段树啊，但是写完发现样例都过不去，然后膜了下别人的题解，发现是我把区间的和算在了单个的数值上，错误的做法就是把当前区间减去当前区间的平均数，加上另一个区间的平均数，因为这样仅仅对该区间成立，对区间内的单独数字不成立，比如1 1000 1000 0 0 0，将$[1,3]$与$[4,6]$区间做一次随机互换操作，那么如果按照我错误的写法，查询$[1,1]$区间的期望值是实际上它变成了一个比较大的负数，然而这是不可能的。因此正确的做法是考虑每一个数的期望变化：区间内的任意一个数都可能被等概率地换出去，不被换出去的概率是$(len_1-1) \over len_1$。
即每个数的期望值要要乘以$(len_1-1) \over len_1$，然后对于一个换进来的数，它会被等概率地换到任意一个位置，因此每一个数的期望值还要再加上$sum_2 \over {len_2*len_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
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
#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 = 1e5 + 7;
const double eps = 1e-6;
struct seg
{
    int l, mid, r;
    double mul, add, s;
    inline double len()
    {
        return (double)(r - l + 1);
    }
} T[N << 2];
double arr[N];

void pushup(int k)
{
    T[k].s = T[LC(k)].s + T[RC(k)].s;
}
void pushdown(int k)
{
    if (fabs(T[k].mul - 1.0) >= eps)
    {
        T[LC(k)].add *= T[k].mul;
        T[LC(k)].s *= T[k].mul;
        T[LC(k)].mul *= T[k].mul;
        T[RC(k)].add *= T[k].mul;
        T[RC(k)].s *= T[k].mul;
        T[RC(k)].mul *= T[k].mul;
        T[k].mul = 1.0;
    }
    if (fabs(T[k].add) >= eps)
    {
        T[LC(k)].add += T[k].add;
        T[LC(k)].s += T[k].add * T[LC(k)].len();
        T[RC(k)].add += T[k].add;
        T[RC(k)].s += T[k].add * T[RC(k)].len();
        T[k].add = 0;
    }
}
void build(int k, int l, int r)
{
    T[k].l = l;
    T[k].r = r;
    T[k].mid = MID(l, r);
    T[k].add = 0;
    T[k].mul = 1.0;
    if (l == r)
        T[k].s = arr[l];
    else
    {
        build(LC(k), l, T[k].mid);
        build(RC(k), T[k].mid + 1, r);
        pushup(k);
    }
}
void update(int k, int l, int r, double mul, double v)
{
    if (l <= T[k].l && T[k].r <= r)
    {
        T[k].add *= mul;
        T[k].s *= mul;
        T[k].mul *= mul;
        T[k].add += v;
        T[k].s += T[k].len() * v;
    }
    else
    {
        pushdown(k);
        if (l <= T[k].mid)
            update(LC(k), l, r, mul, v);
        if (r > T[k].mid)
            update(RC(k), l, r, mul, v);
        pushup(k);
    }
}
double query(int k, int l, int r)
{
    if (l <= T[k].l && T[k].r <= r)
        return T[k].s;
    else
    {
        pushdown(k);
        double s = 0;
        if (l <= T[k].mid)
            s += query(LC(k), l, r);
        if (r > T[k].mid)
            s += query(RC(k), l, r);
        return s;
    }
}
int main(void)
{
    int n, m, i;
    scanf("%d%d", &n, &m);
    for (i = 1; i <= n; ++i)
        scanf("%lf", arr + i);
    build(1, 1, n);
    while (m--)
    {
        int ops, l1, r1;
        scanf("%d%d%d", &ops, &l1, &r1);
        if (ops == 1)
        {
            int l2, r2;
            scanf("%d%d", &l2, &r2);
            double len1 = r1 - l1 + 1, len2 = r2 - l2 + 1;
            double av1 = query(1, l1, r1) / len1, av2 = query(1, l2, r2) / len2;
            update(1, l1, r1, (len1 - 1) / len1, av2 / len1);
            update(1, l2, r2, (len2 - 1) / len2, av1 / len2);
        }
        else
            printf("%.7f\n", query(1, l1, r1));
    }
    return 0;
}