USACO 2018 Open Solution

更好的阅读体验戳此进入

题面 Luogu 链接

LG-P4379 [USACO18OPEN]Lemonade Line S

题面

娱乐题，读完题你们肯定也都秒了。。

有 $n$$n$ 头牛，每头有 $w_i$$w_i$ 表示最多可以忍受多少头牛在其前面排队，每头牛都会尝试排到队尾一次，如果不可行便不会再去排，求一个尝试排队的顺序以最小化最终队列中的牛的数量，求最小值。

Examples

Input_1

xxxxxxxxxx
2
1
5
2
7 1 400 2 2

Output_1

xxxxxxxxxx
1
1
3

Solution

没啥可说的，无脑贪心，排个序即可。。

Code

xxxxxxxxxx
54
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
vector < int > cow;
28
int ans(0);
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= N; ++i)cow.emplace_back(read());
33
    sort(cow.begin(), cow.end(), greater < int >());
34
    for(auto it = cow.begin(); it != cow.end(); ++it)if(*it >= ans)++ans; else break;
35
    printf("%d\n", ans);
36
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
37
    return 0;
38
}
39

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

LG-P4380 [USACO18OPEN]Multiplayer Moo S

题面

存在一个 $n\times n$$n \times n$ 网格图，每格一个数，定义连通块为四联通的相同的数构成区域，求最大的连通块的大小，以及有且仅有两种数字的最大的连通块的大小。

$1\le n\le 250$$1 \le n \le 250$。

Examples

Input_1

xxxxxxxxxx
5
1
4
2
2 3 9 3
3
4 9 9 1
4
9 9 1 7
5
2 1 1 9

Output_1

xxxxxxxxxx
2
1
5
2
10

Solution

第一眼我就感觉这玩意和一个特别远古的经典题《宽搜 海战》特别像，那道题大概就是描述一个 $01$$01$ 矩阵然后让你求四连通块数量，然后发现确实差不多。。第一问的话就是记录一下是否访问过，然后遍历每个点，没访问过的话就搜一下，搜这个点所在的整个连通块，标记一下，然后记录块大小之类的，最后枚举一下取 $max$$\max$ 即可。。然后后来翻了一下题解才知道这玩意还有个名字叫 FloodFill，我一直以为这玩意就是朴素宽搜呢。。

然后对于第二问，我们可以考虑把每块缩一下，然后相邻的不同块建边，在这里枚举所有块，再枚举其相连的块，然后跑一个类似宽搜的东西，无脑枚举还有哪些块是连通的，每次算完取 $max$$\max$ 即可，当然这玩意的时空复杂度都很玄学，中间很多判重，可以考虑用 set 或 unorderer_set 加手写哈希实现，然后发现这玩意会 $\mathtt{\text{TLE}}$$\texttt{TLE}$，各种卡常之后依然寄，于是尝试思考为什么被卡，显然如果想要卡满算法应该让每个块大小均为 $1$$1$ 且隔一个块之后又是自己相同的颜色，这样第二问每次都会搜满图，然后枚举也是 $O(n^2)$$O(n^2)$ 级别的，最后差不多 $O(n^4)$$O(n^4)$，所以会寄。于是我们考虑，如果是这种类型的图一定会在很大部分均为最大值，所以可以不需要枚举完所有点对，加个卡时即可，很难被卡掉，即使被卡了也可以通过 rand 取点并判重，可以让出解率极高。

当然上面都是我口糊的，正解似乎可以通过 map 判重之类的实现，反正也算是暴力枚举加剪枝过的。。

Code

xxxxxxxxxx
156
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 IN_RANGE(x, y) (1 <= x && x <= N && 1 <= y && y <= N)
24

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

28
int N;
29
int mp[300][300];
30
int belong[300][300];
31
// bitset < 90000 > exist[90000];
32

33
struct HashPair{
34
    size_t operator() (const pair < int, int > &x)const{
35
        // auto hash1 = hash < int >{}(x.first);
36
        // auto hash2 = hash < int >{}(x.second);
37
        // return hash1 ^ hash2;
38
        return (ll)x.first * x.second % (1000000007);
39
    }
40
};
41

42
unordered_set < pair < int, int >, HashPair > exist;
43
int mx1(-1), mx2(-1);
44
int cnt(0);
45
pair < int, int > blk[110000];
46
bitset < 90000 > vis[1];
47
int ver(0);
48

49
int dx[10] = {0, -1, 0, 1, 0};
50
int dy[10] = {0, 0, 1, 0, -1};
51

52
struct Edge{
53
    Edge* nxt;
54
    int to;
55
    OPNEW;
56
}ed[910000];
57
ROPNEW(ed);
58
Edge* head[210000];
59

60
void bfs(int idx, int val, int px, int py){
61
    queue < pair < int, int > > cur;
62
    cur.push({px, py});
63
    belong[px][py] = idx;
64
    ++blk[idx].second;
65
    while(!cur.empty()){
66
        auto tp = cur.front(); cur.pop();
67
        for(int i = 1; i <= 4; ++i){
68
            int tx = tp.first + dx[i], ty = tp.second + dy[i];
69
            if(!IN_RANGE(tx, ty))continue;
70
            if(mp[tx][ty] == val && !belong[tx][ty])++blk[idx].second, belong[tx][ty] = idx, cur.push({tx, ty});
71
        }
72
    }
73
}
74

75
int main(){
76
    N = read();
77
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)mp[i][j] = read();
78
    for(int i = 1; i <= N; ++i)
79
        for(int j = 1; j <= N; ++j)
80
            if(!belong[i][j]){
81
                blk[++cnt].first = mp[i][j];
82
                bfs(cnt, mp[i][j], i, j);
83
            }
84
    for(int i = 1; i <= N; ++i)
85
        for(int j = 1; j <= N; ++j)
86
            for(int k = 1; k <= 4; ++k){
87
                int tx = i + dx[k], ty = j + dy[k];
88
                if(IN_RANGE(tx, ty) && belong[tx][ty] != belong[i][j]){
89
                    int t = belong[tx][ty], s = belong[i][j];
90
                    if(exist.find(make_pair(s, t)) == exist.end()){
91
                        exist.insert({s, t});
92
                        head[s] = new Edge{head[s], t};
93
                        head[t] = new Edge{head[t], s};
94
                    }
95
                }
96
            }
97
    // for(int i = 1; i <= cnt; ++i)printf("blk[%d] = %d\n", i, blk[i].second);
98
    for(int i = 1; i <= cnt; ++i)mx1 = max(mx1, blk[i].second);
99
    // printf("Belong:\n");
100
    // for(int i = 1; i <= N; ++i)for(int j = 1; j <= N; ++j)printf("%d%c", belong[i][j], j == N ? '\n' : ' ');
101
    // for(int p = 1; p <= cnt; ++p){
102
    //     printf("Father: %d: ", p);
103
    //     for(auto i = head[p]; i; i = i->nxt){
104
    //         printf("%d ", SON);
105
    //     }printf("\n");
106
    // }
107
    queue < int > tmp;
108
    queue < int > undel;
109
    for(int p = 1; p <= cnt; ++p)
110
        for(auto t = head[p]; t; t = t->nxt){
111
            if((double)clock() / CLOCKS_PER_SEC > 0.9)printf("%d\n%d\n", mx1, mx2), exit(0);
112
            while(!undel.empty()){
113
                int tp = undel.front(); undel.pop();
114
                vis[ver][tp] = false;
115
            }
116
            int ans(0);
117
            // ++ver;
118
            // vis[ver].reset();
119
            vis[ver][p] = vis[ver][t->to] = true;
120
            undel.push(p), undel.push(t->to);
121
            tmp.push(p), tmp.push(t->to);
122
            ans += blk[p].second, ans += blk[t->to].second;
123
            while(!tmp.empty()){
124
                int tp = tmp.front(); tmp.pop();
125
                for(auto i = head[tp]; i; i = i->nxt){
126
                    if(vis[ver][SON])continue;
127
                    if(blk[SON].first == blk[p].first || blk[SON].first == blk[t->to].first){
128
                        vis[ver][SON] = true;
129
                        undel.push(SON);
130
                        tmp.push(SON);
131
                        ans += blk[SON].second;
132
                    }
133
                }
134
            }
135
            mx2 = max(mx2, ans);
136
        }
137
    printf("%d\n%d\n", mx1, mx2);
138
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
139
    return 0;
140
}
141

142
template < typename T >
143
inline T read(void){
144
    T ret(0);
145
    short flag(1);
146
    char c = getchar();
147
    while(c != '-' && !isdigit(c))c = getchar();
148
    if(c == '-')flag = -1, c = getchar();
149
    while(isdigit(c)){
150
        ret *= 10;
151
        ret += int(c - '0');
152
        c = getchar();
153
    }
154
    ret *= flag;
155
    return ret;
156
}

LG-P4376 [USACO18OPEN]Milking Order G

题面

存在 $n$$n$ 头犇，你需要给所有犇挤奶，给定 $m$$m$ 条限制，每条限制有序列 $c_{n^{\prime }}$$c_{n'}$，表示犇 $c_i$$c_i$ 需要在 $c_{i+1}$$c_{i + 1}$ 之前被挤奶。你需要在满足前 $k$$k$ 条限制的条件下求出字典序最小的给所有犇挤奶的顺序序列。最大化 $k$$k$ 并输出此时字典序最小的挤奶序列。

$1\le n\le {10}^5,1\le m\le 5\times {10}^4,1\le \sum n^{\prime }\le 2\times {10}^5$$1 \le n \le 10^5, 1 \le m \le 5 \times 10^4, 1 \le \sum n' \le 2 \times 10^5$。

Examples

Input_1

xxxxxxxxxx
4
1
4 3
2
3 1 2 3
3
2 4 2
4
3 3 4 1

Output_1

xxxxxxxxxx
1
1
1 4 2 3

Solution

首先这个题意二分答案应该很显然吧？二分 $k$$k$ 然后考虑验证。显然我们每次挤奶的时候是应该选择不需要在任意犇之后挤奶的犇，这东西不难想到，把每个关系抽象成先挤奶的向后挤奶的连有向边，这样每次找的就是入度为 $0$$0$ 的犇，也就是拓朴排序。如果排到最后发现有环路了，那么显然说明矛盾，否则记录一下当前答案为局部最优解。然后注意需要输出字典序最小的，那么我们就把拓朴排序的时候的队列改成优先队列即可。最终复杂度 $O((n+\sum n^{\prime })\log m)$$O((n + \sum n') \log m)$。

Code

xxxxxxxxxx
100
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, M;
27

28
struct Edge{
29
    Edge* nxt;
30
    int to;
31
    OPNEW;
32
}ed[210000];
33
static Edge* P = ed;
34
Edge* head[110000];
35
void* Edge::operator new(size_t){return P++;}
36
void Clear(void){
37
    P = ed;
38
    memset(head, 0, sizeof(Edge*) * (N + 10));
39
}
40

41
int ind[110000];
42
vector < int > rnk[51000];
43
vector < int > ans;
44
vector < int > tmp;
45

46
bool Check(int lim){
47
    memset(ind, 0, sizeof(int) * (N + 10));
48
    Clear();
49
    tmp.clear();
50
    for(int i = 1; i <= lim; ++i){
51
        auto lst = rnk[i].begin();
52
        for(auto it = next(rnk[i].begin()); it != rnk[i].end(); ++it)
53
            ++ind[*it], head[*lst] = new Edge{head[*lst], *it}, lst = it;
54
    }
55
    std::priority_queue < int, vector < int >, greater < int > > cur;
56
    for(int i = 1; i <= N; ++i)if(!ind[i])cur.push(i);
57
    while(!cur.empty()){
58
        int tp = cur.top(); cur.pop();
59
        tmp.emplace_back(tp);
60
        for(auto i = head[tp]; i; i = i->nxt){
61
            --ind[SON];
62
            if(!ind[SON])cur.push(SON);
63
        }
64
    }
65
    return (int)tmp.size() == N;
66
}
67

68
int main(){
69
    N = read(), M = read();
70
    for(int i = 1; i <= M; ++i){
71
        int m = read();
72
        while(m--)rnk[i].emplace_back(read());
73
    }
74
    int l = 1, r = M;
75
    while(l <= r){
76
        int mid = (l + r) >> 1;
77
        if(Check(mid))ans.swap(tmp), l = mid + 1;
78
        else r = mid - 1;
79
    }
80
    for(auto i : ans)printf("%d ", i);
81
    printf("\n");
82
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
83
    return 0;
84
}
85

86
template < typename T >
87
inline T read(void){
88
    T ret(0);
89
    short flag(1);
90
    char c = getchar();
91
    while(c != '-' && !isdigit(c))c = getchar();
92
    if(c == '-')flag = -1, c = getchar();
93
    while(isdigit(c)){
94
        ret *= 10;
95
        ret += int(c - '0');
96
        c = getchar();
97
    }
98
    ret *= flag;
99
    return ret;
100
}

LG-P4377 [USACO18OPEN] Talent Show G

题面

给定 $n$$n$ 头牛存在重量 $w_i$$w_i$ 和才艺水平 $t_i$$t_i$，给定重量限制 $W$$W$，要求选出一些牛使得在 $\sum w_i\ge W$$\sum w_i \ge W$ 的条件下最大化 ${\displaystyle \frac{\sum t_i}{\sum w_i}}$$\dfrac{\sum t_i}{\sum w_i}$，具体地，输出最大化后的 $\lfloor ans\times {10}^3\rfloor$$\lfloor ans \times 10^3 \rfloor$。

$1\le n\le 250,1\le W\le {10}^3,1\le w_i\le {10}^6,1\le t_i\le {10}^3$$1 \le n \le 250, 1 \le W \le 10^3, 1 \le w_i \le 10^6, 1 \le t_i \le 10^3$，保证 $\sum _{i=1}^n{w}_i\ge W$$\sum_{i = 1}^n w_i \ge W$。

Examples

Input_1

xxxxxxxxxx
4
1
3 15
2
20 21
3
10 11
4
30 31

Output_1

xxxxxxxxxx
1
1
1066

Solution

完全可以算是 01分数规划 的板子了，然后再套个 01背包即可。具体地，通过 01分数规划，转化一下有 $\sum t_i-ans\times \sum w_i\ge 0$$\sum t_i - ans \times \sum w_i \ge 0$，二分 $ans$$ans$，然后验证通过 01背包 实现，让价值 $c_i=t_i-ans\times w_i$$c_i = t_i - ans \times w_i$，对于 $j+w_i\ge W$$j + w_i \ge W$ 直接转化到 $dp(W)$$dp(W)$，最后判断一下 $dp(W)$$dp(W)$ 是否大于等于 $0$$0$ 即可。注意边界 $dp(0)=0$$dp(0) = 0$ 和枚举 $W$$W$ 的那一维需要到 $0$$0$。最终复杂度没算错的话大概是 $O(nW\log (\sum t_i\times ep{s}^{-1}))$$O(nW \log(\sum t_i \times eps^{-1}))$，也就是 $2e5\times \log 2e9$$2e5 \times \log 2e9$。

Code

xxxxxxxxxx
71
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 EPS (double)(1e-7)
24

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

28
int N, W;
29
int wei[300], val[300];
30
double c[300];
31
double dp[1100];
32

33
bool Check(double lim){
34
    for(int i = 1; i <= 1010; ++i)dp[i] = -114514.0;
35
    for(int i = 1; i <= N; ++i)c[i] = (double)val[i] - lim * (double)wei[i];
36
    for(int i = 1; i <= N; ++i)for(int j = W; j >= 0; --j)
37
        j + wei[i] >= W
38
            ? dp[W] = max(dp[W], dp[j] + c[i])
39
            : dp[j + wei[i]] = max(dp[j + wei[i]], dp[j] + c[i]);
40
    return dp[W] >= 0.0;
41
}
42

43
int main(){
44
    N = read(), W = read();
45
    double l(0.0), r(0.0);
46
    for(int i = 1; i <= N; ++i)wei[i] = read(), val[i] = read(), r += (double)val[i];
47
    int ans;
48
    while(l + EPS <= r){
49
        double mid = (l + r) / 2.0;
50
        if(Check(mid))ans = (int)floor(mid * 1000.0), l = mid;
51
        else r = mid;
52
    }printf("%d\n", ans);
53
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
54
    return 0;
55
}
56

57
template < typename T >
58
inline T read(void){
59
    T ret(0);
60
    int flag(1);
61
    char c = getchar();
62
    while(c != '-' && !isdigit(c))c = getchar();
63
    if(c == '-')flag = -1, c = getchar();
64
    while(isdigit(c)){
65
        ret *= 10;
66
        ret += int(c - '0');
67
        c = getchar();
68
    }
69
    ret *= flag;
70
    return ret;
71
}

LG-P4378 [USACO18OPEN]Out of Sorts S

题面

给定你冒泡排序的 “奶牛码” 实现，特别地，定义语句 moo 为输出 moo，对于给定的序列求该 “奶牛码” 会输出几次 moo。

xxxxxxxxxx
8
1
sorted = false
2
while (not sorted):
3
   sorted = true
4
   moo
5
   for i = 0 to N-2:
6
      if A[i+1] < A[i]:
7
         swap A[i], A[i+1]
8
         sorted = false

$1\le n\le {10}^5,1\le a_i\le {10}^9$$1 \le n \le 10^5, 1 \le a_i \le 10^9$。

Examples

Input_1

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

Output_1

xxxxxxxxxx
1
1
4

Solution

离散化，树状数组求逆序对个数，没了。确实没了，分没了。。。

放学前五分钟糊了一个 BIT + 离散化然后交上去直接 WA，回来扫了一眼题目才发现我是**。

观察发现这玩意不是在每次交换的时候 moo，而是每一趟尝试交换的时候叫一下。那么这东西就需要考虑一下冒泡排序的本质了，发现冒泡排序每次都是扫一遍给所有数的逆序对减少一个，这个应该比较好理解吧，每扫一遍的过程可以认为是把某些数往后移动一段，每次移动都会把这个数对跨过的这段数的 $1$$1$ 的贡献抵消，也就是减少一个逆序对。那么我们的答案就是对于每一位数，最大的逆序对个数然后再 $+1$$+1$，最后的加一是因为即使有序了也还要再跑一边判断。

Code

xxxxxxxxxx
66
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[110000];
28
vector < int > data;
29

30
class BIT{
31
private:
32
    int tr[110000];
33
public:
34
    int lowbit(int x){return x & -x;}
35
    void Modify(int x, int v = 1){while(x <= N)tr[x] += v, x += lowbit(x);}
36
    int Query(int x){int ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
37
}bit;
38

39
int main(){
40
    N = read();
41
    for(int i = 1; i <= N; ++i)a[i] = read(), data.emplace_back(a[i]);
42
    sort(data.begin(), data.end());
43
    data.erase(unique(data.begin(), data.end()), data.end());
44
    for(int i = 1; i <= N; ++i)a[i] = (int)data.size() - distance(data.begin(), lower_bound(data.begin(), data.end(), a[i]) + 1) + 1;
45
    int ans(0);
46
    for(int i = 1; i <= N; ++i)ans = max(ans, bit.Query(a[i] - 1)), bit.Modify(a[i]);
47
    printf("%d\n", ans + 1);
48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

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

LG-P4375 [USACO18OPEN]Out of Sorts G

题面

与上题题意及范围不变，奶牛码变成如下：

xxxxxxxxxx
13
1
sorted = false
2
while (not sorted):
3
   sorted = true
4
   moo
5
   for i = 0 to N-2:
6
      if A[i+1] < A[i]:
7
         swap A[i], A[i+1]
8
   for i = N-2 downto 0:
9
      if A[i+1] < A[i]:
10
         swap A[i], A[i+1]
11
   for i = 0 to N-2:
12
      if A[i+1] < A[i]:
13
         sorted = false

Examples

Input_1

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

Output_1

xxxxxxxxxx
1
1
2

Solution

可以尝试不用 BIT。。可以用 Treap，可以用 LCT。。

考虑和上一题有何不同，上一题是每个数之前的数对其贡献的逆序对取 $max$$\max$，因为每次会把数前面的一个大于它的数移到其之后。考虑本题，不难想到每次先把一个大于它的丢到之后，再把一个小于它的丢到之前，考虑对于一个具体的有序的位置 $i$$i$，不难想到是每次从 $[1,i]$$[1, i]$ 中丢出去一个不属于这段里的并且同时丢进来一个属于这段的，也就是说位置 $i$$i$ 的答案就是 $[1,i]$$[1, i]$ 中不符合的数量（注意这里的位置是在排序之后的有序位置）。所以本题和位置相关，我们把权值排个序，然后丢下标进 BIT 求逆序对即可。记得答案需要和 $1$$1$ 取 $max$$\max$。

Code

xxxxxxxxxx
66
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
pair < int, int > a[110000];
28

29
class BIT{
30
private:
31
    int tr[110000];
32
public:
33
    int lowbit(int x){return x & -x;}
34
    void Modify(int x, int v = 1){while(x <= N)tr[x] += v, x += lowbit(x);}
35
    int Query(int x){int ret(0); while(x)ret += tr[x], x -= lowbit(x); return ret;}
36
}bit;
37

38
int main(){
39
    N = read();
40
    int ans(1);
41
    for(int i = 1; i <= N; ++i)a[i] = {read(), i};
42
    sort(a + 1, a + N + 1);
43
    for(int i = 1; i <= N; ++i)
44
        bit.Modify(a[i].second),
45
        ans = max(ans, i - bit.Query(i));
46
    printf("%d\n", ans);
47

48
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
49
    return 0;
50
}
51

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

LG-P4372 [USACO18OPEN]Out of Sorts P

题面

存在一个奇怪的快速排序，大致过程是每次通过冒泡排序找到分割点，定义分割点为其左侧的数均小于它，右侧均大于它。找到分割点之后将原序列分割并递归处理被分出来的序列。求最终 work_counter 的值。

主程序奶牛码为：

xxxxxxxxxx
8
1
quickish_sort (A) {
2
   if length(A) = 1, return
3
   do { // Main loop
4
      work_counter = work_counter + length(A)
5
      bubble_sort_pass(A)
6
   } while (no partition points exist in A) 
7
   divide A at all partition points; recursively quickish_sort each piece
8
}

对于冒泡排序为：

xxxxxxxxxx
4
1
bubble_sort_pass (A) {
2
   for i = 0 to length(A)-2
3
      if A[i] > A[i+1], swap A[i] and A[i+1]
4
}

Examples

Input_1

xxxxxxxxxx
8
1
7
2
20
3
2
4
3
5
4
6
9
7
8
8
7

Output_1

xxxxxxxxxx
1
1
12

Solution

不难发现题意就是要我们求每次冒泡排序的长度求和，然后发现这东西也不太好求，于是再次转化为求每个数进行了多少次冒泡排序，次数求和显然也是原来的值。不难想到，对于一个数，其不会再被进行冒泡排序当且仅当其左右两个数均为分割点，所以我们的问题就再次转化为求每个点在几次冒泡排序后才会变成分割点，令其为 $ti{m}_i$$tim_i$，那么答案就是 $\sum _{i=1}^{n}max(ti{m}_i,ti{m}_{i-1})$$\sum_{i = 1}^n \max(tim_i, tim_{i - 1})$。

考虑维护这玩意，不难想到，每次冒泡排序都会把这个数相对所有其后面的小于它的数的距离减 $1$$1$，所以答案也就是距离其最远的那个不合法的位置和这个数的位置的距离，记得和 $1$$1$ 取 $max$$\max$。

对于具体的维护方式用单调队列或者双指针之类的东西弄一下即可，注意需要离散化，且这个离散化和掉进兔子洞那题差不多，对于相同的值离散化之后的值应该是不同的，这样我们直接倒序遍历，然后维护一个指针，指向第一个满足 $a_i<i$$a_i \lt i$ 的，求个距离即为答案。

Code

xxxxxxxxxx
62
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[110000];
28
vector < int > data;
29
int tim[110000];
30
int cnt[110000];
31

32
int main(){
33
    N = read();
34
    for(int i = 1; i <= N; ++i)data.emplace_back(a[i] = read());
35
    sort(data.begin(), data.end()); //data.erase(unique(data.begin(), data.end()), data.end());
36
    for(int i = 1; i <= N; ++i)a[i] = distance(data.begin(), lower_bound(data.begin(), data.end(), a[i]) + 1), a[i] += cnt[a[i]]++;
37
    int lst(N);
38
    for(int i = N; i >= 1; --i){
39
        while(a[lst] > i)--lst;
40
        tim[i] = max(lst - i, 1);
41
    }ll ans(0);
42
    for(int i = 1; i <= N; ++i)ans += max(tim[i - 1], tim[i]);
43
    printf("%lld\n", ans);
44
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
45
    return 0;
46
}
47

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

LG-P4374 [USACO18OPEN]Disruption P

题面

给定一棵 $n$$n$ 节点无权树，额外地，给定 $m$$m$ 条有权无向边，连结在 $n$$n$ 个节点之间。对于原始的树上 $n-1$$n - 1$ 条边的每一条，求出若删去这条边，添加 $m$$m$ 条额外边的哪一条可以在使树再次连通的基础上最小化权值，求该权值。

$2\le n,m\le 5\times {10}^4$$2 \le n, m \le 5 \times 10^4$。

Examples

Input_1

xxxxxxxxxx
9
1
6 3
2
1 2
3
1 3
4
4 1
5
4 5
6
6 5
7
2 3 7
8
3 6 8
9
6 4 5

Output_1

xxxxxxxxxx
5
1
7
2
7
3
8
4
5
5
5

Solution

依然在题解里先偷个图。。

显然考虑对于我们每一条连的额外边，如 $5⟺12$$5 \Longleftrightarrow 12$，显然只会对树上两点之间的路径上的边产生贡献，这个比较容易想吧。。随便画一下就好，比如显然如果把原树上非该路径上的边删掉，即使连上这条额外边也无济于事。然后对于某一条原树边，显然答案就是所有贡献取个 $min$$\min$。说到这一个最显而易见的做法已经出来了，树剖转成序列，然后线段树上求区间 $min$$\min$。

然后我们发现，如果把额外边降序排序，显然后面的边更优，那么每次操作实际上就是覆盖原来的值，那么这东西很显然就是个 assign，而且只有 assign 没有任何其它操作，所以可以考虑直接上个 树剖 + ODT 即可，理论上对于只有 assign 的操作 ODT 应该更快，但是可能常数太大了，所以最终表现似乎不如线段树？

然后在此之上，我们又可以想到一个做法，把额外边升序排列，这样前面的一定更优，打个标记，对于已经更新过的不去更新即可，然后用倍增或者 Tarjan 直接的求 LCA 找树上路径之类的，可以省掉一个树剖。

Code

xxxxxxxxxx
153
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
    int idx;
30
    OPNEW;
31
}ed[110000];
32
ROPNEW(ed);
33
Edge* head[51000];
34

35
int ans[51000], nod_idx[51000];
36

37
int N, M;
38
int dep[51000], dfn[51000], idx[51000], top[51000], siz[51000], fa[51000], hson[51000];
39

40
struct Node{
41
    int l, r;
42
    mutable int val;
43
    friend const bool operator < (const Node &a, const Node &b){
44
        return a.l < b.l;
45
    }
46
};
47

48
class ODT{
49
private:
50
    set < Node > tr;
51
public:
52
    auto Insert(Node x){return tr.insert(x);}
53
    auto Split(int p){
54
        auto it = tr.lower_bound(Node{p});
55
        if(it != tr.end() && it->l == p)return it;
56
        --it;
57
        // printf("%d %d %d\n", it->l, it->r, it->val);
58
        int l = it->l, r = it->r, v = it->val;
59
        tr.erase(it), Insert(Node{l, p - 1, v});
60
        return Insert(Node{p, r, v}).first;
61
    }
62
    void Assign(int l, int r, int v){
63
        if(l > r)return;
64
        // printf("assigning %d~%d, %d\n", l, r, v);
65
        auto itR = Split(r + 1), itL = Split(l);
66
        tr.erase(itL, itR);
67
        Insert(Node{l, r, v});
68
    }
69
    void SetAns(void){
70
        for(auto nod : tr)
71
            for(int i = nod.l; i <= nod.r; ++i)
72
                ans[nod_idx[idx[i]]] = nod.val;
73
    }
74
}odt;
75

76
struct Edges{
77
    int s, t;
78
    int val;
79
    friend const bool operator < (const Edges &a, const Edges &b){
80
        return a.val > b.val;
81
    }
82
};
83
vector < Edges > es;
84

85
void dfs_pre(int p = 1, int ffa = 0){
86
    fa[p] = ffa;
87
    dep[p] = dep[ffa] + 1;
88
    siz[p] = 1;
89
    for(auto i = head[p]; i; i = i->nxt){
90
        if(SON == ffa)continue;
91
        nod_idx[SON] = i->idx;
92
        dfs_pre(SON, p);
93
        siz[p] += siz[SON];
94
        if(siz[SON] > siz[hson[p]])hson[p] = SON;
95
    }
96
}
97
void dfs(int p = 1, int tp = 1){
98
    static int cdfn(0);
99
    top[p] = tp;
100
    dfn[p] = ++cdfn;
101
    idx[cdfn] = p;
102
    if(hson[p])dfs(hson[p], tp);
103
    for(auto i = head[p]; i; i = i->nxt){
104
        if(SON == fa[p] || SON == hson[p])continue;
105
        dfs(SON, SON);
106
    }
107
}
108

109
void AssignRange(int s, int t, int val){
110
    while(top[s] != top[t]){
111
        if(dep[top[s]] < dep[top[t]])swap(s, t);
112
        odt.Assign(dfn[top[s]], dfn[s], val);
113
        s = fa[top[s]];
114
    }if(dep[s] < dep[t])swap(s, t);
115
    odt.Assign(dfn[t] + 1, dfn[s], val);
116
}
117

118
int main(){
119
    N = read(), M = read();
120
    for(int i = 1; i <= N - 1; ++i){
121
        int s = read(), t = read();
122
        head[s] = new Edge{head[s], t, i};
123
        head[t] = new Edge{head[t], s, i};
124
    }dfs_pre(), dfs();
125
    // for(int i = 1; i <= N; ++i)printf("[%d]: dfn: %d, fa: %d, dep: %d, top: %d, hson: %d\n", i, dfn[i], fa[i], dep[i], top[i], hson[i]);
126
    // for(int i = 1; i <= N; ++i)printf("nodidx[%d]: %d\n", i, nod_idx[i]);
127
    odt.Insert(Node{1, N, -1});
128
    for(int i = 1; i <= M; ++i){
129
        int s = read(), t = read(), v = read();
130
        es.emplace_back(Edges{s, t, v});
131
    }sort(es.begin(), es.end());
132
    for(auto e : es)AssignRange(e.s, e.t, e.val);
133
    odt.SetAns();
134
    for(int i = 1; i <= N - 1; ++i)printf("%d\n", ans[i]);
135
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
136
    return 0;
137
}
138

139
template < typename T >
140
inline T read(void){
141
    T ret(0);
142
    int flag(1);
143
    char c = getchar();
144
    while(c != '-' && !isdigit(c))c = getchar();
145
    if(c == '-')flag = -1, c = getchar();
146
    while(isdigit(c)){
147
        ret *= 10;
148
        ret += int(c - '0');
149
        c = getchar();
150
    }
151
    ret *= flag;
152
    return ret;
153
}