前言

fw又来了，如果有问题欢迎大家评论或私信指出

题解

A.会赢吗

输出，否则输出

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    double a, b;
    std::cin >> a >> b;
    if (b > a) {
        std::cout << "YES";
    }
    else {
        std::cout << "NO";
    }
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.能做到的吧

如果后一位比前一位大，那么交换这两位即可。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    std::string s;
    std::cin >> s;
    for (int i = 0; i < s.size() - 1; i++) {
        if (s[i] < s[i + 1]) {
            std::cout << "YES" << '\n';
            return;
        }
    }

    std::cout << "NO" << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

C.会赢的

如果目标点不在第一象限内，那么就是平局。如果横纵坐标的和为奇数，则会在阿龙的轮次中到达，即结果只能为阿龙赢或平局，否则结果只能为小歪赢或平局。横纵坐标的差值大于也是平局，比如目标点是值可能是小歪赢或者平局，那阿龙一定不会让小歪顺利到达，那第一步阿龙移动到，第二步小歪移动到，第三步阿龙移动到，第四步无论小歪怎么移动都不可能到达目标点

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long; 

void solve() {
    int n, m;
    std::cin >> n >> m;
    if (n >= 0 && m >= 0) {
        if (std::abs(n - m) > 1) {
            std::cout << "PING" << '\n';
            return;
        }
        if ((n + m) & 1) {
            std::cout << "YES" << '\n';
        }
        else {
            std::cout << "NO" << '\n';
        }
    }
    else {
        std::cout << "PING" << '\n';
    }
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

D.好好好数

输出n在k进制下，最大的那位数字是多少即可。根据定义，我们发现，每次取的数字只能是该进制下的每一位对应的数字只能是或那最少肯定是每次都拿所有能拿的吗，比如某个数在6进制下的串为321，那么就可以分为3个数字分别为+ + ，+ 和。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    i64 ans = 1;
    i64 n, k;
    std::cin >> n >> k;
    if (k == 1) {
        std::cout << 1 << '\n';
        return;
    }
    while(n) {
        ans = std::max(ans, n % k);
        n /= k;
    }

    std::cout << ans << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

好好好数组

手玩样例多玩点就会发现时是无解，剩下的构造也很简单，无非就是0 1 1 1 1,0 0 2 2 2 2 2， 0 0 0 3 3 3等，自己找找规律，不懂再联系我。

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    if (m > 3) {
        std::cout << 0 << '\n';
        return;
    }
    if (n == 1) {
        std::cout << 2 << '\n';
        return;
    }
    if (m == 1) {
        std::cout << n + 1 << '\n';
        return;
    }
    if (m == 2) {
        std::cout << n << '\n';
        return;
    }
    if (m == 3) {
        std::cout << 1 << '\n';
        return;
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

F.随机化游戏时间？

主席树板子，结束了，，，

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

const int Maxn = 100010, LOG = 20;
//一般我们用20倍空间来保存（防止溢出）
int tot = 0; // tot就是时间戳（每个节点的编号）
int ver[Maxn]; // 保存每个版本的根节点编号
struct node {
    int val, lson, rson;
} tr[Maxn * LOG];

//建空树
int build(int l, int r) {
    int rt = ++ tot;
    int mid = l + r >> 1;
    if (l < r) {
        tr[rt].lson = build(l, mid);
        tr[rt].rson = build(mid + 1, r);
    }
    return rt;
}

//更新
int update(int pre/*前一个版本节点*/, int l, int r, int id) {
    int rt = ++ tot;
    tr[rt].val = tr[pre].val + 1; // 新开的链, 链上每个val都加一
    if (l < r) {
        int mid = l + r >> 1;
        if (id <= mid) {
            tr[rt].lson = update(tr[pre].lson, l, mid, id);
            tr[rt].rson = tr[pre].rson;
        }
        else {
            tr[rt].rson = update(tr[pre].rson, mid + 1, r, id);
            tr[rt].lson = tr[pre].lson;
        }
        //左右儿子断开其中一个形成新的链
    }
    return rt;
}

// 查询操作
int query(int u, int v, int l, int r, int k) {
    if (l == r) return l;
    int LsonVal = tr[tr[v].lson].val - tr[tr[u].lson].val;
    //两个历史版本的树相减, LsonVal就是左子树的大小
    int mid = l + r >> 1;
    if (LsonVal >= k) return query(tr[u].lson, tr[v].lson, l, mid, k);
    else return query(tr[u].rson, tr[v].rson, mid + 1, r, k - LsonVal);
}

const int mod = 1e9 + 7;
int ksm(int a, int b) {
    int res = 1;
    while(b) {
        if (b & 1) res = 1ll * res * a % mod;
        a = 1ll * a * a % mod;
        b >>= 1;
    }

    return res;
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    tot = 0;
    //多组输入初始化
    memset(ver, 0, sizeof ver);
    std::vector<int>a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        b[i] = a[i];
    }

    // 离散化 a[i]
    sort(b.begin(), b.end());
    int MaxR = unique(b.begin(), b.end()) - b.begin();
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
    }


    ver[0] = build(0, MaxR); // 初始的空树, 相当于 pre[0], 不能缺
    for (int i = 0; i < n; i++) {
        ver[i + 1] = update(ver[i], 0, MaxR, a[i]);
        //ver[i] 不同历史版本
    }

    int L = 1, R = n;
    while(q--) {
        int l, r, k;
        std::cin >> l >> r >> k;
        if (k == 0) {
            R = std::min(R, b[query(ver[l - 1], ver[r], 0, MaxR, 1)] - 1);
        }
        else {
            L = std::max(L, b[query(ver[l - 1], ver[r], 0, MaxR, k)]);
            if (k != r - l + 1) {
                R = std::min(R, b[query(ver[l - 1], ver[r], 0, MaxR, k + 1)] - 1);
            }
        }
    }
    if (L == R) {
        std::cout << 1 << ' ' << L << '\n';
    }
    else {
        std::cout << ksm((R - L + 1), mod - 2) << '\n';
    }
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
} 

G.随机化游戏时间！

差分约束，但我不会，跟出题人学了之后才明白。提供洛谷上的一个板子题https://www.luogu.com.cn/problem/P1250 。

看了这个题的建边，回来再看这个，为什么要这样建边呢，以下是我的理解，大家可以在网上再学学回来教教我

这个G题给的是区间内有k个数小于等于幸运数，那不就是说明这段区间内最多有k个小于等于幸运数的数

(1)sum[r] - sum[l - 1] <= k;

(2)sum[l - 1] - sum[r] <= -k;

然后对于每个位置的数来说，当前位置最多会有一个小于等于幸运数的数字

(3)sum[i] - sum[i - 1] <= 1;

而反过来之后，最少会有0个幸运数字出现

(4)sum[i - 1] - sum[i] <= 0;

#include<bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;

const int N = 400005;

int head[N], tot = 0;

struct ty
{
    int t, next, l;
}edge[N];

void addedge(int x, int y, int z) {
    edge[++tot].t = y;
    edge[tot].l = z;
    edge[tot].next = head[x];
    head[x] = tot;
}

int dis[N], vis[N];
int n, m;

void spfa(int s, int t) {
    // memset(dis, 0x3f3f3f3f, sizeof(dis));
    // memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= n; i++) {
        dis[i] = 1e9;
        vis[i] = 0;
    }
    std::queue<int> q;
    dis[s] = 0;
    vis[s] = 1;
    q.push(s);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for (int i = head[x]; i != -1; i = edge[i].next) {
            int v = edge[i].t;
            if (dis[v] > dis[x] + edge[i].l) {
                dis[v] = dis[x] + edge[i].l;
                if (!vis[v]) {
                    q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
    // if (dis[t] >= 0x3f3f3f)return -1;
    // return dis[t];
}

void solve() {
    std::cin >> n >> m;

    for (int i = 0; i <= n; i++) {
        head[i] = -1;
    }
    tot = 0;

    for (int i = 1; i <= m; i++) {
        int l, r, k;
        std::cin >> l >> r >> k;
        addedge(l - 1, r, k);
        addedge(r, l - 1, -k);
    }
    
    for (int i = 0; i <= n - 1; i++) {
        addedge(i, i + 1, 1);
        addedge(i + 1, i, 0);
    }

    spfa(n, 0);
    int L = -dis[0];
    spfa(0, n);
    int R = dis[n];
    for (int i = std::max(1, L); i <= std::min(R, n); i++) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
} 

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);
    std::cin.tie(0);

    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}