水题记录

Posted on | In |
Words count in article: 7.8k | Reading time ≈ 41
13/15

水题记录

1.CF1053C Put The Boxes Together

Unfinished

2.BZOJ 4636 蒟蒻的数列

Finished

题意：给出$n$次操作，每次将区间$[l,r)$内所有小于$k$的数修改为$k$。求$n$次操作后所有数的和

思路：裸的数据结构题，因为懒得离散化，所以就用动态开点的线段树节省一下空间就能水过去。最后统计和的时候把整棵树遍历一遍就完了

注意：

  1. 区间左闭右开，所以当$l=r$的时候应跳过
  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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const int maxn = 1e9 + 7;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f=-1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, id, rt;

struct D_SegmentTree
{
	int lson, rson;
	int val;
};
D_SegmentTree T[4 * N];

il void Update(int &p,int L, int R, int l, int r, int d)
{
	if (!p)
		p = ++id;
	if (L == l && R == r)
	{
		T[p].val = max(T[p].val, d);
		return;
	}
	int mid = (L + R) >> 1;
	if (r <= mid)
		Update(T[p].lson, L, mid, l, r, d);
	else if (l > mid)
		Update(T[p].rson, mid + 1, R, l, r, d);
	else
	{
		Update(T[p].lson, L, mid, l, mid, d);
		Update(T[p].rson, mid + 1, R, mid + 1, r, d);
	}
}
il ll Query(int p, int l, int r, int w)
{
	ll ret = 0;
	if (!p)
		return ret;
	w = max(w, T[p].val);
	if (!T[p].lson && !T[p].rson)
	{
		ret += 1ll * (r - l + 1) * w;
		return ret;
	}
	int mid = (l + r) >> 1;
	if (r <= mid)
		ret += Query(T[p].lson, l, r, w);
	else if (l > mid)
		ret += Query(T[p].rson, l, r, w);
	else
		ret += Query(T[p].lson, l, mid, w) + Query(T[p].rson, mid + 1, r, w);
	if (!T[p].lson)
		ret += 1ll * (mid - l + 1) * w;
	if (!T[p].rson)
		ret += 1ll * (r - mid) * w;
	return ret;
}

int main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
	{
		int l = read(), r = read(), d = read();
		if (l == r)
			continue;
		Update(rt,1, maxn, l, r - 1, d);
	}
	printf("%lld", Query(rt, 1, maxn, 0));
	return 0;
}
/*
4
2 5 1
9 10 4
6 8 2
4 6 3

*/

3.Luogu 4231 三步必杀

Finished

题意：给出一个序列，初始所有值都是0，有$m$次操作，每次将区间 $[l,r]$ 内以等差数列增加，等差数列首项、末项已知

思路：两次差分，对于区间$[l,r]$，每一次增加有以下数列（d为公差）：

然后在差分序列上就可以写成：

但是这样好像就不是优美的差分了，有两个不和谐的位置，那么我们再差分一遍，就可以写成：

这样就可以通过求两次前缀和求得答案了

注意：STL max常数较大，建议手写

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e7 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

template <typename T>
il void read(T &x)
{
    x = 0;
    T f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f=-1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    x *= f;
}

int n, m;
ll ans1, ans2 = -inf;
ll a[N], b[N], c[N];

int main()
{
    read(n), read(m);
    for (ri i = 1; i <= m; i++)
    {
        int l, r;
        ll s, e;
        read(l), read(r), read(s), read(e);
        ll delta = (e - s) / (r - l);
        c[l] += s, c[l + 1] += delta - s, c[r + 1] -= (delta + e), c[r + 2] += e;
    }
    for (ri i = 1; i <= n; i++)
    {
        b[i] += b[i - 1] + c[i];
        a[i] = a[i - 1] + b[i];
        ans1 ^= a[i], ans2 = ans2 < a[i] ? a[i] : ans2;
    }
    printf("%lld %lld", ans1, ans2);
    return 0;
}
/*
5 2
1 5 2 10
2 4 1 1

*/

4.Luogu 1140 相似基因

Finished

题意：给出两个只由ATCG组成的字符串 $s$ 和 $t$ ，每个串中间可以插入任意数量的空字符，每两个对应字符有一个确定的值，问最后两个串每一位对应的值的和最大是多少

思路：考虑$dp$，用$dp[i][j]$表示$s$进行到第$i$位，$t$进行到第$j$位，每一位可以由以下三种方式得到：

  1. 在$s$中插入一个空字符；

  2. 在$t$中插入一个空字符；

  3. 不插入空字符。

则可知以下转移方程（$d[i][j]$表示 $i$ 与 $j$ 对应的值）：

注意：基础动态规划，注意不要把 $s[i]$ 和 $t[j]$ 打反就行了

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f=-1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n, m;
char s[N], t[N];
int dp[MAXN][MAXN], d[MAXN][MAXN];

int main()
{
#ifdef Wepdekr
    freopen("testdata.in", "r", stdin);
#endif
    n = read();
    scanf("%s", s + 1);
    m = read();
    scanf("%s", t + 1);
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
            dp[i][j] = -inf;
    d['A']['A'] = d['T']['T'] = d['C']['C'] = d['G']['G'] = 5;
    d['A']['T'] = d['T']['A'] = d['A']['C'] = d['C']['A'] = d[0]['T'] = d['T'][0] = -1;
    d['A']['G'] = d['G']['A'] = d['T']['C'] = d['C']['T'] =
    d['T']['G'] = d['G']['T'] = d['G'][0] = d[0]['G'] = -2;
    d['G']['C'] = d['C']['G'] = d['A'][0] = d[0]['A'] = -3;
    d['C'][0] = d[0]['C'] = -4;
    for (ri i = 1; i <= n; i++)
        dp[i][0] = dp[i - 1][0] + d[s[i]][0];
    for (ri i = 1; i <= m; i++)
        dp[0][i] = dp[0][i - 1] + d[0][t[i]];
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
        {
            dp[i][j] = max(max(dp[i - 1][j] + d[s[i]][0], dp[i][j - 1] + d[t[j]][0]),
                           max(dp[i][j], dp[i - 1][j - 1] + d[s[i]][t[j]]));
        }
    printf("%d", dp[n][m]);
    return 0;
}
/*
7 AGTGATG
5 GTTAG

*/

5.Luogu 4230 连环病原体

Finished

题意：给出一张 $n$ 个点 $m$ 条边的无向图，对于边的序列，如果一个区间内存在环，那么称该区间为一个“加强区间”，问每条边在几个加强区间内出现过。

思路：考虑 $O(m)$ 地枚举区间的左右端点，每次向右移动区间右端点，如果出现环则进行一次统计，然后向右移动区间左端点至没有环为止。使用 $LCT$ ，每次扩展区间就 $Link$ ，缩小区间就 $Cut$ ，然后用 $FindRoot$ 判断连通性，很显然可以知道当要连一条边的时候，如果这条边所连的两个节点已经联通，那么连上这条边就会出现环。

重复的进行上述操作即可完成统计。

统计答案的时候涉及到等差数列的问题，可以参考 三步必杀 ，使用两个差分完成。

注意： $LCT$ 别打挂就行了。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f=-1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int m;
ll s1[N], s2[N], s3[N];

struct edge
{
    int fr, to;
};
edge e[N];

namespace Link_Cut_Tree
{
    int st[N];
    struct node
    {
        int fa, ch[2];
        bool rev;
    };
    node a[N];
    
    il bool Not_Root(int x)
    {
        return a[a[x].fa].ch[0] == x || a[a[x].fa].ch[1] == x;
    }
    il void Push_Reverse(int x)
    {
        if (!x)
            return;
        std :: swap(a[x].ch[0], a[x].ch[1]);
        a[x].rev ^= 1;
    }
    il void Pushdown(int x)
    {
        if (a[x].rev)
        {
            Push_Reverse(a[x].ch[0]);
            Push_Reverse(a[x].ch[1]);
            a[x].rev = 0;
        }
    }
    
    il void Rotate(int x)
    {
        int y = a[x].fa;
        int z = a[y].fa;
        bool k = (a[y].ch[1] == x);
        int w = a[x].ch[!k];
        if (Not_Root(y))
            a[z].ch[a[z].ch[1] == y] = x;
        a[x].ch[!k] = y;
        a[y].ch[k] = w;
        if (w)
            a[w].fa = y;
        a[y].fa = x;
        a[x].fa = z;
    }
    il void Splay(int x)
    {
        int y = x, top = 0;
        st[++top] = y;
        while (Not_Root(y))
            st[++top] = y = a[y].fa;
        while (top)
            Pushdown(st[top--]);
        while (Not_Root(x))
        {
            y = a[x].fa;
            int z = a[y].fa;
            if (Not_Root(y))
                Rotate(((a[y].ch[0] == x) ^ (a[z].ch[0] == y)) ? x : y);
            Rotate(x);
        }
    }
    il void Access(int x)
    {
        for (ri y = 0; x; x = a[y = x].fa)
        {
            Splay(x);
            a[x].ch[1] = y;
        }
    }
    il int Find_Root(int x)
    {
        Access(x);
        Splay(x);
        while (a[x].ch[0])
            Pushdown(x), x = a[x].ch[0];
        Splay(x);
        return x;
    }
    il void Make_Root(int x)
    {
        Access(x);
        Splay(x);
        Push_Reverse(x);
    }
    il void Link(int x, int y)
    {
        Make_Root(x);
        a[x].fa = y;
    }
    il void Cut(int x, int y)
    {
        Make_Root(x);
        Access(y);
        Splay(y);
        a[x].fa = a[y].ch[0] = 0;
    }
}
using namespace Link_Cut_Tree;

il void Add(int l, int r, int a1, int delta)
{
    if (l > r)
    	return;
    s3[l] += a1;
    s3[l + 1] += delta - a1;
    s3[r + 1] -= a1 + 1ll * (r - l + 1) * delta;
    s3[r + 2] += a1 + 1ll * (r - l) * delta;
}

int main()
{
    m = read();
    for (ri i = 1; i <= m; i++)
        e[i].fr = read(), e[i].to = read();
    for (int L = 1, R = 0; L <= m; L++)
    {
        bool flag = 0;
        while(R < m)
        {
            R++;
            if (Find_Root(e[R].fr) == Find_Root(e[R].to))
            {
                flag = 1;
                break;
            }
            Link(e[R].fr, e[R].to);
        }
        if (flag)
        {
            Add(L, R, m - R + 1, 0);
            Add(R + 1, m, m - R, -1);
            R--;
        }
        else
             break;
        Cut(e[L].fr, e[L].to);
    }
    for (ri i = 1; i <= m; i++)
    {
        s2[i] += s2[i - 1] + s3[i];
        s1[i] = s1[i - 1] + s2[i];
    }
    for (ri i = 1; i <= m; i++)
        printf("%lld ", s1[i]);
    return 0;
}
/*
5
1 2
2 3
3 4
1 4
4 2

*/

6.CF1059C Sequence Transformation

Finished

题意：给出序列 $a$ ，使 $a_i = i$ ，每次操作向序列 $b$ 中加入 $a$ 序列中所有值的最大公约数，并从 $a$ 中任意删去一个元素，求最后字典序最大的 $b$ 序列。

思路：可知当且仅当每次删掉当前数列中第奇数位上的数字的时候，可以使得 $b$ 的字典序最大，然后递归的处理一下就好了（当然也可以不递归）

注意：当目前序列中的数小于等于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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, cnt;
int a[N], ans[N];

il void Get_Ans(int num, int val)
{
	if (num == 1)
	{
		ans[++cnt] = val;
		return;
	}
	else if (num == 2)
	{
		ans[++cnt] = val;
		ans[++cnt] = val * 2;
		return;
	}
	else if (num == 3)
	{
		ans[cnt + 1] = ans[cnt + 2] = val;
		ans[cnt + 3] = 3 * val;
		return;
	}
	for (ri i = 1; i <= num; i++)
	{
		if (a[i] & 1)
			ans[++cnt] = val;
	}
	Get_Ans(num / 2, val * 2);
}

int main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
		a[i] = i;
	Get_Ans(n, 1);
	for (ri i = 1; i <= n; i++)
		printf("%d ", ans[i]);
	return 0;
}

7.[HNOI2010]弹飞绵羊

Finished

题意：给出一张图，第 $i$ 个点会被弹到到第 $i + a_i$ 个点， $i + a_i>n$ 时则被弹飞，可以修改每个点被弹到的点的编号，问从某一个被弹多少次后会被弹飞。

思路：建立一个虚拟的 $n + 1$ 表示被弹飞，然后暴力使用 $LCT$ 模拟。每次 $Link$ $i$ 和 $i + a_i$ ，修改就先 $Cut$ 再 $Link$ 就行了，查询操作就先 $Split$ 一下 $i$ 和 $n + 1$，然后直接看 $n + 1$ 子树的 $size$ 就好了。

注意：打好 $LCT$ 的同时要注意随时变更 $a_i$ ，写 $Splay$ 记得维护 $size$

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f=-1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n, q;
int c[N];

namespace Link_Cut_Tree
{
    int st[N];
    
    struct node
    {
        int fa, ch[2];
        int siz;
        bool rev;
    };
    node a[N];
    
    il bool Not_Root(int x)
    {
        return a[a[x].fa].ch[0] == x || a[a[x].fa].ch[1] == x;
    }
    
    il void Pushup(int x)
    {
        a[x].siz = a[a[x].ch[0]].siz + a[a[x].ch[1]].siz + 1;
    }
    il void Push_Reverse(int x)
    {
        if (!x)
            return;
        std :: swap(a[x].ch[0], a[x].ch[1]);
        a[x].rev ^= 1;
    }
    il void Pushdown(int x)
    {
        if (a[x].rev)
        {
            Push_Reverse(a[x].ch[0]);
            Push_Reverse(a[x].ch[1]);
            a[x].rev = 0;
        }
    }
    
    il void Rotate(int x)
    {
        int y = a[x].fa;
        int z = a[y].fa;
        bool k = (a[y].ch[1] == x);
        int w = a[x].ch[!k];
        if (Not_Root(y))
            a[z].ch[a[z].ch[1] == y] = x;
        a[y].ch[k] = w;
        a[x].ch[!k] = y;
        if (w)
            a[w].fa = y;
        a[y].fa = x;
        a[x].fa = z;
        
        Pushup(y);
        Pushup(x);
    }
    il void Splay(int x)
    {
        int y = x, z = 0;
        st[++z] = y;
        while (Not_Root(y))
            st[++z] = y = a[y].fa;
        while (z)
            Pushdown(st[z--]);
        while (Not_Root(x))
        {
            y = a[x].fa;
            z = a[y].fa;
            if (Not_Root(y))
                Rotate(((a[y].ch[0] == x) ^ (a[z].ch[0] == x)) ? x : y);
            Rotate(x);
        }
        Pushup(x);
    }
    
    il void Access(int x)
    {
        for (ri y = 0; x; x = a[y = x].fa)
        {
            Splay(x);
            a[x].ch[1] = y;
            Pushup(x);
        }
    }
    il void Make_Root(int x)
    {
        Access(x);
        Splay(x);
        Push_Reverse(x);
    }
    il int Find_Root(int x)
    {
        Access(x);
        Splay(x);
        while (a[x].ch[0])
            Pushdown(x), x = a[x].ch[0];
        Splay(x);
        return x;
    }
    
    il void Split(int x, int y)
    {
        Make_Root(x);
        Access(y);
        Splay(y);
    }
    il void Link(int x, int y)
    {
        Make_Root(x);
        if (Find_Root(y) != x)
            a[x].fa = y;
    }
    il void Cut(int x, int y)
    {
        Make_Root(x);
        if (Find_Root(y) == x && a[y].fa == x && !a[y].ch[0])
        {
            a[y].fa = a[x].ch[1] = 0;
            Pushup(x);
        }
    }
    
    il int Query(int x)
    {
        Split(x, n + 1);
        return a[n + 1].siz - 1;
    }
    il void Change(int x, int y)
    {
        Cut(x, (x + c[x] <= n) ? x + c[x] : n + 1);
        Link(x, (x + y <= n) ? x + y : n + 1);
        c[x] = y;
    }
}
using namespace Link_Cut_Tree;

int main()
{
#ifdef Wepdekr
    freopen("testdata1.in", "r", stdin);
#endif
    n = read();
    for (ri i = 1; i <= n; i++)
    {
        c[i] = read();
        Link(i, (i + c[i] <= n) ? i + c[i] : n + 1);
        a[i].siz = 1;
    }
    a[n + 1].siz = 1;
    q = read();
    for (ri i = 1; i <= q; i++)
    {
        int opt = read(), x = read();
        if (opt & 1)
            printf("%d\n", Query(x + 1));
        else
        {
            int y = read();
            Change(x + 1, y);
        }
    }
    return 0;
}
/*
4
1 2 1 1
3
1 1
2 1 1
1 1

*/

8.CF1066F Yet another 2D Walking

Finished

题意：在二维平面上给出 $n$ 个点，第 $i$ 个点的坐标为 $(x_i, y_i)$ ，我们把 $max(x, y)$ 相同的点称为同一层的点。定义两个点的距离为它们的曼哈顿距离，从 $(0, 0)$ 出发，遍历全部的 $n$ 个点，且在遍历完这一层的所有点之前不能遍历下一层的点，求走过的最短距离。

思路：很显然有这样一个结论：遍历同一层的点时，从左上到右下一定是最佳策略。此时我们只需要记录在层间转移的代价即可。然后就可以 $\text{DP}$ ，用 $dp[i][j]\ (j\in{0,1})$ 来表示到第 $i$ 层，从左上/右下向下一层转移时的最小距离，假如用 $dist(A,B)$ 表示 $A$ , $B$ 两点间的距离，则有以下转移方程：

注意：并没有什么要注意的QwQ，记得使用long long

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
#define int long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, cnt;
int dp[N][2];

struct node
{
	int x, y;
	friend bool operator < (node a1, node a2)
	{
		return a1.x == a2.x ? a1.y > a2.y : a1.x < a2.x;
	}
};
node a[N], b[N][2];
il bool cmp(node a1, node a2)
{
	return max(a1.x, a1.y) < max(a2.x, a2.y);
}

il int Get_dist(node a1, node a2)
{
	return abs(a1.x - a2.x) + abs(a1.y - a2.y);
}

signed main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
		a[i].x = read(), a[i].y = read();
	sort(a + 1, a + 1 + n, cmp);
	a[n + 1] = (node) {inf, inf};
	b[0][0] = b[0][1] = (node) {0, 0};
	int now = 0, pos = 0;
	for (ri i = 1; i <= n + 1; i++)
		if (max(a[i].x, a[i].y) > now)
		{
			sort(a + pos, a + i);
			b[cnt][0] = a[pos];
			b[cnt][1] = a[i - 1];
			cnt++;
			now = max(a[i].x, a[i].y);
			pos = i;
		}
    cnt--;
	dp[0][0] = dp[0][1] = 0;
	for (ri i = 1; i <= cnt; i++)
	{
		dp[i][0] = min(dp[i - 1][0] + Get_dist(b[i - 1][0], b[i][1]),
					   dp[i - 1][1] + Get_dist(b[i - 1][1], b[i][1])) + Get_dist(b[i][0], b[i][1]);
		dp[i][1] = min(dp[i - 1][0] + Get_dist(b[i - 1][0], b[i][0]),
					   dp[i - 1][1] + Get_dist(b[i - 1][1], b[i][0])) + Get_dist(b[i][0], b[i][1]);
	}
	printf("%lld", min(dp[cnt][0], dp[cnt][1]));
	return 0;
}

9.[SDOI2008]洞穴勘测

Finished

题意：给出一张图，有 $m$ 次操作，每次连接一条边或者切断一条边，每次查询两个点的连通性

思路： $LCT$ 裸题，连边就 $Link$ ，断边就 $Cut$ ，查询就 $FindRoot$ 就行了。

注意： $LCT$ 不要打挂了。

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f=-1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n, m;

namespace Link_Cut_Tree
{
    int st[N];
    
    struct node
    {
        int fa, ch[2];
        bool rev;
    };
    node a[N];
    
    il bool Not_Root(int x)
    {
        return a[a[x].fa].ch[0] == x || a[a[x].fa].ch[1] == x;
    }
    
    il void Push_Reverse(int x)
    {
        if (!x)
            return;
        std :: swap(a[x].ch[0], a[x].ch[1]);
        a[x].rev ^= 1;
    }
    il void Pushdown(int x)
    {
        if (a[x].rev)
        {
            Push_Reverse(a[x].ch[0]);
            Push_Reverse(a[x].ch[1]);
            a[x].rev = 0;
        }
    }
    
    il void Rotate(int x)
    {
        int y = a[x].fa;
        int z = a[y].fa;
        bool k = (a[y].ch[1] == x);
        int w = a[x].ch[!k];
        if (Not_Root(y))
            a[z].ch[a[z].ch[1] == y] = x;
        a[y].ch[k] = w;
        a[x].ch[!k] = y;
        if (w)
            a[w].fa = y;
        a[y].fa = x;
        a[x].fa = z;
    }
    il void Splay(int x)
    {
        int y = x, z = 0;
        st[++z] = y;
        while (Not_Root(y))
            st[++z] = y = a[y].fa;
        while (z)
            Pushdown(st[z--]);
        while (Not_Root(x))
        {
            y = a[x].fa;
            z = a[y].fa;
            if (Not_Root(y))
                Rotate(((a[y].ch[0] == x) ^ (a[z].ch[0] == x)) ? x : y);
            Rotate(x);
        }
    }
    
    il void Access(int x)
    {
        for (ri y = 0; x; x = a[y = x].fa)
        {
            Splay(x);
            a[x].ch[1] = y;
        }
    }
    il void Make_Root(int x)
    {
        Access(x);
        Splay(x);
        Push_Reverse(x);
    }
    il int Find_Root(int x)
    {
        Access(x);
        Splay(x);
        while (a[x].ch[0])
            Pushdown(x), x = a[x].ch[0];
        Splay(x);
        return x;
    }
    
    il void Split(int x, int y)
    {
        Make_Root(x);
        Access(y);
        Splay(y);
    }
    il void Link(int x, int y)
    {
        Make_Root(x);
        if (Find_Root(y) != x)
            a[x].fa = y;
    }
    il void Cut(int x, int y)
    {
        Make_Root(x);
        if (Find_Root(y) == x && a[y].fa == x && !a[y].ch[0])
            a[y].fa = a[x].ch[1] = 0;
    }
}
using namespace Link_Cut_Tree;

int main()
{
    n = read(), m = read();
    for (ri i = 1; i <= m; i++)
    {
        char s[20];
        scanf("%s", s);
        int x = read(), y = read();
        switch (s[0])
        {
            case 'C': Link(x, y); break;
            case 'D': Cut(x, y); break;
            case 'Q': (Find_Root(x) == Find_Root(y)) ? printf("Yes\n") : printf("No\n"); break;
        }
    }
    return 0;
}
/*
200 5
Query 123 127
Connect 123 127
Query 123 127
Destroy 127 123
Query 123 127

*/

10.[ZJOI2012]网络

Unfinished

题意：给出一张无向图，每个点有权值，每条边有一个颜色，且满足以下两个条件：

  1. 对于任意节点连出去的边中，相同颜色的边不超过两条；
  2. 图中不存在同色的环，同色的环指相同颜色的边构成的环。

在这个图上要支持以下三种操作：

  1. 修改一个节点的权值；
  2. 修改一条边的颜色；
  3. 查询由颜色 $c$ 的边构成的图中，所有可能在节点 $u$ 到节点 $v$ 之间的简单路径上的节点的权值的最大值。

思路：由于题目中的图是动态的，所以 $\text{LCT}$ 是很显然的，但是涉及到多个颜色的问题比较难办，然而由于数据并不是很大，而且时限也给了 $2s$ ，所以暴力对每一种颜色建一棵 $\text{LCT}$ 就行了。

11.Luogu 1282 多米诺骨牌

Finished

题意：给出两个序列，分别将它们中所有数字的和记为 $S_1, S_2$ ，你可以任意交换两个序列同一位置上的数，使得 $|S_1 - S_2|$ 最小。

思路：很显然这是一个 $\text{DP}$ ，考虑用 $dp[i][j]$ 表示第一个序列目前和为 $i$ ，当前进行到第 $j$ 个数时的最小交换次数，则有以下转移方程：

注意：初始化的时候应该先初始化 $dp[b[1]][1] = 1$ 再 $dp[a[1]][1] = 0$ ，这样可以防止 $a_1 = b_1$ 导致的 $\color{red}{\text{WA}}$ 。

代码：

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>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 1e9;
const double eps = 1e-8;
const int maxn = 1010;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n, s;
int a[N], b[N];
int dp[maxn * 6][maxn];

int main()
{
	n = read();
	for (ri i = 1; i <= n; i++)
	{
		a[i] = read(), b[i] = read();
		s += a[i] + b[i];
	}
	for (ri i = 0; i <= n * 6; i++)
		for (ri j = 1; j <= n; j++)
			dp[i][j] = inf;
	dp[b[1]][1] = 1, dp[a[1]][1] = 0;
	for (ri i = 0; i <= n * 6; i++)
		for (ri j = 2; j <= n; j++)
		{
			if (i - a[j] >= 0)
				dp[i][j] = min(dp[i][j], dp[i - a[j]][j - 1]);
			if (i - b[j] >= 0)
				dp[i][j] = min(dp[i][j], dp[i - b[j]][j - 1] + 1);
		}
	int minn = inf, ans = inf;
	for (ri i = 0; i <= min(s, n * 6); i++)
		if (dp[i][n] != inf)
		{
			if (abs(i - (s - i)) < minn)
			{
				minn = abs(i - (s - i));
				ans = dp[i][n];
			}
			else if (abs(i - (s - i)) == minn)
				ans = min(ans, dp[i][n]);
		}
	printf("%d", ans);
	return 0;
}
/*
4
6 1
1 5
1 3
1 2

*/

12.[NOIp2008]传纸条

Finished

题意：给出一个矩阵，从左上角到右下角求出两条不重合的路径，求两条路径上数字之和的最大值。

思路：很显然是一个动态规划，直接做有一个 $O(n^4)$ 的解法：简单地用 $dp[i][j][k][l]$ 表示第一条路径到了点 $(i, j)$ ，第二条路径到了点 $(k, l)$ 时的最大值。但是这样当数据强了以后就可能会 $\color{darkblue}{\text{TLE}}$ ，所以就必须要优化一下。然后我们可以想到，假设两条路径同步延伸的情况下，很显然就有 $i + j = k + l$ ，于是我们可以考虑将点的横纵坐标之和作为第一维，然后只要枚举横纵坐标中的某一个就可以知道两个点的坐标，然后复杂度就降低到了 $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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n, m;
int a[MAXN][MAXN], dp[MAXN][MAXN][MAXN];

il bool Illegal(int x, int y, int z)
{
    return y == z || x - y < 1 || x - z < 1;
}

int main()
{
    n = read(), m = read();
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
            a[i][j] = read();
    memset(dp, 0xc0, sizeof(dp));
    dp[2][1][1] = 0;
    for (ri i = 3; i <= n + m - 1; i++)
        for (ri j = 1; j <= n; j++)
            for (ri k = 1; k <= n; k++)
            {
                if (Illegal(i, j, k))
                    continue;
                dp[i][j][k] = max(max(dp[i - 1][j][k], dp[i - 1][j - 1][k]),
                                  max(dp[i - 1][j][k - 1], dp[i - 1][j - 1][k - 1])) +
                                  a[j][i - j] + a[k][i - k];
            }
    printf("%d\n", dp[n + m - 1][n][n - 1]);
    return 0;
}
/*
3 3
0 3 9
2 8 5
5 7 0

*/

13.Luogu 1736 创意吃鱼法

Finished

题意：给出一个01矩阵，求出仅一条对角线上全部为1，其余位置均为0的正方形子矩阵的对角线最大长度。

思路：这个题与最大正方形很像，一样可以考虑暴力 $\text{DP}$ ，但是需要做一点简单的预处理。

考虑用 $s1[i][j]$ 表示从点 $(i, j)$ 向左/右扩展的连续0的个数，用 $s2[i][j]$ 表示从点 $(i, j)$ 向上扩展的连续0的个数，于是乎可以很简单的得到以下转移方程：

注意：要 $\text{DP}$ 两次，因为正方形的对角线不止一条。

代码：

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>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;
const int maxn = 2567;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n, m, ans = -inf;
int a[maxn][maxn], dp[maxn][maxn];
int s1[maxn][maxn], s2[maxn][maxn];

int main()
{
    n = read(), m = read();
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
        {
            a[i][j] = read();
            if (!a[i][j])
            {
                s1[i][j] = s1[i][j - 1] + 1;
                s2[i][j] = s2[i - 1][j] + 1;
            }
            else
                dp[i][j] = min(min(s1[i][j - 1], s2[i - 1][j]), dp[i - 1][j - 1]) + 1;
        }
    
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
            ans = max(ans, dp[i][j]);
    memset(s1, 0, sizeof(s1));
    memset(dp, 0, sizeof(dp));
    for (ri i = 1; i <= n; i++)
        for (ri j = m; j; j--)
        {
            if (!a[i][j])
                s1[i][j] = s1[i][j + 1] + 1;
            else
                dp[i][j] = min(min(s1[i][j + 1], s2[i - 1][j]), dp[i - 1][j + 1]) + 1;
        }
    for (ri i = 1; i <= n; i++)
        for (ri j = 1; j <= m; j++)
            ans = max(ans, dp[i][j]);
    printf("%d", ans);
    return 0;
}
/*
4 6
0 1 0 1 0 0
0 0 1 0 1 0
1 1 0 0 0 1
0 1 1 0 1 0

*/

14.Luogu 4918 信仰收集

Finished

题意：给出一个 $\text{DAG}$ 图，每条边长为 $1$ 个单位，一些点有 $val$ 的价值，早苗从 $1$ 号点出发，一步可以走 $a$ 个单位或 $b$ 个单位，代价分别为 $w_a$ 和 $w_b$ ，她走到一个点的时候可以获得等于这个点价值的收益，她可以在任意一个点停下来，求获得的(收益-代价)的最大值。

思路：很显然这可以 $\text{DP}$ ，我最开始想到了一个很暴力的转移，从 $1$ 号点开始枚举往后走 $a$ 个单位和 $b$ 个单位能到达的点然后转移，但是这样很显然是过不了全部点的。于是拿 $60pts$ 走人

然后正解其实想到了并不难写，但相当的难想，毕竟 $\text{YSJ}$ 聚聚的原话就是这道题难度主要集中在思维难度上（毒瘤！）。

我们可以把一步走 $k$ 个单位拆成走 $k$ 步，每步走一个单位然后停下来，那么就可以用 $dp[i][j]$ 表示从第 $i$ 个点开始，还要走几步才能停下来的最大(收益-代价)。

拓扑排序后，对于一个点 $u$ ，枚举与它相邻的所有点 $v$ ，就会有以下转移方程：

注意：要特判 $a = 1$ 和 $b = 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
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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 2e5 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int n, m, k, a, b, w_a, w_b, fr, tl;
int w[N], in[N];
int dp[N][51], q[N * 5];

struct Graph
{
    int head[N], cnt;
    
    struct edge
    {
        int to, nxt;
    };
    edge e[N * 2];
    
    il void add_edge(int u, int v)
    {
        e[++cnt] = (edge) {v, head[u]};
        head[u] = cnt;
        in[v]++;
    }
};
Graph G;

il void Delete(int x)
{
    for (ri i = G.head[x]; i; i = G.e[i].nxt)
    {
        int v = G.e[i].to;
        in[v]--;
        if (!in[v])
            q[++tl] = v;
    }
} 

il void Solve()
{
    tl = 0, fr = 0;
    q[++tl] = 1;
    dp[1][0] = w[1];
    while (fr < tl)
    {
        int u = q[++fr];
        Delete(u);
        for (ri i = G.head[u]; i; i = G.e[i].nxt)
        {
            int v = G.e[i].to;
            if (dp[u][0] != dp[0][0])
            {
                if (a != 1)
                    dp[v][a - 1] = max(dp[v][a - 1], dp[u][0] - w_a);
                else
                    dp[v][0] = max(dp[v][0], dp[u][0] - w_a + w[v]);
                if (b != 1)
                    dp[v][b - 1] = max(dp[v][b - 1], dp[u][0] - w_b);
                else
                    dp[v][0] = max(dp[v][0], dp[u][0] - w_b + w[v]);
            }
            if (dp[u][1] != dp[0][0])
                dp[v][0] = max(dp[v][0], dp[u][1] + w[v]);
            for (ri j = b; j > 1; j--)
                if (dp[u][j] != dp[0][0])
                    dp[v][j - 1] = max(dp[v][j - 1], dp[u][j]);
        }
    }
}

int main()
{
    n = read(), m = read(), k = read();
    a = read(), b = read(), w_a = read(), w_b = read();
    
    for (ri i = 1; i <= n; i++)
    {
        int pos = read(), t = read();
        w[pos] += t;
    }
    
    for (ri i = 1; i <= k; i++)
    {
        int u = read(), v = read();
        G.add_edge(u, v);
    }
    
    for (ri i = 2; i <= m; i++)
        if (!in[i])
            q[++tl] = i;
    
    while (fr < tl)
        Delete(q[++fr]);
    
    memset(dp, 0xc0, sizeof(dp));
    Solve();
    
    int ans = 0;
    for (ri i = 1; i <= m; i++)
        ans = max(ans, dp[i][0]);
    
    printf("%d",ans);
    return 0;
}
/*
3 7 8
1 2
3 2
2 2
4 3
6 4
1 2
2 4
4 5
2 6
7 6
6 4
3 2
3 4

*/

15. Luogu 1052 过河

Finished

题意：一座长 $L$ 的桥，某些位置上有石头，一步可以走区间 $[s, t]$ 中的任意正整数，问最少会踩到多少石头。

思路：其实很显然是一道 $\text{DP}$ ，假如不考虑 $L$ 那个大的变态的范围，还是一道很水的题目，但是现在情况并不一样，所以怎么办呢？当然问题也不大，因为 $m$ 并不是很大，所以有很多石头之间的间距很大，但这些间距并没有意义，所以我们可以考虑把间距合理的缩小。

由数据范围可知 $s$ 和 $t$ 都在 $10$ 以内，然后我们可以求得 $1$ 到 $10$ 的 $lcm$ 为 $2520$ ，所以我们考虑把间距大于这个值的所有石头平移 $2520n$ 个单位长度，这样就可以做了。

注意：并没有什么要注意的（

代码：

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
#include <bits/stdc++.h>
#define ri register int
#define il inline
#define ll long long
using namespace std;

const int N = 1e6 + 110;
const int MAXN = 110;
const int inf = 0x7fffffff;
const double eps = 1e-8;

il int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (isdigit(ch))
	{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int l;
int s, t, m;
int a[N], b[N], f[N];
bool vis[N];

int main()
{
	l = read();
	s = read(), t = read(), m = read();
	for (ri i = 1; i <= m; i++)
		a[i] = read();
	sort(a + 1, a + 1 + m);
	for (ri i = 1; i <= m; i++)
	{
		int d = a[i] - a[i - 1];
		if (d > 2520)
			d %= 2520;
		b[i] = b[i - 1] + d;
		vis[b[i]] = 1;
	}
	b[++m] = b[m] + (l - b[m]) % 2520;
	l = b[m];
	memset(f, 63, sizeof(f));
	f[0] = 0;
	for (ri i = s; i < b[m] + t; i++)
		for (ri j = s; j <= t; j++)
			if (i >= j)
				f[i] = min(f[i - j] + vis[i], f[i]);
	int ans = inf;
	for (ri i = b[m]; i < b[m] + t; i++)
		ans = min(ans, f[i]);
	printf("%d", ans);
	return 0;
}
/*
10
2 3 5
2 3 5 6 7

*/
0%