USACO 2017 Dec Solution

更好的阅读体验戳此进入

题面 Luogu 链接

LG-P4122 [USACO17DEC]Blocked Billboard B

题面

给定不交的两个矩形的左下和右上坐标，再给定第三个矩形的左下右上坐标，求两个矩形的没有被第三个矩形所覆盖的面积。

坐标均在 $[-{10}^3,{10}^3]$$[-10^3, 10^3]$ 范围内。

Examples

Input_1

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

Output_1

1
1
17

Solution

水题，但是也可以想一下如何更好实现，可以直接枚举范围内所有点的坐标然后判断，这样会比嗯讨论点之间的位置方便得多，注意判断 $x_1,x_2$$x_1, x_2$ 之间的值的时候应该是 $[x1,x2)$$[x1, x2)$ 的。

Code

53
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 v[4][5];
27
int ans(0);
28
int main(){
29
    for(int i = 1; i <= 3; ++i)for(int j = 1; j <= 4; ++j)v[i][j] = read();
30
    #define JGx(id, x, y) (v[id][1] <= x && x < v[id][3] && v[id][2] <= y && y < v[id][4])
31
    for(int i = -1000; i <= 1000; ++i)
32
        for(int j = -1000; j <= 1000; ++j)
33
            if((JGx(1, i, j) || JGx(2, i, j)) && !JGx(3, i, j))++ans;
34
    printf("%d\n", ans);
35
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
36
    return 0;
37
}
38

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

LG-P4089 [USACO17DEC]The Bovine Shuffle S

题面

给定 $n$$n$ 和序列 $a_n$$a_n$，初始每个位置各有一只犇，每次操作后位置 $i$$i$ 的牛会到 $a_i$$a_i$，显然最终一定会有 $k$$k$ 个位置始终有犇存在，求 $k$$k$。

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

Examples

Input_1

2
1
4
2
3 2 1 3

Output_1

1
1
3

Solution

一道水题，画画图就不难想到这玩意实际上是内向树再加一条外向边，可以认为其为一个奇怪的有向的基环树森林，然后我们要求的就是每个环长求和。这个不难理解，我们发现内向树上所有节点最终都会汇集到根节点上，然后根节点出去的外向边，也就是形成的这个环路，每个点一定一直都有犇，所以 $i\to a_i$$i \rightarrow a_i$ 建图，算一下环长和就行。

至于实现拓扑排序可能比较短，或者 dfs 也行，所以我写的并查集。

Code

69
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 cnt(0);
28
int to[110000];
29
bool vis[110000];
30
class UnionFind{
31
private:
32
    int fa[110000];
33
    int dis[110000];
34
public:
35
    UnionFind(void){for(int i = 1; i <= 101000; ++i)fa[i] = i, dis[i] = 0;}
36
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
37
    int GetDis(int x){return dis[x];};
38
    void Union(int origin, int son){fa[son] = Find(origin);}
39
}uf;
40
int main(){
41
    N = read();
42
    for(int i = 1; i <= N; ++i){
43
        to[i] = read();
44
        if(uf.Find(to[i]) == i){
45
            int cur(to[i]);
46
            while(cur != i)++cnt, cur = to[cur];
47
            ++cnt;
48
        }else uf.Union(to[i], i);
49
    }
50
    printf("%d\n", cnt);
51
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
52
    return 0;
53
}
54

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

LG-P4087 [USACO17DEC]Milk Measurement S

题面

llq 有一大群 OIer，每个 OIer 都有相同的初始日做题量 $g$$g$，显然 OIer 们的日做题数可能会变化，llq 在他的神秘笔记本上记录了 $N$$N$ 条不保证有序的记录，每个记录三个数，分别表示日期 $d$$d$，OIer 编号 $n$$n$，变化量 $c$$c$，表示 $n$$n$ 在 $d$$d$ 的时候增加 / 减少了 $c$$c$，llq 每天都要记录所有日做题量最高的 OIer，如果有多人并列最高，那么都会被记录（只记录人，不记录具体数值），求在整段时间内 llq 的记录的变化次数。

$1\le N\le {10}^5,1\le d\le {10}^6,1\le n\le {10}^9$$1 \le N \le 10^5, 1 \le d \le 10^6, 1 \le n \le 10^9$。保证每只 OIer 任何时刻日做题量都不大于 ${10}^9$$10^9$。

$n,g$$n, g$

$d_1,n_1,c_1$$d_1, n_1, c_1$

$d_2,n_2,c_2$$d_2, n_2, c_2$

$\cdots$$\cdots$

$d_n,n_n,c_n$$d_n, n_n, c_n$

Examples

Input_1

5
1
4 10
2
7 3 +3
3
4 2 -1
4
9 3 -1
5
1 1 +2

Output_1

1
1
3

Solution

离散化不难想到吧，然后按照日期排序不难想到吧。

这样之后就更不难想到线段树维护了，单点修改，区间（整个区间）查询，比一般线段树都好写，也不用 lazytag。

不过我不想写线段树线段树看着不好看，所以考虑无脑模拟一下，离散化后，排序之后，开个 vector 插入所有的 OIer 的做题量（也就是原题犇的产奶量），然后额外开个数组对应着记录每个 OIer 的做题量，每次修改就是在静态数组里找对应做题量然后从 vector 中删除后修改值再插入回去，中间判断一下最优值或其的数量是否有变化，有变化就 ++cnt 即可。

然后发现因为 vector 的 erase 和 insert 之类的都是 $O(n)$$O(n)$ 的，所以这玩意会退化成 $O(n^2)$$O(n^2)$，于是把 vector 变成 multiset，这样最终复杂度 $O(n\log n)$$O(n \log n)$ 可以通过。

然后注意我们离散化之后应该还有大量的没有修改过的 OIer（犇），他们始终保持着原来的量，所以我们还需要额外加一个数值为原来的初始值并不改变即可。

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, G;
27
ll cur[110000];
28
struct Node{
29
    int date, num, delt;
30
    friend const bool operator < (const Node &x, const Node &y){return x.date < y.date;}
31
};
32
vector < Node > notes;
33
multiset < ll > milk;
34
vector < int > vals;
35
int main(){
36
    N = read(), G = read();
37
    for(int i = 1; i <= N; ++i){
38
        int d = read(), n = read(), del = read();
39
        if(del == 0){--N, --i; continue;}
40
        notes.emplace_back(Node{d, n, del});
41
        milk.insert(G);
42
        cur[i] = G;
43
        vals.emplace_back(n);
44
    }sort(notes.begin(), notes.end());
45
    sort(vals.begin(), vals.end());
46
    milk.insert(G);
47
    int cnt(0);
48
    for(auto &x : notes){
49
        x.num = distance(vals.begin(), upper_bound(vals.begin(), vals.end(), x.num));
50
        bool mvbst(false), insbst(false), mulbst(false);
51
        if(cur[x.num] == *prev(milk.end()))mvbst = true;
52
        if((int)milk.size() >= 2 && *prev(milk.end()) == *prev(milk.end(), 2))mulbst = true;
53
        milk.erase(milk.lower_bound(cur[x.num]));
54
        cur[x.num] += x.delt;
55
        if(cur[x.num] >= *prev(milk.end()))insbst = true;
56
        milk.insert(milk.upper_bound(cur[x.num]), cur[x.num]);
57
        if((int)milk.size() >= 2 && *prev(milk.end()) == *prev(milk.end(), 2))mulbst = true;
58
        if((mvbst && !insbst) || (!mvbst && insbst) || (mvbst && insbst && mulbst))++cnt;
59
    }printf("%d\n", cnt);
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-P4086 [USACO17DEC]My Cow Ate My Homework S

题面

这题你们读完应该就切掉了吧。。

给定长度为 $n$$n$ 的序列 $a_n$$a_n$，你可以去掉序列的前 $k$$k$ 个数，再去掉剩下的数中最小的一个数，在最后剩下的数中取平均值即为本次答案，要求 $1\le k\le n-2$$1 \le k \le n - 2$，求最大化答案的所有可能的 $k$$k$。

$3\le n\le {10}^5$$3 \le n \le 10^5$。

Examples

Input_1

xxxxxxxxxx
2
1
5
2
3 1 9 2 7

Output_1

xxxxxxxxxx
1
1
2

Solution

随便做一下后缀和和后缀最小值，然后 $O(n)$$O(n)$ 枚举一遍即可。。没啥可说的，注意 $eps$$eps$ 就行。

Code

xxxxxxxxxx
64
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-8)
24

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

28
int N;
29
int a[110000];
30
int sum[110000];
31
int smin[110000];
32

33
int main(){
34
    N = read();
35
    for(int i = 1; i <= N; ++i)a[i] = read();
36
    smin[N + 1] = INT_MAX;
37
    for(int i = N; i >= 1; --i)
38
        sum[i] = sum[i + 1] + a[i], smin[i] = min(smin[i + 1], a[i]);
39
    double mx(-1.0);
40
    vector < int > mxk;
41
    for(int k = 1; k <= N - 2; ++k){
42
        double val = double(sum[k + 1] - smin[k + 1]) / double(N - k - 1);
43
        if(abs(val - mx) <= EPS)mxk.emplace_back(k);
44
        else if(val > mx){mx = val, mxk.clear(), mxk.emplace_back(k);}
45
    }for(auto K : mxk)printf("%d\n", K);
46
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
47
    return 0;
48
}
49

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

LG-P4083 [USACO17DEC]A Pie for a Pie G

题面

sssmzy 和 zpair 各自烤了 $n$$n$ 个馅饼，两人对这 $2n$$2n$ 个馅饼都有各自的评分 $a_i,b_i$$a_i, b_i$，两人会互赠馅饼。初始时 sssmzy 给 zpair 赠送一个馅饼，然后 zpair 进行回礼，sssmzy 再次回礼，如此往复。对于每个人的回礼方式，会根据自己的评分来选择回礼，回礼馅饼的分数必须要大于等于收到的馅饼，且分数差不大于 $d$$d$，若没有符合要求的馅饼了那么为 BE，若其中一人收到了其自己评分为 $0$$0$ 的馅饼那么认为是 HE，对于 sssmzy 的每个馅饼，你需要求出以其为初始时 sssmzy 送的馅饼的时候最少需要多少次赠送才能 HE，如果只能 BE 那么输出 -1。

馅饼不能被重复赠送。

Tips：输入评分时前 $n$$n$ 行为 sssmzy 的馅饼，后 $n$$n$ 行为 zpair 的馅饼。

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

$n,d$$n, d$

$a_1,b_1$$a_1, b_1$

$a_2,b_2$$a_2, b_2$

$\cdots$$\cdots$

$a_{2n},b_{2n}$$a_{2n}, b_{2n}$

Examples

Input_1

xxxxxxxxxx
5
1
2 1
2
1 1
3
5 0
4
4 2
5
1 4

Output_1

xxxxxxxxxx
2
1
3
2
1

Solution

一道神仙线段树优化建图，个人认为是一道很有意思的题，缝合怪，码量大细节多。

首先建图应该很好想到吧？日常正难则反，以 sssmzy 的 zpair 评分为 $0$$0$ 的和放过来为 $0$$0$ 的为起点反着开始取。显然我们每次取完之后，想要找下一个的时候，一定是有一部分点可以选，我们把当前点向可以选的建一条有向边，这个是 $O(n^2)$$O(n^2)$ 的，这样最后直接无脑宽搜 $O(nm)$$O(nm)$ 找最短路，显然这东西时空复杂度都是 $O(n^2)$$O(n^2)$ 的，大寄特寄，于是考虑优化。

不难想到我们可以把 sssmzy 的和 zpair 的分别排个序，不难想到前者的馅饼按照后者的评分排，后者的馅饼按照前者的评分排。这样每次连边一定是连到了对方馅饼的某一段区间，不难想到为 $[a_{i+n}-d,a_{i+n}]$$[a_{i + n} - d, a_{i + n}]$，反之亦然，然后看着一坨坨的区间，很显然就是线段树优化建图。（你们大概都会吧

线段树上每个点向其子节点连个 $0$$0$ 边，然后记录叶子节点的位置，然后每次二分找到要连的区间的左右端点，把对应的叶子节点连上区间的节点，然后这玩意细节巨多。（但是不是很难调

连完之后从每个可行的 $0$$0$ 点开始跑 01BFS，记录一下答案然后最后更新对应的 $idx$$idx$ 即可。

Code

xxxxxxxxxx
123
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 MAXN (110000)
24
#define MAXN2 (MAXN << 1)
25
#define MAXN4 (MAXN << 2)
26
#define MAXN8 (MAXN << 3)
27

28
template< typename T = int >
29
inline T read(void);
30

31
struct Edge{
32
    Edge* nxt;
33
    int to;
34
    bool val;
35
    OPNEW;
36
}ed[MAXN8 << 1];
37
ROPNEW(ed);
38
Edge* head[MAXN8];
39

40
struct Node{int a, b; int idx;};
41

42
int leaf[MAXN2];
43
int N, D;
44
#define N2 (N << 1)
45
Node val[MAXN2];
46
Node A[MAXN], B[MAXN];
47
int dis[MAXN8];
48
int ans[MAXN4];
49

50
class SegTree{
51
#define MID ((gl + gr) >> 1)
52
#define LS (p << 1)
53
#define RS (LS | 1)
54
private:
55
public:
56
    void Build(int p = 1, int gl = 1, int gr = N2){
57
        if(gl == gr)return leaf[gl = gr] = p, void();
58
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
59
        head[p] = new Edge{head[p], LS, 0};
60
        head[p] = new Edge{head[p], RS, 0};
61
    }
62
    void Connect(int ori, int l, int r, int p = 1, int gl = 1, int gr = N2){
63
        if(l > r)return;
64
        if(l <= gl && gr <= r)return head[ori] = new Edge{head[ori], p, 1}, void();
65
        if(l <= MID)Connect(ori, l, r, LS, gl, MID);
66
        if(MID + 1 <= r)Connect(ori, l, r, RS, MID + 1, gr);
67
    }
68
}st;
69
void bfs(void){
70
    memset(dis, 0x3f, sizeof dis);
71
    deque < int > dq;
72
    for(int i = 1; i <= N2; ++i)
73
        if((!val[i].a && i >= N + 1) || (!val[i].b && i <= N))
74
            dis[leaf[i]] = 1, dq.push_back(leaf[i]);
75
    while(!dq.empty()){
76
        int tp = dq.front(); dq.pop_front();
77
        for(auto i = head[tp]; i; i = i->nxt)
78
            if(dis[tp] + i->val < dis[SON]){
79
                dis[SON] = dis[tp] + i->val;
80
                i->val ? dq.push_back(SON) : dq.push_front(SON);
81
            }
82
    }
83
    for(int i = 1; i <= N2; ++i)ans[val[i].idx] = dis[leaf[i]];
84
}
85
int main(){
86
    // freopen("P4083_5.in", "r", stdin);
87
    #define CMP_SECOND [](Node x, Node y)->bool{return x.b < y.b;}
88
    #define CMP_FIRST [](Node x, Node y)->bool{return x.a < y.a;}
89
    N = read(), D = read(); st.Build();
90
    for(int i = 1; i <= N; ++i)A[i].a = read(), A[i].b = read(), A[i].idx = i;
91
    for(int i = 1; i <= N; ++i)B[i].a = read(), B[i].b = read(), B[i].idx = i + N;
92
    sort(A + 1, A + N + 1, CMP_SECOND);
93
    sort(B + 1, B + N + 1, CMP_FIRST);
94
    for(int i = 1; i <= N; ++i)val[i] = A[i], val[i + N] = B[i];
95
    // for(int i = 1; i <= N2; ++i)printf("VAL %d : %d | %d | %d\n", i, val[i].a, val[i].b, val[i].idx);
96
    for(int i = 1; i <= N; ++i){
97
        int ptl = distance(B + 1, lower_bound(B + 1, B + N + 1, Node{A[i].a - D, 0, 0}, CMP_FIRST) + 1);
98
        int ptr = distance(B + 1, upper_bound(B + 1, B + N + 1, Node{A[i].a, 0, 0}, CMP_FIRST));
99
        st.Connect(leaf[i], ptl + N, ptr + N);
100
        ptl = distance(A + 1, lower_bound(A + 1, A + N + 1, Node{0, B[i].b - D, 0}, CMP_SECOND) + 1);
101
        ptr = distance(A + 1, upper_bound(A + 1, A + N + 1, Node{0, B[i].b, 0}, CMP_SECOND));
102
        st.Connect(leaf[i + N], ptl, ptr);
103
    }bfs();
104
    for(int i = 1; i <= N; ++i)printf("%d\n", ans[i] == 0x3f3f3f3f ? -1 : ans[i]);
105
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
106
    return 0;
107
}
108

109
template < typename T >
110
inline T read(void){
111
    T ret(0);
112
    short flag(1);
113
    char c = getchar();
114
    while(c != '-' && !isdigit(c))c = getchar();
115
    if(c == '-')flag = -1, c = getchar();
116
    while(isdigit(c)){
117
        ret *= 10;
118
        ret += int(c - '0');
119
        c = getchar();
120
    }
121
    ret *= flag;
122
    return ret;
123
}

LG-P4084 [USACO17DEC]Barn Painting G

题面

给定 $n$$n$ 个节点的树，需要给每个节点染上三种颜色之一，相邻两个节点颜色不同，已经固定 $k$$k$ 个节点的颜色，求合法染色方案数。

$1\le n\le {10}^5,0\le k\le n$$1 \le n \le 10^5, 0 \le k \le n$。

Examples

Input_1

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

Output_1

xxxxxxxxxx
1
1
8

Solution

经典 树形DP 水题，开始感觉和 COCI 的那个 基环树DP 挺像，但是吧这玩意比那道题要简单得多。

不难想到设 $dp(i,c)$$dp(i, c)$ 为考虑第 $i$$i$ 所在子树，$i$$i$ 点染为 $c$$c$ 的合法方案数，默认所有 $dp(i,c)$$dp(i, c)$ 的初值为 $1$$1$，然后对于每个修改，如果颜色不是 $c$$c$ 那么把对应的 $dp$$dp$ 设为 $0$$0$，然后从根节点搜一遍，转移方程为例如 $dp(i,1)\leftarrow dp(i,1)\times (dp(son(i),2)+dp(son(i),3))$$dp(i, 1) \leftarrow dp(i, 1) \times (dp(son(i), 2) + dp(son(i), 3))$，对于另外两个也同理，随便跑一下就过了。

Code

xxxxxxxxxx
79
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 (int)(1e9 + 7)
24

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

28
int N, K;
29
struct Edge{
30
    Edge* nxt;
31
    int to;
32
    OPNEW;
33
}ed[210000];
34
ROPNEW(ed);
35
Edge* head[110000];
36
int dp[110000][4];
37

38
void dfs(int p = 1, int fa = 0){
39
    for(auto i = head[p]; i; i = i->nxt){
40
        if(SON == fa)continue;
41
        dfs(SON, p);
42
        dp[p][1] = ((ll)dp[p][1] * ((ll)dp[SON][2] + dp[SON][3])) % MOD;
43
        dp[p][2] = ((ll)dp[p][2] * ((ll)dp[SON][1] + dp[SON][3])) % MOD;
44
        dp[p][3] = ((ll)dp[p][3] * ((ll)dp[SON][1] + dp[SON][2])) % MOD;
45
    }
46
}
47

48
int main(){
49
    N = read(), K = read();
50
    for(int i = 1; i <= N - 1; ++i){
51
        int s = read(), t = read();
52
        head[s] = new Edge{head[s], t};
53
        head[t] = new Edge{head[t], s};
54
    }
55
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= 3; ++j)dp[i][j] = 1;
56
    for(int i = 1; i <= K; ++i){
57
        int p = read(), c = read();
58
        for(int j = 1; j <= 3; ++j)if(j != c)dp[p][j] = 0;
59
    }dfs();
60
    printf("%lld\n", ((ll)dp[1][1] + dp[1][2] + dp[1][3]) % MOD);
61
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
62
    return 0;
63
}
64

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

LG-P4085 [USACO17DEC]Haybale Feast G

题面

给定两个长度为 $n$$n$ 的序列 $F_n,S_n$$F_n, S_n$，需要找到使得 $\sum _{k=i}^j{F}_k\ge m$$\sum_{k = i}^jF_k \ge m$ 的 $i,j$$i, j$，并找到所有满足条件的 $i,j$$i, j$ 中，$\underset{i,j}{min}\{\underset{k=i}{\overset{j}{max}}{S}_k\}$$\min_{i, j}\{ \max_{k = i}^jS_k \}$。（不要问我为什么写成这种奇怪的形式，就是最小化区间内 $S$$S$ 的最大值

$1\le n\le {10}^5,1\le m\le {10}^{18},1\le F_i,S_i\le {10}^9$$1 \le n \le 10^5, 1 \le m \le 10^{18}, 1 \le F_i, S_i \le 10^9$。

Examples

Input_1

xxxxxxxxxx
6
1
5 10
2
4 10
3
6 15
4
3 5
5
4 9
6
3 6

Output_1

xxxxxxxxxx
1
1
9

Solution

一道小清新蓝色水题，思维简单代码极短，做起来很舒服。

不难想到二分答案，二分 $\underset{i,j}{min}\{\underset{k=i}{\overset{j}{max}}{S}_k\}$$\min_{i, j}\{ \max_{k = i}^jS_k \}$，可以认为就是给 $S_i$$S_i$ 加了个限制，对于二分的每个答案，遍历一遍 $F$$F$，对于一个新的 $i$$i$ 如果 $S_i>lim$$S_i \gt lim$ 那么把当前的 $sum$$sum$ 变为 $0$$0$，反之 $sum\leftarrow sum+F_i$$sum \leftarrow sum + F_i$，如果 $sum\ge m$$sum \ge m$ 那么直接返回真，全部遍历完之后返回假，特别好写。

当然线段树猫树树状数组之类的东西维护也一样，但是 duck不必。

复杂度 $O(n\log \underset{k=i}{\overset{j}{max}}{S}_k)$$O(n \log \max_{k = i}^jS_k)$。

Code

xxxxxxxxxx
67
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 M;
28
int F[110000], S[110000];
29

30
bool Check(int lim){
31
    ll sum(0);
32
    for(int i = 1; i <= N; ++i){
33
        if(S[i] > lim){sum = 0; continue;}
34
        sum += F[i];
35
        if(sum >= M)return true;
36
    }return false;
37
}
38

39
int main(){
40
    N = read(), M = read < ll >();
41
    int mx(-1);
42
    for(int i = 1; i <= N; ++i)F[i] = read(), S[i] = read(), mx = max(mx, S[i]);
43
    int l = 1, r = mx, ans(-1);
44
    while(l <= r){
45
        int mid((l + r) >> 1);
46
        if(Check(mid))ans = mid, r = mid - 1;
47
        else l = mid + 1;
48
    }printf("%d\n", ans);
49
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
50
    return 0;
51
}
52

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

LG-P4090 [USACO17DEC]Greedy Gift Takers P

题面

给定 $n$$n$ 只犇排成一列，编号 $1$$1$ 到 $n$$n$，给定序列 $c_n$$c_n$，对于每次操作，会将队首的犇 $i$$i$ 变成合法并插入到从队尾开始数第 $c_i$$c_i$ 只犇之前的位置，求经过无限次操作后有几只犇一定不合法。

$1\le n\le {10}^5,0\le c_i\le n-1$$1 \le n \le 10^5, 0 \le c_i \le n - 1$。

Examples

Input_1

xxxxxxxxxx
2
1
3
2
1 2 0

Output_1

xxxxxxxxxx
1
1
1

Solution

还是二分“答案”，显然如果一只犇无法变成合法，那么它之后的所有犇都无法被变成合法的，所以这东西就算是有单调性了，于是我们考虑二分第几只犇是第一个不合法的，然后验证的时候把这只犇前面的所有犇的 $c$$c$ 升序排列，然后判断一下是插在了犇之前还是之后，如果插在之前那么犇一定不会合法，返回假，反之插在之后那么就把验证的犇的位置前移 $1$$1$，都遍历完之后返回真，最终复杂度 $O(n{\log }^{2}n)$$O(n \log^2 n)$，二分一只 $\log$$\log$，排序一只 $\log$$\log$。

Code

xxxxxxxxxx
68
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 c[110000];
28

29
bool Check(int pos){
30
    std::priority_queue < int, vector < int >, greater < int > > q;
31
    for(int i = 1; i < pos; ++i)q.push(c[i]);
32
    int cur(N - pos);
33
    while(!q.empty()){
34
        int tp = q.top(); q.pop();
35
        if(tp > cur)return false;
36
        else ++cur;
37
    }return true;
38
}
39

40
int main(){
41
    N = read();
42
    for(int i = 1; i <= N; ++i)c[i] = read();
43
    int l = 1, r = N, ans = -1;
44
    while(l <= r){
45
        int mid = (l + r) >> 1;
46
        if(!Check(mid))ans = mid, r = mid - 1;
47
        else l = mid + 1;
48
    }
49
    printf("%d\n", N - ans + 1);
50
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
51
    return 0;
52
}
53

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

LG-P4081 [USACO17DEC]Standing Out from the Herd P

题面

SAM 和 SA，跳！

LG-P4082 [USACO17DEC]Push a Box P

题面

这场里最有意思的题来了

给定 $n\times m$$n \times m$ 的网格图，sssmzy 站在其中一个格子里（A），另外一个格子里有个木箱（B），某些格子里是障碍（#），剩下的是空地（.），sssmzy 不能和木箱和障碍在同一个格子内，按照一般的推箱子游戏规则，$q$$q$ 次询问求是否能将箱子推到对应位置。

Examples

Input_1

xxxxxxxxxx
10
1
5 5 4
2
##.##
3
##.##
4
A.B..
5
##.##
6
##.##
7
3 2
8
3 5
9
1 3
10
5 3