水题记录1.0

15/15

水题记录

1.BZOJ1951古代猪文

题目大意 : 要求求出 \[ G^{\sum \{C_{K}^{N}, K\mid N\}} \% 999911659 \] \(N \leq 10^9 , G \leq 10^9\)

题解 :

我们考虑一个事实 \[ G ^ P = G ^ {P \% \phi(P)} (mod \ \ P) \] 因为 \(P\) 是质数所以\(G^{\phi(P)} = 1(mod \ \ P)\), 然后可以知道, \[ G ^ P = G ^ {P + k \cdot \phi(P)} (mod \ \ P) \] 即与上面那个式子等价

然后我们考虑怎么求 \[ \sum \{C_{K}^{N}, K\mid N\} \% \phi(P) \] 因为\(\phi(P)\)不是质数我们考虑用\(Lucas\) \[ \phi(P) = P - 1 = 2 \cdot 3 \cdot 4679 \cdot 35617 \] 这样就很水了, 因为对于\(\phi(P)\)的每个素因子的幂都是\(1\)

所以直接对于每个素因子用一下\(Lucas\), 最后直接\(CRT\)合并一下素膜数就好了, 并不用ExCRT, 水水水

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

using namespace std;

const int maxn = 4e4 + 5;
const int P[5] = {999911659, 2, 3, 4679, 35617};

int fac[5][maxn], G, N, num[maxn], a[5];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int ksm(int x, int k, int mod){
if(x == mod)return 0;
int cnt = 1;
while(k){
if(k & 1)cnt = 1ll * cnt * x % mod;
x = 1ll * x * x % mod; k >>= 1;
} return cnt;
}

inline int com(int n, int m, int k){
if(m > n)return 0;
return (int)(1ll * fac[k][n] * ksm(fac[k][n - m], P[k] - 2, P[k]) % P[k] * ksm(fac[k][m], P[k] - 2, P[k]) % P[k]);
}

inline int C(int n, int m, int k){
if(m == 0 || n == 0)return 1;
return (int)(1ll * C(n / P[k], m / P[k], k) * com(n % P[k], m % P[k], k) % P[k]);
}

inline int exgcd(int a, int b, int &x, int &y){
if(b == 0){x = 1; y = 0; return a;}
int x0 = 0, y0 = 0;
int d = exgcd(b, a % b, y0, x0);
x = x0; y = y0 - ((a / b) * x0);
return d;
}

inline int china(int *a, const int *m, int n){
int A = 0, M = 1, tmp;
for(register int i = 1; i <= n; i++)M *= m[i];
for(register int i = 1; i <= n; i++){
int Mi = M / m[i], inv;
exgcd(Mi, m[i], inv, tmp);
A = (A + 1ll * a[i] * Mi * inv) % M;
} return (A % M + M) % M;
}

int main(){
N = read(); G = read();
for(register int i = 1; i * i <= N; i++)
if(N % i == 0){
num[++num[0]] = i;
if(i * i != N)num[++num[0]] = N / i;
}
for(register int k = 1; k < 5; k++){
fac[k][0] = 1;
for(register int i = 1; i < maxn; i++)
fac[k][i] = 1ll * fac[k][i - 1] * i % P[k];
}
for(register int k = 1; k < 5; k++)
for(register int i = 1; i <= num[0]; i++)
a[k] = (a[k] + C(N, num[i], k)) % P[k];
/*for(register int i = 1; i <= num[0]; i++)
cout << "num[" << i << "] = " << num[i] << endl;
for(register int i = 1; i < 5; i++)
cout << "a[" << i << "] = " << a[i] << endl;
int o = china(a, P, 4);
cout << "P = " << o << endl;
cout << "G = " << G << endl;*/
cout << ksm(G, china(a, P, 4), P[0]);
return 0;
}

2.BZOJ2142礼物

题目大意 : 有\(n\)件礼物, \(m\)个人, 要求每个人分得\(w_i\)件礼物, 问有法案数对\(P\)取膜后的结果

题解 : 很显然答案应该是 \[ \binom {n}{\sum w_i} \prod_{i = 1}^{m} \binom{w_i}{\sum_{j = 1}^{m}w_j} (mod \ \ P) \] 然后因为题目不保证\(P\)为素数, 所以直接 $ ExLucas $ 就好了

如果不会\(ExLucas\)的, 可以点击这里

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

using namespace std;

typedef long long LL;

const int maxn = 15;

LL n, m, P, a[maxn], s[maxn];

inline LL read(){
char ch = getchar(); LL u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline LL ksm(LL x, LL k, LL P){
LL cnt = 1;
while(k){
if(k & 1)cnt = cnt * x % P;
x = x * x % P; k >>= 1;
} return cnt;
}

inline LL Exgcd(LL a, LL b, LL &x, LL &y){
if(b == 0){x = 1; y = 0; return a;}
LL x0 = 0, y0 = 0;
LL d = Exgcd(b, a % b, y0, x0);
x = x0; y = y0 - ((a / b) * x0);
return d;
}

inline LL inv(LL x, LL P){
LL inv, tmp;
Exgcd(x, P, inv, tmp);
return (inv + P) % P;
}

inline LL fac(LL n, LL Pi, LL Pk){
if(n == 0)return 1;
LL rnt = 1;
for(register LL i = 2; i <= Pk; i++)
if(i % Pi)rnt = rnt * i % Pk;
rnt = ksm(rnt, n / Pk, Pk);
for(register LL i = 2; i <= n % Pk; i++)
if(i % Pi)rnt = rnt * i % Pk;
return rnt * fac(n / Pi, Pi, Pk) % Pk;
}

inline LL ExLucas(LL n, LL m, LL Pi, LL Pk){
LL C1 = fac(n, Pi, Pk), C2 = fac(n - m, Pi, Pk), C3 = fac(m, Pi, Pk);
LL tim = 0;
for(register LL i = n; i; i /= Pi)tim += i / Pi;
for(register LL i = n - m; i; i /= Pi)tim -= i / Pi;
for(register LL i = m; i; i /= Pi)tim -= i / Pi;
return C1 * inv(C2, Pk) % Pk * inv(C3, Pk) % Pk * ksm(Pi, tim, Pk) % Pk;
}

inline LL calc(LL n, LL m, LL Pi, LL Pk){
LL ans = ExLucas(n, a[0], Pi, Pk);
for(register int i = 1; i <= m; i++)
ans = ans * ExLucas(s[i], a[i], Pi, Pk) % Pk;
return ans;
}

inline LL China(LL n, LL m, LL P){
LL A = 0, M = P, Pk = 1;
for(register LL i = 2; i <= P; i++)
if(P % i == 0){
Pk = 1;
while(P % i == 0)Pk *= i, P /= i;
A = (A + calc(n, m, i, Pk) * (M / Pk) % M * inv(M / Pk, Pk) % M) % M;
}
return (A + M) % M;
}

int main(){
P = read(); n = read(); m = read();
for(register int i = 1; i <= m; i++)
a[0] += (a[i] = read());
for(register int i = m; i >= 1; i--)
s[i] = s[i + 1] + a[i];
if(a[0] > n){cout << "Impossible"; return 0;}
cout << China(n, m, P);
return 0;
}

3.ARC59-EキャンディーとN人の子供 / Children and Candies

题目大意 : 幼儿园里有\(n\)个小朋友, 你有\(C\)块糖, 第\(i\)个小朋友一开始有一个兴奋程度\(x, x\in [A_i, B_i]\), 如果这个朋友获得了\(a_i\)块糖, 那么\(Ta\)的兴奋程度会变为\(x^{a_i}\), 定义整个幼儿园的兴奋程度为 \[ \prod_{i = 1}^{n}x^{a_i} \] 要求求出, 对于所有的分糖方案的的整个幼儿园兴奋程度的和

题解 : 我们考虑\(dp\), 定义\(f[i][j]\), 为前\(i\)个小朋友分了 \(j\) 块糖的所有方案的幼儿园兴奋程度的和, 所以很显然有一个这样的转移 : \[ f[i][j] = \sum_{k = 0}^{j} \big(f[i][j - k] \cdot \sum_{v = A[i]}^{B[i]} v^{k}\big) \] 我们发现样的话复杂度是\(O(n^4)\)的, 复杂度很有问题

然后我们观察可以发现\(\sum_{v = A[i]}^{B[i]}v^k\)\(j\)根本就没有关系, 所以没有必要每次都求一遍, 那么我么可以直接把\(k\)放在第二层枚举, \(j\)丢到最后一层枚举, 这样的话复杂度就成功的降为\(O(n^3)\)

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

using namespace std;

typedef long long LL;

const int maxn = 4e2 + 5;
const int P = 1e9 + 7;

int n, C, A[maxn], B[maxn], mi[maxn][maxn], f[maxn][maxn];
int maxv;

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y){x += y; return x >= P ? x - P : x;}

inline int mul(int x, int y){LL rnt = 1ll * x * y; return (int)(rnt >= P ? rnt % P : rnt);}

int main(){
n = read(); C = read();
for(register int i = 1; i <= n; i++)A[i] = read();
for(register int i = 1; i <= n; i++)maxv = max(maxv, B[i] = read());
for(register int i = 1; i <= maxv; i++){
mi[i][0] = 1;
for(register int j = 1; j <= C; j++)
mi[i][j] = mul(mi[i][j - 1], i);
}
f[0][0] = 1;
for(register int i = 1; i <= n; i++)
for(register int k = 0; k <= C; k++){
int res = 0;
for(register int j = A[i]; j <= B[i]; j++)res = pls(res, mi[j][k]);
for(register int j = k; j <= C; j++)
f[i][j] = pls(f[i][j], mul(f[i - 1][j - k], res));
}
cout << f[n][C];
return 0;
}
/*
2 3
1 1
1 1

*/

4.ARC60E-高橋君とホテル / Tak and Hotels

题目大意 : 在一条直线有\(n\)个旅馆, 每个旅馆在直线上有坐标, 每个旅馆的坐标为\(x_i\), 你每一步最多走\(L\), 也可以小于\(L\), 现在有\(m\)个询问\((a_i, b_i)\), 询问从\(a_i\)号旅馆到\(b_i\)号旅馆的最少步数

题解 : 我们考虑倍增\(go[i][j]\)表示从第\(i\)个旅馆往前走\(2^j\)步最远可以走到哪个旅馆, 然后就可以直接倍增了

但是有个问题 : \(go[i][0]\)我们怎么预处理, 直接暴力? 但是这样有可能被卡, 所以我们考虑搞一个双指针往后扫, 这样就可以\(O(n)\)预处理了

然后就水过了

代码 :

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

using namespace std;

const int maxn = 1e5 + 5;

int n, L, Q, x[maxn], go[maxn][20];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline void PreGo(int n, int L, int *x){
int pos = 1;
for(register int i = 1; i <= n; i++){
while(pos <= n && x[pos] - x[i] <= L)pos++;
go[i][0] = pos - 1;
}
for(register int j = 1; j <= 19; j++)
for(register int i = 1; i <= n; i++)
go[i][j] = go[go[i][j - 1]][j - 1];
}

int main(){
n = read();
for(register int i = 1; i <= n; i++)x[i] = read();
L = read(); Q = read();
PreGo(n, L, x);
for(register int i = 1; i <= Q; i++){
int a = read(), b = read(), now, ans = 0;
if(a > b)swap(a, b);
now = a;
for(register int k = 19; ~k; k--)
if(go[now][k] < b){
now = go[now][k];
ans |= (1 << k);
}
printf("%d\n", ans + 1);
}
return 0;
}
/*
9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

*/

5.ARC60E-すぬけ君の地下鉄旅行 / Snuke's Subway Trip

题目大意 : 现在有一张图, 上面有\(n\)个点, \(m\)条边, 每条边隶属于一个公司, 当你从\(u\)移动到\(v\)时, 经过的这条边\((u, v)\)

隶属的公司和转移到\(u\)的那条边隶属的公司不一样, 你的花费就会加一, 求从\(1\)走到\(n\)的最小花费, 如果可以到达输出花费, 否则输出\(-1\)

题解 : 我们考虑一下最短路的原理, 最短路我们只关心到某个点的最短路, 就算当前距离和以前更新过的答案一样也不用更新, 因为这样对后面的更新没有影响

我们再来考虑一下这道题, 我们考虑记录一下当前最优状态是可能从哪几条边转移过来的, 然后以后的转移基于我们记录的边, 就像这样 :

\(S[v]\)表示到\(v\)点的最短距离时, 有可能转移到这个状态的边集, 这时如果我们想从\(u\)点移动到\(v\)点, 如果\((u, v)\)这条边在\(S[v]\)这个集合中出现过了, 那么这次转移的花费就是\(0\), 否则是\(1\), 然后如果\(dis[u] + w < dis[v]\), 我们就清空\(S[v]\), 并加入\((u, v)\)这条边, 如果\(dis[u] + w = dis[v]\)就直接往\(S[v]\)中加一条边就行了

那么这样做为什么是正确的呢?

因为对于某个点无论是什么状态, 它往外转移的边都是相同的, 所以就算某个不优的状态转移时可以更优, 但也只能少\(1\), 这样也不会比当前最优的要优

我们可以用式子说明, 我们设不优的状态为\(old\), 最优状态为\(new\), 我们有\(old - new \geq 1\), 所以我们有 : \[ new + 1 \le old + 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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;

int n, m, head[maxn], cnt, dis[maxn], vis[maxn];
struct Graph{int to, nt, C;}e[maxn << 1];
set<int>S[maxn];
priority_queue<pair<int, int> >q;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline void ini(int x, int y, int C) {e[++cnt] = (Graph){y, head[x], C}; head[x] = cnt;}

inline void Dij(int s) {
memset(dis, 0x3f, sizeof(dis));
memset(vis, 0, sizeof(vis));
q.push(make_pair(dis[s] = 0, s));
while(!q.empty()) {
int now = q.top().second; q.pop();
if(vis[now])continue; vis[now] = 1;
for(register int i = head[now]; i; i = e[i].nt) {
int v = e[i].to, w;
w = S[now].count(e[i].C) ? 0 : 1;
if(dis[v] > dis[now] + w) {
dis[v] = dis[now] + w;
q.push(make_pair(-dis[v], v));
S[v].clear();
S[v].insert(e[i].C);
}
else if(dis[v] == dis[now] + w) S[v].insert(e[i].C);
}
}
}

int main(){
n = read(); m = read();
for(register int i = 1; i <= m; i++){
int x = read(), y = read(), C = read();
ini(x, y, C); ini(y, x, C);
}
Dij(1);
cout << (dis[n] == inf ? -1 : dis[n]);
return 0;
}

6.ARC58C - こだわり者いろはちゃん / Iroha's Obsession

题目大意 : 求出一个不小于\(n\)的数, 要求其满足以下条件 :

设这个数的各个位的数字的集合为\(S\), 给出一个集合\(D\), (保证集合D当中的元素属于\([0,9]\)) \[ \large{S} \large\cap \large{D} = \varnothing \] 题解 : 考虑直接暴力枚举, 如果符合条件直接输出就好了

代码 :

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

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 5;
const int P = 1e9 + 7;

int n, k, D[maxn];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline bool check(int x) {
while(x) {
if(D[x % 10])return false;
x /= 10;
} return true;
}

int main(){
n = read(); k = read();
for(register int i = 1; i <= k; i++) D[read()] = 1;
for(register int i = n; i <= maxn; i++)
if(check(i)) {cout << i; return 0;}
return 0;
}

7.ARC58D - いろはちゃんとマス目 / Iroha and a Grid

题目大意 : 给你一个\(n \times m\)的矩阵, 你只能往下或者往右走, 问你从左上角走到右下角并且不经过左下角\(H \times W\)的矩阵的所有方案数对\(10^9 + 7\)取膜后的答案

题解 : 我们先考虑一个事实, 如果我们从一个\(N \times M\)的没有任何障碍的矩阵的左上角走到右下角的方案数, 我们可以\(dp\), 但是复杂度不对, 事实上我们这个方案数其实就是 \[ \binom{n + m - 2}{n - 1} \] 其实就是, 我们一共走\(n + m - 2\)步, 纵向走\(n-1\)步, 问你有多少总方案, 然后就可以转化成上面那个东西了

知道上面那个结论以后, 我们再来考虑有障碍物的情况, 如图 :

我们知道从左上角分别走到蓝色区域的第一排的每个格子的方案数, 我们也知道从右下角分别走到蓝色区域第二排的每个格子的方案数, 根据乘法原理答案很显然就是就是 : \[ \sum _{i = B + 1}^{i \le m} \binom {n - H + i - 2}{n - H - 1} \cdot \binom {H + m - i - 1}{H - 1} (mod \ \ 10^9 + 7) \] 代码 :

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

using namespace std;

typedef long long LL;

const int maxn = 2e5 + 5;
const int P = 1e9 + 7;

int n, m, fac[maxn], A, B, ans;

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}

inline int mul(int x, int y) {LL rnt = 1ll * x * y; return (int)(rnt >= P ? rnt % P : rnt);}

inline int ksm(int x, int k) {
int cnt = 1;
while(k) {
if(k & 1) cnt = mul(cnt, x);
x = mul(x, x); k >>= 1;
} return cnt;
}

inline int C(int x, int y) {
int n = x + y - 2, m = x - 1;
if(m > n) return 0;
return mul(mul(ksm(fac[n - m], P - 2), ksm(fac[m], P - 2)), fac[n]);
}

int main(){
n = read(); m = read(); fac[0] = 1;
for(register int i = 1; i <= n + m; i++)
fac[i] = mul(fac[i - 1], i);
A = read(); B = read();
for(register int i = B + 1; i <= m; i++) {
//cerr << (n - A) << " " << i << " " << B << " " << m - i + 1 << endl;
ans = pls(ans, mul(C(n - A, i), C(A, m - i + 1)));
}
cout << ans;
return 0;
}

8.ARC58E - 和風いろはちゃん / Iroha and Haiku

题目大意 : 你现在有一个长度为\(N\)的序列(序列中的每个数小于等于\(10\)), 让你求有多少个序列, 存在一个子序列满足这个子序列可以分为三个子序列, 且第一个子序列的和为\(X\), 第二个子序列的和为\(Y\), 第三个子序列的和为\(Z\)

题解 :

首先我先讲一下我一开始想的辣鸡错误方法

我们考虑直接\(dp\), \(h[i][j]\)表示长度为\(i\)的和为\(j\)的序列的方案数, \(g[i]\)表示长度为\(i\)满足题目条件的序列的方案数

\(f[L][i][j]\), 表示长度为\(L\)的序列中只存在从第\(i\)个数开始的一个长度为\(j\)的子序列满足题目中的条件的方案数

那么转移就是 : \[ f[L][i][j] = g[j] \cdot 10^{L - j} - \sum _{l = 1}^{l < i}\sum _{p = 1}^{p \le l} \sum_{v = 1}^{p + v - 1 \le l} f[l][p][v] - \sum _{l = 1}^{l \le L - (i + j - 1)}\sum _{p = 1}^{p \le l} \sum_{v = 1}^{p + v - 1 \le l} f[l][p][v] \] 这个转移就是, 枚举两个区间\([1, i - 1], [L- (i + j - 1)]\), 把这两个区间中所有包含合法序列的方案数都减掉, 但是还是会算重, 为什么呢?

因为如果枚举到左侧的一个长度为\(i - 1\)的区间, 你无法去掉这个区间和\([i, i + j - 1]\)这个区间拼起来的区间中的合法方案数, 所以如果这样搞得话, 根本无法去重

然后, 我就去抄了一波正解

我们还是考虑\(dp\), 如果我们无法直接计算合法的方案数, 那我们就考虑不合法的方案数, 最后直接拿总方案数减去不合法的方案数就好了

设状态\(f[i][S]\)表示前\(i\)个数, 后若干个数加起来不超过\(X+Y+Z\)的状态的不合法的方案数

什么意思呢? 举个栗子吧 :

序列\(1, 2, 3\), 被表示成二进制状态就是\(1 | 100 |100000 = 100101\)

我们知道一个序列的状态为 \[ \sum _{i = 1} ^ {i \le n} (1 << s[i]) \] \(s[i]\)为这个序列的前缀和

这样表示一个序列的状态有什么好处呢 ? 这样的话这个状态一定会包含其一个子序列的状态, 这样的话我们就可以用这个状态来判别是否合法了

那么转移十分显然 , 设题目中给出的合法方案的状态为 \(S_2\) : \[ f[i][S] = \sum _{k = 1} ^ {k \le 10}f[i - 1][(S << k) | (1 << k - 1) \& U] \cdot [(((S<<k) | (1 << k - 1) \& U) \& S_2) != S_2] \] 我们考虑一下这样转移的正确性 :

显然如果当地前状态包含了题目给出的状态肯定是无法转移的, 如果当前不包含题目中所给出的状态, 那么转移一定是合法的, 因为每一次转移都是基于当前状态不包含合法状态, 所以最后正确性是一定没有问题的

代码 :

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

using namespace std;

typedef long long LL;

const int maxn = 45;
const int P = 1e9 + 7;

int n, x, y, z, f[maxn][1 << 18];

inline int read(){
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)){if(ch == '-')f = -1; ch = getchar();}
while(isdigit(ch)){u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}
inline int dec(int x, int y) {x -= y; return x < 0 ? x + P : x;}
inline int mul(int x, int y) {LL rnt = 1ll * x * y; return (int)(rnt >= P ? rnt % P : rnt);}

inline int ksm(int x, int k) {
int cnt = 1;
while(k) {
if(k & 1) cnt = mul(cnt, x);
x = mul(x, x); k >>= 1;
} return cnt;
}

int main(){
n = read(); x = read(); y = read(); z = read();
int ans = ksm(10, n);
int tot = (1 << x - 1) | (1 << x + y - 1) | (1 << x + y + z - 1);
int S = (1 << x + y + z);
f[0][0] = 1;
for(register int i = 1; i <= n; i++)
for(int S2 = 0; S2 < S; S2++)
for(register int k = 1; k <= 10; k++) {
int cur = ((S2 << k) | (1 << k - 1)) & (S - 1);
if((cur & tot) != tot)
f[i][cur] = pls(f[i][cur], f[i - 1][S2]);
}
for(register int S2 = 0; S2 < S; S2++) {
ans = dec(ans, f[n][S2]);
//if((S2 & tot) == tot) cout << f[n][S2] << endl;
}
cout << ans;
return 0;
}

9.ARC58F - 文字列大好きいろはちゃん / Iroha Loves Strings

题目大意 : 给你\(N\)个字符串, 现在你可以从其中任意选出几个, 要求拼成一个长度为\(K\)的字符串, 要求输出字典序最小的那一个, 拼接顺序要按照题目给出的顺序拼接 \[ N \in [1, 2000], \sum |s_i| \le 10^6, K \le 10^4 \]

题解 : 我们先考虑一下暴力\(dp\)直接背包, 设状态\(f[i][j]\)为前\(i\)个字符串中拼成长度为\(j\)的最小字典序的字符串, 由于每一次转移为\(|s_i|\), 这样的话复杂度是\(O(N\cdot K \cdot \sum|s_i|)\)的, 非常的不正确

我们考虑一下这样\(dp\)的原因是什么, 因为我们无法保证你当前最优的串, 是否能再后续的字符串中拼接到\(K\)的长度, 所以我们考虑保存每一种可能的长度的最优解, 但是如果我们知道是否能够拼成的话, 这样的保存就变得非常没有必要了

所以我们考虑先利用\(dp\)的思想预处理出来一个数组\(Rm[i][j]\), 表示用\(i \sim N\)的字符串是否能够拼成长度为\(j\)的字符串, 然后每次我们只用保存一个字符串就可以了, 并且我们每次更新一下这个字符串的断点, 每次考虑从这个位置接上当前串, 看是否能够组成更优的串, 以此来做到更新答案的目的

但是还有一个很重要的问题就是, 如何快速比较字典序, 如果我们直接比较的话复杂度肯定是\(O(|s_i|)\)的, 我们考虑把比较字典序的问题转化为找\(LCP\)的问题, 最后直接比较\(LCP\)的后一位就好了, 这里我们可以直接\(Hash\)一下,每次二分一个位置, 比较一下就好了, 这样我们就成功的把比较的复杂度降至\(O(log|s_i|)\)

至此, 题目我们已经完成了一大半了, 可是还有一个很重要的问题就是, 如果当前串真包含一个颗可以拼接而成的串的话, 我们要额外的更新一下断点, 这样才可以保证最后答案的正确性

\(PS:\) 我说的好像头头是道, 但是这道题我调了一个星期还是\(WA\)\(5\)个点, 求神犇查错

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

using namespace std;

typedef unsigned long long ull;

const int maxn = 2e3 + 505;
const int maxm = 1e4 + 505;
const ull seed = 233;

int n, k, len[maxn];
ull Hash[maxm], cur[maxm], fac[maxn * 505];

char ex[maxm];
string s[maxn], st[maxn];

bool Rm[maxn][maxm], ok[2][maxm];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int checkit(string &st, string &s, int pos, int j) {
int l = 1, r = min(pos, j) + s.size(), R = 0, mid = (l + r) / 2; R = r;
int siz = s.size(), ans = 0, ch0, ch1;
while(l <= r) {
mid = (l + r) / 2;
ull H0 = 0, H1 = 0;
if(mid <= pos) H0 = cur[mid];
else H0 = cur[pos] * fac[mid - pos] + Hash[mid - pos];
if(mid <= j) H1 = cur[mid];
else H1 = cur[j] * fac[mid - j] + Hash[mid - j];
if(H0 == H1) l = mid + 1, ans = mid;
else r = mid - 1;
}
if(ans == R) return j > pos ? j : pos;
else {
if(ans >= pos) ch0 = s[ans - pos]; else ch0 = st[ans];
if(ans >= j) ch1 = s[ans - j]; else ch1 = st[ans];
return ch0 > ch1 ? j : pos;
}
}

inline string checkagain(string &st, string &now, string &s, int pos) {
int l = 1, r = min(now.size(), st.size()), R = 0, mid = (l + r) / 2; R = r;
int siz = s.size(), ans = 0, ch0, ch1;
while(l <= r) {
mid = (l + r) / 2;
ull H0 = 0, H1 = 0;
H0 = cur[mid];
if(mid <= pos) H1 = cur[mid];
else H1 = cur[pos] * fac[mid - pos] + Hash[mid - pos];
if(H0 == H1) l = mid + 1, ans = mid;
else r = mid - 1;
}
if(ans == R) {
if(st.size() > now.size()) return st;
else return now;
}
else {
ch0 = now[ans]; ch1 = st[ans];
if(ch0 > ch1) return st;
else return now;
}
}

int main() {
freopen("in", "r", stdin);
freopen("MY", "w", stdout);
n = read(); k = read(); fac[0] = 1;

for(register int i = 1; i <= maxn * 500; i++)
fac[i] = fac[i - 1] * seed;

for(register int i = 1; i <= n; i++) {
scanf("%s", ex); s[i] = ex;
}

Rm[n + 1][0] = 1;
for(register int i = n; i >= 1; i--)
for(register int j = 0; j <= k; j++) {
if(j >= s[i].size()) Rm[i][j] |= Rm[i + 1][j - s[i].size()];
Rm[i][j] |= Rm[i + 1][j];
}

if(Rm[2][k - s[1].size()]) {
ok[0][1] = 1; st[1] = s[1];
}

for(register int i = 2; i <= n; i++) {
int t = i & 1, t0 = t ^ 1, p = -1;
memset(ok[t0], 0, sizeof(ok[t0]));

cur[0] = Hash[0] = 0;
for(register int j = 1; j <= st[i - 1].size(); j++)
cur[j] = cur[j - 1] * seed + st[i - 1][j - 1];
for(register int j = 1; j <= s[i].size(); j++)
Hash[j] = Hash[j - 1] * seed + s[i][j - 1];


for(register int j = 1; j <= st[i - 1].size() + 1; j++) {
if(!Rm[i + 1][k - (j + s[i].size() - 1)] || !(ok[t][j] || j > st[i - 1].size())) continue;
if(p == -1) p = j;
else p = checkit(st[i - 1], s[i], p - 1, j - 1) + 1;
}

if(p != -1)
st[i] = st[i - 1].substr(0, p - 1) + s[i];
else st[i] = st[i - 1];

if(Rm[i + 1][k - st[i - 1].size()])
st[i] = checkagain(st[i - 1], st[i], s[i], p - 1);

if(st[i] == st[i - 1]) p = st[i].size() + 1;


for(register int j = 1; j <= k; j++) {
int o = j + s[i].size() - 1;
if(o > st[i].size()) break;
if(!Rm[i + 1][k - o] || !ok[t][j]) continue;
ull H0 = 0, H1 = 0;
if(o > p - 1) H0 = cur[p - 1] * fac[o - (p - 1)] + Hash[o - (p - 1)];
else H0 = cur[o];
H1 = cur[j - 1] * fac[s[i].size()] + Hash[s[i].size()];
if(H0 == H1) ok[t0][o + 1] = 1;
}

ok[t0][p] = 1;
for(register int j = 1; j <= k; j++) {
if(j > st[i].size()) continue;
if(!Rm[i + 1][k - (j - 1)] || !ok[t][j]) continue;
ull H0 = 0, H1 = 0;
H0 = cur[j - 1];
if(j > p - 1) H1 = cur[p - 1] * fac[j - p] + Hash[j - p];
else H1 = cur[j - 1];
if(H0 == H1) ok[t0][j] = 1;
}

/*cerr << "case" << i << ": " << endl;
cerr << st[i] << endl;
for(register int j = 1; j <= k; j++)
cerr << ok[t0][j] << " ";
cerr << "\n\n";
*/}

cout << st[n];
return 0;
}
/*
*/

10.NOI.AC 模拟赛R2 T1 palindrome

题目大意 : 要你求一个最长回文字串的切分, 我们平常定义回文串是比较开头和结尾的字符, 这道题里面就是将一个子串看成一个字符来比较, 详情见题面

题解 : 考虑直接\(Hash\)头一个指针, 尾一个指针, 往中间扫, 一匹配到相同的就直接\(ans += 2\), 最后判一下\(ans\)是否要加一就行了, 水水水

代码 :

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

using namespace std;

typedef long long LL;
typedef unsigned long long ull;

const int maxn = 1e6 + 5;
const int seed0 = 233;
const int seed1 = 277;
const ull P = 998244353;

int T, n, ans;
ull fac0[maxn], fac1[maxn];
char s[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

struct Hash {
ull hash0, hash1;
Hash (ull H0 = 0, ull H1 = 0) {hash0 = H0; hash1 = H1;}
inline void mul(ull s, int k) {
hash0 = hash0 + s * fac0[k];
hash1 = (hash1 + s * fac1[k] % P) % P;
}
inline void push(ull s) {
hash0 = hash0 * seed0 + s;
hash1 = (hash1 * seed1 % P + s) % P;
}
inline void clear() {hash0 = hash1 = 0;}
bool operator == (const Hash &t) const {return hash0 == t.hash0 && hash1 == t.hash1;}
}t0, t1;

int main() {
#ifndef ONLINE_JUDGE
freopen("palindrome.in", "r", stdin);
freopen("palindrome.out", "w", stdout);
#endif
T = read(); fac0[0] = fac1[0] = 1;
for(register int i = 1; i < maxn; i++)
fac0[i] = fac0[i - 1] * seed0, fac1[i] = fac1[i - 1] * seed1 % P;
while(T--) {
scanf("%s", s + 1);
n = strlen(s + 1); ans = 0;
t0.clear(); t1.clear();
int l = 1, r = n, L = 1, R = n;
while(l < r) {
t0.push(s[l]);
t1.mul(s[r], R - r);
if(t0 == t1) {
ans += 2;
t0.clear(); t1.clear();
L = l + 1; R = r - 1;
} l++; r--;
}
printf("%d\n", ans + (!(t0 == t1) || (n & 1)));
}
return 0;
}
/*
1
abananab

*/

11.NOA.AC 模拟赛R2 T2 string

题目大意 : 你有一个只由\(A,B,C,D\)组成的长度为\(N\)的字符串, 你有\(M\)种魔法, 每次可以把一个字符串\(S_i\)变为\(S_i'\)

并且你可一交换一个字符串中的相邻的两个字符, 问你最多可以变成多少种不同的字符串

题解 : 不要被题目所迷惑了, 题目中告诉我们可以交换一个字符串中相邻的两个字符, 也就是间接的告诉我, 我们不用考虑, 这个字符串的具体形态是什么, 只用考虑这个字符串中有多少个\(A\), 多少个\(B\), 多少个\(C\), 多少个\(D\), 就行了

那么我们可以将题目中给出的\(M\)种魔法看成从一种状态向另一种状态的转移, 我们可以直接把每一种状态看成一个点, 每个点的权值是当前状态可以组成不同的字符串的方案数, 每一种魔法看成一种状态向另一种状态的连边, 并且是单向边, 最后我们把图建出来以后, 直接缩一下点, 然后在\(DAG\)图上\(dp\)一下就好了

最后对于一开始每种状态的权值, 我们也可\(dp\)一下就可以了

设状态\(g[i][j][k][v]\)表示长度为\(i\)的字符串, 有\(j\)\(A\), \(k\)\(B\), \(v\)\(C\)的方案数, 转移很显然就是 : \[ g[i][j][k][v] += \begin{cases}g[i - 1][j - 1][k][v] \ \ \ \ if(j > 1) \\ g[i - 1][j][k - 1] \ \ \ \ \ \ \ \ if(k > 1) \\ g[i - 1][j][k][v - 1] \ \ \ \ if(v > 1) \\ g[i - 1][j][k][v] \ \ \ \ \ \ \ \ \ \ \ if(i - j - k - v > 1) \end{cases} \]

代码 :

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

using namespace std;

const int maxn = 55;
const int maxs = 2e4 + 5e3 + 5;
const int maxm = 1e6 + 5;

int n, m, con, cal[maxn << 1][2][1 << 8], in[maxn], bcnt;
int P[maxn][maxn][maxn], st[maxs], top, be[maxs], becnt, dfn[maxs], low[maxs];

__int128 g[maxn][maxn][maxn][maxn], w[maxs], ans, f[maxs];

bool vis0[maxs], vis1[maxs], instack[maxs];

char s0[maxn], s1[maxn], putit[maxs];

struct Node {int A, B, C, D;} t[maxs];

struct Graph {
int head[maxs], cnt = 1;
struct node {int to, nt;} e[maxm];
inline void ini(int x, int y) {e[++cnt] = (node){y, head[x]}; head[x] = cnt;}
}G, E;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline __int128 getit(int id) {
int A = t[id].A, B = t[id].B, C = t[id].C;
return g[n][A][B][C];
}

inline void Tarjan(int now) {
dfn[now] = low[now] = ++dfn[0];
instack[st[++top] = now] = true;
for(register int i = G.head[now]; i; i = G.e[i].nt) {
int v = G.e[i].to;
if(!dfn[v]) {
Tarjan(v);
low[now] = min(low[now], low[v]);
} else if(instack[v])
low[now] = min(low[now], low[v]);
}
if(dfn[now] == low[now]) {
bcnt++;
while(now != st[top]) {
be[st[top]] = bcnt; w[bcnt] += getit(st[top]);
instack[st[top--]] = false;
}
be[st[top]] = bcnt; w[bcnt] += getit(st[top]);
instack[st[top--]] = false;
}
}

inline void rebuild() {
for(register int now = 1; now <= con; now++)
for(register int i = G.head[now]; i; i = G.e[i].nt) {
int v = G.e[i].to;
if(be[now] != be[v])
E.ini(be[now], be[v]), in[be[v]]++;
}
}

inline void write(__int128 x) {
int len = 0;
while(x) {
putit[++len] = x % 10 + '0';
x /= 10;
}
for(register int i = len; i >= 1; i--)putchar(putit[i]);
}

inline void Topsort() {
queue<int>q;
while(!q.empty()) q.pop();
for(register int i = 1; i <= bcnt; i++)
if(in[i] == 0) q.push(i), f[i] = w[i];
while(!q.empty()) {
int now = q.front(); q.pop(); ans = max(ans, f[now]);
for(register int i = E.head[now]; i; i = E.e[i].nt) {
int v = E.e[i].to;
f[v] = max(f[v], f[now] + w[v]);
in[v]--;
if(in[v] == 0)q.push(v);
}
}
}

int main() {
n = read(); m = read();

for(register int i = 0; i <= n; i++)
for(register int j = 0; i + j <= n; j++)
for(register int k = 0; i + j + k <= n; k++) {
t[++con] = (Node) {i, j, k, n - i - j - k};
P[i][j][k] = con;
}
/*cerr << endl;
for(register int i = 1; i <= con; i++)
cerr << "case " << i << ": A = " << t[i].A << " B = " << t[i].B << " C = " << t[i].C << " D = " << t[i].D << endl;
*/
g[0][0][0][0] = 1;
for(register int i = 1; i <= n; i++)
for(register int j = 0; j <= i; j++)
for(register int k = 0; j + k <= i; k++)
for(register int v = 0; j + k + v <= i; v++) {
if(j > 0) g[i][j][k][v] += g[i - 1][j - 1][k][v];
if(k > 0) g[i][j][k][v] += g[i - 1][j][k - 1][v];
if(v > 0) g[i][j][k][v] += g[i - 1][j][k][v - 1];
if(i - j - k - v > 0) g[i][j][k][v] += g[i - 1][j][k][v];
}

//cerr << g[6][3][1][1] << endl;
//write(g[6][3][1][1]); cerr << endl;

for(register int i = 1; i <= m; i++) {
int len = 0, t0 = 0, t1 = 0;
scanf("%s%s", s0 + 1, s1 + 1);
len = strlen(s0 + 1);
for(register int j = 1; j <= len; j++) {
cal[i][0][s0[j]]++;
cal[i][1][s1[j]]++;
}
}
for(register int i = 1; i <= con; i++) {
//cerr << "#case : " << i << endl;
for(register int j = 1; j <= m; j++) {
int A0 = cal[j][0]['A'], B0 = cal[j][0]['B'];
int C0 = cal[j][0]['C'], D0 = cal[j][0]['D'];
int A1 = cal[j][1]['A'], B1 = cal[j][1]['B'];
int C1 = cal[j][1]['C'], D1 = cal[j][1]['D'];
if(A0 == A1 && B0 == B1 && C0 == C1)continue;
if(t[i].A >= A0 && t[i].B >= B0 && t[i].C >= C0 && t[i].D >= D0) {
G.ini(i, P[t[i].A - A0 + A1][t[i].B - B0 + B1][t[i].C - C0 + C1]);
//cerr << i << " " << P[t[i].A - A0 + A1][t[i].B - B0 + B1][t[i].C - C0 + C1] << endl;
}
}
//cerr << endl;
}

for(register int i = 1; i <= con; i++)
if(!dfn[i]) Tarjan(i);
/*for(register int i = 1; i <= bcnt; i++) {
cerr << "w[" << i << "] = ";
write(w[i]); cerr << endl;
}
cerr << endl;
for(register int i = 1; i <= con; i++) {
cerr << "g[" << i << "] = ";
write(getit(i)); cerr << endl;
}*/
rebuild(); Topsort();
write(ans);
return 0;
}

12.BZOJ1027合金

题目大意 : 给你\(N\)个点, 再给你\(M\)个点, 要求从\(M\)个点中选出若干个点使得这些点中的凸包能够包含\(N\)个点所构成的凸包, 要求最小化选出的点集的大小

题解 : 考虑枚举一个点对,

  • 如果所有的需求点都在这两个点所连成的线段上或在直线的上方, 连正向边
  • 如果所有的需求点都在这两个点所连成的线段上或在直线的下方, 连反向边

最后跑一遍\(Floyd\), 答案就是 \[ min \{ dis[i][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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 5e2 + 5;
const int inf = 0x3f3f3f3f;
const double eps = 1e-13;

int n, m, dis[maxn][maxn], ans = inf;

double x;

struct Vector {
double x, y;
Vector (double X = 0, double Y = 0) {x = X; y = Y;}
Vector operator + (const Vector &t) const {return Vector(x + t.x, y + t.y);}
Vector operator - (const Vector &t) const {return Vector(x - t.x, y - t.y);}
double operator * (const Vector &t) const {return x * t.x + y * t.y;}
double operator ^ (const Vector &t) const {return x * t.y - y * t.x;}
bool operator < (const Vector &t) const {return x < t.x;}
bool operator <= (const Vector &t) const {return x <= t.x;}
}Ha[maxn], Ne[maxn];

inline void judge(int x, int y) {
int H0 = 0, H1 = 0;
for(register int i = 1; i <= m; i++) {
double getit = (Ha[x] - Ha[y]) ^ (Ha[x] - Ne[i]);
bool is = Ha[x] <= Ne[i] && Ne[i] <= Ha[y];
H0 += (getit < -eps || (fabs(getit) < eps && is));
H1 += (getit > eps || (fabs(getit) < eps && is));
}
if(H0 == m) dis[x][y] = 1;
if(H1 == m) dis[y][x] = 1;
//if(dis[x][y] == 1) cerr << x << "-->" << y << endl;
//if(dis[y][x] == 1) cerr << y << "-->" << x << endl;
//cerr << endl;
}

int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i++) scanf("%lf%lf%lf", &Ha[i].x, &Ha[i].y, &x);
for(register int i = 1; i <= m; i++) scanf("%lf%lf%lf", &Ne[i].x, &Ne[i].y, &x);

memset(dis, 0x3f, sizeof(dis));

for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= n; j++)
judge(i, j);

for(register int k = 1; k <= n; k++)
for(register int i = 1; i <= n; i++)
for(register int j = 1; j <= n; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

for(register int i = 1; i <= n; i++) ans = min(ans, dis[i][i]);

cout << (ans == inf ? -1 : ans);
return 0;
}

13.ARC59-Cいっしょ / Be Together

题目大意 : 给你一个序列\(a_i\), 要求求出 \[ \sum _ {i = 1} ^ {i \le n} (a_i - x)^2 \] 的最小值

题解 : 枚举一个\(x\), 取最小值

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

#define IL inline
IL int read() {
char ch = getchar(); int u = 0, f = 1;
while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
while (isdigit(ch)) { u = (u << 1) + (u << 3) + ch - 48; ch = getchar(); }
return u * f;
}

int n;
int a[150];
int main() {
n = read();
int ans = INT_MAX;
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = -100; i <= 100; ++i) {
int now = 0;
for (int j = 1; j <= n; ++j)
now += (i - a[j]) * (i - a[j]);
ans = min(ans, now);
}
cout << ans << endl;
return 0;
}

以上为\(Edgration\)的代码, 我是伪的

14.ARC59-Dアンバランス / Unbalanced

题目大意 : 给你一个字符串, 要求求出一个长度至少为\(2\)的子串满足, 这个子串至少存在一个字符出现的次数的两倍大于这个子串的长度

题解 : \(S[a \sim z][i]\)表示\(a \sim z\)在前\(i\)个字符中出现的次数

我们可以贪心的考虑一下, 对于每一个左端点我们只考虑这个位置上的字符在一个区间内是否能满足条件, 其它的可以不用考虑, 因为如果后面的某个位置也出现了这个位置上没有出现的字符, 那么一定会比在这个位置上考虑更优

设当前位置上的字符为\(ch\)

根据题面中给出的条件我们可以列出一个约束条件 \[ 2 \cdot (S[ch][r] - S[ch][l - 1]) > r - l + 1 \] 我们移项一下 \[ 2 \cdot S[ch][r] - r > 2 \cdot S[ch][l - 1] - (l - 1) \] 这个时候就看得很明显了, 设\(b[ch][i] = 2 \cdot S[ch][i] - i\)

然后对于一个左端点\(l\), 直接查询在它的右边是否存在一个\(r\)满足\(b_r > b_l\)

然后这个东西直接用\(ST\)表维护一下就好了

复杂度\(O(26 \cdot nlogn)\), 然后因为找到答案就退出了, 所以跑不满, 然后还跑得飞快

代码 :

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

using namespace std;

const int maxn = 1e5 + 5;
const int inf = 1e9 + 5;

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

int n, sum[maxn];
pair<int, int> st[maxn][20];

char s[maxn];

inline pair<int, int> query(int l, int r) {
int k = log2(r - l + 1);
return max(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
scanf("%s", s + 1);
n = strlen(s + 1);

for(register int k = 'a'; k <= 'z'; k++) {
memset(sum, 0, sizeof(sum));
memset(st, 0, sizeof(st));

for(register int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + (k == s[i]);

for(register int i = 1; i <= n; i++)
st[i][0] = make_pair(2 * sum[i] - i, i);
for(register int j = 1; j < 20; j++)
for(register int i = 1; i + (1 << j) - 1 <= n; i++)
st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);

for(register int i = 1; i < n; i++) {
if(s[i] != k) continue;
pair<int, int> tmp = query(i + 1, n);
if(tmp > st[i][0]) {
cout << i << " " << tmp.second; return 0;
}
}
}

cout << -1 << " " << -1;
return 0;
}

15.ARC59-Fバイナリハック / Unhappy Hacking

题目大意 : 你有一个键盘, 键盘上只有三个键, \(0\), \(1\), \(backspace\), 你可以敲击键盘\(n\)

然后给定一个\(0, 1\)串, 问你敲击键盘\(n\)下后, 有多少种方案可以得到这个零一串

题解 : 其实题面中给的那个串其实是用来忽悠你的, 如果你硬要靠虑那个零一串的话这道题会变得非常不好做

然而, 事实我们根本就不用考虑最后的目标串是什么, 因为我们可以通过调整中间的按键来改变最后的串, 所以不用

考虑最后的串, 我们直接\(dp\)然后最后除以\(2^{目标串的长度}\), 就是答案了

然后设\(f[i][j]\) 表示按了\(i\)下键, 得到了一个长度为\(j\)的零一串的总方案数, 然后转移很明显 \[ \begin{cases} f[i][j] = f[i][j] + 2 \cdot f[i - 1][j - 1] \ \ \ \ if(j > 0) \\ f[i][j] = f[i][j] + f[i - 1][j] \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ if(j = 0) \\ f[i][j] = f[i][j] + f[i - 1][j + 1]\end{cases} \] 解释一下,

  • 如果串的长度大于一你可以按零或一
  • 如果串的长度大于等于零你可以按\(backspace\)

代码 :

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

using namespace std;

typedef long long LL;

const int maxn = 5e3 + 5;
const int P = 1e9 + 7;

int n, f[maxn][maxn], len;

char s[maxn];

inline int read() {
char ch = getchar(); int u = 0, f = 1;
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {u = u * 10 + ch - 48; ch = getchar();} return u * f;
}

inline int ksm(int x, int k) {
int cnt = 1;
while(k) {
if(k & 1) cnt = 1ll * cnt * x % P;
x = 1ll * x * x % P; k >>= 1;
} return cnt;
}

inline int pls(int x, int y) {x += y; return x >= P ? x - P : x;}

int main() {
n = read(); scanf("%s", s + 1);
len = strlen(s + 1);

f[0][0] = 1;
for(register int i = 1; i <= n; i++)
for(register int j = 0; j <= i; j++) {
if(j > 0)
f[i][j] = pls(f[i][j], f[i - 1][j - 1] * 2 % P);
else f[i][j] = pls(f[i][j], f[i - 1][j]);
f[i][j] = pls(f[i][j], f[i - 1][j + 1]);
}

cout << (1ll * f[n][len] * ksm(ksm(2, len), P - 2) % P);
return 0;
}