跳转至

THUPC2023 初赛题解

好像是第三次还是第二次打 THUPC 了，上次和 Sept 还有 clf 组队，结果大家都开摆了）

这次和 JR 还有 leexzq 组队，队名：银牌选手喔皮只因。

成分比较复杂；

img

我贡献了最后一题，第二题，第一题的一半。

只写点我会的。

THUPC 怎么这么喜欢分讨博弈论和工业题/zhem

题面

A - 大富翁ψ(｀∇´)ψ

首先一个比较显然的事情是，如果我们考虑无权树的情况，显然先手最优策略是选 dep 小的。

如果同层来看，那优先选 siz 大的，好，现在我们会无权树了。

那么考虑带权怎么做，也很简单，在满足以上条件的情况下我们尽量选 w 小的就行！

结论我是感性理解证明的，或者说瞎蒙感性理解了一下直接开莽了，所以就不放上来了，有会证明的佬可以评论区发表高见！

所以我们先给节点按照 \(dep - siz + w\) 排序，优先选这个权值更小的就行。

然后怎么维护答案呢？这个是一个经典 trick 啊，要查子树和祖先，我们直接 dfs 序拉下来，Fenwick 维护一下就行。

代码是 xzq 写的。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
//I play to win
#include<bits/stdc++.h>

#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
inline void out(ll x){if(x>9)out(x/10);putchar(x%10^48);}
inline void print(ll x,char c='\n'){if(x<0)putchar('-'),x=-x;out(x),putchar(c);}
const int N=5e5+10;
int fa[N],dfn[N],w[N],siz[N],dep[N],id[N];
vector<int>v[N];
struct BIT
{
    int c[N];
    void add(int x,int v){for(;x<N;x+=x&-x)c[x]+=v;}
    int ask(int x){int r=0;for(;x;x&=x-1)r+=c[x];return r;}
}T[2][2];
void dfs(int x)
{
    siz[x]=1,dep[x]=dep[fa[x]]+1,dfn[x]=++dfn[0];
    for(int y:v[x])dfs(y),siz[x]+=siz[y];
}
int main()
{
    int n=read();
    ll ans=0;
    for(int i=1;i<=n;i++)w[i]=read(),id[i]=i;
    for(int i=2;i<=n;i++)v[fa[i]=read()].push_back(i);
    dfs(1),sort(id+1,id+n+1,[](int x,int y){return w[x]+dep[x]-siz[x]<w[y]+dep[y]-siz[y];});
    for(int i=1;i<=n;i++)
    {
        int k=i&1,x=id[i],l=dfn[x],r=dfn[x]+siz[x]-1;
        if(k)ans-=T[k^1][0].ask(l),ans+=T[k^1][1].ask(r)-T[k^1][1].ask(l-1),ans-=w[x];//先手
        else ans+=T[k^1][0].ask(l),ans-=T[k^1][1].ask(r)-T[k^1][1].ask(l-1);
        T[k][0].add(l,1),T[k][0].add(r+1,-1),T[k][1].add(l,1);
        // cout<<x<<" "<<l<<" "<<r<<" "<<ans<<endl;
    }
    print(ans);
}

B - 拧螺丝ψ(｀∇´)ψ

首先观察发现，如果 \(k \ge n\) 显然一步对吧，如果 \(k < n\) 的时候 \(k = 1\) 显然无解对吧。

于是我们考虑剩下的部分（\(k < n, k > 1\)）怎么做。

手推模拟可以发现，\(k = 2\) 答案是 \(2^{n - 2}\)。

\(k \ge 3\) 的手推很难受。

注意到这个问题具有极其明显的单调性，所以我们二分组装了多少个模块，然后枚举天数，显然的策略是要平均分配，因为老板会尽力不让小 E 达成目的，所以我们需要最小化损失。

然后 check 一下就可以得到答案了，这个东西复杂度 \(O(n^2\log n)\)，也不知道咋优化。

于是选择了下策，考虑 OEIS，于是我打出 \(k = 3\) 的前几项，输进 OEIS 下发现有这个数列！！！

https://oeis.org/A073941

然后我注意到公式是 \(a(n) = \lceil \sum\limits_{k = 1}^{n - 1} a(k) / 2\rceil, n \ge 2, a(1) = 1\)。

于是我尝试把这里的常数项替换成 \(k\) 相关的式子，发现只有 \(2\)，于是我们把它变成 \(k - 1\)。

带入和 \(k = 4\) 暴力对拍发现是对的。

于是我们写个高精或者 py 交上去就行了！！！

高精度板子没写整除，就直接现学 py 了：

代码我写的。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
# author : black_trees

n, k = map(int, input().split())

if k >= n:
    print(1)
if k < n and k == 1:
    print("Poor E.S.!")
if k < n and k == 2:
    print(2**(n-2))
if k < n and k >= 3:
    ans = 1
    s = k - 1
    for i in range(k - 1, n):
        ans = (s + k - 2) // (k - 1)
        s = s + ans
    print(ans)

乱搞做法，只是博君一笑，不必在意。

J - 欺诈游戏ψ(｀∇´)ψ

盒！

听说是纳什均衡，也可以直接推式子，但是我不会！

可以看看可爱 tyq 的题解：P9142 [THUPC 2023 初赛] LIAR GAME! 题解 & 纳什均衡浅探

Code 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>

#define endl '\n'
// #define int long long

using namespace std;
using i64 = long long;
using ldb = long double;
using u64 = unsigned long long;

constexpr i64 safe_mod(i64 x, i64 m) { return x %= m, x < 0 ? x + m : x; }
constexpr i64 pow_mod_constexpr(i64 x, i64 n, int m) {
    if(m == 1) return 0;
    unsigned _m = m; uint64_t r = 1, _x = safe_mod(x, m);
    for(; n; n >>= 1, _x = _x * _x % _m) if(n & 1) r = r * _x % m;
    return r;
}
constexpr bool is_prime_constexpr(int n) {
    if(n <= 1) return false;
    if(n == 2 || n == 7 || n == 61) return true;
    if(n % 2 == 0) return false;
    i64 d = n - 1; while(~d & 1) d /= 2;
    for(i64 a : {2, 7, 61}) {
        i64 t = d, y = pow_mod_constexpr(a, t, n);
        while(t != n - 1 && y != 1 && y != n - 1) y = y * y % n, t <<= 1;
        if(y != n - 1 && t % 2 == 0) return false;
    }
    return true;
}
constexpr pair<i64, i64> inv_gcd(i64 a, i64 b) {
    a = safe_mod(a, b);
    if(a == 0) return {b, 0};
    i64 s = b, t = a, m0 = 0, m1 = 1;
    while(t) {
        i64 u = s / t; s -= t * u, m0 -= m1 * u;
        i64 tmp = s; s = t, t = tmp, tmp = m0, m0 = m1, m1 = tmp;
    }
    if(m0 < 0) m0 += b / s;
    return {s, m0};
}
struct Barrett_Reduction {
    unsigned m; uint64_t im;
    Barrett_Reduction(unsigned m) :m(m), im(~0ull / m + 1) {}
    unsigned mul(unsigned a, unsigned b) const {
        uint64_t z = (uint64_t)a * b, x = (__uint128_t)z * im >> 64; unsigned v = z - x * m;
        return m <= v ? v + m : v;
    }
};
template<int m> struct static_modint {
    using _mint = static_modint;
  public:
    static _mint raw(int v) { _mint x; return x._v = v, x; }
    static_modint() :_v(0) {}
    template<class __Tp> static_modint(__Tp v) { i64 x = v % m; _v = x < 0 ? x + m : x; }
    unsigned val() const { return _v; }
    _mint& operator ++ () { if(++_v == m) _v = 0; return *this; }
    _mint& operator -- () { if(!_v--) _v = m - 1; return *this; }
    _mint operator ++ (int) { _mint res = *this; ++*this; return res; }
    _mint operator -- (int) { _mint res = *this; --*this; return res; }
    _mint& operator += (const _mint& rhs) { _v += rhs._v; if(_v >= m) _v -= m; return *this; }
    _mint& operator -= (const _mint& rhs) { _v -= rhs._v; if(_v >= m) _v += m; return *this; }
    _mint& operator *= (const _mint& rhs) { uint64_t z = _v; z *= rhs._v, _v = z % m; return *this; }
    _mint& operator /= (const _mint& rhs) { return *this = *this * rhs.inv(); }
    _mint operator + () const { return *this; }
    _mint operator - () const { return _mint() - *this; }
    _mint pow(i64 n) const { assert(0 <= n); _mint x = *this, r = 1; for(; n; n >>= 1, x *= x) if(n & 1) r *= x; return r; }
    _mint inv() const{ if(prime) { assert(_v); return pow(m - 2); } else { auto eg = inv_gcd(_v, m); assert(eg.first == 1); return eg.second; } }
    friend _mint operator + (const _mint& lhs, const _mint& rhs) { return _mint(lhs) += rhs; }
    friend _mint operator - (const _mint& lhs, const _mint& rhs) { return _mint(lhs) -= rhs; }
    friend _mint operator * (const _mint& lhs, const _mint& rhs) { return _mint(lhs) *= rhs; }
    friend _mint operator / (const _mint& lhs, const _mint& rhs) { return _mint(lhs) /= rhs; }
    friend bool operator == (const _mint& lhs, const _mint& rhs) { return lhs._v == rhs._v; }
    friend bool operator != (const _mint& lhs, const _mint& rhs) { return lhs._v != rhs._v; }
  private:
    unsigned _v;
    static constexpr bool prime = is_prime_constexpr(m);
};
using modint = static_modint<998244353>;

const int si = 2e6 + 10;

int n;
modint a[si], b[si];

signed main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cin >> n;
    a[0] = b[0] = 1, a[1] = 2, b[1] = 3;
    for(int i = 2; i <= n; ++i) {
        a[i] = (b[i - 1] + (i - 1) * a[i - 1]);
        a[i] = a[i] / i, a[i] *= 2, b[i] = b[i - 1] + a[i];
    }

    modint t = n + 2;
    modint ans = 2 * t.inv();
    cout << ans.val() << " ";
    for(int i = 1; i <= n; ++i)
        cout << (ans = t.inv()).val() << " \n"[i == n];

    modint ss = 0;
    for(int i = 0; i <= n; ++i) ss += a[i];

    for(int i = 0; i <= n; ++i)
        cout << (ans = a[i] / ss).val() << " \n"[i == n];

    return 0;
}

K - 众数ψ(｀∇´)ψ

JR 和 xzq 小讨论了一手就会了，我没看。

具体就是，假设当前最大数是 \(mx\)，有 \(k\) 个 \(mx\)，就放 \(k\) 个在后面，然后考虑对 \(mx - 1\) 递归做这个过程。

代码 xzq 写的，JR 打摆。

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//I play to win
#include<bits/stdc++.h>

#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
inline void out(ll x){if(x>9)out(x/10);putchar(x%10^48);}
inline void print(ll x,char c='\n'){if(x<0)putchar('-'),x=-x;out(x),putchar(c);}
const int N=5e5+10;
ll a[N],b[N],s[N];
int main()
{
    int n=read();
    ll use=0,ans=0;
    for(int i=1;i<=n;i++)a[i]=b[i]=read();
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)s[i]=b[i]+s[i-1];
    for(int i=n;i;i--)
    {
        if(a[i]<use)continue;
        int l=upper_bound(b+1,b+n+1,use)-b,r=upper_bound(b+1,b+n+1,a[i])-b-1;
        ans+=i*(s[r]-s[l-1]-use*(r-l+1)+(a[i]-use)*(n-r)),use=a[i];
        // cout<<l<<" "<<r<<" "<<ans<<endl;
    }
    print(ans);
}

M - 世界杯ψ(｀∇´)ψ

中国队牛逼！

Code 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// author : black_trees

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'

using namespace std;
using i64 = long long;

int main() {

    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit | cin.badbit);

    cout << "China" << endl;    

    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//I play to win
#include<bits/stdc++.h>

#define ll long long
#define ull unsigned ll
#define pi pair<int,int>
#define ld long double
#define vi vector<int>
#define all(x) begin(x),end(x)
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
inline void out(ll x){if(x>9)out(x/10);putchar(x%10^48);}
inline void print(ll x,char c='\n'){if(x<0)putchar('-'),x=-x;out(x),putchar(c);}
const int N=1e5+10;
int main()
{
    puts("China");
}
最后更新: May 9, 2023