Asusetic
0%

2021.07.07模拟赛

发表于 分类于 Valine：
本文字数： 1.2k 阅读时长 ≈ 1 分钟

难度倒序（

2021.07.07 模拟赛

T1 [Bracketの模拟器日常]生于黑夜

原学军网络赛C题病毒研究

比较怪的题目

先做一一遍背包来得到每个减少的代价

设 dpl,rdp_{l,r} 表示 $ [l,r] $ 的期望代价

暴力转移不可取，考虑只有把这个区间减到某个分界点上才会知道额外的信息（判断原区间的每个数的范围）

或者说把被分割的点当作关键节点，因为如果一个转移没经过关键点，一定是直接减到了 11 状态，那和之间减到 11 状态没有区别（因为做过背包），只有关键点才会带来影响

按这个思路记忆话搜索，因为分界点状态是 O(n)O(n)，只有 O(n2)O(n^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
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
#include <array>
#include <iostream>
#include <vector>
using namespace std;
using ll     = long long;
const ll INF = (1ll << 48);
const int N  = 2005;
array<int, N> belong, a;
array<ll, N> v, sum;
array<array<ll, N>, N> dp;
struct Data {
    int v, w;
};
int T;
ll solve(int l, int r) {
    if (dp[l][r] != INF)
        return dp[l][r];
    if (belong[l] == 1) {
        return 0;
    }
    ll res = INF + 1;
    for (int i = 1; i < l; i++) {
        if (v[i] == INF)
            continue;
        int L = l - i, R = r - i;
        if (belong[L] == belong[R]) {
            if (belong[R] == 1) {
                res = min(res, v[i] * (r - l + 1));
            }
            continue;
        }
        ll sum = solve(L, a[belong[L]]);
        int k;
        for (k = belong[L] + 1; a[k] < R; k++) {
            sum += solve(a[k - 1] + 1, a[k]);
        }
        sum += solve(a[k - 1] + 1, R) + v[i] * (r - l + 1);
        res = min(sum, res);
    }
    dp[l][r] = min(INF, res);
    return dp[l][r];
}
int main() {
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        vector<Data> q(m + 1);
        for (int i = 1; i <= m; i++) {
            cin >> q[i].v >> q[i].w;
        }
        v.fill(INF);
        v[0] = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = q[i].w; j <= a[n]; j++) {
                v[j] = min(v[j], v[j - q[i].w] + q[i].v);
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = a[i] + 1; j <= a[i + 1]; ++j) {
                belong[j] = i + 1;
            }
        }
        for (int i = 1; i <= a[n] + 1; i++) {
            dp[i].fill(INF);
        }
        sum[0]    = 0;
        bool flag = 1;
        for (int i = 1; i < n; i++) {
            sum[i] = sum[i - 1] + solve(a[i] + 1, a[i + 1]);
            flag &= (sum[i] < INF);
        }
        if (!flag) {
            cout << -1 << endl;
        } else {
            cout << sum[n - 1] << endl;
        }
    }
}

T2 区间dp

O(n2)O(n^2) 的做法比较显然，设 dpl,rdp_{l,r} 是 [l,r][l,r] 区间要多少个区间才能拼起来

转移的时候记录下当前访问的位置，如果新加入的值在一个区间的某一端那么不变，如果不在任何一侧那么 +1+1 同时在两个区间的两端则 −1-1

考虑优化这个转移，钦定右端点不变，考虑加入的新右端点会带来什么影响

如果新的右端点在排列的位置的两侧有且仅有一个位置小于它，那么说明在这个值之后的左端点 ll 会 +1+1 ，因为只要左端点大于这个数字就会断开与 rr 的连接

如果均大于那么说明是个孤立点，全 +1+1

如果均小于则是在较小的位置 −1-1 较大的到 rr +1+1

线段树维护即可

可以改成找 kk 个区间 分块维护

虽然题目没说但是 [x,x][x,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
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
#include <iostream>
using namespace std;
const int N = 3e5 + 10;
namespace SegmentTree {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)
struct Node {
    struct Data {
        int val, cnt;
        Data operator+(const Data &B) const {
            Data res;
            if (val == B.val) {
                res.val = val;
                res.cnt = cnt + B.cnt;
            } else if (val < B.val) {
                res.val = val;
                res.cnt = cnt;
            } else {
                res.val = B.val;
                res.cnt = B.cnt;
            }
            return res;
        }
        bool operator<(const Data &B) const {
            return val < B.val;
        }
        bool operator>(const Data &B) const {
            return val > B.val;
        }
    };
    Data min, semin;
    int l, r, tag;
} tr[N * 4];
void pushup(int x) {
    tr[x].min = tr[ls(x)].min + tr[rs(x)].min;
    if (tr[ls(x)].min < tr[rs(x)].min) {
        tr[x].semin = tr[ls(x)].semin + tr[rs(x)].min;
    } else if (tr[ls(x)].min > tr[rs(x)].min) {
        tr[x].semin = tr[ls(x)].min + tr[rs(x)].semin;
    } else {
        tr[x].semin = tr[ls(x)].semin + tr[rs(x)].semin;
    }
}
void pushdown(int x) {
    if (tr[x].tag) {
        tr[ls(x)].tag += tr[x].tag;
        tr[ls(x)].min.val += tr[x].tag;
        tr[ls(x)].semin.val += tr[x].tag;
        tr[rs(x)].tag += tr[x].tag;
        tr[rs(x)].min.val += tr[x].tag;
        tr[rs(x)].semin.val += tr[x].tag;
        tr[x].tag = 0;
    }
}
void build(int rt, int l, int r) {
    tr[rt].l = l;
    tr[rt].r = r;
    if (l == r) {
        tr[rt].min   = {0, 1};
        tr[rt].semin = {1 << 28, 0};
        return;
    }
    int mid = (l + r) / 2;
    build(ls(rt), l, mid);
    build(rs(rt), mid + 1, r);
    pushup(rt);
}
void update(int rt, int L, int R, int v) {
    auto &l = tr[rt].l;
    auto &r = tr[rt].r;
    if (l >= L && r <= R) {
        tr[rt].min.val += v;
        tr[rt].semin.val += v;
        tr[rt].tag += v;
        return;
    }
    pushdown(rt);
    int mid = (l + r) / 2;
    if (L <= mid) {
        update(ls(rt), L, R, v);
    }
    if (mid < R) {
        update(rs(rt), L, R, v);
    }
    pushup(rt);
}
int query(int rt, int L, int R) {
    auto &l = tr[rt].l;
    auto &r = tr[rt].r;
    if (l >= L && r <= R) {
        return (tr[rt].min.val <= 2 ? tr[rt].min.cnt : 0) +
               (tr[rt].semin.val <= 2 ? tr[rt].semin.cnt : 0);
    }
    pushdown(rt);
    int mid = (l + r) / 2;
    int res = 0;
    if (L <= mid) {
        res += query(ls(rt), L, R);
    }
    if (mid < R) {
        res += query(rs(rt), L, R);
    }
    return res;
}
#undef ls
#undef rs
} // namespace SegmentTree
int n;
int a[N], p[N];
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        p[a[i]] = i;
    }
    SegmentTree::build(1, 1, n);
    long long ans = 0;
    for (int r = 1; r <= n; r++) {
        int x = 0x3f3f3f3f, y = 0x3f3f3f3f, cnt = 0;
        int pos = p[r];
        if (pos > 1 && a[pos - 1] < r) {
            ++cnt;
            x = a[pos - 1];
        }
        if (pos < n && a[pos + 1] < r) {
            ++cnt;
            y = a[pos + 1];
        }
        if (x > y) {
            swap(x, y);
        }
        if (cnt == 0) {
            SegmentTree::update(1, 1, r, 1);
        } else if (cnt == 1) {
            SegmentTree::update(1, x + 1, r, 1);
        } else {
            SegmentTree::update(1, 1, x, -1);
            SegmentTree::update(1, y + 1, r, 1);
        }
        ans += SegmentTree::query(1, 1, r);
    }
    cout << ans - n << endl;
}

T3 成绩单

原题 THUSC2016 同名

发现只有 l,rl,r 是没法做的，考虑再记一个 x,yx,y 表示当前还剩的最大是 yy ，最小的 xx

转移暴力转移 dpl,r,min⁡(x,ar),max⁡(y,ar)←dpl,r−1,x,ydp_{l,r,\min(x,a_r),\max(y,a_r)} \gets dp_{l,r-1,x,y}

即加入一个数字

然后合并到 gl,rg_{l,r} 的答案，同时转移 dpl,r,∗,∗←dpl,k,∗,∗+gk+1,rdp_{l,r,*,*} \gets dp_{l,k,*,*}+g_{k+1,r}

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 <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int N = 55;
int n;
ll A, B;
ll dp[N][N][N][N];
ll nya[N][N];
ll a[N];
ll b[N];
int main() {
	cin >> n >> A >> B;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = a[i];
	}
	memset(dp, 0x3f, sizeof(dp));
	memset(nya, 0x3f, sizeof(nya));
	sort(b + 1, b + 1 + n);
	int tot=unique(b + 1, b + 1 + n) - b - 1;
	for (int i = 1; i <= n; i++) {
		a[i] = lower_bound(b + 1,b + 1 + tot, a[i]) - b;
		dp[i][i][a[i]][a[i]] = 0;
		nya[i][i] = A;
	}
	for (int len = 1; len <= n; len++) {
		for (int l = 1; l + len - 1 <= n ; l++) {
			int r = l + len - 1;
			for (ll x = 1; x <= tot; x++) {
				for (ll y = x; y <= tot; y++) {
					auto &val = dp[l][r][min(x, a[r])][max(y, a[r])];
					val = min(val, dp[l][r - 1][x][y]);
					for(int k = l; k < r; k++){
						dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][k][x][y] + nya[k + 1][r]);
					}
				}
			}
			for (int x = 1; x <= tot; x++) {
				for (int y = x; y <= tot; y++) {
					nya[l][r] = min(nya[l][r], dp[l][r][x][y] + A + B * (b[y] - b[x]) * (b[y] - b[x]));
				}
			}
		}
	}
	cout << nya[1][n] <<endl;
}
//Asusetic eru quionours.

T4 周期性字串计数

考虑设 f(n)f(n) 表示长度为 nn 的不周期字串

那么有 f(n)=26n−∑d∣nf(d)+f(n)f(n)=26^n-\sum\limits_{d|n}f(d)+f(n)

因为所有的周期字串都是由某个非周期的字串的倍数来的，同时减去自己的 11 倍串

可得 26n=∑d∣nf(d)26^n=\sum\limits_{d|n}f(d)

二项式反演即可

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
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

using ll = long long;
const ll mod = 1e9 + 7;

ll n, factor[2333333];

ll qpow(ll a, ll k) {
    ll base = a, ans = 1;
    while(k) {
        if (k&1) {
			ans = ans * base % mod;
		}
        base = 1ll * base * base % mod;
		k /= 2;
    }
    return ans;
}

ll mu(ll k) {
    ll ans = 1;
    for(ll i = 2; i * i <= k; i++) {
    	if(k % i == 0){
    		int cnt = 0;
    		while(k % i == 0) {
    			cnt++;
    			k /= i;
			}
			if(cnt > 1){
				return 0;
			}else{
				ans = -ans;
			}
		}
	}
	if(k > 1){
		ans = -ans;
	}
	return ans;
}
int fcnt;
ll sum;
int main() {
    cin >> n;
    for(ll i = 1; i * i <= n; i++) {
    	if (n % i == 0){
    		factor[++fcnt] = i;
    		if(1ll * i * i != n){
    			factor[++fcnt] = n/i;
			}
		}
	}
	sum = qpow(26ll, n);
    for(ll i = 1; i <= fcnt; i++){
    	sum = (sum + (mod - qpow(26ll, factor[i]) * 1ll * mu(n / factor[i]))) % mod;
    }
    cout << sum << endl;
    cin>>n;
    return 0;
}
//Asusetic eru quionours.