First Last

题目大意

给定两个数，分别表示小凡将进行m场比赛，每场比赛有n个人，他在每场比赛等可能概率的排在第1~n名，问他每场都排在第1名或第n名的概率。

解题思路

当n小于等于2时，不管怎么比赛都要么排在第一名要么排在第n名，概率为1.

否则，他在一场比赛中排第一或最后一名的概率为，m场比赛都排第一或最后一名的概率为

直接计算即可。

参考代码

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
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=0;

void solve(){
    int n, m;
    cin >> n >> m;
    if(n > 2){
        double a = (1LL << m);
        for(int i = 0; i < m; i++){
            a /= n;
        }
        cout << fixed << setprecision(20) << a << '\n';
    }else{
        cout << 1 << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Grayscale Confusion

题目大意

给定n个三元组，构造一个长度为n的数组f，使得:

对于任意，若，则，输出任意合法方案。

解题思路

首先，由于颜色1和颜色2灰度值应该相同，若偏序则无合法方案。

接着考虑将最小的颜色从0开始，对于每个偏序条件连一条边，构建一个图，若，则从向连一条边，并维护每个点的入度。考虑到颜色1和颜色2的灰度值f要相同，我们干脆把f缩成一个点。

可以发现，由于当两种颜色严格偏序时才有相连的边，且边只会从小的连向到的，因此发现是一个拓扑图，直接跑一个拓扑序。显然，若u连向v，则v的灰度值至少比u大1，每一条边都是一组条件，因此我们每次更新v的灰度值为max(f[v],f[u]+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
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
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=0;
const int N=1010;
struct Node{
    int r, g, b;
    bool operator<(const Node &w){
        return r < w.r && g < w.g && b < w.b;
    }
    bool operator>(const Node &w){
        return r > w.r && g > w.g && b > w.b;
    }
}c[N];
vector<int> g[N];
int n;
int din[N];
int ans[N];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> c[i].r >> c[i].g >> c[i].b;
    }
    if(c[1] < c[2] || c[1] > c[2]) {
        cout << "-1\n";
        return;
    }
    for(int i = 3; i <= n; i++) {
        if(c[1] < c[i] || c[2] < c[i]) {
            g[2].push_back(i);
            din[i]++;
        }
        if(c[1] > c[i] || c[2] > c[i]) {
            g[i].push_back(2);
            din[2]++;
        }
    }
    for(int i = 3; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            if(c[i] < c[j]) {
                g[i].push_back(j);
                din[j]++;
            }else if(c[i] > c[j]) {
                g[j].push_back(i);
                din[i]++;
            }
        }
    }

    queue<int> q;
    for(int i = 2; i <= n; i++) {
        if(din[i] == 0) {
            q.push(i);
        }
    }
    while(q.size()) {
        int u = q.front();
        q.pop();
        for(auto v: g[u]){
            ans[v] = max(ans[v], ans[u] + 1);
            if(--din[v] == 0) q.push(v);
        }
    }

    if(*max_element(ans + 1, ans + 1 + n) > 255) {
        cout << -1 << '\n';
        return;
    }else{
        for(int i = 1; i <= n; i++) {
            cout << ans[max(2LL, i)] << '\n';
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}

Fair Equation

题目大意

给定三个数，问在这三个数中插入一个数字，是否能使A+B=C成立。若能，则输出Yes，再输出这个方案；否则输出No

解题思路

直接暴力枚举在每个数的每个位置插0~9的数即可，若能找到则输出方案，都找不到输出No

参考代码

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
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
using ll = long long;

bool multi=0;

int getbit(int x){
    int cnt=0;
    while(x){
        x/=10;
        cnt++;
    }
    return cnt;
}

int f(int x,int i,int d){
    int p=pow(10,i)+0.01;
    int t=x%p;
    x-=t;
    x*=10;
    x+=d*p;
    x+=t;
    return x;
}

bool out(int a,int b,int c){
    if(a+b==c){
        cout<<"Yes"<<'\n';
        cout<<a<<" + "<<b<<" = "<<c<<'\n';
        return true;
    }
    return false;
}

void solve(){
    char ch;
    int a,b,c;
    cin>>a>>ch>>b>>ch>>c;
    int c1=getbit(a),c2=getbit(b),c3=getbit(c);
    for(int i=0;i<=c1;i++){
        for(int j=0;j<=9;j++){
            if(i==c1&&j==0){
                continue;
            }
            int t=f(a,i,j);
            if(out(t,b,c)) return;
        }
    }

    for(int i=0;i<=c2;i++){
        for(int j=0;j<=9;j++){
            if(i==c2&&j==0){
                continue;
            }
            int t=f(b,i,j);
            if(out(a,t,c)) return;
        }
    }

    for(int i=0;i<=c3;i++){
        for(int j=0;j<=9;j++){
            if(i==c3&&j==0){
                continue;
            }
            int t=f(c,i,j);
            if(out(a,b,t)) return;
        }
    }
    cout<<"No"<<'\n';
    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    while(T--){
        solve();
    }

    return 0;
}