2022.10.28 模拟赛小结

最惨的一场，基本所有题都挂了，最终得分 $20\mathtt{\text{pts}}$$20\texttt{pts}$。

更好的阅读体验戳此进入

赛时思路

T1

给定不降序列 $a_n$$a_n$，对于 $\mathrm{\forall }m\le k$$\forall m \le k$，将序列分为可空的 $m$$m$ 段，对于第 $i$$i$ 段的数加 $i$$i$，对于每一个 $m$$m$ 令 $q_m$$q_m$ 为增加后的 $\sum _{j=1}^n{a}_j^2$$\sum_{j = 1}^na_j^2$，使 $q_m$$q_m$ 最大，给定 $k$$k$，求最大的 $\sum q_m$$\sum q_m$。

原题 LG-P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳。

贪心策略找到了。。但是式子没推好，最后想了半天只能糊了一个线段树求平方和上去，复杂度 $O(n+k\log n)$$O(n + k \log n)$，理论上能过 $60\mathrm{\%}$$60\%$ 左右，但是大概是写挂了，花花绿绿的，有 WA 也有 RE，直接爆零。

Code

xxxxxxxxxx
108
1
#define USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
using namespace std;
5

6
typedef long long ll;
7
typedef unsigned long long unll;
8
typedef unsigned int uint;
9
typedef long double ld;
10

11
#define MAXN (1100000)
12
#define MOD (998244353)
13

14
template < typename T = int >
15
inline T read(void){
16
    T ret(0);
17
    short flag(1);
18
    char c = getchar();
19
    while(!isdigit(c) && c != '-')c = getchar();
20
    if(c == '-')flag = -1, c = getchar();
21
    while(isdigit(c)){
22
        ret *= 10;
23
        ret += int(c - '0');
24
        c = getchar();
25
    }return ret * flag;
26
}
27

28
int N, K;
29
int a[MAXN];
30

31
class SegTree{
32
private:
33
    ll tr[MAXN << 2];
34
    ll trsq[MAXN << 2];
35
    ll lz[MAXN << 2];
36
    #define LS (p << 1)
37
    #define RS (LS | 1)
38
    #define MID ((gl + gr) >> 1)
39
    #define SIZ (gr - gl + 1)
40
public:
41
    void Pushup(int p){
42
        tr[p] = (tr[LS] + tr[RS]) % MOD;
43
        trsq[p] = (trsq[LS] + trsq[RS]) % MOD;
44
    }
45
    void Pushdown(int p, int gl, int gr){
46
        lz[LS] = (lz[LS] + lz[p]) % MOD, lz[RS] = (lz[RS] + lz[p]) % MOD;
47
        trsq[LS] = (trsq[LS] + 2ll * lz[p] % MOD * tr[LS] % MOD + lz[p] * lz[p] % MOD * (MID - gl + 1) % MOD) % MOD;
48
        trsq[RS] = (trsq[RS] + 2ll * lz[p] % MOD * tr[RS] % MOD + lz[p] * lz[p] % MOD * (gr - MID - 1 + 1) % MOD) % MOD;
49
        tr[LS] = (tr[LS] + lz[p] * (MID - gl + 1) % MOD) % MOD;
50
        tr[RS] = (tr[RS] + lz[p]* (gr - MID - 1 + 1) % MOD) % MOD;
51
        lz[p] = 0;
52
    }
53
    void Build(int p = 1, int gl = 1, int gr = N){
54
        if(gl == gr)return tr[p] = a[gl], trsq[p] = tr[p] * tr[p] % MOD, void();
55
        Build(LS, gl, MID);
56
        Build(RS, MID + 1, gr);
57
        Pushup(p);
58
    }
59
    void Modify(int l, int r, ll val, int p = 1, int gl = 1, int gr = N){
60
        // printf("l = %d, r = %d,  val = %lld, p = %d, gl = %d, gr = %d\n", l, r, val, p, gl, gr);
61
        if(l <= gl && gr <= r)
62
            return trsq[p] = (trsq[p] + 2ll * val % MOD * tr[p] % MOD + val * val % MOD * SIZ % MOD) % MOD,
63
            tr[p] = (tr[p] + val * SIZ % MOD) % MOD,
64
            lz[p] = (lz[p] + val) % MOD,
65
            void();
66
        Pushdown(p, gl, gr);
67
        if(l <= MID)Modify(l, r, val, LS, gl, MID);
68
        if(MID + 1 <= r)Modify(l, r, val, RS, MID + 1, gr);
69
        Pushup(p);
70
    }
71
    ll Query(int l, int r, int p = 1, int gl = 1, int gr = N){
72
        if(l <= gl && gr <= r)return trsq[p];
73
        Pushdown(p, gl, gr);
74
        return
75
            ((l <= MID ? Query(l, r, LS, gl, MID) : 0) +
76
            (MID + 1 <= r ? Query(l, r, RS, MID + 1, gr) : 0)) % MOD;
77
    }
78
}st;
79

80
int main(){
81
    freopen("function.in", "r", stdin);
82
    freopen("function.out", "w", stdout);
83

84
    N = read(), K = read();
85
    for(int i = 1; i <= N; ++i)a[i] = read();
86
    st.Build();
87
    ll ans(0);
88
    for(int i = 1; i <= K; ++i){
89
        int sp = -(int)ceil((double)(K + 1) / 2.0);
90
        auto ptr = lower_bound(a + 1, a + N + 1, sp);
91
        int idx = distance(a + 1, ptr + 1);
92
        st.Modify(1, idx - 1, 1);
93
        st.Modify(idx, N, i);
94
        ans = (ans + st.Query(1, N));
95
        st.Modify(1, idx - 1, -1);
96
        st.Modify(idx, N, -i);
97
        // int mn(1), mx(i);
98
        // for(int j = 1; j <= N; ++j){
99
        //     ll val = max(abs(a[j] + mn), abs(a[j] + mx));
100
        //     // printf("val: %lld\n", val);
101
        //     ans = (ans + val * val % MOD) % MOD;
102
        // }
103
        // // printf("Cur ans : %lld\n", ans);
104
        // printf("Curans : %d = %lld\n", i, ans);
105
    }printf("%lld\n", ans);
106

107
    return 0;
108
}

T2

原题 LG-P8564 ρars/ey。

想到了一些性质，考虑到令 $dp(i)(0/1)$$dp(i)(0/1)$ 设状态然后转移不了假掉了，然后想不到了，然后寄了，虽然这题因为数据随机生成直接输出 $f(n)$$f(n)$ 也能获得 $40\mathtt{\text{pts}}$$40\texttt{pts}$，当然原题没这么良心。

T3

原题 LG-P3921 小学数学题。

基本都切了，然后我没想到。。寄了

T4

原题 51NOD-1819 黑白树 V2。

完全不阳间的题，然后恐怖的水是生命之源在赛时做完调完了，恐怖如斯。。

正解

T1

显然对于一个数最优的要么为 $+1$$+1$ 要么为 $+m$$+m$，并且由于序列的单调性一定存在一个分界点 $sp$$sp$，让前面的数均 $+1$$+1$ 后面的数均 $+m$$+m$ 为最优，且当 $m$$m$ 增加时显然 $sp$$sp$ 单调递减，于是枚举 $m$$m$，延续之前的 $sp$$sp$ 找新的，显然第一个不满足 $(a_{sp}+1{)}^2\le (a_{sp}+m{)}^2$$(a_{sp} + 1)^2 \le (a_{sp} + m)^2$ 的即为分界点，于是此时答案为 $\sum _{i=1}^{sp}(a_i+1{)}^2+\sum _{i=sp+1}^n(a_i+m{)}^2$$\sum_{i = 1}^{sp}(a_i + 1)^2 + \sum_{i = sp + 1}^{n}(a_i + m)^2$，化简一下，$a_i$$a_i$ 前缀和为 $su{m}_i$$sum_i$，$a_i^2$$a_i^2$ 前缀和为 $sums{q}_i$$sumsq_i$，则为 $sums{q}_n+2\times su{m}_{sp}+sp+2\times m\times (su{m}_n-su{m}_{sp})+(n-sp)\times m^2$$sumsq_n + 2 \times sum_{sp} + sp + 2 \times m \times (sum_n - sum_{sp}) + (n - sp) \times m^2$。然后需要注意如果比较为 $\le$$\le$ 那么 $m=1$$m = 1$ 的时候会让 $sp$$sp$ 直接变为 $0$$0$，所以选择 $<$$\lt$。

Code

xxxxxxxxxx
79
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD 998244353
24
#define int ll
25

26
template< typename T = int >
27
inline T read(void);
28

29
int N, K;
30
ll a[1100000];
31
ll sum[1100000];
32
ll sumsq[1100000];
33
ll ans(0);
34

35
signed main(){
36
    N = read(), K = read();
37
    int sp(0);
38
    for(int i = 1; i <= N; ++i)
39
        a[i] = read(),
40
        sum[i] = (sum[i - 1] + a[i] + MOD) % MOD,
41
        sumsq[i] = (sumsq[i - 1] + a[i] * a[i] % MOD) % MOD,
42
        sp = a[i] < 0 ? i : sp;
43
    for(int k = 1; k <= K; ++k){
44
        while(sp && abs(a[sp] + 1) < abs(a[sp] + k))--sp;
45
        ans = (
46
            ans +
47
            (sumsq[N] +
48
                (
49
                    2ll * sum[sp] % MOD +
50
                    (sp +
51
                    (2 * k % MOD * ((sum[N] - sum[sp] + MOD) % MOD)) % MOD +
52
                    (N - sp) * k % MOD * k % MOD
53
                    ) % MOD
54
                ) % MOD
55
            )
56
        ) % MOD;
57
    }printf("%lld\n", ans);
58

59
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
60
    return 0;
61
}
62

63

64

65
template < typename T >
66
inline T read(void){
67
    T ret(0);
68
    short flag(1);
69
    char c = getchar();
70
    while(c != '-' && !isdigit(c))c = getchar();
71
    if(c == '-')flag = -1, c = getchar();
72
    while(isdigit(c)){
73
        ret *= 10;
74
        ret += int(c - '0');
75
        c = getchar();
76
    }
77
    ret *= flag;
78
    return ret;
79
}

T2

咕咕咕。

T3

咕咕咕。

T4

咕咕咕。

UPD

update-2022_10_28 初稿