巅峰赛24题解

userId_undefined

盛翰祺

出道萌新分支·分支解题者时间刺客时空双修者空间掌握者秩序白银

2025-08-18 10:35:26

发布于：浙江

5阅读
0回复
0点赞

T1

#include <iostream>
#include <vector>
using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int k;
cin >> k;

if (k == 0 || k == 1) {
    cout << "Yes" << endl;//如果k=0或者k=1就输出Yes。
    return 0;
}

char prev_c;
long long num;
cin >> prev_c >> num; 

for (int i = 1; i < k; i++) {
    char c;
    cin >> c >> num;
    if (c == prev_c) {
        cout << "No" << endl;
        return 0;
    }
    prev_c = c;
}

cout << "Yes" << endl;
return 0;

}
T2
#include <iostream>
using namespace std;

const int MOD = 998244353;

int hamming_distance(int x, int y) {
int xor_xy = x ^ y;
int distance = 0;
while (xor_xy > 0) {
distance += xor_xy & 1;
xor_xy >>= 1;
}
return distance;
}

int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
int count = 0;
for (int x = 0; x <= n; ++x) {
for (int y = x + 1; y <= n; y) {
if (hamming_distance(x, y) <= k) {
count = (count + 1) % MOD;
}
}
}
cout << count << endl;
}
return 0;
}
T3
#include <bits/stdc.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int x, y;
cin >> x >> y;
if ((x * y) % 2 != 0) {
cout << "No" << endl;
continue;
}
int min_side = min(x, y);
int max_side = max(x, y);
if (min_side == 1) {
if (max_side % 4 == 0) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
} else if (min_side == 2) {
if (max_side % 3 == 0) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
} else if (min_side == 3) {
if (max_side % 2 == 0) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
} else {
cout << "Yes" << endl;
}
}
return 0;
}
T4
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;
const int MAX_N = 1000000;
const int MAX_K = 21;

int d_table[MAX_N+1];
int m_table[MAX_N+1];
int C[21][21];
int T_table[21][21];

int main() {
for (int n_value = 0; n_value <= MAX_N; n_value++) {
if (n_value == 0) {
d_table[0] = -1;
m_table[0] = 0;
continue;
}
int d = 0;
while ((1 << (d+1)) <= n_value) {
d++;
}
d_table[n_value] = d;
m_table[n_value] = n_value - (1 << d);
}

for (int d = 0; d <= 20; d++) {
    C[d][0] = 1;
    if (d > 0) {
        for (int j = 1; j <= d; j++) {
            C[d][j] = C[d-1][j] + C[d-1][j-1];
        }
    }
}

for (int d = 0; d <= 20; d++) {
    T_table[d][0] = C[d][0];
    for (int j = 1; j <= 20; j++) {
        if (j <= d) {
            T_table[d][j] = T_table[d][j-1] + C[d][j];
        } else {
            T_table[d][j] = (1 << d);
        }
    }
}

vector<vector<long long>> dp(MAX_N+1, vector<long long>(MAX_K+1, 0));
for (int k_value = 0; k_value <= MAX_K; k_value++) {
    dp[0][k_value] = 0;
}
for (int k_value = 0; k_value <= MAX_K; k_value++) {
    dp[1][k_value] = (k_value >= 1) ? 1 : 0;
}

for (int n_value = 2; n_value <= MAX_N; n_value++) {
    int d = d_table[n_value];
    int m = m_table[n_value];
    for (int k_value = 0; k_value <= MAX_K; k_value++) {
        long long value = 0;
        int A = (1 << d) - 1;
        value = (value + dp[A][k_value]) % MOD;
        value = (value + dp[m][k_value]) % MOD;
        if (k_value >= 1) {
            int j = k_value - 1;
            long long cross;
            if (j >= d) {
                cross = (1LL << d);
            } else {
                cross = T_table[d][j];
            }
            cross = cross * (m + 1) % MOD;
            value = (value + cross) % MOD;
        }
        dp[n_value][k_value] = value;
    }
}

ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) {
    int n, k;
    cin >> n >> k;
    cout << dp[n][k] << '\n';
}
return 0;

}
T5
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
#ifndef ONLINE_JUDGE
#include "test.h"
#else

#define debug(...) 42
#define debug_assert(...) 42
#endif

namespace myMath {
i64 mod = 998244353;

i64 add(i64 x, i64 y) {
    x += y;
    if (x > mod) x -= mod;
    return x;
}

i64 sub(i64 x, i64 y) {
    x -= y;
    if (x < 0)x += mod;
    return x;
}

i64 mul(i64 x, i64 y) {
    x *= y;
    x -= x / mod * mod;
    return x;
}

i64 qpow(i64 x, i64 y) {
    i64 res = 1;
    while (y) {
        if (y & 1) res = mul(res, x);
        y >>= 1;
        x = mul(x, x);
    }
    return res;
}

i64 inv(i64 x) {
    return qpow(x, mod - 2);
}

i64 qdiv(i64 x, i64 y) {
    return mul(x, inv(y));
}

void set_mod(i64 x) {
    mod = x;
}

namespace Comb {
    int n;
    vector<i64> fa;
    vector<i64> ifa;

    void init(int _n) {
        n = _n;
        fa.assign(n + 1, 1), ifa.assign(n + 1, 1);
        for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1], i);
        ifa[n] = inv(fa[n]);
        for (i64 i = n - 1; i; i--) {
            ifa[i] = mul(ifa[i + 1], i + 1);
        }
    }

    i64 C(int i, int j) {
        return mul(fa[i], mul(ifa[j], ifa[i - j]));
    }
}

//线性求逆元

vector<i64> get_inv(int k) {
    vector<i64> in(k + 1, 1);
    for (int i = 2; i <= k; i++) {
        in[i] = mul(in[mod % i], sub(mod, mod / i));
    }
    return in;
}

}

using namespace myMath;

int main() {
iossync_with_stdio(0), cin.tie(0);
int n, m;
Combinit(4e6);
cin >> n >> m;
vector<int> cx(n + 1), cy(m + 1);
vector<int> fx(1e6 + 1, 1e9), tx(1e6 + 1, 1e9), fy(1e6 + 1), ty(1e6 + 1);
for (int i = 1; i <= n; i++) {
cin >> cx[i];
fx[cx[i]] = min(i, fx[cx[i]]);
tx[cx[i]] = i;
}
for (int i = 1; i <= m; i++) {
cin >> cy[i];
fy[cy[i]] = min(fy[cy[i]], i);
ty[cy[i]] = i;
}
auto run = & -> pair<i64, i64> {
int i = 1, j = 1;
i64 t = 0, sums = 1;
while (i <= n && j <= m) {
int fxx = i, txx = max(tx[cx[i]], tx[cy[j]]);
int fyy = j, tyy = max(ty[cx[i]], ty[cy[j]]);
int a = 0, b = 0;
while (i < txx || j < tyy) {
while (i < txx) {
a++;
i++;
txx = max(tx[cx[i]], txx);
tyy = max(ty[cx[i]], tyy);
}
while (j < tyy) {
b++;
j++;
txx = max(txx, tx[cy[j]]);
tyy = max(tyy, ty[cy[j]]);
}
}
t += a + b + 1;
sums = mul(sums, Comb::C(a + b, a));
i++, j++;
}
return {t, sums};
};
auto [a , b] = run();

cout << a << "\n" << b << endl;

}
T6
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ull = unsigned long long;

#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define endl "\n"
#define int ll

//点 工作 总时间
const int maxn = 5e5+10;
int n, m, w;
vector<int> mp[maxn];
unordered_map<int, int> tim;
unordered_map<int, int> we;
int fa[maxn], top[maxn], son[maxn], dfn[maxn], dep[maxn], siz[maxn];
int tot = 1;
vector<array<int, 3> > v;
set<int> mp2[maxn];

void dfs1(int now) {
siz[now] = 1;
for (auto c: mp[now]) {
dep[c] = dep[now] + 1;
dfs1(c);
siz[now] += siz[c];

    if (siz[c] > son[siz[now]]) {
        son[now] = c;
    }
}

}

void dfs2(int now) {
dfn[now] = tot++;
if (son[fa[now]] == now) {
top[now] = top[fa[now]];
} else {
top[now] = now;
}
if (son[now]) {
dfs2(son[now]);
}
for (auto i: mp[now]) {
if (i == son[now])continue;
dfs2(i);
}
}

int lca(int p,int q) {
while (top[q] != top[p]) {
// cerr<<dep[top[q]]<<" "<<dep[top[p]]<<endl;
if (dep[top[q]] < dep[top[p]])
swap(q, p);
q = fa[top[q]];
}
if (dep[q] < dep[p])swap(q, p);
return p;
}

int cost(int u,int v) {
return 2 * abs(dep[u] - dep[v]);
}

void build_virtual_tree() {
sort(v.begin(), v.end(), [&](array<int, 3> a, array<int, 3> b) {
return dfn[a[0]] < dfn[b[0]];
});
vector<int> a;
for (int i = 0; i < m; i) {
a.emplace_back(v[i][0]);
a.emplace_back(lca(v[i][0], v[i + 1][0]));
}
a.emplace_back(v[m][0]);
sort(a.begin(), a.end(), [&](int a1, int b1) {
return dfn[a1] < dfn[b1];
});
int sizs = a.size();
for (int i = 0; i < sizs - 1; i) {
int lc = lca(a[i], a[i + 1]);
if (lc == a[i + 1])continue;
mp2[lc].emplace(a[i + 1]);
mp2[a[i + 1]].emplace(lc);
}
}

vector<int> dp(int f, int t) {
vector<int> fas(w + 10);
fas[tim[t]] = we[t];
for (auto c: mp2[t]) {
if (c == f)continue;
vector<int> v1 = dp(t, c);
int mul = cost(t, c);
for (int i = max(w - 2 * dep[t], 0ll); i >= 0; i--) {
for (int j = 0; j <= w; j++) {
if (i - mul - j < 0)break;
fas[i] = max(fas[i], v1[j] + fas[i - mul - j]);
}
}
}
return fas;
}

void solve() {
//7 3 10
cin >> n >> m >> w;

v.resize(m + 1);

v[0] = {1, 0, 0};


siz[0] = 0;
dep[0] = 0;
for (int i = 2; i <= n; i++) {
    int f;
    cin >> f;
    mp[f].emplace_back(i);
    fa[i] = f;
}
for (int i = 1; i <= m; i++) {
    cin >> v[i][0] >> v[i][1] >> v[i][2];
    tim[v[i][0]] = v[i][1];
    we[v[i][0]] = v[i][2];
}

dfs1(1);
dfs2(1);
build_virtual_tree();
vector<int> aa = dp(0, 1);
int maxs = -1;
for (int i = 0; i <= w; i++) {
    maxs = max(maxs, aa[i]);
}
cout << maxs << endl;

}

signed main() {
IOS
int t = 1;
// cin >> t;
while (t--)solve();
}
都看到这了，还不点个赞

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论