T20200922

Posted on Edited on In Word count in article: 1.9k Reading time ≈ 7 mins.
大东辰的测试

T1 集合均值(mos)

就是暴力+线性求逆元即可

Code

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
#define Mod 998244353
using namespace std;
const LL MaxN=2e7+10;

LL N,M;
LL Num[MaxN],Inv[MaxN];
LL Ans;

inline LL Fast(LL A,LL B) {
    LL Res=1;
    while(B) {
        if(B & 1) Res=(Res*A)%Mod;
        A=(A*A)%Mod;
        B>>=1;
    }
    return Res%Mod;
}

inline int C(int A,int B) {
	int a=1,b=1;
	FOR(i,A-B+1,A) (a*=i)%=Mod;
	FOR(i,1,B) (b*=i)%=Mod;
	return A*Fast(b,Mod-2)%Mod;
}

signed main() {
    ios::sync_with_stdio(false);
    cin>>N>>M;
    LL Sum=0;
    FOR(i,1,N) cin>>Num[i],Sum+=Num[i];
    LL S=N*M;
    Sum*=M;
    LL Ans=Sum%Mod*Fast(S,Mod-2)%Mod;
    LL Temp=0;
    Inv[0]=Inv[1]=1;
    LL Res=0;
    FOR(i,2,S+1) Inv[i]=(Mod-Mod/i)*Inv[Mod%i]%Mod,(Res+=Inv[i])%Mod;
    cout<<Ans*(((S-Res)%Mod+Mod)%Mod)%Mod<<endl;
}

T2 聚烷撑乙二醇(pag)

Solution

考虑清楚“最优操作”到底是什么样的，这题就很简单

假设只有两个发生器，那么如果放弃第一个选用第二个，第二个发生器产生的数的期望是

\[ Y=\frac{L_2+R_2}{2} \]

不难想到如果第一个发生器产生了 \(X\)，\(X<Y\) 时放弃 \(X\) 更优，否则拿走 \(x\) 更优。

更一般的，假设当前在使用第 \(i\) 个发生器，其产生了 \(X\)，设从第 \(i\) 个发生器开始游戏得到的最优答案是 \(f_{i+1}\) ，那么比较 \(X\) 和 \(f_{i+1}\) 的大小关系就可以确定是否拿走 \(X\) 。那么 \(f_i\) 的计算就是一个分段的一次函数的积分，来个加权平均数什么的算一下就好了。

时间复杂度\(O(n)\)

Code

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 <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)

typedef long long ll;
typedef long double ld;

const int maxn = 1000005;
int l[maxn], r[maxn];

int main () {
	freopen ("pag.in", "r", stdin);
	freopen ("pag.out", "w", stdout);
	int n = read;
	for (int i = 1; i <= n; i ++) scanf ("%d %d", l + i, r + i);

	ld ans = 0;
	for (int i = n; i; i --) {
		int L = l[i], R = r[i];
		if (ans < L)
			ans = ld(L + R) / 2;
		else if (ans < R)
			ans = (ans * (ans - L) + (ans + R) / 2 * (R - ans)) / (R - L);
		/* else */
		/* 	ans = ans; */
	}

	printf("%.5Lf\n", ans);
}

T3 技术情报局(tio)

对于\(20\)分的数据，暴力枚举即可

这个最大值太突兀了，不难想到枚举每个数，考虑其作为最大值的区间的贡献。

建大根笛卡尔树，设 \(i\) 在笛卡尔树上管辖的区间为 \([l,r]\)，那么当区间 \([L,R]\) 满足 \(L\in[l,i]\land R\in[i,R]\) 时 \(i\) 恰好作为 \([L,R]\) 的最大值。在笛卡尔树上做些信息合并即可统计答案。

Code

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>

using namespace std;

typedef long long ll;
const int maxn = 1e7 + 10;

int a[maxn], mod;
int ls[maxn], rs[maxn];
int stk[maxn], top;
ll ans;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x * t;
}

namespace GenHelper {
    unsigned z1, z2, z3, z4, b;
    unsigned rand_() {
        b = ((z1 << 6) ^ z1) >> 13;
        z1 = ((z1 & 4294967294U) << 18) ^ b;
        b = ((z2 << 2) ^ z2) >> 27;
        z2 = ((z2 & 4294967288U) << 2) ^ b;
        b = ((z3 << 13) ^ z3) >> 21;
        z3 = ((z3 & 4294967280U) << 7) ^ b;
        b = ((z4 << 3) ^ z4) >> 12;
        z4 = ((z4 & 4294967168U) << 13) ^ b;
        return (z1 ^ z2 ^ z3 ^ z4);
    }   
} // namespace GenHelper

inline void get (int n, unsigned s, int l, int r) {
    using namespace GenHelper;
    z1 = s;
    z2 = unsigned((~s) ^ 0x233333333U);
    z3 = unsigned(s ^ 0x1234598766U);
    z4 = (~s) + 51;
    for (int i = 1; i <= n; i ++) {
        int x = rand_() & 32767;
        int y = rand_() & 32767;
        a[i] = (l + (x * 32768 + y) % (r - l + 1));
    }
}

struct Data
{
    ll p, q, x;
    Data operator + (const Data &r) const 
    {
        return {
            (p + x * r.p) % mod,
            (r.q + r.x * q) % mod,
            x * r.x % mod
        };
    }
};

Data Slove(int i, int l, int r)
{
    if (!i) return {0, 0, 1};
    Data L = Slove(ls[i], l, i - 1);
    Data R = Slove(rs[i], i + 1, r);
    Data D = {a[i], a[i], a[i]};
    ans = (ans + (L.q + 1) * (R.p + 1) % mod * a[i] % mod * a[i] % mod) % mod;
    return L + D + R;
}

signed main()
{
    int n = __read(), s = __read(), l = __read(), r = __read();
    mod = __read();
    get(n, unsigned(s), l, r);

    for (int i = 1; i <= n; ++i) {
        while (top and a[stk[top]] < a[i]) ls[i] = stk[top--];
        if (top) rs[stk[top]] = i;
        stk[++top] = i;
    }
    Slove(stk[1], 1, n);
    printf ("%lld\n", ans);
}

T4 肯德基(KFC)

先吐槽一下，这道题是真的战术失误

我当时不知道是傻了还是怎么了，只想到了统计无平方因字数的个数的做法

竟然没想到怎么加权。。。

害，学艺不精啊。。。

关于无平方因字数的个数看这里

记\([1,n]\)范围内无平方因字数的个数为\(Count_n\)，那么有： \[ Count_n=\sum_{i=1}^\sqrt n\mu(i)\left\lfloor\frac n{i^2}\right\rfloor \] 在此基础上，加上\(i^2\)的贡献即为答案啊

我是真的蠢了

所以得到： \[ ans=\sum_{i=1}^\sqrt n\mu(i)i^2S(\left\lfloor\frac n{i^2}\right\rfloor) \] 然后就是关于这个\(std\)的玄学优化了，表示没看得很明白

不加优化的话，那就只有\(80\)分的好成绩，对于我来说就够啦

Code(80)

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;

typedef unsigned long long ll;
const ll maxn = 1e7 + 10;

ll n, pr[maxn], mu[maxn];
ll cnt, g[maxn];
bool vis[maxn];

inline ll __read()
{
    ll x(0);
    char o (getchar());
    while (o < '0' || o > '9') 
        o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline void init()
{
    mu[1] = 1;
    for (ll i = 2; i < maxn; ++i) {
        if (!vis[i]) pr[++cnt] = i, mu[i] = -1;
        for (ll j = 1; j <= cnt && pr[j] * i < maxn; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) mu[i * pr[j]] = -mu[i];
            else break;
        }
    }

    for (ll i = 1; i < maxn; ++i) g[i] = mu[i] * i * i;
}

inline ll S(ll x)
{
    if (x & 1) return ((x + 1) >> 1) * x;
    return (x >> 1) * (x + 1); 
}

signed main()
{
    freopen ("kfc.in", "r", stdin);
    freopen ("kfc.out", "w", stdout);
    init();
    ll T = __read();
    while (T--) {
        ll n = __read();
        ll ans(0);
        for (ll i = 1; i * i <= n; ++i) 
            ans += g[i] * S(n / i / i);
        printf ("%llu\n", ans);
    }
}

Code(100)

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
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const ll maxn = 2e7 + 10;

ll n, pr[maxn], mu[maxn];
ll cnt, g[maxn];
bool vis[maxn];

inline ll __read()
{
    ll x(0);
    char o (getchar());
    while (o < '0' || o > '9') 
        o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline void init()
{
    mu[1] = 1;
    for (ll i = 2; i < maxn; ++i) {
        if (!vis[i]) pr[++cnt] = i, mu[i] = -1;
        for (ll j = 1; j <= cnt && pr[j] * i < maxn; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) mu[i * pr[j]] = -mu[i];
            else break;
        }
    }

    for (ll i = 1; i < maxn; ++i) g[i] = g[i - 1] + mu[i] * i * i;
}

inline ll S(ll x)
{
    if (x & 1) return ((x + 1) >> 1) * x;
    return (x >> 1) * (x + 1); 
}

signed main()
{
    freopen ("kfc.in", "r", stdin);
    freopen ("kfc.out", "w", stdout);
    init();
    ll T = __read();
    while (T--) {
        ll n = __read();
        ll ans(0);
        int B = int(powl(n, 1.0l / 3));
        int m = int (n / B / B);
        for (int i = 1; i <= B and n / i / i > m; ++i) 
            ans += (g[i] - g[i - 1]) * S(n / i / i);
        for (ll i = m; i; --i) 
            ans += S(i) * (g[int(sqrtl(n / i))] - g[int(sqrt(n / (i + 1)))]);
        printf ("%llu\n", ans);
    }
}

我竟然来更新了

发现\(\left\lfloor\frac n{i^2}\right\rfloor\)这个东西可以直接分块

那么就可以直接写了

才不需要什么其他的三次方根之类的鬼畜玩意儿呢！！！

Code(100+)

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
#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
const ll maxn = 2e7 + 10;

ll n, pr[maxn], mu[maxn];
ll cnt, g[maxn];
bool vis[maxn];

inline ll __read()
{
    ll x(0);
    char o (getchar());
    while (o < '0' || o > '9') 
        o = getchar();
    for (; o >= '0' && o <= '9'; o = getchar()) x = (x << 1) + (x << 3) + (o ^ 48);
    return x;
}

inline void init()
{
    mu[1] = 1;
    for (ll i = 2; i < maxn; ++i) {
        if (!vis[i]) pr[++cnt] = i, mu[i] = -1;
        for (ll j = 1; j <= cnt && pr[j] * i < maxn; ++j) {
            vis[i * pr[j]] = 1;
            if (i % pr[j]) mu[i * pr[j]] = -mu[i];
            else break;
        }
    }

    for (ll i = 1; i < maxn; ++i) g[i] = g[i - 1] + mu[i] * i * i;
}

inline ll S(ll x)
{
    if (x & 1) return ((x + 1) >> 1) * x;
    return (x >> 1) * (x + 1); 
}

signed main()
{
    freopen ("kfc.in", "r", stdin);
    freopen ("kfc.out", "w", stdout);
    init();
    ll T = __read();
    while (T--) {
        ll n = __read();
        ll ans(0);
        for (ll l = 1, r; l * l <= n; l = r + 1) {
            r = sqrt(n / (n / l / l));
            ans += (g[r] - g[l - 1]) * S(n / l / l);
        }
        printf ("%llu\n", ans);
    }
}
附件下载