rwbyblake的博客

ECPC-2015部分题解

2021-03-17 分类于 ACM 作者 rwbyblake ~ 5.94K 字
  1. 1. A - Arcade Game
  2. 2. C - Connecting Graph
  3. 3. L - Candy Jars

A - Arcade Game

题意：给一个小于9位且每一位各不相同的数字，一次可以让这个数字的所有位重新排列，如果获得的排列是所有排列的最大情况则获胜，否则如果大于当前数字则可继续游戏，直到获胜或失败。

题解：直接用组合数做肯定会超时，可以通过推式子的方式推出所有情况

首先求出当前位数一共有多少种排列情况n，并求出在所有排列情况中大于给出数字的数量sum。则一次到达最大值的概率为$\frac{n!}{(n-0)!0!}\frac{1}{n}$，第二次到达最大值的概率为$\frac{n!}{(n-1)!1!}\frac{1}{nn}$可以看到两项之间仅差$\frac{n-1}{1n}$，故可以通过递推式找到每一种情况，相加求和即为索求答案

代码：

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;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
int a[20], b[20];
int len = 0;
bool check(){
    for(int i = 0;i<len;i++)    if(a[i]!=b[i])  return false;
    return true;
}
void solve(){
    int n;
    cin>>n;
    len = 0;
    while(n){
        a[len++] = n%10;
        n/=10;
    }
    int sum = 0;
    for(int i = 0;i<len;i++){
        b[len-i-1] = a[i];
    }
    for(int i = 0;i<len;i++)    a[i] = b[i];
    int flag = 0;
    n = 0;
    sort(a, a + len);
    if (!flag) {
        if (check()) {
            flag = 1;
        }
    }
    while(next_permutation(a,a+len)){
        if(flag)    sum++;
        if(!flag){
            if(check()) flag = 1;
        }
        n++;
    }
    double ans;
    n++;
    if(sum==0)  ans = 0;
    else    ans = 1.0/n;
    double now = ans;
    for(int i = 1;i<sum;i++){
        now = now*(sum-i)*1.0/i*1.0/n;
        ans += now;
    }
    printf("%.9f\n",ans);
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

C - Connecting Graph

题意：有两个操作，第一个操作在第i秒时连接u和v，第二个操作询问u和v最早的联通时间，如果未联通则输出-1

题解：连边操作可以考虑使用并查集进行查询，如果两点未联通即两点不在同一并查集中则令两点所在并查集连接到一起，并令边权为当前时间。同时查询操作可以存储下来查询的时间和两点，最后当图建完后对每一次询问使用倍增LCA快速查找uv之间路径上的时间最大值，并判断输出答案。

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

using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;
struct node{
    int u,v,w,next;
}a[M];
int f[N],cnt;
void add(int u,int v,int w){
    a[++cnt].v = v;
    a[cnt].w = w;
    a[cnt].next = f[u];
    f[u] = cnt;
}
int lg;
int father[N][30],root[N],Time[N][30],dep[N];
int lca(int u,int v){
    int x = u,y = v;
    if(dep[u] < dep[v]) swap(u,v);
    int Max = 0;
    for(int i = lg;i>=0;i--){
        if(dep[father[u][i]] >= dep[v]) {
            Max = max(Max,Time[u][i]);
            u = father[u][i];
        }
    }
    if(u==v)    return Max;
    for(int i = lg;i>=0;i--){
        if(father[u][i]!=father[v][i]){
            Max = max(Max,max(Time[u][i],Time[v][i]));
            u = father[u][i],v = father[v][i];
        }
    }
    return max(Max,max(Time[u][0],Time[v][0]));
}
void dfs(int u,int fa){
    for (int j = 1; j <= lg; j++) {
        father[u][j] = father[father[u][j - 1]][j - 1];
        Time[u][j] = max(Time[u][j - 1], Time[father[u][j - 1]][j - 1]);
    }
    for(int i = f[u];i;i = a[i].next){
        int v = a[i].v,w = a[i].w;
        if(v==fa)   continue;
        dep[v] = dep[u] + 1;
        father[v][0] = u;
        Time[v][0] = w;
        dfs(v,u);
    }
}
int c[N];
int getf(int v){
    if(c[v]==v) return v;
    else    return c[v] = getf(c[v]);
}
void solve(){
    cnt = 0;
    memset(f,0,sizeof f);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++) c[i] = i;
    lg = (int)(log(n)/log(2))+1;
    int type,u,v;
    vector<pair<int,pair<int,int>>> query;
    for(int i = 1;i<=m;i++){
        scanf("%d%d%d",&type,&u,&v);
        if(type==1){
            int id1 = getf(u),id2 = getf(v);
            if(id1==id2)    continue;
            c[id1] = id2;
            add(id1, id2, i);
            add(id2,id1,i);
        }else{
            query.push_back({i,{u,v}});
        }
    }
    for(int i =1;i<=n;i++)  if(c[i]==i){
        father[i][0] = i;
        Time[i][0] = 0;
        dep[i] = 0;
        dfs(i,-1);
    }
    for(auto it:query){
        int t = it.first,u = it.second.first,v = it.second.second;
        if(u==v) puts("0");
        else{
            int t1 = getf(u),t2 = getf(v);
            if(t1!=t2)  puts("-1");
            else{
                int res = lca(u,v);
                printf("%d\n",res>t?-1:res);
            }
        } 
    }
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

L - Candy Jars

题意：给出n个罐子，每个罐子里装有一定数量的糖，每次选择一个罐子，扔掉其余所有糖，并将选择罐子里的糖分到所有罐子里使得所有罐子里都不为空。不能分配糖的人输。

题解：第一种情况当所有罐子里的糖都不够n个罐子分也就是小于n的时候，先手必输。当存在糖数可以使得分完后任意罐子都小于n则先手必赢。即存在$a_i<=n(n-1)$。当$a_i>n(n-1)$时由于此时先手无论怎么分，都必然存在分完后的$a_i<=n(n-1)且a_i>=n$即分完后先手必赢，即该游戏先手必输。归纳可得如果存在$n<=a_i$%$n(n-1)<n*(n-1)$则先手赢，否则后手赢。

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

using namespace std;
const int N = 1e5 + 10;
const int M = 1e6 + 10;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-3;

void solve(){
    int n;
    cin>>n;
    int flag = 0;
    for(int i = 1;i<=n;i++){
        int x;
        scanf("%d",&x);
        int w = x%((n-1)*n);
        if(w>=n||w==0){
            flag = 1;
        }
    }
    if(flag)    puts("Alice");
    else    puts("Bob");
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2021-03-17