牛客小白月赛28

个人博客：http://www.kindkidll.com/index.php/archives/157/

A-牛牛和牛可乐的赌约

知识点：概率计算

求其对立事件的概率。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 100010;

int t;
LL n, m;
LL fast_pow(LL a, LL n) {
    LL ret = 1;
    while(n) {
        if(n & 1) ret = ret * a % mod;
        a = a * a % mod;
        n /= 2;
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &m) ;
        n = fast_pow(n, m);
        printf("%lld\n", (n - 1)*fast_pow(n, mod - 2) % mod);
    }
    return 0;
}

B-牛牛和牛可乐的赌约2

知识点：博弈论

根据必胜态和必败态的关系可得出，当 $x\%3=y\%3$ 时为必败态。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 100010;

int t;
LL n, m;
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &n, &m) ;
        if(n % 3 == m % 3) puts("awsl");
        else puts("yyds");
    }
    return 0;
}

C-单词记忆方法

知识点：模拟

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 100010;

stack<int> st;
int match[MAXN];
char s[MAXN];
int getnum(char c) {
    if(isdigit(c)) return c - '0';
    return c - 'A' + 1;
}
LL solve(int l, int r) {
    LL ret = 0;
    while(l <= r) {
        if(s[l] == '(') {
            LL tmp = solve(l + 1, match[l] - 1);
            l = match[l] + 1;

            LL num = 0;
            while(l <= r && isdigit(s[l])) {
                num = num * 10 + getnum(s[l]);
                l++;
            }

            if(num) ret += tmp * num;
            else ret += tmp;
        } else {
            if(l + 1 <= r && isdigit(s[l + 1])) {
                int tmp = getnum(s[l++]);
                LL num = 0;
                while(l <= r && isdigit(s[l])) {
                    num = num * 10 + getnum(s[l]);
                    l++;
                }
                ret += tmp * num;
            } else ret += getnum(s[l++]);
        }
    }
    return ret;
}
int main() {
    scanf("%s", s);
    int len = strlen(s);
    for(int i = 0; i < len; i++) {
        if(s[i] == '(') st.push(i);
        else if(s[i] == ')') {
            match[st.top()] = i;
            st.pop();
        }
    }
    printf("%lld\n", solve(0, len - 1));
    return 0;
}

D-位运算之谜

知识点：位运算

$a+b=a\,xor\,b+2*(a\,\&\,b)$

不合法情况： $a\,xor\,b<0$ 或 $((a\,xor\,b)\&(a\,\&\,b))!=0$ 。

#include <map>1
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 100010;

int t;
LL x, y;
int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%lld%lld", &x, &y);
        LL ans = x - 2 * y;
        if(ans < 0 || ans & y) puts("-1") ;
        else printf("%lld\n", ans);
    }
    return 0;
}

E-会当凌绝顶，一览众山小

知识点：线段树、二分

将山峰按坐标排序之后使用线段树维护最大值最小值和对应的下标。

对于右边，直接对区间 $[i+1,n]$ 进行查询和修改操作。
对于左边，对区间 $[l,i-1]$ 进行操作，二分求解 $l$ 的值。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int now[MAXN];
struct mountain {
    int id;
    int x, h;
    bool operator <(const mountain &r)const {
        return x < r.x;
    }
} a[MAXN];
///线段树
struct node {
    int l, r;
    int mx, mxid;
    int mn, mnid;
} tree[MAXN];
void to_up(int i) {///更新区间最大值和最小值
    ///同大时取右区间的
    if(tree[i * 2].mx > tree[i * 2 + 1].mx) {
        tree[i].mx = tree[i * 2].mx;
        tree[i].mxid = tree[i * 2].mxid;
    } else {
        tree[i].mx = tree[i * 2 + 1].mx;
        tree[i].mxid = tree[i * 2 + 1].mxid;
    }
    ///同小时取左区间的
    if(tree[i * 2].mn <= tree[i * 2 + 1].mn) {
        tree[i].mn = tree[i * 2].mn;
        tree[i].mnid = tree[i * 2].mnid;
    } else {
        tree[i].mn = tree[i * 2 + 1].mn;
        tree[i].mnid = tree[i * 2 + 1].mnid;
    }
}
void build(int i, int l, int r) {///构建线段树
    tree[i].l = l;
    tree[i].r = r;
    if(l == r) {
        tree[i].mxid = tree[i].mnid = l;
        tree[i].mx = tree[i].mn = a[l].h;
        return;
    }
    int mid = (l + r) / 2;
    build(i * 2, l, mid);
    build(i * 2 + 1, mid + 1, r);
    to_up(i);
}
void update(int i, int p, int x) {///p点的值更新为x
    if(tree[i].l == tree[i].r) {
        tree[i].mx = tree[i].mn = x;
        return;
    }
    int mid = (tree[i].l + tree[i].r) / 2;
    if(p <= mid) update(i * 2, p, x);
    else update(i * 2 + 1, p, x);
    to_up(i);
}
int querymx(int i, int l, int r) {
    ///返回区间最大值的下标
    ///多个最大值返回最右边的
    ///返回0为不合法情况
    if(l > r) return 0;
    if(l <= tree[i].l && tree[i].r <= r) return tree[i].mxid;

    int ret = 0;
    int mid = (tree[i].l + tree[i].r) / 2;
    if(l <= mid) {
        int id = querymx(i * 2, l, r);
        if(ret == 0 || a[id].h > a[ret].h) ret = id;
    }
    if(r > mid) {
        int id = querymx(i * 2 + 1, l, r);
        if(ret == 0 || a[id].h >= a[ret].h) ret = id;
    }
    return ret;
}
int querymn(int i, int l, int r) {
    ///返回区间最小值的下标
    ///多个最小值返回最左边的
    ///返回0为不合法情况
    if(l > r) return 0;
    if(l <= tree[i].l && tree[i].r <= r) return tree[i].mnid;

    int ret = 0;
    int mid = (tree[i].l + tree[i].r) / 2;
    if(l <= mid) {
        int id = querymn(i * 2, l, r);
        if(ret == 0 || a[id].h < a[ret].h) ret = id;
    }
    if(r > mid) {
        int id = querymn(i * 2 + 1, l, r);
        if(ret == 0 || a[id].h < a[ret].h) ret = id;
    }
    return ret;
}
int erfen(int l, int r, int i) {
    while(l <= r) {
        int mid = (l + r) / 2;
        int id = querymx(1, mid, i - 1);
        if(a[id].h > a[i].h) l = mid + 1;
        else r = mid - 1;
    }
    return r;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i].x, &a[i].h);
        a[i].id = i;
    }
    ///按坐标排序并建立排序前后的下标关系
    sort(a + 1, a + n + 1);
    build(1, 1, n);
    for(int i = 1; i <= n; i++) now[a[i].id] = i;

    for(int j = 1; j <= n; j++) {
        int i = now[j];
        ///处理左边
        int id = erfen(1, i - 1, i);
        if(id) {
            a[id].h = a[i].h;
            update(1, id, a[i].h);
        }
        ///处理右边
        id = querymx(1, i + 1, n);
        if(id != 0 && a[id].h <= a[i].h) {
            id = querymn(1, i + 1, n);
            a[id].h = a[i].h;
            update(1, id, a[i].h);
        }
    }
    ///输出最终结果
    for(int i = 1; i <= n; i++) printf("%d ", a[now[i]].h);
    return 0;
}

F-牛牛的健身运动

知识点：三分

将器材两两组合得到所有可能的值，三分天数找到能增加的最大力量值。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 4e6 + 117;
const int MAXM = 4e6 + 117;

int n, tot;
LL m;
LL a[2020], b[2020];
LL aa[MAXN], bb[MAXN];
LL getnum(int k) {
    LL ret = (LL)INF * INF * 4;
    for(int i = 0; i < tot; i++) ret = min(ret, aa[i] * k + bb[i]);
    return ret;
}
LL sanfen(int l, int r) {
    while(l < r) {
        int midl = l + (r - l) / 3;
        int midr = r - (r - l) / 3;
        if(getnum(midl) > getnum(midr)) r = midr - 1;
        else l = midl + 1;
    }
    return getnum(l);
}
int main() {
    scanf("%d%lld", &n, &m);
    for(int i = 0; i < n; i++) scanf("%lld%lld", &a[i], &b[i]);
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            aa[tot] = a[i] + a[j];
            bb[tot++] = b[i] + b[j];
        }
    }
    printf("%lld\n", sanfen(1, m));
    return 0;
}

G-牛牛和字符串的日常

知识点：KMP算法

给定一个模式串，求在主串中最长能匹配多少，KMP模板题。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 100010;

int n;
int len, m;
char s[MAXN], t[MAXN];
int ans, kmpNext[MAXN];
void preKMP() {
    int i = 0, j = kmpNext[0] = -1;
    while(i < len) {
        while(-1 != j && s[i] != s[j]) j = kmpNext[j];
        if(s[++i] == s[++j]) kmpNext[i] = kmpNext[j];
        else kmpNext[i] = j;
    }
}
int main() {
    scanf("%s%d", s, &n);
    len = strlen(s);
    preKMP();
    while(n--) {
        scanf("%s", t);
        m = strlen(t);
        int num = 0, i = 0, j = 0;
        while(i < m) {
            while(-1 != j && t[i] != s[j]) j = kmpNext[j];
            i++, j++;
            num = max(num, j);
        }
        ans += num;
    }
    printf("%d\n", ans);
    return 0;
}

H-上学要迟到了

知识点：最短路

关键在于理解题意，相邻的车站建立双向边，公交车的运行线路建立单向边，然后跑最短路。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 100010;

int n, m, s, t, T;
int tt[MAXN], a[MAXN], idex[MAXN];
///建图
struct Edge {
    int v, w, ne;
} edge[MAXN];
int head[MAXN], tot;
void addedge(int u, int v, int w) {
    edge[tot].v = v;
    edge[tot].w = w;
    edge[tot].ne = head[u];
    head[u] = tot++;
}
///最短路
struct qnode {
    int v, w;
    qnode(int _v = 0, int _w = 0): v(_v), w(_w) {}
    bool operator <(const qnode &r)const {
        return w > r.w;
    }
};
bool vis[MAXN];
int dist[MAXN];
void Dijkstra() {
    memset(vis, false, sizeof(vis));
    memset(dist, INF, sizeof(dist));
    priority_queue<qnode> que;
    dist[s] = 0;
    que.push(qnode(s, 0));
    qnode tmp;
    while(!que.empty()) {
        tmp = que.top();
        que.pop();
        int u = tmp.v;
        if(vis[u]) continue;
        vis[u] = true;
        for(int i = head[u]; i != -1; i = edge[i].ne) {
            int v = edge[i].v;
            int w = edge[i].w;
            if(!vis[v] && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                que.push(qnode(v, dist[v]));
            }
        }
    }
}
int main() {
    tot = 0;
    memset(head, -1, sizeof(head));

    scanf("%d%d%d%d%d", &n, &m, &s, &t, &T);
    for(int i = 1; i <= m; i++) scanf("%d", &tt[i]);
    for(int i = 1; i <= n; i++) {
        if(i > 1) addedge(i, i - 1, T);
        if(i < n) addedge(i, i + 1, T);
        scanf("%d", &a[i]);
        if(idex[a[i]]) addedge(idex[a[i]], i, tt[a[i]]);
        idex[a[i]] = i;
    }
    Dijkstra();
    printf("%d\n", dist[t]);
    return 0;
}

I-迷宫

知识点：dp

每个格子的状态只有 $10^4+7$ 种，遍历一遍网格并更新网格的状态。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n, m;
int p = 10007;
int a[100][100];
bool dp[100][100][10007];
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            scanf("%d", &a[i][j]);
            a[i][j] %= p;
            if(i == 0 && j == 0) dp[i][j][a[i][j]] = true;
            for(int k = 0; k < p; k++) {
                if(dp[i][j][k] == 0) continue;
                if(i < n - 1) dp[i + 1][j][(k + a[i][j]) % p] = true;
                if(j < m - 1) dp[i][j + 1][(k + a[i][j]) % p] = true;
            }
        }
    }
    int cnt = 0;
    for(int i = 0; i < p; i++)
        if(dp[n - 1][m - 1][i]) cnt++;
    printf("%d\n", cnt);
    return 0;
}

J-树上行走

知识点：并查集

并查集处理之后输出答案即可。

#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <cmath>
#include <queue>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <fstream>
#include <cstdlib>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;
#define LL long long
const int INF = 0x3f3f3f3f;     ///1 061 109 567
const int negative_infinite = 0xcfcfcfcf;   ///-808 464 433
const double pi = acos(-1);
const LL mod = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 1e6 + 117;
const int MAXM = 1e6 + 117;

int n;
int a[MAXN];
struct Edge {
    int v, ne;
} edge[MAXN];
int head[MAXN], tot;
void addedge(int u, int v) {
    edge[tot].v = v;
    edge[tot].ne = head[u];
    head[u] = tot++;
}

int ans, num;
int root[MAXN], cnt[MAXN];
bool vis[MAXN];
void dfs(int id, int r) {
    root[id] = r;
    vis[id] = true;
    for(int i = head[id]; i != -1; i = edge[i].ne) {
        int v = edge[i].v;
        if(!vis[v] && a[v] == a[r]) dfs(v, r);
    }
}
int main() {
    ///初始化
    ans = num = tot = 0;
    memset(vis, false, sizeof(vis));
    memset(head, -1, sizeof(head));
    memset(cnt, 0, sizeof(cnt));
    ///建图
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addedge(u, v);
        addedge(v, u);
    }
    ///并查集
    for(int i = 1; i <= n; i++)
        if(!vis[i]) dfs(i, i);
    ///计算答案
    for(int i = 1; i <= n; i++) {
        cnt[root[i]]++;
        ans = max(ans, cnt[root[i]]);
    }
    for(int i = 1; i <= n; i++ )
        if(cnt[root[i]] == ans) num++;
    printf("%d\n", num);
    for(int i = 1; i <= n; i++)
        if(cnt[root[i]] == ans) printf("%d ", i);
    return 0;
}