Cauphenuny's blog

20201226~27 考试总结

发表于 更新于 分类于

考的是六省联考的卷子

problem

Day1

review

开考先看三题, 发现第一题是很容易写假的贪心题的样子，于是就跳了。看到第二题，正好之前见过 cccc…c^{c^{c^{c^{\ldots}}}} 这种套路，决定开这个，第三题貌似是个数学题，弃了。

然后调着调着就再一次发现了著名的坑，等下写，调出来的时候已经过了两个半小时，然后一测第 3 个大样例就 T飞，到处卡常，结果发现没有预处理 phi[] 数组，，，

三个小时过了，赶紧把 T3 30pts 暴力写了，没有仔细想第一题，甚至没看数据范围，可能是最大的错误

solution

exam

problem

比较容易的题，正解是三分，但是可以暴力 O(值域) 搞过去

考虑一个状态 T ，如果 A 小于 B ，那么就可以将所有公布时间在 T 之前的学科移到 T 时刻公布，“挤出”sum1 的时间，用于将公布时间在 T 之后的学科移到 T 时刻，花掉 sum2 的时间，这一部分的代价为 min⁡(sum1,sum2)⋅A\min(sum_1,sum_2)\cdot A ，如果 sum2 比 sum1 大，那么还要花 (sum2−sum1)⋅B(sum_2-sum_1)\cdot B 才能把所有科目移到时间 T；A 大于 B 的，直接跳过第一个步骤即可。接着计算 T 时的不愉快值即可。

还是要多观察状态，比如这个题就可以 O(1)O(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
//#pragma GCC diagnostic error "-std=c++11"
//#pragma Gcc optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdarg>
#include<typeinfo>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
template <class T> bool mvmax(T &a, T b) {return b > a ? (a = b, 1) : 0;}
template <class T> bool mvmin(T &a, T b) {return b < a ? (a = b, 1) : 0;}
void read(char *s) {scanf("%s", s);} void read(char &c) {scanf("%c", &c);}
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
//#define fastin cin
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

const int MAXN = 1e5 + 10;
#define int long long

int A, B, C, maxv;
int n, m, t[MAXN], b[MAXN];
int sum1[MAXN], sum2[MAXN], cnt[MAXN], act[MAXN];
int ans;

signed main() {
#ifndef ONLINE_JUDGE
    freopen("exam.in", "r", stdin);
    freopen("exam.out", "w", stdout);
    freopen("exam.err", "w", stderr);
#endif
    fastin >> A >> B >> C;
    fastin >> n >> m;
    for (int i = 1; i <= n; i++) {
        fastin >> t[i];
        mvmax(maxv, t[i]);
    }
    sort(t + 1, t + n + 1);
    for (int i = 1; i <= m; i++) {
        fastin >> b[i];
        mvmax(maxv, b[i]);
    }
    sort(b + 1, b + m + 1);
    for (int i = 1; i <= n; i++) {
        act[t[i]]++;
    }
    for (int i = 1, p = 0; i <= maxv; i++) {
        p += act[i - 1];
        cnt[i] = cnt[i - 1] + p;
//        debugf("cnt[%d] = %d\n", i, cnt[i]);
    }
    memset(act, 0, sizeof(act));
    for (int i = 1; i <= m; i++) {
        act[b[i]]++;
//        debugf("add act[%d] to %d\n", b[i], act[b[i]]);
    }
    memset(&ans, 0x3f, sizeof(decltype(ans)));
    for (int i = 1, p = 0; i <= maxv; i++) {
        p += act[i - 1];
        sum1[i] = sum1[i - 1] + p;
//        debugf("sum1[%d]=%d\n", i, sum1[i]);
    }
    for (int i = maxv, p = 0; i >= 0; i--) {
        p += act[i + 1];
        sum2[i] = sum2[i + 1] + p;
//        debugf("sum2[%d] = %d\n", i, sum2[i]);
    }
    for (int i = 0; i <= maxv; i++) {
        if (A >= B) {
            if (sum2[i] * B + cnt[i] * C >= 0)
            if (mvmin(ans, sum2[i] * B + cnt[i] * C)) {
//                debugf(
//                "update ans(%d) on T = %d, sum1 = %d, sum2 = %d, cnt = %d\n"
//                , ans, i, sum1[i], sum2[i], cnt[i]);
            }
        } else {
            if (
                          ((min(sum1[i], sum2[i]) * A) +
                          (max(sum2[i] - sum1[i], 0ll) * B) +
                          cnt[i] * C) >= 0)
            if (mvmin(ans,
                          (min(sum1[i], sum2[i]) * A) +
                          (max(sum2[i] - sum1[i], 0ll) * B) +
                          cnt[i] * C)) {
//                debugf(
//                "update ans(%d) on T = %d, sum1 = %d, sum2 = %d, cnt = %d,"
//                " A/B/C=%d/%d/%d\n"
//                , ans, i, sum1[i], sum2[i], cnt[i], A, B, C);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

verbinden

problem

长度为 n 的数组，m 个操作（两类），给定数 c

0 l r 将 al…ra_{l\ldots r} 中每一个数换成 caic^{a_i}

1 l r 求 ∑i=lraimod  p\sum\limits_{i=l}^{r}a_i\mod p

略套路的题，如果之前做过 CF906D Power Tower 和 P4145 花神游历各国 以及P4139 上帝与集合的正确用法 的话应该是不难想到做法的，感觉就是几个题目的杂糅版

考虑一个数 aia_i 当它被操作多次后变成了 cccccaic^{c^{c^{c^{c^{a_i}}}}} ，而这个数  mod p\bmod p 的结果是固定的，与 aia_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
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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
//#pragma GCC diagnostic error "-std=c++11"
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdarg>
#include<typeinfo>
#include<cmath>
#define debug(x) cerr << #x << " = " << x << endl
#define debugf(...) fprintf(stderr, __VA_ARGS__)
#define darray(x, a, b) fprintf(stderr, #x"[%lld][%lld] = %lld\n", a, b, x[a][b])
using namespace std;
template <class T> bool mvmax(T &a, T b) {return b > a ? (a = b, 1) : 0;}
template <class T> bool mvmin(T &a, T b) {return b < a ? (a = b, 1) : 0;}
template <class T> void read(T &a) {
    a = 0; char c = getchar(); int f = 0;
    while (!isdigit(c)) { f ^= c == '-',  c = getchar(); }
    while (isdigit(c)) { a = a * 10 + (c ^ 48),  c = getchar(); }
    a *= f ? -1 : 1;
}
//#define fastin cin
struct Fastin {
    template <class T> Fastin& operator >> (T &x) {read(x); return *this;}
} fastin;

#define int unsigned long long

const int MAXN = 5e4 + 10;
const int SQRTP = 5e4 + 10;
const int SQRTN = 240;

int mod, g_val, g_cnt;
int n, m, c;
int a[MAXN];
int phip[50];

namespace quickpow {

    int s1[50][SQRTP], s2[50][SQRTP], sqr[50];

    void init() {
        for (int t = 0; t < 50; t++) {
            if (phip[t] == 0) break;
            sqr[t] = sqrt(mod * 2);
            debug(mod * 2);
            s2[t][0] = 1;
            for (int i = 1; i <= sqr[t]; i++) {
                s2[t][i] = s2[t][i - 1] * c;
                if (s2[t][i] >= phip[t]) {
                    s2[t][i] %= phip[t];
                    s2[t][i] += phip[t];
                }
            }
            s1[t][0] = 1, s1[t][1] = s2[t][sqr[t]];
            for (int i = 2, delta = s1[t][1]; i <= ((phip[t] + phip[t + 1] + 10) / sqr[t]); i++) {
                s1[t][i] = s1[t][i - 1] * delta;
                if (s1[t][i] >= phip[t]) {
                    s1[t][i] %= phip[t];
                    s1[t][i] += phip[t];
                }
            }
        }
    }

    int calc(int x, int mod) {
        //printf("%llu ^ %llu mod %llu = %llu\n", c, x, phip[mod], (s1[mod][x / sqr[mod]] * s2[mod][x % sqr[mod]]) % phip[mod]);
        int ret = (s1[mod][x / sqr[mod]] * s2[mod][x % sqr[mod]]);
        if (ret >= phip[mod]) {
            ret %= phip[mod];
            ret += phip[mod];
        }
        return ret;
    }
}

int phi(int x) {
    int ans = x, p = x;
    for (int i = 2; i * i <= p; i++) {
        if (x % i == 0) {
            ans = ans / i * (i - 1);
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x != 1) {
        ans = ans / x * (x - 1);
    }
    return ans;
}

int power_tag;

int power(int a, int b, int p) {
    int res = 1;
    power_tag = 0;
    while (b) {
        if (b & 1) {
            res = res * a;
            if (res >= p) {
                power_tag = 1;
                res %= p;
            }
        }
        a = a * a;
        if (a >= p) {
            power_tag = 1;
            a %= p;
        }
        b >>= 1;
    }
    return res;
}

int pre(int p) {
    if (p == 1) { return 0; }
    g_cnt++;
    phip[g_cnt] = phi(p);
    int ret = pre(phip[g_cnt]);
    return power(c, ret + phip[g_cnt], p);
}

int gg_tag, mod_tag;

int mod_power(int cnt, int a, int tim = 0) {
    int p = phip[tim];
    if (cnt == 0) {/*//debug(p)*/; return (a > p) ? a % p + p : a;}
    if (p == 1) { gg_tag = 1; return (c != 0) || a != 0; }
    int prev = mod_power(cnt - 1, a, tim + 1);
    //int ret = power(c, prev, p);
    //printf("tim = %llu[%llu], prev = %llu\n", tim, p, prev);
    return quickpow::calc(prev, tim);
}

#undef mul

struct Segment {
    int cnt;
    int val;
    int tag;
    Segment(): cnt(0), val(0), tag(0) {}
} s[MAXN * 30];

#define mid ((l + r) >> 1)
#define ls ((p) << 1)
#define rs ((p) << 1 | 1)

inline void pushup(int p, int l, int r) {
    if (l != r) {
        if (s[ls].tag && s[rs].tag) {
            s[p].tag |= 1;
        }
        s[p].val = s[ls].val + s[rs].val;
    }
}

void build_tree(int p, int l, int r) {
    if (l == r) {
        s[p].val = a[l];
        return;
    }
    build_tree(ls, l, mid);
    build_tree(rs, mid + 1, r);
    pushup(p, l, r);
}

void print_tree(int p, int l, int r) {
    //printf("tree #%lld[%lld, %lld]:\nls = #%lld, rs = #%lld, val = %lld\n", p, l, r, ls, rs, s[p].val);
    if (l < r) {
        print_tree(ls, l, mid);
        print_tree(rs, mid + 1, r);
    }
}

int m_cnt, x, y;

void modify(int p, int l, int r) {
    m_cnt++;
    if (l == r) {
        s[p].cnt++;
        //s[p].val = power(c, s[p].val, mod);
        //gg_tag = 1;
        gg_tag = 0;
        s[p].val = mod_power(s[p].cnt, a[l]);
        if (gg_tag) {
            s[p].tag = 1;
        }
        return;
    }
    if (x <= mid) {
        if (!s[ls].tag)
            modify(ls, l, mid);
    }
    if (mid < y) {
        if (!s[rs].tag)
            modify(rs, mid + 1, r);
    }
    pushup(p, l, r);
}

int query(int p, int l, int r) {
    if (x <= l && r <= y) {
        return s[p].val;
    }
    int res = 0;
    int m = mid;
    if (x <= m) {
        (res += query(ls, l, m)) %= mod;
    }
    if (m < y) {
        (res += query(rs, m + 1, r)) %= mod;
    }
    return res;
}

#undef mid
#undef ls
#undef rs

signed main() {
    //debugf("started.\n");
    fastin >> n >> m >> mod >> c;
    for (int i = 1; i <= n; i++) {
        fastin >> a[i];
    }
    //debug(base_siz);
    //debugf("input done.\n");
    phip[0] = mod;
    pre(mod);
    quickpow::init();
    debug(quickpow::calc(8, 0));
    //debug(g_cnt);
    build_tree(1, 1, n);
    //puts("----after build----");
    //puts("----(end)----");
    for (int i = 1, opt; i <= m; i++) {
        //debugf("i = %lld, m_cnt = %lld\n", i, m_cnt);
        fastin >> opt >> x >> y;
        switch (opt) {
            case 0:
                modify(1, 1, n);
                //printf("----------operation @%lld------------\n", i);
                //print_tree(1, 1, n);
                //printf("--------------(end)---------------\n");
                break;
            case 1:
                printf("%llu\n", query(1, 1, n) % mod);
                break;
        }
    }
    return 0;
}

problem

Day2