A - 3.14

题意

π≈3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679\pi\approx 3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679

输出 π\pi 精确到小数点第 nn 位的结果。

解法

用字符串处理即可。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

string s="3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";

int main(){
    int n=read();
    cout<<s.substr(0,n+2);
    return 0;
}

B - Roulette

题意

有 nn 个人在预测一个轮盘。一共有 0∼360\sim36 共 3737 种结果。每个人预测了几个结果，最终结果是 XX。请输出所有预测了 XX 且预测数量最少的人。

解法

字面意思。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


const int N = 100;
vector<pii> a[N];

int main(){
    int n=read();
    for(int i=1;i<=n;i++){
        int c=read();
        for(int j=0;j<c;j++){
            int x=read();
            a[x].push_back({c,i});
        }
    }

    int k=read();
    sort(all(a[k]));

    if(a[k].size()==0){
        puts("0");
        return 0;
    }
    vector<int> ans;
    int pp = a[k][0].first;
    for(auto [p,q]:a[k]){
        if(p==pp){
            ans.push_back(q);
        }
    }
    printf("%lu\n",ans.size());
    for(int x:ans){
        printf("%d ",x);
    }
    puts("");
    
    
    return 0;
}

C - Rotate Colored Subsequence

题意

有一个序列，每个元素被染了一个颜色。现在对于每一个颜色，都单独将这个颜色的元素向右旋转一次。请问最后的序列是什么样的？

解法

用一个 vector 数组储存每个颜色的元素，然后分别使用 rotate 进行旋转一次。
最后输出的时候只需要记录这一位原来是什么颜色的，然后找到那个颜色的下一个进行输出。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
vector<char> colors[N];
vector<int> c;
char s[N];
int now[N];

int main(){
    int n=read(),m=read();
    scanf("%s",s);
    for(int i=0;i<n;i++){
        int k=read();
        c.push_back(k);
        colors[k].push_back(s[i]);
    }

    for(int i=1;i<=m;i++){
        rotate(colors[i].rbegin(), colors[i].rbegin() + 1, colors[i].rend());
    }

    for(int i=0;i<n;i++){
        putchar(colors[c[i]][now[c[i]]]);
        now[c[i]]++;
    }
    return 0;
}

D - LOWER

题意

给定一个字符串，要求能够维护如下三种操作：

  • 改变一个字符；
  • 所有字符变为大写；
  • 所有字符变为小写。

解法

维护每一个字符的最后修改时间以及最后一个大小写操作的事件。

如果这个字符在最后一次大小写操作之后被修改了，那么就原样输出，要不然就转换到对应的大小写然后再输出。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 5e5+5;
int lastMod[N];
char s[N];

int modT=-1,modType;

int main(){

    int n=read();
    scanf("%s",s);
    int m=read();
    for(int i=0;i<m;i++){
        int t,x;
        char c;
        scanf("%d %d %c",&t,&x,&c);

        if(t==1){
            s[x-1]=c;
            lastMod[x-1]=i;
        }
        else if(t==2){
            modT=i;modType=2;
                    }
        else{
            modT=i;modType=3;
        }
    }


    for(int i=0;i<n;i++){
        if(lastMod[i]>modT){
            putchar(s[i]);
        }
        else{
            if(modType==2)putchar(tolower(s[i]));
            else putchar(toupper(s[i]));
        }
    }
    return 0;
}

E - Roulettes

题意

有 nn 个轮盘，每个轮盘需要 cic_i 转一次，等概率转出 si,1,si,2,…,si,pis_{i,1},s_{i,2},\ldots,s_{i,p_i} 中的任意一个。

小 T 想要获得 mm 点。他可以根据目前获得的点的个数选择策略，请求出他获得 mm 点花钱的最小期望？

解法

设 dp[i]dp[i] 为达到至少 ii 点时花钱的最小期望。

假设 dp[i]dp[i] 从某个价格为 CC, 转出来的为 S1,S2,…,SPS_1,S_2,\ldots,S_P 转盘转移。

那么就可以写出如下转移表达式：

dp[i]=∑i=1P(dp[max⁡(0,i−Si)]+C)Pdp[i]= { {\sum_{i=1}^P\left(dp[\max(0,i-S_i)]+C\right) }\over {P}}

直接暴力转移就可以了，复杂度足够。

还有最后一个问题，有可能可以转出来 00，但是如果这样的话，我们转移方程式中就出现了自己，这是我们不希望的。因此，我们考虑进行一些小小的转化。

我们可以把转盘的价格按比例调高，然后把 00 全部删去，这样对于期望是没有影响的。
例：100100 元转出 {0,1,2}\{0,1,2\} 的转盘等价于 150150 元转出 {1,2}\{1,2\} 的转盘。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
T read(){
    T f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
template <class T>
void write(T x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}

const int N = 105;
double dp[N];
vector<int> p[N];
double val[N];
int zerocnt[N];
 
int main(){
    int n=read(),m=read();
    for(int i=0;i<n;i++){
        val[i]=read();
        int c=read();
        for(int j=0;j<c;j++){
            int x=read();
            if(x==0)zerocnt[i]++;
            else p[i].push_back(x);
        }
        val[i] = val[i]*c/(c-zerocnt[i]); // 修改价格，处理0
    }
    for(int i=1;i<=m;i++){
        dp[i] = 1e100; // 初始值
        for(int j=0;j<n;j++){
            double now = 0;
            for(int k:p[j]){
                now += (dp[max(0,i-k)]+val[j])/p[j].size();
            }
            dp[i]=min(dp[i],now);
        }
    }

    printf("%f\n",dp[m]);
    return 0;
}

F - A Certain Game

题意

nn 个人在进行比赛，初始每个人各自一队。
现在有 n−1n-1 场比赛，每场比赛为 ai,bia_i,b_i 所在队伍进行比赛。人数为 pp 和 qq 的队伍进行比赛，pp 胜率为 pp+q\dfrac{p}{p+q}，qq 胜率为 qp+q\dfrac{q}{p+q}。然后 aia_i 和 bib_i 所在的队伍进行合并。

求出每个人的胜利场数期望。

解法

考虑对这个比赛过程建立一颗二叉树。建立二叉树时，需要一些额外的节点，使用并查集维护现在一个连通块的根，就可以 O(n)O(n) 建出这一颗树。

然后进行一次 dfs 求出每个节点子树内的人数，然后再进行一次 dfs 转移胜利期望场数。

用线性求逆元求出 1∼n1\sim n 的逆元。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}


const int N = 2e5+5;
const ll MOD = 998244353;
int fa[N];
int represent[N];
int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void unite(int u,int v){
    fa[find(u)]=find(v);
}

vector<int> G[N*2];

void add_edge(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u);
}


ll inv[N];
int n;
int cnt=1;
int sz[N*2];
ll ans[N];
void dfs(int u,int p){
    if(u<=n)sz[u]=1;
    for(int v:G[u]){
        if(v!=p){
            dfs(v,u);
            sz[u]+=sz[v];
        }
    }
}
void dfs2(int u,int p, ll k){
    if(G[u].size()==1){
        ans[u]=k;
        return;
    }

    vector<int> children;
    for(int v:G[u]){
        if(v!=p){
            children.push_back(v);
        }
    }
    int c1=children[0],c2=children[1];
    ll pLeft = (sz[c1])*(inv[sz[c1]+sz[c2]])%MOD;
    ll pRight = (sz[c2])*(inv[sz[c1]+sz[c2]])%MOD;

    dfs2(c1,u,(k+pLeft)%MOD);
    dfs2(c2,u,(k+pRight)%MOD);
}


int main(){
    n=read();

    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(ll)(MOD-MOD/i)*inv[MOD%i]%MOD;
    }


    int now=n;
    for(int i=1;i<=n;i++){
        fa[i]=i;
        represent[i]=i;
    }
    for(int i=1;i<n;i++){
        int u=read(),v=read();
        int k1=represent[find(u)],k2=represent[find(v)];
        int newNode = ++now;
        add_edge(now,k1);
        add_edge(now,k2);
        unite(u,v);
        represent[find(u)]=newNode;
    }

    dfs(now,now);
    dfs2(now,now,0);

    for(int i=1;i<=n;i++){
        printf("%lld ",ans[i]);
    }

    return 0;
}

G - Amulets

题意

有 nn 个怪物，mm 个护身符，你有 hh 点生命。
怪物由攻击力 aa 和类型 bb 决定。

你携带了一些护身符，遇到一个怪物，如果你携带了和 bb 相同的护身符，那么不用受到伤害，不然要受到 aa 点伤害，当你的生命小于等于 0 时就失败了。

请求出携带 0∼m0\sim m 个护身符时，最多能打败几个怪物？

解法

不妨将问题转化为打败前 ii 个怪物至少需要几个护身符。

我们设 CjC_j 为类型 jj 的怪物的攻击力总和。
我们目标就是选出最多的 CjC_j，使得它们的和小于等于 hh。因此我们只需要从更小的 CjC_j 开始选即可。

对单独一个 ii 问题的解决已经很简单了，接下来考虑如何快速对所有的 ii 进行计算。事实上，我们不妨考虑两个 ii 之间的 CjC_j 变化，只会变化一个 CkC_k，然后再用 set 维护当前选和不选的护身符就可以了。

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
#include<bits/stdc++.h>
using namespace std;

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define all(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("YES")
#define NO puts("NO")
#define Yes puts("Yes")
#define No puts("No")
#define errorf(...) fprintf(stderr, __VA_ARGS__) 
#define endl '\n'
#define pb push_back

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 3e5+5;
int p[N];
int ans[N];

set<pair<ll,int>> S,T;
ll c[N];

int main(){
    int n=read(),m=read();
    ll h=read();
    for(int i=1;i<=m;i++){
        S.insert({0,i});
    }
    ll sum = 0;
    for(int i=1;i<=n;i++){
        ll a=read();int b=read();
        
        if(S.erase({c[b],b})){
            c[b]+=a;
            S.insert({c[b],b});
        }
        if(T.erase({c[b],b})){
            sum-=c[b];
            c[b]+=a;
            S.insert({c[b],b});
        }

        while(S.size() && S.begin()->first+sum<h){
            sum += S.begin()->first;
            T.insert(*S.begin());
            S.erase(S.begin());
        }
        while(S.size() && T.size() && S.begin()->first<T.rbegin()->first){
            sum += S.begin()->first-T.rbegin()->first;
            auto itS=S.begin(),itT=--T.end();
            S.insert(*itT);T.insert(*itS);
            S.erase(itS);T.erase(itT);
        }

        p[i]=S.size();
    }

    for(int i=0;i<=m;i++){
        int pos = upper_bound(p+1,p+1+n,i)-p-1;
        printf("%d " ,pos);
    }
    return 0;
}