qwq

A. 日历游戏

$f[年][月][日]$
$f[2024][8][1] = 0, 其余初始-1$
将每个日期当作一种状态，当前状态可以转移的状态只有+1天或者 +1个月;
SG处理每种状态最后判断即可。
也有一种规律做法，点此查看题解即可;

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;

int f[5000][50][50];

bool check(int x) {
    if (x % 400 == 0 || (x % 4 == 0 && x % 100 != 0)) {
        return 1;
    } else {
        return 0;
    }
}
int month[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int sg(int y, int h, int d) {

    if (y > 2024 || (y == 2024 && h > 8) || (y == 2024 && h == 8 && d > 1)) {
        return 0;
    }
    auto &v = f[y][d][h];

    if (v != -1) {
        return v;
    }
    std :: unordered_set<int> S;
    int ok = check(y);
    // + 1 Day
    int nowd;
    if (h == 2) {
        nowd = month[h] + ok;
    } else {
        nowd = month[h];
    }
    if (d + 1 <= nowd) {
        S.insert(sg(y, h, d + 1));
    } else {
        if (h + 1 <= 12) {
            S.insert(sg(y, h + 1, 1));
        } else {
            S.insert(sg(y + 1, 1, 1));
        }
    }
    // + 1 month
    if (h + 1 <= 12) {
        S.insert(sg(y, h + 1, d));
    } else {
        S.insert(sg(y + 1, 1, d));
    }

	for (int i = 0; ; i ++)
		if (!S.count(i))
			return v = i;
}
void solve() {
    int X, Y, Z;
    std :: cin >> X >> Y >> Z;

    int res = sg(X, Y, Z);

    if (res) {
        std :: cout << "YES\n";
    } else {
        std :: cout << "NO\n";
    }
      
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    // init();
    memset(f, -1, sizeof f);
    f[2024][8][1] = 0;
    int T = 1;
    std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

B.学生分组

模拟&思维.

计算每个学生个数变到[L,R]的需要的次数，根据题意进行模拟即可.

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;

void solve() {
    int n;
    std :: cin >> n;
    std :: vector<i64> a(n + 1);

    for (int i = 1; i <= n; i ++) {
        std :: cin >> a[i];
    }
    i64 L, R;
    std :: cin >> L >> R;
    
    if (n == 1) {
        if (a[1] >= L && a[1] <= R) {
            std :: cout << 0 << "\n";
        } else {
            std :: cout << -1 << "\n";
        }
        return;
    }
    i64 l = 0, r = 0;
    i64 canl = 0, canr = 0;
    for (int i = 1; i <= n; i ++) {
        if (a[i] < L) {
            l += (L - a[i]);
        }
        if (a[i] > R) {
            r += (a[i] - R);
        }
        if (a[i] <= R) canl += (R - std :: max(L, a[i]));
        if (a[i] >= L) canr += (std :: min(R, a[i]) - L);
    }
    // std :: cout << l << " " << r << "\n";
    if (l + canl < r || r + canr < l) {
        std :: cout << -1 << "\n";
        return;
    }

    std :: cout << std :: max<i64>(l, r) << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

C. 小美想收集

二分答案 + 染色法判断二分图。

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using PII = std :: pair<int, int>;
//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 1e5 + 10;

std :: vector<PII> g[N];
int n, m;
int color[N];
// 染色法判断是否为二分图
bool dfs(int u, int c, int mid) {
    color[u] = c;
    for (auto [v, w] : g[u]) {
        if (w <= mid)
            continue;
        if (color[v] == c)
            return false;
        if (!color[v] && !dfs(v, 3 - c, mid))
            return false;
    }
    return true;
}
bool check(int mid) {
    memset(color, 0, sizeof color);
    for (int i = 1; i <= n; ++i) {
        if (!color[i] && !dfs(i, 1, mid))
            return false;
    }
    return true;
}
void solve() {
    std :: cin >> n >> m;
    std :: vector<std :: tuple<int, int, int> > a;
    for (int i = 0; i < m; i ++) {
        int u, v, w;
        std :: cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    
    int l = 1, r = 1e6;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    std :: cout << l << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

另有二分答案 + 并查集的做法。

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 1e5 + 10;

std :: vector<int> g[N];
int n, m;
std :: vector<int> p(N);
int find(int x) {
    if (p[x] != x) {
        p[x] = find(p[x]);
    }
    return p[x];
}
void solve() {
    std :: cin >> n >> m;
    std :: vector<std :: tuple<int, int, int> > a;
    for (int i = 0; i < m; i ++) {
        int u, v, w;
        std :: cin >> u >> v >> w;
        a.push_back({u, v, w});
    }
    auto check = [&](int mid) -> int {
        iota(p.begin(), p.begin() + n + n + 1, 0);
        for (auto [a, b, c] : a) {
            if (c > mid) {
                int pa = find(a), pb = find(b);
                if (pa == pb) return false;
                p[find(a + n)] = find(b);
                p[find(b + n)] = find(a);
            }
        }
        return true;
    };
    int l = 1, r = 1e6;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    std :: cout << l << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

D. 区间问题1

线段树模板题

#include <bits/stdc++.h>
const int N = 1e5 + 10;
int a[N];
int n, q;

struct Tree
{
    int l, r;
    int sum, add;
} tr[N << 2];

void pushup(Tree &root, Tree &li, Tree &ri)
{
    root.sum = li.sum + ri.sum;
}

void pushup(int u) //上传更新
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r) //建树
{
    tr[u].l = l, tr[u].r = r;

    if(l == r)
    {
        tr[u].sum = a[l];
        return;
    }

    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void pushdown(Tree &root, Tree &li, Tree &ri)
{
    li.add += root.add;
    ri.add += root.add;
    li.sum += (li.r - li.l + 1) * root.add;
    ri.sum += (ri.r - ri.l + 1) * root.add;
    root.add = 0;
}

void pushdown(int u)
{
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void modify(int u, int l, int r, int k)
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].sum += (tr[u].r - tr[u].l + 1) * k;
        tr[u].add += k;
        return;
    }
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if(mid >= l) modify(u << 1, l, r, k);
    if(mid < r) modify(u << 1 | 1, l, r, k);
    pushup(u);
}

int query(int u, int l, int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int res = 0;
    if(mid >= l) res += query(u << 1, l, r);
    if(mid < r) res += query(u << 1 | 1, l, r);
    return res;
}
int main()
{
    std :: cin >> n;
    for (int i = 1; i <= n; i ++) {
        std :: cin >> a[i];
    }
    build(1, 1, n);
    std :: cin >> q;
    while(q--)
    {
        int op;
        std :: cin >> op;
        if(op == 1)
        {
            int x, y, d;
            std :: cin >> x >> y >> d ;
            modify(1, x, y, d);
        }
        else
        {
            int x;
            std :: cin >> x;
            std :: cout << query(1, x, x) << "\n";
        }
    }
}

E. 哥德巴赫猜想

分解质因数，暴力枚举即可

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;

int primes[N], cnt;
int st[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

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

    for (int i = 0; i < cnt; i ++) {
        for (int j = 0; j < cnt; j ++) {
            int sum = primes[i] + primes[j];
            if (n - sum >= 2 && !st[n - sum]) {
                std :: cout << primes[i] << " " << primes[j] << " " << (n - sum) << "\n";
                return; 
            }
        }
    }
    std :: cout << -1 << "\n";
    return;
}
int main() {
    get_primes(50010);
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

F. 小美想跑步

题意就是求1号点到其余所有节点的最短路的和 + 其余所有节点到1号节点的最短路的和
Dijkstra求最短路
首先求1号点到其余所有节点的最短路的和：只需按照题意建图跑一遍Dijkstra即可求出.
接下来如何求出其余所有节点到1号节点的最短路的和？
只需要将题目给定的有向边，反过来建图，在跑一遍Dijkstra即可解决问题。

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;
using PII = std :: pair<i64, int>;
std :: vector<PII> g[N];
int n, m;
i64 ans = 0;
void dijkstra() {
    std :: vector<i64> d(n + 1, 1e18);
    std :: vector<int> st(n + 1);

    std :: priority_queue<PII, std :: vector<PII>, std :: greater<PII> > q;
    q.push({0, 1});
    d[1] = 0;

    while (q.size()) {
        auto u = q.top().second;
        q.pop();

        if (st[u]) {
            continue;
        }
        st[u] = 1;

        for (auto [v, w] : g[u]) {
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push({d[v], v});
            }
        }
    }  
    for (int i = 2; i <= n; i ++) {
        ans += d[i];
    }
}
void solve() {
    std :: cin >> n >> m;
    std :: vector<std :: tuple<int, int, int> > a;
    for (int i = 0; i < m; i ++) {
        int u, v, w;
        std :: cin >> u >> v >> w;
        a.push_back({u, v, w});
        g[u].push_back({v, w});
    }        
    dijkstra();
    for (int i = 1; i <= n; i ++) {
        g[i].clear();
    }
    for (auto [u, v, w] : a) {
        g[v].push_back({u, w});
    }
    dijkstra();
    std :: cout << ans << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

G.爬楼梯

经典线性Dp
$Dp[i]表示到第i个台阶的方案数，那么$ $Dp[i] =$ $Dp[i - 1]$ + $Dp[i - 2]$ + $Dp[i - 3];$

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;
const int mod = 1e9 + 7;

void solve() {
    int n;
    std :: cin >> n;
    std :: vector<int> dp(n + 1);
    dp[1] = 1, dp[2] = 2, dp[3] = 4;
    for (int i = 4; i <= n; i++) {
        dp[i] = (1ll * dp[i - 1] + dp[i - 2] + dp[i - 3]) % mod;
    }
    std :: cout << dp[n] << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

H.区间问题2

ST表模板题求区间最大值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
const int N = 1e6 + 10;
int n;
int f[N][22];

int main()
{
    scanf("%d", &n);
    std :: vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++) std :: cin >> a[i];
    
    for(int i = 0; i < 22; i ++)
    {
        for(int j = 1; j + (1 << i) - 1 <= n; j ++)
        {
            if(!i) f[j][i] = a[j];
            else f[j][i] = std :: max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
        }
    }
    int q;
    scanf("%d", &q);
    while(q --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int k = (r - l + 1);
        int j = log2(k);
        printf("%d\n", std :: max(f[l][j], f[r - (1 << j) + 1][j]));
    }
    return 0;
}

I.小美想打音游

注：本人做法略偏，使用三分找出极小值，最后求出答案，实际本题可以使用较为简单的前缀和做法\

可以观察本题其实就是需要求一个X，使得 $\sum_{i = 1}^{n} |c_i - X|$ 尽可能小，所以我使用三分找出了这个X;
最后答案就是 $\sum_{i = 1}^{n} |c_i - X|$ + 1；

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;

int n;
void solve() {
    std :: cin >> n;
    std :: vector<int> c(n + 1);
    for (int i = 1; i <= n; i ++) {
        std :: cin >> c[i];
    }
    auto calc = [&](int x) -> i64 {
        i64 sum = 0;

        for (int i = 1; i <= n; i ++) {
            sum += abs(c[i] - x);
        }
        return sum;
    };
    int l = 0, r = 1e6;
    while (l < r) {
        int midl = l + (r - l) / 3, midr = r - (r - l) / 3;

        if (calc(midl) < calc(midr)) r = midr - 1;
        else l = midl + 1;
    }

    std :: cout << calc(l) + 1 << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

J 平方根

签到题

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 2e5 + 10;

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

    std :: cout << (i64)sqrt(n) << "\n";   
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

K 小美想游泳

二分 + Dijkstra 每次check，跑dijkstra，同时以mid为上限，如果某条边波浪值大于mid则不能通过此边

#include <bits/stdc++.h>

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

//std :: mt19937_64 rng {std :: chrono::steady_clock::now().time_since_epoch().count()};
constexpr int N = 1e4 + 10;
using PII = std :: pair<int, int>;
std :: vector<PII> g[N];
int n, m, s, t;

int dijkstra(int x) {
    std :: vector<int> st(n + 1);
    std :: vector<int> d(n + 1, 1e9);
    std :: priority_queue<PII, std :: vector<PII>, std :: greater<PII> > q;
    q.push({0, s});
    d[s] = 0;

    while (q.size()) {
        auto u = q.top().second;
        q.pop();
        if (st[u]) {
            continue;
        }
        st[u] = 1;

        for (auto [v, w] : g[u]) {
            if (w > x) {
                continue;
            }
            if (d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                q.push({d[v], v}); 
            }
        }
    }
    return d[t];
}

bool check(int x) {
    if (dijkstra(x) == (int)1e9) {
        return false;
    }
    return true;
}
void solve() {
    std :: cin >> n >> m;

    for (int i = 0; i < m; i ++) {
        int u, v, a;
        std :: cin >> u >> v >> a;
        g[u].push_back({v, a});
        g[v].push_back({u, a});
    }
    std :: cin >> s >> t;
    int l = 1, r = 1e4;
    while (l < r) {
		int mid = (l + r >> 1);

		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	std :: cout << l << "\n";
    return;
}
int main() {
    std :: ios :: sync_with_stdio(false);
    std :: cin.tie(0);
    int T = 1;
    //std :: cin >> T;
    while (T --) {
        solve();
    }
    return 0;
}

题解 | #河南萌新联赛2024第（五）场：信息工程大学 #

qwq