OI
15 minutes read (About 2202 words)

「模拟测试」20170822

T1 连环

给定一个长度为 $n$ 的字符串 $S$ 和一个长度为 $m$ 的字符串 $T$，现在有 $k$ 个询问，每个询问是给出两个整数 $l, r$，询问任选一对 $(i, j)$ 满足 $0 \leq i \leq l, n \geq j \geq r$，删去 $S$ 的 $[i + 1, j - 1]$ 这个区间的子串，剩下两块拼在一起，$T$ 在其中匹配数的期望。

题解

由于输出格式乘上了对应种数，保证输出是整数，于是我们可以考虑计算对应的贡献。
删去一段之后的匹配分两种，一种是本来就匹配的，另一种是两端连接产生的新匹配。

先考虑本来就匹配的，设 $T$ 的某个匹配为 $(l, r)$，那么若 $r \leq L$，其贡献为 $(L - r + 1) \times (n - R + 1) = (L + 1)(n - R + 1) - r(n - R + 1)$，那么我们可以预处理一下匹配的 $r$ 的前缀和匹配数的前缀和，同理 $l \geq R$ 时，贡献为 $(l - R + 1) \times L$。
而拼接起来的匹配，只需要分成两段分别计算就好了。

时间复杂度 $O(cnm + ck)$。

代码

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
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「模拟测试」20170822 T1 连环 22-08-2017
 *
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}

namespace Task {

const int MAXN = 50000;
const int MAXM = 100;

char s[MAXN + 1], t[MAXM + 1];

typedef unsigned int uint;
typedef unsigned long long ulong;

const uint HASH_BASE = 31;
uint hashS[MAXN + 1], hashT[MAXM + 1], pow31[MAXN + 1];
uint f[2][MAXM + 1][MAXN + 1];

ulong sumL[MAXN + 1], sumR[MAXN + 1], numL[MAXN + 1], numR[MAXN + 1];

inline uint hash(uint *h, int l, int r) {
    return h[r] - h[l - 1] * pow31[r - l + 1];
}

inline void initPow() {
    pow31[0] = 1, pow31[1] = HASH_BASE;
    for (register int i = 2; i <= MAXN; i++)
        pow31[i] = pow31[i - 1] * HASH_BASE;
}

inline void init(int n, int m) {
    for (register int i = 1; i <= n; i++)
        hashS[i] = hashS[i - 1] * HASH_BASE + s[i];
    for (register int i = 1; i <= m; i++)
        hashT[i] = hashT[i - 1] * HASH_BASE + t[i];
    for (register int i = 1; i <= m - 1; i++) {
        for (register int j = 1; j + i - 1 <= n; j++)
            if (hash(hashT, 1, i) == hash(hashS, j, j + i - 1))
                f[0][i][j + i - 1]++;
        for (register int j = 1; j + (m - i) - 1 <= n; j++)
            if (hash(hashT, i + 1, m) == hash(hashS, j, j + (m - i) - 1))
                f[1][i][j]++;
        for (register int j = 1; j <= n; j++) f[0][i][j] += f[0][i][j - 1];
        for (register int j = n; j >= 1; j--) f[1][i][j] += f[1][i][j + 1];
    }
    for (register int i = 1; i + m - 1 <= n; i++) {
        if (hash(hashT, 1, m) == hash(hashS, i, i + m - 1)) {
            sumR[i + m - 1] += i + m - 1, sumL[i] += i;
            numR[i + m - 1]++, numL[i]++;
        }
    }
    for (register int i = 1; i <= n; i++)
        sumR[i] += sumR[i - 1], numR[i] += numR[i - 1];
    for (register int i = n; i >= 1; i--)
        sumL[i] += sumL[i + 1], numL[i] += numL[i + 1];
}

inline void query(int l, int r, int n, int m) {
    using namespace IO;
    register ulong ret = (l + 1) * (n - r + 1) * numR[l] -
                         (n - r + 1) * sumR[l] + (1 - r) * l * numL[r] +
                         l * sumL[r];

    for (register int j = 1; j < m; j++) ret += (ulong)f[0][j][l] * f[1][j][r];
    print(ret), print('\n');
}

inline void solve() {
    using namespace IO;
    initPow();
    register int T, n, m, k;
    for (read(T); T--;) {
        read(n), read(m), read(k), read(s + 1), read(t + 1), init(n, m);
        for (register int l, r; k; k--) read(l), read(r), query(l, r, n, m);
        memset(sumL, 0, sizeof(ulong) * (n + 1));
        memset(sumR, 0, sizeof(ulong) * (n + 1));
        memset(numL, 0, sizeof(ulong) * (n + 1));
        memset(numR, 0, sizeof(ulong) * (n + 1));
        memset(f, 0, sizeof(f));
    }
}
}

int main() {
    freopen("lianhuan.in", "r", stdin);
    freopen("lianhuan.out", "w", stdout);
    Task::solve();
    IO::flush();
    return 0;
}

T2 游戏

一开始有 $n$ 个石子，一个人先手，每次可以取 $p$ 的倍数个石子，若 $n < p$ 则只能添加 $p$ 个石子；另一个人每次可以取 $q$ 的倍数个石子，若 $n < q$ 则只能添加 $q$ 个石子，两人都按照最优方案来走，不能操作的人输，问最后谁胜。

题解

假设先手是甲，后手是乙，如果 $n \nmid \gcd(p, q)$，显然无解，然后让 $p, q, n$ 都除以他们的 $\gcd$。

现在不断地 $+p, +q$ 直到当前的先手可以拿石子了为止，如果是乙的话就交换甲乙的地位。

容易知道如果 $p \leq q$ 且 $n \geq p$ 的话先手就赢了，因为每次 $p$ 拿完之后 $q$ 必须加上去，而 $p \perp
q$，因此每次 $p$ 拿完之后剩的石子数是不一样的，因此总有一天 $p$ 能把他拿到 $0$ 个。
如果 $p > q$，那么先手肯定要给乙留下必须加石子的局面，否则就像上面说的那样，乙必胜了，设 $p$ 拿完之后剩下的石子数是 $k$，那么之后一定是不断加 $q$ 个，拿 $p$ 个，因此可以检查 $k \text{ mod } (p - q)$，如果为 $0$ 的话就是甲胜，否则总有一天乙可以达成上述的必胜情况。

代码

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
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「模拟测试」20170822 T2 游戏 22-08-2017
 *
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void print(const char *s) {
    for (; *s; s++) print(*s);
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}

namespace Force {

const char *KONG_ZI = "kongzi\n";
const char *YAN_HUI = "yanhui\n";

inline void solve(int n, int p, int q) {
    using namespace IO;
    const char *word[2] = {KONG_ZI, YAN_HUI};
    register int gcd = std::__gcd(p, q);
    if (n % gcd != 0) {
        print("wujie\n");
        return;
    }
    p /= gcd, q /= gcd, n /= gcd;
    register bool flag = false;
    if (n < p && n + p >= q) {
        n += p, std::swap(p, q), std::swap(word[0], word[1]);
    } else if (n < p) {
        n += p + q;
    }
    if (p <= q) {
        print(word[0]);
        return;
    }
    register int k = n % p;
    if (k >= q) {
        print(word[1]);
        return;
    }
    if (k % (p - q) == 0) {
        print(word[0]);
        return;
    }
    print(word[1]);
}

inline void solve() {
    using namespace IO;
    register int T, n, p, q;
    for (read(T); T--;) read(p), read(q), read(n), solve(n, p, q);
}
}

int main() {
    freopen("youxi.in", "r", stdin);
    freopen("youxi.out", "w", stdout);
    Force::solve();
    IO::flush();
    return 0;
}

T3 德充符

给定 $n$ 个数，$a_1, a_2, a_3, \cdots, a_n$，现在重排这些数使得
$$||\cdots ||a_1 - a_2| - a_3| - \cdots| - a_n|$$
最大。

题解

这个题数据也太水了，随手叉掉了 A 掉的乱随机和贪心!!!

直接模拟退火就好，正确率还是比乱随机有保障的…

正解是用堆积木模型 dp，设 $f[i][k]$ 表示只用前 $i$ 个，两边的高度差达到 $k$ 可行不可行，转移就是
$$f[i][k + a[i]] = f[i][|k - a[i]|] = \text{true} \ \ (f[i - 1][k] = \text{true})$$

代码

模拟退火

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
/**
 * Copyright (c) 2017, xehoth
 * All rights reserved.
 * 「模拟测试」20170822 T3 德充符 22-08-2017
 * 模拟退火
 * @author xehoth
 */
#include <bits/stdc++.h>

namespace IO {

inline char read() {
    static const int IN_LEN = 1000000;
    static char buf[IN_LEN], *s, *t;
    s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin) : 0;
    return s == t ? -1 : *s++;
}

template <typename T>
inline void read(T &x) {
    static char c;
    static bool iosig;
    for (c = read(), iosig = false; !isdigit(c); c = read()) {
        if (c == -1) return;
        c == '-' ? iosig = true : 0;
    }
    for (x = 0; isdigit(c); c = read()) x = (x + (x << 2) << 1) + (c ^ '0');
    iosig ? x = -x : 0;
}

inline int read(char *buf) {
    register int s = 0;
    register char c;
    while (c = read(), isspace(c) && c != -1)
        ;
    if (c == -1) {
        *buf = 0;
        return -1;
    }
    do
        buf[s++] = c;
    while (c = read(), !isspace(c) && c != -1);
    buf[s] = 0;
    return s;
}

const int OUT_LEN = 1000000;

char obuf[OUT_LEN], *oh = obuf;

inline void print(char c) {
    oh == obuf + OUT_LEN ? (fwrite(obuf, 1, OUT_LEN, stdout), oh = obuf) : 0;
    *oh++ = c;
}

template <typename T>
inline void print(T x) {
    static int buf[30], cnt;
    if (x == 0) {
        print('0');
    } else {
        x < 0 ? (print('-'), x = -x) : 0;
        for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 | 48;
        while (cnt) print((char)buf[cnt--]);
    }
}

inline void flush() { fwrite(obuf, 1, oh - obuf, stdout); }
}

namespace Task {

const int MAXN = 300;

int a[MAXN + 1], n;

inline int abs(int a) { return a < 0 ? -a : a; }

inline int check() {
    register int ans = abs(a[1] - a[2]);
    for (register int i = 3; i <= n; i++) ans = abs(ans - a[i]);
    return ans;
}

const double EPS = 0.1;
const double DROP = 0.999;
int MAX_TIMES = 5e7;

inline void solveForce() {
    std::sort(a + 1, a + n + 1);
    register int max = check();
    do {
        max = std::max(max, check());
    } while (std::next_permutation(a + 1, a + n + 1));
    IO::print(max);
}

inline void solve() {
    srand(time(0));
    using namespace IO;
    read(n);
    for (register int i = 1; i <= n; i++) read(a[i]);
    if (n <= 10) {
        solveForce();
        return;
    }
    std::random_shuffle(a + 1, a + n + 1);
    register int max = check(), now = max;
    for (double t = 20000; t > EPS; t *= DROP) {
        register int l = rand() % n + 1, r = rand() % n + 1;
        if (l == r) continue;
        std::swap(a[l], a[r]);
        register int tmp = check(), delta = tmp - now;
        if (delta >= 0 || exp(delta / t) * RAND_MAX >= rand()) {
            now = tmp;
        } else {
            std::swap(a[l], a[r]);
        }
        max = std::max(max, now);
    }
    MAX_TIMES /= n;
    for (register int i = 1; i <= MAX_TIMES; i++) {
        register int l = rand() % n + 1, r = rand() % n + 1;
        if (l == r) continue;
        std::swap(a[l], a[r]);
        register int tmp = check(), delta = tmp - now;
        if (delta >= 0) {
            now = tmp;
        } else {
            std::swap(a[l], a[r]);
        }
        max = std::max(max, now);
    }
    print(max);
}
}

int main() {
    freopen("dcf.in", "r", stdin);
    freopen("dcf.out", "w", stdout);
    Task::solve();
    IO::flush();
    return 0;
}
「BZOJ 3589」动态树-树链剖分 + 容斥
「ARC 071E」TrBBnsformBBtion

Comments

Follow

Tag Cloud

Algorithm CG DP Data Structure Frontend Geometry Graph Theory Hash Hexo Language Math Note Ray Tracing Rendering STL String Test

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Recent

Categories

Tags

Algorithm 2
CG 11
DP 26
Data Structure 68
Frontend 1
Geometry 7
Graph Theory 28
Hash 6
Hexo 1
Language 3
Math 42
Note 37
Ray Tracing 8
Rendering 8
STL 11
String 44
Test 1

Links

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×