2023.02.16 模拟赛小结

更好的阅读体验戳此进入

赛时思路

T1

给定 $n\times m$$n \times m$ 的 $01$$01$ 矩阵，你需要构造一个初始矩阵，每过 $1$$1$ 单位时间，所有 $1$$1$ 会八向扩展使得周围所有 $0$$0$ 变成 $1$$1$。过程不能使得 $1$$1$ 向矩阵外扩展，你需要使得你构造的初始矩阵能够最大化扩展次数，输出扩展次数与任一最优合法初始矩阵。

$n\times m\le {10}^6$$n \times m \le 10^6$。

一个显而易见的思路，用 $3\times 3,5\times 5,\cdots$$3 \times 3, 5 \times 5, \cdots$ 的矩阵去填充即可，并且尽量用更大的填充，二分答案然后枚举验证跑一下即可，实现上可以强行维护二位前缀和强行做，也可以写个宽搜之类的东西搞一搞，比较简单，签到题。

（最后拿到了 $95\mathtt{\text{pts}}$$95\texttt{pts}$ 主要是因为 ty > M ? M : ty 最开始写成 $n$$n$ 了。。。

Code

xxxxxxxxxx
146
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.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 void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
10
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
11

12
using namespace std;
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
template < typename T = int >
24
inline T read(void);
25

26
int N, M;
27
vector < vector < bool > > mp;
28
vector < vector < int > > sum;
29
vector < vector < bool > > mark;
30
vector < vector < int > > csum;
31

32
bool Check(int siz){
33
    for(int i = 1; i <= N; ++i)
34
        for(int j = 1; j <= M; ++j)
35
            mark[i][j] = false, csum[i][j] = 0;
36
    for(int i = siz + 1; i <= N - siz; ++i){
37
        for(int j = siz + 1; j <= M - siz; ++j){
38
            int sx = i - siz, sy = j - siz, tx = i + siz, ty = j + siz;
39
            int rsum = sum[tx][ty] - sum[sx - 1][ty] - sum[tx][sy - 1] + sum[sx - 1][sy - 1];
40
            int esum = ((siz << 1) | 1) * ((siz << 1) | 1);
41
            if(esum == rsum)mark[i][j] = true;
42
        }
43
    }
44
    for(int i = 1; i <= N; ++i)
45
        for(int j = 1; j <= M; ++j)
46
            csum[i][j] = csum[i - 1][j] + csum[i][j - 1] - csum[i - 1][j - 1] + mark[i][j];
47
    for(int i = 1; i <= N; ++i)
48
        for(int j = 1; j <= M; ++j){
49
            int sx = i - siz, sy = j - siz, tx = i + siz, ty = j + siz;
50
            if(mp[i][j] && !(csum[tx > N ? N : tx][ty > M ? M : ty] - csum[tx > N ? N : tx][sy - 1 < 0 ? 0 : sy - 1] - csum[sx - 1 < 0 ? 0 : sx - 1][ty > M ? M : ty] + csum[sx - 1 <= 0 ? 0 : sx - 1][sy - 1 < 0 ? 0 : sy - 1]))
51
                return false;
52
        }
53
    return true;
54
}
55

56
int main(){
57
    freopen("yawn.in", "r", stdin);
58
    freopen("yawn.out", "w", stdout);
59
    N = read(), M = read();
60
    for(int i = 0; i <= N; ++i){
61
        mark.emplace_back(vector < bool >());
62
        csum.emplace_back(vector < int >());
63
        for(int j = 0; j <= M; ++j)
64
            // mark[i] += false, csum[i] += 0;
65
            mark[i].emplace_back(false), csum[i].emplace_back(0);
66
    }
67
    // mp += vector < bool >();
68
    mp.emplace_back(vector < bool >());
69
    // vis += vector < bool >();
70
    for(int i = 0; i <= M; ++i)mp[0].emplace_back(false);//, vis[0] += false;
71
    for(int i = 1; i <= N; ++i){
72
        mp.emplace_back(vector < bool >());//   += vector < bool >();
73
        // vis += vector < bool >();
74
        // mp[i] += false;//, vis[i] += false;
75
        mp[i].emplace_back(false);
76
        for(int j = 1; j <= M; ++j){
77
            char c = getchar(); while(c != '.' && c != 'X')c = getchar();
78
            // mp[i] += c == '.' ? false : true;
79
            mp[i].emplace_back(c == '.' ? false : true);
80
            // vis[i] += c == '.' ? false : true;
81
        }
82
    }
83
    // sum += vector < int >();
84
    sum.emplace_back(vector < int >());
85
    for(int i = 0; i <= M; ++i)sum[0].emplace_back(0);  //sum[0] += 0;
86
    for(int i = 1; i <= N; ++i){
87
        // sum += vector < int >();
88
        sum.emplace_back(vector < int >());
89
        // sum[i] += 0;
90
        sum[i].emplace_back(0);
91
        for(int j = 1; j <= M; ++j)
92
            // sum[i] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mp[i][j];
93
            sum[i].emplace_back(sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mp[i][j]);
94
    }
95

96
    printf("Checking 50 %d\n\n\n\n\n", Check(50) ? 1 : 0);
97

98

99
    int l = 1, r = min((N - 1) >> 1, (M - 1) >> 1), ans = -1;
100
    while(l <= r){
101
        int mid = (l + r) >> 1;
102
        if(Check(mid))ans = mid, l = mid + 1;
103
        else r = mid - 1;
104
    }
105
    if(!~ans){
106
        printf("0\n");
107
        for(int i = 1; i <= N; ++i)
108
            for(int j = 1; j <= M; ++j)
109
                printf("%c%s", mp[i][j] ? 'X' : '.', j == M ? "\n" : "");
110
        exit(0);
111
    }
112
    int siz = ans;
113
    for(int i = 1; i <= N; ++i)
114
        for(int j = 1; j <= M; ++j)
115
            mark[i][j] = false;
116
    for(int i = siz + 1; i <= N - siz; ++i){
117
        for(int j = siz + 1; j <= M - siz; ++j){
118
            int sx = i - siz, sy = j - siz, tx = i + siz, ty = j + siz;
119
            int rsum = sum[tx][ty] - sum[sx - 1][ty] - sum[tx][sy - 1] + sum[sx - 1][sy - 1];
120
            int esum = ((siz << 1) | 1) * ((siz << 1) | 1);
121
            if(esum == rsum)mark[i][j] = true;
122
        }
123
    }
124
    printf("%d\n", ans);
125
    for(int i = 1; i <= N; ++i)
126
        for(int j = 1; j <= M; ++j)
127
            printf("%c%s", mark[i][j] ? 'X' : '.', j == M ? "\n" : "");
128
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
129
    return 0;
130
}
131

132
template < typename T >
133
inline T read(void){
134
    T ret(0);
135
    int flag(1);
136
    char c = getchar();
137
    while(c != '-' && !isdigit(c))c = getchar();
138
    if(c == '-')flag = -1, c = getchar();
139
    while(isdigit(c)){
140
        ret *= 10;
141
        ret += int(c - '0');
142
        c = getchar();
143
    }
144
    ret *= flag;
145
    return ret;
146
}

T2

给定序列，每次从序列中取数直至取空，每次取 $a_i$$a_i$ 时的贡献为 $min(a_{i-1},a_{i+1})$$\min(a_{i - 1}, a_{i + 1})$，若不存在则贡献为 $0$$0$，最大化贡献，求最大值。

赛时思路是考虑记录 $va{l}_i$$val_i$ 表示两侧数的较小值，记录 $pr{i}_i$$pri_i$ 表示 $va{l}_i$$val_i$ 减去其两侧 $val$$val$ 因 $i$$i$ 的删除而导致的贡献减少量，以 $pri$$pri$ 为关键字丢到优先队列里，然后每次取出后动态维护，即对 $i$$i$ 维护 $pr{e}_i,pr{e}_{pr{e}_i},nx{t}_i,nx{t}_{nx{t}_i}$$pre_i, pre_{pre_i}, nxt_i, nxt_{nxt_i}$ 的 $pri$$pri$ 变化，大概这样跑一下，当然最终对拍时发现假了。

$1\le T\le 10,1\le n\le {10}^6,1\le a_i\le {10}^6$$1 \le T \le 10, 1 \le n \le 10^6, 1 \le a_i \le 10^6$。

Code

xxxxxxxxxx
103
1
/*
2
2
3
5
4
7 10 4 9 4
5
3
6
2 1 7
7

8
3
9
7
10
22 34 48 12 48 37 27
11
10
12
19 37 37 51 40 87 25 28 81 26
13
9
14
51 60 21 52 25 46 40 37 3
15
*/
16
#define _USE_MATH_DEFINES
17
#include <bits/stdc++.h>
18

19
#define PI M_PI
20
#define E M_E
21
#define npt nullptr
22
#define SON i->to
23
#define OPNEW void* operator new(size_t)
24
#define ROPNEW void* Edge::operator new(size_t){static Edge* P = ed; return P++;}
25
#define ROPNEW_NODE void* Node::operator new(size_t){static Node* P = nd; return P++;}
26

27
using namespace std;
28

29
mt19937 rnd(random_device{}());
30
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
31
bool rnddd(int x){return rndd(1, 100) <= x;}
32

33
typedef unsigned int uint;
34
typedef unsigned long long unll;
35
typedef long long ll;
36
typedef long double ld;
37

38
template < typename T = int >
39
inline T read(void);
40

41
int N;
42
int A[1100000];
43
int val[1100000];
44
int pri[1100000];
45
int pre[1100000], nxt[1100000];
46
bitset < 1100000 > vis;
47
ll ans(0);
48

49
priority_queue < pair < int, int >, vector < pair < int, int > >, less < pair < int, int > > > cur;
50

51
int main(){
52
    freopen("sum.in", "r", stdin);
53
    freopen("sum.out", "w", stdout);
54
    int T = read();
55
    while(T--){
56
        for(int i = 0; i <= N + 1; ++i)vis[i] = false;
57
        N = read();
58
        A[0] = A[N + 1] = 0; pre[0] = 0, nxt[N + 1] = N + 1, pre[N + 1] = N, nxt[0] = 1;
59
        val[0] = val[N + 1] = pri[0] = pri[N + 1] = 0, ans = 0;
60
        for(int i = 1; i <= N; ++i)A[i] = read();
61
        for(int i = 1; i <= N; ++i)pre[i] = i - 1, nxt[i] = i + 1;
62
        for(int i = 1; i <= N; ++i)val[i] = min(A[pre[i]], A[nxt[i]]);
63
        for(int i = 1; i <= N; ++i)pri[i] = val[i] - (val[pre[i]] - min(A[pre[pre[i]]], A[nxt[i]])) - (val[nxt[i]] - min(A[nxt[nxt[i]]], A[pre[i]]));
64
        for(int i = 1; i <= N; ++i)cur.push({pri[i], i});
65
        while(!cur.empty()){
66
            auto tp = cur.top(); cur.pop();
67
            int idx = tp.second;
68
            if(tp.first != pri[idx] || vis[idx])continue;
69
            ans += val[idx], vis[idx] = true;
70
            val[pre[idx]] = min(A[pre[pre[idx]]], A[nxt[idx]]);
71
            val[nxt[idx]] = min(A[nxt[nxt[idx]]], A[pre[idx]]);
72
            pri[pre[idx]] = val[pre[idx]] - (val[pre[pre[idx]]] - min(A[pre[pre[pre[idx]]]], A[nxt[idx]])) - (val[nxt[idx]] - min(A[nxt[nxt[idx]]], A[pre[pre[idx]]]));
73
            pri[nxt[idx]] = val[nxt[idx]] - (val[pre[idx]] - min(A[pre[pre[idx]]], A[nxt[nxt[idx]]])) - (val[nxt[nxt[idx]]] - min(A[nxt[nxt[nxt[idx]]]], A[pre[idx]]));
74
            cur.push({pri[pre[idx]], pre[idx]}), cur.push({pri[nxt[idx]], nxt[idx]});
75
            nxt[pre[idx]] = nxt[idx], pre[nxt[idx]] = pre[idx];
76
            int i = pre[pre[idx]];
77
            pri[i] = val[i] - (val[pre[i]] - min(A[pre[pre[i]]], A[nxt[i]])) - (val[nxt[i]] - min(A[nxt[nxt[i]]], A[pre[i]]));
78
            cur.push({pri[i], i});
79
            i = nxt[nxt[idx]];
80
            pri[i] = val[i] - (val[pre[i]] - min(A[pre[pre[i]]], A[nxt[i]])) - (val[nxt[i]] - min(A[nxt[nxt[i]]], A[pre[i]]));
81
            cur.push({pri[i], i});
82
        }printf("%lld\n", ans);
83
    }
84

85
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
86
    return 0;
87
}
88

89
template < typename T >
90
inline T read(void){
91
    T ret(0);
92
    // int flag(1);
93
    char c = getchar();
94
    while(!isdigit(c))c = getchar();
95
    // if(c == '-')flag = -1, c = getchar();
96
    while(isdigit(c)){
97
        ret *= 10;
98
        ret += int(c - '0');
99
        c = getchar();
100
    }
101
    // ret *= flag;
102
    return ret;
103
}

T3

给定序列 $p_n,q_n$$p_n, q_n$，形成函数序列 $f_n$$f_n$，其中 $f_i(x)=\lfloor {\displaystyle \frac{x}{p_i}}\rfloor +q_i$$f_i(x) = \lfloor \dfrac{x}{p_i} \rfloor + q_i$。

给定 $m$$m$ 个操作，包括单点修改 $p_i,q_i$$p_i, q_i$，以及给定 $s,t$$s, t$，查询 $f_t(f_{t-1}(\cdots f_s(x)))$$f_t(f_{t - 1}(\cdots f_s(x)))$。

$n,m\le 5\times {10}^5$$n, m \le 5 \times 10^5$。

赛时写了个暴力，就不挂 Code 了。

T4

奇怪题，没写。

正解

T2

考虑三个数 $x,y,z$$x, y, z$，若 $x\ge y,z\ge y$$x \ge y, z \ge y$，那么删 $y$$y$ 最优，处理后最终剩下一个单峰的凸函数，考虑最大值次大值，显然其相邻且不会被作为答案，于是考虑第三大，若第三大与最大值相邻则删去最大值，反之则一定与次大值相邻，此时删除次大值，以此维护即可。

T3

首先说一下 @sssmzy 的高妙思路（确实巧妙，必须 %%%%%%%

考虑下取整的意义就是正常的除法之后再取整，于是直接考虑我们不考虑下取整，认为其为标准除法，然后则可以在线段树上合并，最后再取整即可。有一个问题就是这个东西并不是适用于所有，本题适用应该是因为对于 $<1$$\lt 1$ 的小数部分除以一个 $\ge 1$$\ge 1$ 的数一定不会变得 $\ge 1$$\ge 1$，所以合并之后不会对答案造成影响。还有个细节就是不能用 long double，会 $\mathtt{\text{TLE}}$$\texttt{TLE}$，所以说 long double 真的很慢。（@sssmzy 就是因为 long double 而 $\mathtt{\text{TLE}}$$\texttt{TLE}$ 了

UPD

update-2023_02_16 初稿