题面

这题你们基本都读完就能切吧。。真的很水。。

~~私人教练~~ $l$ $n$ $x_i, c_i$ $0$ $r_f\texttt{秒/米}$ $r_b\texttt{秒/米}$ $r_b \lt r_f$ ，但是因为年轻人比较有活力，所以他必须全程都不在 sssmzy 后面，求 zpair 最多可以吃到多少彩虹糖。

$1 \le l \le 10^6, 1 \le n \le 10^5, 1 \le r_b \lt r_f \le 10^6, 1 \le c_i \le 10^6, 0 \lt x_i \lt l$ 。

$l, n, r_f, r_b$
$x_1, c_1$
$x_2, c_2$
$\cdots$
$x_n, c_n$

Examples

Input_1


xxxxxxxxxx
3
1
10 2 4 3
2
7 2
3
8 1

Output_1


xxxxxxxxxx
1
1
15

Solution

$c_i$ 排个序，无脑优先选可以选的最高价值的补给站，模拟一下即可，记得开 long long，这个贪心我感觉没有绿色的难度。。

Code


xxxxxxxxxx
57
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int L, N;
27
vector < pair < int, int >/*price, position*/ > rest;
28
int spdF, spdB;
29
int d;
30
ll ans(0);
31

32
int main(){
33
    L = read(), N = read(), spdF = read(), spdB = read(); d = spdF - spdB;
34
    for(int i = 1; i <= N; ++i){int p = read(), c = read(); rest.emplace_back(c, p);}
35
    int cur(0); sort(rest.begin(), rest.end(), greater < pair < int, int > >());
36
    for(auto res : rest)
37
        ans += (ll)res.first * max(0, res.second - cur) * d, cur = max(cur, res.second);
38
    printf("%lld\n", ans);
39
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
40
    return 0;
41
}
42

43
template < typename T >
44
inline T read(void){
45
    T ret(0);
46
    short flag(1);
47
    char c = getchar();
48
    while(c != '-' && !isdigit(c))c = getchar();
49
    if(c == '-')flag = -1, c = getchar();
50
    while(isdigit(c)){
51
        ret *= 10;
52
        ret += int(c - '0');
53
        c = getchar();
54
    }
55
    ret *= flag;
56
    return ret;
57
}

LG-P4264 [USACO18FEB]Teleportation S

题面

$n$ $a_i, b_i$ $a_i$ $b_i$ $d_i = \vert a_i - b_i \vert$ $0$ $y$ $0$ $0$ $y$ ，同样贡献为不用传送门走的距离，最小化贡献和，求最小值。

$1 \le n \le 10^5, -10^8 \le a_i, b_i \le 10^8$ 。

Examples

Input_1


xxxxxxxxxx
4
1
3
2
-5 -7
3
-3 10
4
-2 7

Output_1


xxxxxxxxxx
1
1
10

Solution

~~这道题告诉我们，题做不出来的时候要多去去厕所，去溜达一圈之后或许就突然想明白了~~。。

我感觉还算是一道挺有意思的题，比较奇妙，难度适中，蓝色评的也很合理。

$y$ $a_i, b_i$ $f(y)_i = \min(\vert a_i - b_i \vert, \vert a_i \vert + \vert y - b_i \vert)$ $\sum_{i = 1}^n f(y)_i$ 。

$\vert a_i - b_i \vert \lt \vert a_i \vert$ $a_i \ge b_i \gt 0 \vee 0 \le a_i \lt b_i \lt 2a_i \vee 0 \gt a_i \gt b_i \gt 2a_i \vee a_i \lt b_i \lt 0$ $f(y)_i$ 就是一条直线，不过这一大坨不等式看着就很阴间，画个图吧：

Oops! The image is blocked! Please visit my own website to observe the image! 图片被墙了，请通过文章头的跳转链接访问！

$0 \le 2a_i \lt b_i \vee b_i \lt2a_i \le 0 \vee a_i \lt 0 \lt b_i \vee b_i \lt 0 \lt a_i$ $y$ 相关，需要额外讨论一下。

$f(y)_i = \min(\vert a_i - b_i \vert, \vert a_i \vert + \vert y - b_i \vert)$ $0 \le 2a_i \lt b_i$ $\min(b_i - a_i, a_i + \vert y - b_i \vert)$ $y$ $b_i$ $b_i \lt 2b_i - 2a_i$ 在条件下恒成立即可），最终可以写成一下柿子：

$0 \le 2a_i \lt b_i$ ：

\begin{matrix} f (y)_{i} = {\begin{cases} b_{i} - a_{i} & y \in (- \infty, 2 a_{i}] \cup [2 b_{i} - 2 a_{i}, + \infty) \\ - y + a_{i} + b_{i} & y \in (2 a_{i}, b_{i}) \\ y + a_{i} - b_{i} & y \in [b_{i}, 2 b_{i} - 2 a_{i}) \end{cases} \end{matrix}

$b_i \lt2a_i \le 0$ 同理可以推出：

$b_i \lt2a_i \le 0$ ：

\begin{matrix} f (y)_{i} = {\begin{cases} a_{i} - b_{i} & y \in (- \infty, 2 b_{i} - 2 a_{i}] \cup [2 a_{i}, + \infty) \\ - y - a_{i} + b_{i} & y \in (2 b_{i} - 2 a_{i}, b_{i}) \\ y - a_{i} - b_{i} & y \in [b_{i}, 2 a_{i}) \end{cases} \end{matrix}

剩下的两个区间也同理推导一下即可：

$a_i \lt 0 \lt b_i$ ：

\begin{matrix} f (y)_{i} = {\begin{cases} b_{i} - a_{i} & y \in (- \infty, 0] \cup [2 b_{i}, + \infty) \\ - y - a_{i} + b_{i} & y \in (0, b_{i}) \\ y - a_{i} - b_{i} & y \in [b_{i}, 2 b_{i}) \end{cases} \end{matrix}

$b_i \lt 0 \lt a_i$ ：

\begin{matrix} f (y)_{i} = {\begin{cases} a_{i} - b_{i} & y \in (- \infty, 2 b_{i}] \cup [0, + \infty) \\ - y + a_{i} + b_{i} & y \in (2 b_{i}, b_{i}) \\ y + a_{i} - b_{i} & y \in [b_{i}, 0) \end{cases} \end{matrix}

$f(y)_i$ $y$ 无关的认为其没有转折点即可。

Oops! The image is blocked! Please visit my own website to observe the image! 图片被墙了，请通过文章头的跳转链接访问！

$\sum_{i = 1}^nf(y)_i$ 了。

$O(n)$ $-1$ $-1$ $1$ $2$ $y$ $-1$ $i$ $i - 1$ $0$ $\sum_{i = 1}^n \vert a_i - b_i \vert$ $sum_i$ $\min\{sum_i\}$ ，然后这里因为坐标值域范围很大，所以考虑离散化，为了写着方便，直接开一个 map 存即可，排序也省了。

$O(n \log n)$ ，卡在排序上。

Code


xxxxxxxxxx
78
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N;
27
ll origin(0);
28
ll mn(LONG_LONG_MAX);
29
map < ll, ll > mp;
30
ll sum[310000]; int cnt(0);
31

32
void Insert(int p, int v){
33
    if(mp.find(p) == mp.end())mp.insert({p, v});
34
    else mp[p] += v;
35
}
36
void InsertAll(int sp1, int sp2, int sp3){
37
    Insert(sp1, -1);
38
    Insert(sp2, 2);
39
    Insert(sp3, -1);
40
}
41

42
int main(){
43
    N = read();
44
    for(int i = 1; i <= N; ++i){
45
        int a = read(), b = read();
46
        origin += abs(a - b);
47
        if(0 <= 2 * a && 2 * a < b)InsertAll(2 * a, b, 2 * b - 2 * a);
48
        else if(b < 2 * a && 2 * a <= 0)InsertAll(2 * b - 2 * a, b, 2 * a);
49
        else if(a < 0 && 0 < b)InsertAll(0, b, 2 * b);
50
        else if(b < 0 && 0 < a)InsertAll(2 * b, b, 0);
51
    }
52
    ll cur(0), sum(origin); int lft(INT_MIN);
53
    mn = origin;
54
    for(auto v : mp){
55
        sum += (ll)cur * (v.first - lft);
56
        cur += v.second, lft = v.first;
57
        mn = min(mn, sum);
58
    }
59
    printf("%lld\n", mn);
60
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
61
    return 0;
62
}
63

64
template < typename T >
65
inline T read(void){
66
    T ret(0);
67
    short flag(1);
68
    char c = getchar();
69
    while(c != '-' && !isdigit(c))c = getchar();
70
    if(c == '-')flag = -1, c = getchar();
71
    while(isdigit(c)){
72
        ret *= 10;
73
        ret += int(c - '0');
74
        c = getchar();
75
    }
76
    ret *= flag;
77
    return ret;
78
}

LG-P4088 [USACO18FEB]Slingshot P

题面

$n$ $x_i, y_i, t_i$ $t_i$ $x_i$ $y_i$ $d$ $d$ $m$ $a_i, b_i$ $a_i$ $b_i$ ，最多可以使用一次便便弹弓，最少需要花费多少时间。

$1 \le n, m \le 10^5, 0 \le x_i, y_i, t_i, a_i, b_i \le 10^9$ 。

Examples

Input_1

Output_1


xxxxxxxxxx
3
1
4
2
3
3
10

Solution

$a, b$ $\lvert a - b \rvert$ $x, y, t$ $\lvert a - x \rvert + \lvert b - y \rvert + t$ ，我们需要最小化这个值。

$(x, y)$ $x$ $(x, y)$ 的那些信息，随便搞一下就行了，细节不少。。

$x$ $rx$ $x$ $x \leftarrow -x + lim + 1, rx \leftarrow -rx$ $a - x$ $x - a$ ，此时前者为负，后者一定为正。

Code


xxxxxxxxxx
108
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define NM (N + M)
24

25
template< typename T = int >
26
inline T read(void);
27

28
vector < int > data;
29
struct Node{
30
    int idx;
31
    int x, y;
32
    int rx, ry;
33
    int t;
34
    friend const bool operator < (Node a, Node b){return a.x < b.x;}
35
}nod[210000];
36

37
int N, M;
38
ll lim;
39
ll ans[110000];
40

41
class BIT{
42
private:
43
    ll tr[410000];
44
public:
45
    void clear(void){memset(tr, 0x3f, sizeof tr);}
46
    int lowbit(int x){return x & -x;}
47
    void Modify(int x, ll v){while(x <= lim)tr[x] = min(tr[x], v), x += lowbit(x);}
48
    ll Query(int x){ll ret((ll)INT_MAX * 114514); while(x)ret = min(ret, tr[x]), x -= lowbit(x); return ret;}
49
}bit;
50

51
void Make(void){
52
    sort(nod + 1, nod + NM + 1);
53
    bit.clear();
54
    for(int i = 1; i <= NM; ++i){
55
        if(!~nod[i].t)ans[nod[i].idx] = min(ans[nod[i].idx], bit.Query(nod[i].y) + nod[i].rx + nod[i].ry);
56
        else bit.Modify(nod[i].y, (ll)-nod[i].rx - nod[i].ry + nod[i].t);
57
    }
58
}
59

60
int main(){
61
    memset(ans, 0x3f, sizeof ans);
62
    N = read(), M = read();
63
    for(int i = 1; i <= N; ++i){
64
        int x = read(), y = read(), t = read();
65
        nod[i] = Node{i, x, y, x, y, t};
66
        data.emplace_back(x), data.emplace_back(y);
67
    }
68
    for(int i = 1; i <= M; ++i){
69
        int x = read(), y = read();
70
        nod[i + N] = Node{i, x, y, x, y, -1};
71
        data.emplace_back(x), data.emplace_back(y);
72
        ans[i] = abs(y - x);
73
    }sort(data.begin(), data.end());
74
    data.erase(unique(data.begin(), data.end()), data.end());
75
    lim = data.size();
76
    for(int i = 1; i <= NM; ++i)
77
        nod[i].x = distance(data.begin(), lower_bound(data.begin(), data.end(), nod[i].x) + 1),
78
        nod[i].y = distance(data.begin(), lower_bound(data.begin(), data.end(), nod[i].y) + 1);
79
    Make();
80
    for(int i = 1; i <= NM; ++i)
81
        nod[i].x = -nod[i].x + lim + 1, nod[i].rx = -nod[i].rx;
82
    Make();
83
    for(int i = 1; i <= NM; ++i)
84
        nod[i].y = -nod[i].y + lim + 1, nod[i].ry = -nod[i].ry;
85
    Make();
86
    for(int i = 1; i <= NM; ++i)
87
        nod[i].x = -nod[i].x + lim + 1, nod[i].rx = -nod[i].rx;
88
    Make();
89
    for(int i = 1; i <= M; ++i)printf("%lld\n", ans[i]);
90
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
91
    return 0;
92
}
93

94
template < typename T >
95
inline T read(void){
96
    T ret(0);
97
    short flag(1);
98
    char c = getchar();
99
    while(c != '-' && !isdigit(c))c = getchar();
100
    if(c == '-')flag = -1, c = getchar();
101
    while(isdigit(c)){
102
        ret *= 10;
103
        ret += int(c - '0');
104
        c = getchar();
105
    }
106
    ret *= flag;
107
    return ret;
108
}

LG-P4265 [USACO18FEB]Snow Boots S

题面

$f_n$ $i$ $f_1 = f_n = 0$ $b$ $s_i, d_i$ $s_i$ $d_i$ $d_i$ $n$ 需要丢掉的靴子数，求最小值。

$d_i$ $s_i$ ，保证起始和终点满足条件即可（~~这也是我理解错的地方~~）。

$2 \le n, b, \le 250, 0 \le f_i, s_i \le 10^9, 1 \le d_i \le n$ 。

Examples

Input_1


xxxxxxxxxx
6
1
10 4
2
0 2 8 3 6 7 5 1 4 0
3
2 3
4
4 2
5
3 4
6
7 1

Output_1


xxxxxxxxxx
1
1
2

Solution

$250$ $\texttt{2D2D}$ $250^4$ $O(nb)$ $O(b \log n)$ $O(b^2 n \log n)$ $O(n^2b + nb^2)$ $pre(i, j)$ $i$ $j$ $j$ $j$ $+1$ $O(n^2b)$ $dp(i, j)$ $i$ $i$ $j$ $i - 1$ $pre$ $O(nb^2)$ 的，当然我的方程写的有点小问题（正确性好像也有点问题），不过也没必要调，这个东西很不优而且边界不好设置。

$\texttt{2D2D}$ $dp(i)$ $i$ $\texttt{1D2D}$ 的就行了。

Code


xxxxxxxxxx
83
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N, B;
27
int dep[300];
28
int s[300], d[300];
29
bool dp[300][300];
30
// int dp[300][300];
31
// int pre[300][300];
32

33
int main(){
34
    // memset(dp, 0x3f, sizeof dp);
35
    // for(int i = 0; i <= 260; ++i)dp[i][0] = i;
36
    dp[1][1] = 1;
37
    N = read(), B = read();
38
    for(int i = 1; i <= N; ++i)dep[i] = read();
39
    for(int i = 1; i <= B; ++i)s[i] = read(), d[i] = read();
40

41
    // Waiting for debugging...
42
    // for(int i = 1; i <= B; ++i)
43
    //     for(int j = 1; j <= N; ++j)
44
    //         for(int k = j; k >= 1; --k)
45
    //             if(dep[k] <= s[i] && j - k + 1 <= d[i])pre[i][j] = k;
46
    //             else break;
47
    // for(int i = 1; i <= B; ++i)
48
    //     for(int j = 1; j <= N; ++j)
49
    //         if(dep[j] <= s[i])
50
    //             for(int k = i - 1; k >= 0; --k)
51
    //                 if(pre[i][j])dp[i][j] = min(dp[i][j], dp[k][pre[i][j] - 1] + i - k - 1);
52
    // int mn(INT_MAX);
53
    // for(int i = 1; i <= B; ++i)mn = min(mn, dp[i][N]);
54
    // printf("%d\n", mn);
55

56
    for(int i = 1; i <= B; ++i)
57
        for(int j = 1; j <= N; ++j)
58
            if(dp[i][j])
59
                for(int k = i; k <= B; ++k)
60
                    if(s[k] >= dep[j])
61
                        for(int l = j + 1; l <= min(N, j + d[k]); ++l)
62
                            if(s[k] >= dep[l])
63
                                dp[k][l] = true;
64
    for(int i = 1; i <= B; ++i)if(dp[i][N])printf("%d\n", i - 1), exit(0);
65
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
66
    return 0;
67
}
68

69
template < typename T >
70
inline T read(void){
71
    T ret(0);
72
    short flag(1);
73
    char c = getchar();
74
    while(c != '-' && !isdigit(c))c = getchar();
75
    if(c == '-')flag = -1, c = getchar();
76
    while(isdigit(c)){
77
        ret *= 10;
78
        ret += int(c - '0');
79
        c = getchar();
80
    }
81
    ret *= flag;
82
    return ret;
83
}

LG-P4269 [USACO18FEB]Snow Boots G

题面

$n$ $f_n$ $b$ $s_i, d_i$ $f_n$ $d_i$ $s_i$ $1$ $0$ 。

$1 \le n, b \le 10^5, 0 \le f_i, s_i \le 10^9, 1 \le d_i \le n - 1$ 。

Examples

Input_1


xxxxxxxxxx
9
1
8 7
2
0 3 8 5 6 9 0 0
3
0 5
4
0 6
5
6 2
6
8 1
7
10 1
8
5 3
9
150 7

Output_1


xxxxxxxxxx
7
1
0
2
1
3
1
4
0
5
1
6
1
7
1

Solution

$1$ $0$ $1$ $f_i$ $O(n)$ $O(n \log n + q \log q)$ $O(n + q)$ 了。

Code


xxxxxxxxxx
85
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
// struct List{
27
//     List *pre, *nxt;
28
//     int dep;
29
// };
30
// List* lst[110000];
31
struct List{
32
    int pre, nxt;
33
    int dep;
34
}lst[110000];
35
int N, B;
36
struct Snow{
37
    int idx, dep;
38
    friend const bool operator < (const Snow &a, const Snow &b){return a.dep > b.dep;}
39
}snow[110000];
40
struct Boot{
41
    int idx, dis, dep;
42
    friend const bool operator < (const Boot &a, const Boot &b){return a.dep > b.dep;}
43
}boot[110000];
44
bool ans[110000];
45

46
int main(){
47
    N = read(), B = read();
48
    for(int i = 1; i <= N; ++i){
49
        // lst[i]->dep = read();
50
        // if(i != 1)lst[i]->pre = lst[i - 1];
51
        // if(i != N)lst[i]->nxt = lst[i + 1];
52
        snow[i] = Snow{i, read()};
53
        lst[i] = List{i - 1, i + 1, snow[i].dep};
54
    }
55
    for(int i = 1; i <= B; ++i){int s = read(), d = read(); boot[i] = Boot{i, d, s};}
56
    sort(snow + 1, snow + N + 1), sort(boot + 1, boot + B + 1);
57
    int cur(0), mx(0);
58
    for(int i = 1; i <= B; ++i){
59
        while(cur <= N - 1 && snow[cur + 1].dep > boot[i].dep){
60
            ++cur;
61
            lst[lst[snow[cur].idx].nxt].pre = lst[snow[cur].idx].pre;
62
            lst[lst[snow[cur].idx].pre].nxt = lst[snow[cur].idx].nxt;
63
            mx = max(mx, lst[snow[cur].idx].nxt - lst[snow[cur].idx].pre);
64
        }if(mx <= boot[i].dis)ans[boot[i].idx] = true;
65
    }
66
    for(int i = 1; i <= B; ++i)printf("%d\n", ans[i] ? 1 : 0);
67
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68
    return 0;
69
}
70

71
template < typename T >
72
inline T read(void){
73
    T ret(0);
74
    short flag(1);
75
    char c = getchar();
76
    while(c != '-' && !isdigit(c))c = getchar();
77
    if(c == '-')flag = -1, c = getchar();
78
    while(isdigit(c)){
79
        ret *= 10;
80
        ret += int(c - '0');
81
        c = getchar();
82
    }
83
    ret *= flag;
84
    return ret;
85
}

LG-P4268 [USACO18FEB]Directory Traversal G

题面

sssmzy 在他的电脑中存储了很多学习资料，我们都知道在系统大多数路径中都存在名为 .. 的路径，通过此路径可以回到上一级（通过 . 和 .. 等连接的一般叫做相对路径）。给定一些文件夹和文件之间的关系，sssmzy 可以处于某个文件夹中，他要访问所有的文件，显然这些文件相对于其所在文件夹会有很多路径，你需要最小化每个文件路径长度和，并输出。特别地，我们不考虑使用 ./。

$2 \le n \le 10^5$ 。

对于样例，其文件之间的结构为：


xxxxxxxxxx
8
1
bessie/
2
--folder1/
3
----file1
4
----folder2/
5
------file2
6
--folder3/
7
----file3
8
--file4

可以证明从 folder2 出发会有最小路径长度和，路径为：


xxxxxxxxxx
4
1
../file1
2
file2
3
../../folder3/file3
4
../../file4

$2 \leq N \leq 100,000$ $1$ $N$ $N$ $a-z$ $0-9$ $16$ $m$ $m$ $0$ $m > 0$ $m$ $m$ $m$ 个整数，为该文件夹下的对象的 ID。

Examples

Input_1


xxxxxxxxxx
9
1
8
2
bessie 3 2 6 8
3
folder1 2 3 4
4
file1 0
5
folder2 1 5
6
file2 0
7
folder3 1 7
8
file3 0
9
file4 0

Output_1


xxxxxxxxxx
1
1
42

Solution

一个有点像换根 DP 但是没换根的树形 DP。

首先根据定义，显然不会有空文件夹，所以叶子节点均为文件夹。

$f(x)$ $\omega(x)$ / $\omega(root) = 0$ $root$ $x$ $leaf(x)$ 。

$f(y)$ $f(x)$ $f(y) = f(x) - leaf(y) \times (\omega(y) + 1) + (leaf(root) - leaf(y)) \times 3$ 。

$\times 3$ ../ $f(x)$ 就行。

Code


xxxxxxxxxx
85
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
struct Edge{
27
    Edge* nxt;
28
    int to;
29
    OPNEW;
30
}ed[210000];
31
ROPNEW(ed);
32
Edge* head[110000];
33

34
int N;
35
ll f[110000];
36
int leaf[110000], w[110000];
37
ll dis[110000];
38
ll mn;
39

40
void dfs_pre(int p = 1, int fa = 0){
41
    if(p != 1 && !head[p]->nxt)leaf[p] = 1, f[1] += dis[fa] + w[p];
42
    else dis[p] = p == 1 ? 0 : dis[fa] + w[p] + 1;
43
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)dfs_pre(SON, p), leaf[p] += leaf[SON];
44
}
45
void dfs(int p = 1, int fa = 0){
46
    if(p != 1 && head[p]->nxt)f[p] = f[fa] - (ll)leaf[p] * (w[p] + 1) + (ll)(leaf[1] - leaf[p]) * 3, mn = min(mn, f[p]);
47
    for(auto i = head[p]; i; i = i->nxt)if(SON != fa)dfs(SON, p);
48
}
49

50
int main(){
51
    N = read();
52
    for(int i = 1; i <= N; ++i){
53
        string dir;
54
        cin >> dir;
55
        w[i] = i == 1 ? 0 : (int)dir.size();
56
        int M = read();
57
        for(int j = 1; j <= M; ++j){
58
            int son = read();
59
            head[i] = new Edge{head[i], son};
60
            head[son] = new Edge{head[son], i};
61
        }
62
    }
63
    dfs_pre();
64
    mn = f[1];
65
    dfs();
66
    printf("%lld\n", mn);
67
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
68
    return 0;
69
}
70

71
template < typename T >
72
inline T read(void){
73
    T ret(0);
74
    short flag(1);
75
    char c = getchar();
76
    while(c != '-' && !isdigit(c))c = getchar();
77
    if(c == '-')flag = -1, c = getchar();
78
    while(isdigit(c)){
79
        ret *= 10;
80
        ret += int(c - '0');
81
        c = getchar();
82
    }
83
    ret *= flag;
84
    return ret;
85
}

LG-P4267 [USACO18FEB]Taming the Herd G

题面

原题面说的很奇怪，我理解了半天才看懂，所以这题就不简化题面了。。

$0$ $3$ $3$ 。Farmer John一丝不苟地记录了每一天计数器的读数。
年末到了，Farmer John准备做一些统计。他说，你们这些奶牛会付出代价的！然而他的某些记录看上去不太对劲……
Farmer John想要知道从他开始记录以来发生过多少次出逃。但是，他怀疑这些奶牛篡改了它的记录，现在他所确定的只有他是从发生出逃的某一天开始记录的。请帮助他求出，对于每个从他开始记录以来可能发生的出逃次数，他被篡改了的记录条数的最小值。
$N$ $1 \leq N \leq 100$ $N$ $i$ $a_i$ $100$ $i$ $a_i$ ，除非奶牛篡改了这一天的记录条目。
$N$ $i$ $i$ 次出逃的事件序列中，与该事件序列不一致的记录条目条数的最小值。

阳间题面：

题目说在一个牛棚里有一个计数器，用来记录每一天有没有奶牛逃跑。假设今天是第 i 天，如果今天有奶牛逃跑，那么计数器就为 0 。如果在第 i−j 天有奶牛逃跑，那么计数器就为 j 。但是记录有可能被篡改，给定一个记录的数列（有可能被篡改过），求在有 i 个奶牛逃跑时的最小被篡改量。

Input_1


xxxxxxxxxx
2
1
6
2
1 1 2 0 0 1

Output_1


xxxxxxxxxx
6
1
4
2
2
3
1
4
2
5
3
6
4

Solution

一道比较裸的 DP，难度在于理解题意。

$dp(i, j)$ $i$ $j$ $i$ $\texttt{2D2D}$ $dp(k, j) = \min\{dp(i, j - 1) + cal(i + 1, k)\}$ $i \lt k \le n$ $\texttt{2D1D}$ ，但是没必要。。

Code


xxxxxxxxxx
63
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N;
27
int a[110];
28
int dp[110][110];
29
int cal(int s, int t){
30
    int cnt(0);
31
    for(int i = s; i <= t; ++i)if(a[i] != i - s)++cnt;
32
    return cnt;
33
}
34

35
int main(){
36
    memset(dp, 0x3f, sizeof dp);
37
    dp[0][0] = 0;
38
    N = read();
39
    for(int i = 1; i <= N; ++i)a[i] = read();
40
    for(int i = 0; i <= N; ++i)
41
        for(int j = 1; j <= N; ++j)
42
            for(int k = i + 1; k <= N; ++k)
43
                dp[k][j] = min(dp[k][j], dp[i][j - 1] + cal(i + 1, k));
44
    for(int i = 1; i <= N; ++i)printf("%d\n", dp[N][i]);
45
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
46
    return 0;
47
}
48

49
template < typename T >
50
inline T read(void){
51
    T ret(0);
52
    short flag(1);
53
    char c = getchar();
54
    while(c != '-' && !isdigit(c))c = getchar();
55
    if(c == '-')flag = -1, c = getchar();
56
    while(isdigit(c)){
57
        ret *= 10;
58
        ret += int(c - '0');
59
        c = getchar();
60
    }
61
    ret *= flag;
62
    return ret;
63
}

LG-P4270 [USACO18FEB]Cow Gymnasts P

题面

$n$ $[1, n]$ $i$ $i - 1$ 个平台并落下，求有多少种排列能使无论多少次操作每个平台的奶牛数都不改变。

$1 \le n \le 10^{12}$ 。

$(1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4), (2, 3, 2, 3), (3, 2, 3, 2)$ 。

Examples

Input_1


xxxxxxxxxx
1
1
4

Output_1


xxxxxxxxxx
1
1
6

Solution

一道纯粹的人类智慧题。。。

$i$ $\xi$ $i$ $\xi$ 层所需要的旋转次数。也就是对于一个合法的排列，两个同一高度平台之间的距离即为平台内所有牛的循环周期。

首先对于符合条件的排列，有好几个奇怪的性质：

$i$ $i$ 层的奶牛平移过来，而不可以是从更高层的奶牛掉下来。

$m$ $m - 1$ $m$ $m + 1$ $m - 1$ $2$ $3$ $\cdots$ $m - 1$ $m$ $m - 1$ $m - 1$ $m$ ，然后以此类推即可证明所有层数都是由对应层数平移过来的，得证。

$i$ $i$ 的约数。

$i$ $T_i$ $k$ $i = kT_i$ ，得证。

$i - 1$ $i$ 层奶牛循环周期的约数。

$i$ $i$ $i$ $i - 1$ $i$ $T_{i - 1} \mid T_i$ ，得证。

$1$ 。

$T_i \mid i, T_{i + 1} \mid i + 1$ $T_{i} \mid T_{i + 1}$ $\gcd(i, i + 1) = 1$ $\gcd(T_i, T_{i + 1}) = 1$ $1$ $T_1 = T_2 = \cdots = T_{n - 1} = 1$ $i$ $i - 1$ $1$ $i - 1$ $1$ .

以此我们便可以得出结论：

a n s = 2 - n + \sum_{i = 1}^{n - 1} 2^{gcd (n, i)}

$i$ $i$ $i$ $n$ $n$ 最大的 $\gcd(n, i)$ $n = 6, i = 3, \gcd = 3$ 的例子：

Oops! The image is blocked! Please visit my own website to observe the image! 图片被墙了，请通过文章头的跳转链接访问！

$2^{\gcd(n, i)}$ $A, B, C$ $i$ $i$ $i$ $-1$ 。

$i$ $A = i$ $B$ $i$ $B$ $i + 1$ $i - 1$ $i$ $i + 1$ $C$ $i$ $i + 1$ $i + 2$ $C$ $A$ $i + 2$ $i$ $1$ $i + 2 = 5$ $3 \nmid 5$ $i + 1$ $i$ 要么不是，不是的时候数也唯一确定，故可以如此枚举。

$i$ $i + 1$ 。

$i$ $i + 1$ $1$ $i - 1$ $i + 2$ $T_{i + 1} \ge 2$ $i + 2$ $i + 1$ $T_{i + 1} = 1$ $i$ $i + 1$ $i + 1$ $1$ 的条件的，所以这样才是合法的。故得证。

$i$ $i + 1$ $i + 1$ $2^{\gcd(n, i)} - 1$ $i = n$ $i + 1$ $n$ $n$ $n$ 则为唯一的方案，如此最终答案便为：

\begin{aligned} a n s & = \sum_{i = 1}^{n - 1} (2^{gcd (n, i)} - 1) + 1 \\ = 2 - n + \sum_{i = 1}^{n - 1} 2^{gcd (n, i)} \\ = 2 - n - 2^{n} + \sum_{i = 1}^{n} 2^{gcd (n, i)} \end{aligned}

然后发现数据范围这个柿子肯定过不去，于是考虑优化，继续推柿子：

\begin{aligned} \sum_{i = 1}^{n} 2^{gcd (n, i)} & = \sum_{j = 1}^{n} 2^{j} \sum_{i = 1}^{n} [gcd (n, i) = j] \\ = \sum_{j = 1}^{n} 2^{j} \sum_{i = 1}^{n} [j ∣ i \land j ∣ n \land gcd (\frac{n}{j}, \frac{i}{j}) = 1] \\ = \sum_{j = 1}^{n} (2^{j} \times φ (\frac{n}{j}) \times [j ∣ n]) \\ = \sum_{j ∣ n} (2^{j} \times φ (\frac{n}{j})) \\ = \sum_{j ∣ n} (2^{\frac{n}{j}} \times φ (j)) \end{aligned}

$O(\sqrt{n}\log n)$ $O(\sqrt{n})$ $O(\sqrt{n})$ $O(n)$ $O(n^{\frac{2}{3}})$ 实现，刚好能过，不过 duck 不必。

$p_i$ $c_i \neq 0$ ，如果有：

n = \prod_{i = 1}^{k} p_{i}^{c^{i}}

那么：

φ (n) = n \times \prod_{i = 1}^{k} \frac{p_{i} - 1}{p_{i}}

$n$ $O(1)$ $O(\sqrt{n})$ $\log$ $2^j$ long long $n \div \prod p_i$ $\prod p_i - 1$ ，否则会爆 long long，当然像我一样直接用 __int128_t 可以直接忽略这些问题。

至此此题解决，还是很精妙的。

Code


xxxxxxxxxx
86
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (ll)(1e9 + 7)
24

25
template< typename T = int >
26
inline T read(void);
27

28
ll N;
29
int tot(0);
30
pair < ll, int > fact[1100000];
31
int cur[1100000];
32
__int128_t ans(0);
33

34
__int128_t qpow(ll a, ll b){
35
    __int128_t ret(1), mul(a);
36
    while(b){
37
        if(b & 1)ret = ret * mul % MOD;
38
        b >>= 1;
39
        mul = mul * mul % MOD;
40
    }return ret;
41
}
42

43
void dfs(int p = 1, ll base = 1, __int128_t phi = 1, __int128_t div = 1){
44
    if(p > tot){
45
        phi *= base, phi /= div, phi %= MOD;
46
        ans = (ans + phi * qpow(2, N / base) % MOD) % MOD;
47
        return;
48
    }
49
    dfs(p + 1, base, phi, div);
50
    phi *= fact[p].first - 1;
51
    div *= fact[p].first;
52
    for(int i = 1; i <= fact[p].second; ++i)
53
        base *= fact[p].first, dfs(p + 1, base, phi, div);
54
}
55

56
int main(){
57
    N = read < ll >();
58
    ll tmp(N); ll cur(2), cnt(0);
59
    while(tmp > 1){
60
        if(cur * cur > tmp)break;
61
        while(tmp % cur == 0)tmp /= cur, ++cnt;
62
        if(cnt)fact[++tot] = {cur, cnt}, cnt = 0;
63
        ++cur;
64
    }if(tmp > 1)fact[++tot] = {tmp, 1};
65
    dfs();
66
    ans = ((((ans + 2 - N) % MOD) - qpow(2, N)) % MOD + MOD) % MOD;
67
    printf("%lld\n", (ll)ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template < typename T >
73
inline T read(void){
74
    T ret(0);
75
    short flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

LG-P4271 [USACO18FEB]New Barns P

题面

奇怪题，先咕着，laterrrrrr 再来写。

Examples

Input_1


xxxxxxxxxx
1
1

Output_1


xxxxxxxxxx
1
1

Solution

Code


xxxxxxxxxx
1
1

UPD

update-2022_11_10 初稿

USACO 2018 Feb Solution

题面

Examples

Solution

Code

题面

Examples

Solution

Code

题面

Examples

Solution

Code

题面

Examples

Solution

Code

题面

Examples

Solution

Code

题面

Examples

Solution

Code

题面

Solution

Code

题面

Examples

Solution

Code

题面

Examples

Solution

Code

UPD