标签：return int 题解 void ret getchar 2017 Dec define

USACO 2017 Dec Solution

目录

• USACO 2017 Dec Solution
  • 更好的阅读体验戳此进入
  • 题面 Luogu 链接
  • LG-P4122 [USACO17DEC]Blocked Billboard B
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4089 [USACO17DEC]The Bovine Shuffle S
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4087 [USACO17DEC]Milk Measurement S
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4086 [USACO17DEC]My Cow Ate My Homework S
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4083 [USACO17DEC]A Pie for a Pie G
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4084 [USACO17DEC]Barn Painting G
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4085 [USACO17DEC]Haybale Feast G
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4090 [USACO17DEC]Greedy Gift Takers P
    • 题面
    • Examples
    • Solution
    • Code
  • LG-P4081 [USACO17DEC]Standing Out from the Herd P
    • 题面
  • LG-P4082 [USACO17DEC]Push a Box P
    • 题面
    • Examples
    • Solution
    • Code
  • UPD

更好的阅读体验戳此进入

题面 Luogu 链接

LG-P4122 [USACO17DEC]Blocked Billboard B

题面

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

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

Examples

Input_1

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

Output_1

17

Solution

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int v[4][5];
int ans(0);
int main(){
    for(int i = 1; i <= 3; ++i)for(int j = 1; j <= 4; ++j)v[i][j] = read();
    #define JGx(id, x, y) (v[id][1] <= x && x < v[id][3] && v[id][2] <= y && y < v[id][4])
    for(int i = -1000; i <= 1000; ++i)
        for(int j = -1000; j <= 1000; ++j)
            if((JGx(1, i, j) || JGx(2, i, j)) && !JGx(3, i, j))++ans;
    printf("%d\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4089 [USACO17DEC]The Bovine Shuffle S

题面

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

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

Examples

Input_1

4
3 2 1 3

Output_1

3

Solution

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
int cnt(0);
int to[110000];
bool vis[110000];
class UnionFind{
private:
    int fa[110000];
    int dis[110000];
public:
    UnionFind(void){for(int i = 1; i <= 101000; ++i)fa[i] = i, dis[i] = 0;}
    int Find(int x){return x == fa[x] ? x : fa[x] = Find(fa[x]);}
    int GetDis(int x){return dis[x];};
    void Union(int origin, int son){fa[son] = Find(origin);}
}uf;
int main(){
    N = read();
    for(int i = 1; i <= N; ++i){
        to[i] = read();
        if(uf.Find(to[i]) == i){
            int cur(to[i]);
            while(cur != i)++cnt, cur = to[cur];
            ++cnt;
        }else uf.Union(to[i], i);
    }
    printf("%d\n", cnt);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4087 [USACO17DEC]Milk Measurement S

题面

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

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

$ n, g $

$ d_1, n_1, c_1 $

$ d_2, n_2, c_2 $

$ \cdots $

$ d_n, n_n, c_n $

Examples

Input_1

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

Output_1

3

Solution

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

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

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N, G;
ll cur[110000];
struct Node{
    int date, num, delt;
    friend const bool operator < (const Node &x, const Node &y){return x.date < y.date;}
};
vector < Node > notes;
multiset < ll > milk;
vector < int > vals;
int main(){
    N = read(), G = read();
    for(int i = 1; i <= N; ++i){
        int d = read(), n = read(), del = read();
        if(del == 0){--N, --i; continue;}
        notes.emplace_back(Node{d, n, del});
        milk.insert(G);
        cur[i] = G;
        vals.emplace_back(n);
    }sort(notes.begin(), notes.end());
    sort(vals.begin(), vals.end());
    milk.insert(G);
    int cnt(0);
    for(auto &x : notes){
        x.num = distance(vals.begin(), upper_bound(vals.begin(), vals.end(), x.num));
        bool mvbst(false), insbst(false), mulbst(false);
        if(cur[x.num] == *prev(milk.end()))mvbst = true;
        if((int)milk.size() >= 2 && *prev(milk.end()) == *prev(milk.end(), 2))mulbst = true;
        milk.erase(milk.lower_bound(cur[x.num]));
        cur[x.num] += x.delt;
        if(cur[x.num] >= *prev(milk.end()))insbst = true;
        milk.insert(milk.upper_bound(cur[x.num]), cur[x.num]);
        if((int)milk.size() >= 2 && *prev(milk.end()) == *prev(milk.end(), 2))mulbst = true;
        if((mvbst && !insbst) || (!mvbst && insbst) || (mvbst && insbst && mulbst))++cnt;
    }printf("%d\n", cnt);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4086 [USACO17DEC]My Cow Ate My Homework S

题面

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

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

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

Examples

Input_1

5
3 1 9 2 7

Output_1

2

Solution

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define EPS (double)(1e-8)

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

int N;
int a[110000];
int sum[110000];
int smin[110000];

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)a[i] = read();
    smin[N + 1] = INT_MAX;
    for(int i = N; i >= 1; --i)
        sum[i] = sum[i + 1] + a[i], smin[i] = min(smin[i + 1], a[i]);
    double mx(-1.0);
    vector < int > mxk;
    for(int k = 1; k <= N - 2; ++k){
        double val = double(sum[k + 1] - smin[k + 1]) / double(N - k - 1);
        if(abs(val - mx) <= EPS)mxk.emplace_back(k);
        else if(val > mx){mx = val, mxk.clear(), mxk.emplace_back(k);}
    }for(auto K : mxk)printf("%d\n", K);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

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

题面

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

馅饼不能被重复赠送。

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

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

$ n, d $

$ a_1, b_1 $

$ a_2, b_2 $

$ \cdots $

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

Examples

Input_1

2 1
1 1
5 0
4 2
1 4

Output_1

3
1

Solution

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

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

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

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MAXN (110000)
#define MAXN2 (MAXN << 1)
#define MAXN4 (MAXN << 2)
#define MAXN8 (MAXN << 3)

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

struct Edge{
    Edge* nxt;
    int to;
    bool val;
    OPNEW;
}ed[MAXN8 << 1];
ROPNEW(ed);
Edge* head[MAXN8];

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

int leaf[MAXN2];
int N, D;
#define N2 (N << 1)
Node val[MAXN2];
Node A[MAXN], B[MAXN];
int dis[MAXN8];
int ans[MAXN4];

class SegTree{
#define MID ((gl + gr) >> 1)
#define LS (p << 1)
#define RS (LS | 1)
private:
public:
    void Build(int p = 1, int gl = 1, int gr = N2){
        if(gl == gr)return leaf[gl = gr] = p, void();
        Build(LS, gl, MID), Build(RS, MID + 1, gr);
        head[p] = new Edge{head[p], LS, 0};
        head[p] = new Edge{head[p], RS, 0};
    }
    void Connect(int ori, int l, int r, int p = 1, int gl = 1, int gr = N2){
        if(l > r)return;
        if(l <= gl && gr <= r)return head[ori] = new Edge{head[ori], p, 1}, void();
        if(l <= MID)Connect(ori, l, r, LS, gl, MID);
        if(MID + 1 <= r)Connect(ori, l, r, RS, MID + 1, gr);
    }
}st;
void bfs(void){
    memset(dis, 0x3f, sizeof dis);
    deque < int > dq;
    for(int i = 1; i <= N2; ++i)
        if((!val[i].a && i >= N + 1) || (!val[i].b && i <= N))
            dis[leaf[i]] = 1, dq.push_back(leaf[i]);
    while(!dq.empty()){
        int tp = dq.front(); dq.pop_front();
        for(auto i = head[tp]; i; i = i->nxt)
            if(dis[tp] + i->val < dis[SON]){
                dis[SON] = dis[tp] + i->val;
                i->val ? dq.push_back(SON) : dq.push_front(SON);
            }
    }
    for(int i = 1; i <= N2; ++i)ans[val[i].idx] = dis[leaf[i]];
}
int main(){
    // freopen("P4083_5.in", "r", stdin);
    #define CMP_SECOND [](Node x, Node y)->bool{return x.b < y.b;}
    #define CMP_FIRST [](Node x, Node y)->bool{return x.a < y.a;}
    N = read(), D = read(); st.Build();
    for(int i = 1; i <= N; ++i)A[i].a = read(), A[i].b = read(), A[i].idx = i;
    for(int i = 1; i <= N; ++i)B[i].a = read(), B[i].b = read(), B[i].idx = i + N;
    sort(A + 1, A + N + 1, CMP_SECOND);
    sort(B + 1, B + N + 1, CMP_FIRST);
    for(int i = 1; i <= N; ++i)val[i] = A[i], val[i + N] = B[i];
    // for(int i = 1; i <= N2; ++i)printf("VAL %d : %d | %d | %d\n", i, val[i].a, val[i].b, val[i].idx);
    for(int i = 1; i <= N; ++i){
        int ptl = distance(B + 1, lower_bound(B + 1, B + N + 1, Node{A[i].a - D, 0, 0}, CMP_FIRST) + 1);
        int ptr = distance(B + 1, upper_bound(B + 1, B + N + 1, Node{A[i].a, 0, 0}, CMP_FIRST));
        st.Connect(leaf[i], ptl + N, ptr + N);
        ptl = distance(A + 1, lower_bound(A + 1, A + N + 1, Node{0, B[i].b - D, 0}, CMP_SECOND) + 1);
        ptr = distance(A + 1, upper_bound(A + 1, A + N + 1, Node{0, B[i].b, 0}, CMP_SECOND));
        st.Connect(leaf[i + N], ptl, ptr);
    }bfs();
    for(int i = 1; i <= N; ++i)printf("%d\n", ans[i] == 0x3f3f3f3f ? -1 : ans[i]);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4084 [USACO17DEC]Barn Painting G

题面

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

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

Examples

Input_1

4 1
1 2
1 3
1 4
4 3

Output_1

8

Solution

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

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

#define MOD (int)(1e9 + 7)

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

int N, K;
struct Edge{
    Edge* nxt;
    int to;
    OPNEW;
}ed[210000];
ROPNEW(ed);
Edge* head[110000];
int dp[110000][4];

void dfs(int p = 1, int fa = 0){
    for(auto i = head[p]; i; i = i->nxt){
        if(SON == fa)continue;
        dfs(SON, p);
        dp[p][1] = ((ll)dp[p][1] * ((ll)dp[SON][2] + dp[SON][3])) % MOD;
        dp[p][2] = ((ll)dp[p][2] * ((ll)dp[SON][1] + dp[SON][3])) % MOD;
        dp[p][3] = ((ll)dp[p][3] * ((ll)dp[SON][1] + dp[SON][2])) % MOD;
    }
}

int main(){
    N = read(), K = read();
    for(int i = 1; i <= N - 1; ++i){
        int s = read(), t = read();
        head[s] = new Edge{head[s], t};
        head[t] = new Edge{head[t], s};
    }
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= 3; ++j)dp[i][j] = 1;
    for(int i = 1; i <= K; ++i){
        int p = read(), c = read();
        for(int j = 1; j <= 3; ++j)if(j != c)dp[p][j] = 0;
    }dfs();
    printf("%lld\n", ((ll)dp[1][1] + dp[1][2] + dp[1][3]) % MOD);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4085 [USACO17DEC]Haybale Feast G

题面

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

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

Examples

Input_1

5 10
4 10
6 15
3 5
4 9
3 6

Output_1

9

Solution

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

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

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

复杂度 $ O(n \log \max_{k = i}^jS_k) $。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
ll M;
int F[110000], S[110000];

bool Check(int lim){
    ll sum(0);
    for(int i = 1; i <= N; ++i){
        if(S[i] > lim){sum = 0; continue;}
        sum += F[i];
        if(sum >= M)return true;
    }return false;
}

int main(){
    N = read(), M = read < ll >();
    int mx(-1);
    for(int i = 1; i <= N; ++i)F[i] = read(), S[i] = read(), mx = max(mx, S[i]);
    int l = 1, r = mx, ans(-1);
    while(l <= r){
        int mid((l + r) >> 1);
        if(Check(mid))ans = mid, r = mid - 1;
        else l = mid + 1;
    }printf("%d\n", ans);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

LG-P4090 [USACO17DEC]Greedy Gift Takers P

题面

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

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

Examples

Input_1

3
1 2 0

Output_1

1

Solution

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

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

int N;
int c[110000];

bool Check(int pos){
    std::priority_queue < int, vector < int >, greater < int > > q;
    for(int i = 1; i < pos; ++i)q.push(c[i]);
    int cur(N - pos);
    while(!q.empty()){
        int tp = q.top(); q.pop();
        if(tp > cur)return false;
        else ++cur;
    }return true;
}

int main(){
    N = read();
    for(int i = 1; i <= N; ++i)c[i] = read();
    int l = 1, r = N, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(!Check(mid))ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    printf("%d\n", N - ans + 1);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

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

题面

SAM 和 SA，跳！

LG-P4082 [USACO17DEC]Push a Box P

题面

这场里最有意思的题来了

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

Examples

Input_1

5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3

Output_1

NO
YES
NO
NO

Solution

似乎是一道显然的圆方树（不会），但是圆方树看着太不联赛了，于是我们考虑把圆方树的思想换一种说法，这道题就和圆方树“没有关系”了。

bfs 会吧，tarjan 点双缩点会吧，好的现在你会圆方树了。

我们发现如果没有这个 nt 的箱子，这题就能变成无脑 bfs 了，但是这个破箱子每个时候都会阻挡一些道路让我们能走的位置变化，仔细思考一下发现这个东西似乎有点像割点，也就是一个障碍物让本来可以走的路径变得不能走了（所以这是正常人能联想到的吗。。

所以我们考虑当我们在一个箱子相邻的四个位置时，想让一个箱子被推动的时候，比如我们想让箱子向上移动一格，那么我们要么在最初在箱子的下面，要么在上左右且在有这个箱子阻挡的情况下可以从对应位置到箱子下面，所以我们此时可以使用人类智慧考虑一个 DP 状态，令 $ dp(x, y, dir) $ 表示箱子在 $ (x, y) $ 且人在箱子的 $ dir $ 方向是否可行，这样的转移也不难想到就是从相邻的四个点的不变向推过来，或有进行变向的路径的情况下通过移动改变所在的箱子的位置。

显然当你从箱子四个方向相邻的某个位置到另一个相邻箱子四个方向的位置的时候一定有一条路径是通过箱子直接过去的，但是这条路径已经被堵死了，我们要求的就是是否还存在另一条可行的路径，然后这玩意你嗯跑肯定过不去，所以发挥人类智慧之后不难想到这东西可以转化为两点之间有至少两条无重点的简单路径，这东西不就是点双吗。

于是我们考虑给这图进行点双缩点（建图不难想到吧，每个方格向四个方向建边，当然不用真正建出来），然后记录每个点都在哪些点双里，开个 vector 就行，每次判断暴力枚举一遍两个点是否有相同的点双，有的话就说明两点在同一点双里，有两个或以上的路径，去掉箱子占用的一条依然可以转移。

对于最初，显然我们很有可能离箱子很远，这个时候我们可以跑一遍无脑的 bfs，记录一下能够到达箱子四个方向的哪几个方向，并以此为 DP 的边界，然后跑一下 Tarjan点双缩点，最后的 DP 过程可以通过一个类似记忆化搜索的宽搜实现，也就是从箱子的四个方向的状态向其它点扩展，具体转移之前已经说过了。

然后还有一个坑，就是有可能最初我们根本无法到达箱子周围，这样我们会全部输出 NO，但是如果某次询问恰好是箱子原本的位置这个东西也应该是可行的，所以特判一下就好。

然后注意精细实现，如果写的比较丑的话码量会额外大很多，写的不是特别丑的话 5KiB 左右就够了。

Code

#define _USE_MATH_DEFINES
#include <bits/extc++.h>

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

using namespace std;
using namespace __gnu_pbds;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;
typedef long double ld;

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

struct Coord{
    int x, y;
    friend const bool operator == (const Coord &a, const Coord &b){return a.x == b.x && a.y == b.y;}
};
int N, M, Q;
Coord S, T;
char mp[1600][1600];
int dx[10] = {0,  -1, 0, 1, 0};
int dy[10] = {0,  0, 1, 0, -1};
bool dire[10];
bool vis[1600][1600];
bool reach[1600][1600][5];
int dfn[1600][1600], low[1600][1600];
bool inS[1600][1600];
vector < int > belong[1600][1600];
int cnt(0), BCC(0);
#define CHECK(x, y) (1 <= x && x <= N && 1 <= y && y <= M)

void bfs_pre(void){
    queue < Coord > cur; cur.push(S); vis[S.x][S.y] = true;
    while(!cur.empty()){
        auto tp = cur.front(); cur.pop();
        for(int i = 1; i <= 4; ++i){
            int tx(tp.x + dx[i]), ty(tp.y + dy[i]);
            if(CHECK(tx, ty) && !vis[tx][ty] && mp[tx][ty] ^ '#' && mp[tx][ty] ^ 'B'){
                vis[tx][ty] = true;
                for(int j = 1; j <= 4; ++j)
                    if(tx == T.x + dx[j] && ty == T.y + dy[j])dire[j] = true;
                cur.push(Coord{tx, ty});
            }
            if(dire[1] && dire[2] && dire[3] && dire[4])return;
        }
    }
}

void Tarjan(int x, int y){
    static stack < Coord > cur;
    dfn[x][y] = low[x][y] = ++cnt;
    cur.push(Coord{x, y}); inS[x][y] = true;
    for(int i = 1; i <= 4; ++i){
        int tx(x + dx[i]), ty(y + dy[i]);
        if(!CHECK(tx, ty) || mp[tx][ty] == '#')continue;
        if(!dfn[tx][ty]){
            Tarjan(tx, ty);
            low[x][y] = min(low[x][y], low[tx][ty]);
            if(low[tx][ty] >= dfn[x][y]){
                ++BCC;
                while(true){
                    auto tp = cur.top(); cur.pop();
                    belong[tp.x][tp.y].emplace_back(BCC);
                    inS[tp.x][tp.y] = false;
                    if(tp == Coord{tx, ty})break;
                }belong[x][y].emplace_back(BCC);
            }
        }else if(inS[tx][ty])
            low[x][y] = min(low[x][y], dfn[tx][ty]);
    }
}
bool InSameBSS(Coord A, Coord B){
    for(auto i : belong[A.x][A.y])
        for(auto j : belong[B.x][B.y])
            if(i == j)return true;
    return false;
}
struct Status{int x, y; int dire;};
#define OPPOSITE(x) (x <= 2 ? x + 2 : x - 2)
void bfs(void){
    queue < Status > cur;
    for(int i = 1; i <= 4; ++i)if(dire[i])cur.push(Status{T.x, T.y, i}), reach[T.x][T.y][i] = true;
    while(!cur.empty()){
        auto tp = cur.front(); cur.pop();
        for(int i = 1; i <= 4; ++i){
            int tx(tp.x + dx[i]), ty(tp.y + dy[i]);
            if(
                CHECK(tx, ty) &&
                mp[tx][ty] ^ '#' &&
                (
                    OPPOSITE(i) == tp.dire ||
                    InSameBSS(
                        Coord{tp.x + dx[tp.dire], tp.y + dy[tp.dire]},
                        Coord{tp.x + dx[OPPOSITE(i)], tp.y + dy[OPPOSITE(i)]}
                    )
                ) &&
                !reach[tx][ty][OPPOSITE(i)]
            ){
                reach[tx][ty][OPPOSITE(i)] = true;
                cur.push(Status{tx, ty, OPPOSITE(i)});
            }
        }
    }
}

int main(){
    N = read(), M = read(), Q = read();
    char c = getchar();
    for(int i = 1; i <= N; ++i)for(int j = 1; j <= M; ++j){
        while(c != '#' && c != '.' && c != 'A' && c != 'B')c = getchar();
        mp[i][j] = c;
        if(mp[i][j] == 'A')S = Coord{i, j};
        if(mp[i][j] == 'B')T = Coord{i, j};
        c = getchar();
    }bfs_pre();
    Tarjan(S.x, S.y);
    bfs();
    while(Q--){
        int x = read(), y = read();
        if(Coord{x, y} == T){printf("YES\n"); continue;}
        printf("%s\n", (reach[x][y][1] || reach[x][y][2] || reach[x][y][3] || reach[x][y][4]) ? "YES" : "NO");
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template < typename T >
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

UPD

update-2022_11_02 初稿

标签：return,int,题解,void,ret,getchar,2017,Dec,define
From： https://www.cnblogs.com/tsawke/p/16945798.html