A - To Be Saikyo

题意

有 nn 个人，实力分别为 p1,p2,…,pnp_1,p_2,\ldots,p_n。
请问第一个人实力需要增加多少才能严格大于后面所有的人？

解法

如果只有一个人，答案是 00。
否则答案是 max⁡(0,max⁡(p2,p3,…,pn)+1−n)\max(0,\max(p_2,p_3,\ldots,p_n)+1-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
#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;
}

int main(){
    int n=read();

    vector<int>v;
    int x=read();
    if(n==1){
        puts("0");
        return 0;
    }
    for(int i=1;i<n;i++){
        int a=read();
        v.push_back(a);
    }

    auto maxn = *max_element(all(v));
    printf("%d\n",max(0,maxn+1-x));
    return 0;
}

B - Who is Saikyo?

题意

有 nn 个人。给出 mm 组强弱关系。
试问：能否确定最强的人？如果能确定，输出这个人的编号，否则输出 -1。

保证存在一种合法的实力满足强弱关系。

解法

因为是存在的，所以这 mm 组强弱关系不会矛盾。
建一张有向图，如果有且仅有一个节点的入度为 00，那么这个节点就是最强的人，否则就不确定。（拓扑排序）

不用真的建图，直接维护入度即可。

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
#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 = 105;
int in[N]; // 入度

int main(){
    int n=read(),m=read();
    for(int i=0;i<m;i++){
        int u=read(),v=read();
        in[v]++;
    }

    int cnt = 0;
    int val;
    for(int i=1;i<=n;i++){
        if(in[i]==0){
            cnt++;
            val = i;
        }
    }

    if(cnt==1){
        printf("%d\n",val);
    }
    else{
        puts("-1");
    }
    return 0;
}

C - Approximate Equalization 2

题意

有 nn 个数 a1,a2,…,ana_1,a_2,\ldots,a_n。
现在一次操作可以让一个数减一，另一个数加一。
求让所有数的最大值和最小值差不超过一的最小操作次数。

解法

设 s=a1+a2+…+ans=a_1+a_2+\ldots+a_n，s=pn+qs=pn+q。
则最后答案一定是 p,…,p,(p+1),…,(p+1)p,\ldots,p,(p+1),\ldots,(p+1)。 （n−q+1n-q+1 个 pp，qq 个 p+1p+1）

操作次数就是操作前后差的总和除二。（证明略）
为了最小，一定让大的数变为 p+1p+1，小的数变为 pp。（证明略）

复杂度 O(nlog⁡n)O(n\log 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
#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;
ll a[N];

int main(){
    int n=read();
    ll sum = 0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        sum+=a[i];
    }
    sort(a+1,a+1+n,greater<ll>());

    ll need = sum/n;
    ll extra = sum%n;

    ll v = 0;
    for(int i=1;i<=extra;i++){
        v+=abs(a[i]-(need+1));
    }
    for(int i=extra+1;i<=n;i++){
        v+=abs(a[i]-(need));
    }

    printf("%lld\n",v/2);
    return 0;
}

D - Odd or Even

题意

交互题。
有一个 0−10-1 序列 a1,a2,…,ana_1,a_2,\ldots,a_n。

给定一个奇数 1≤k<N1\le k<N，每次你可以询问 kk 个不同的数的和奇偶性，请在 nn 次询问内找出每一个的数。

解法

先用 k+1k+1 次询问，第 ii 次询问 1∼k+11\sim k+1 中少 ii 的结果。然后就可以得到 a1,a2,…,aka_1,a_2,\ldots,a_k 的值（可以通过异或）。

既然已经知道了 1∼k+11\sim k+1，k+2∼nk+2\sim n 一次多询问一个也就都知道了。

特判一下 k=1k=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
89
90
91
92
93
94
95
96
#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 = 1005;
int a[N];

int main(){
    int n=read(),k=read();
    if(k==1){
        for(int i=1;i<=n;i++){
            printf("? %d\n",i);
            fflush(stdout);
            a[i]=read();
        }
        
        printf("! ");
        for(int i=1;i<=n;i++){
            printf("%d ",a[i]);
        }
        puts("");fflush(stdout);
        return 0;
    }
    
    int valfirst = 0;
    for(int i=1;i<=k;i++){
        printf("? ");
        for(int j=1;j<=k+1;j++){
            if(j==i)continue;
            printf("%d ",j);
        }
        puts("");fflush(stdout);
        a[i]=read();
        if(i==1)valfirst=a[i];
    }

    printf("? ");
    for(int i=1;i<=k;i++){
        printf("%d ",i);
    }
    puts("");fflush(stdout);
    int ans = read();
    int real = 0;
    for(int i=1;i<=k;i++)real+=a[i];
    if(real%2!=ans){
        for(int i=1;i<=k;i++){
            a[i]^=1;
        }
    }


    int now = 0;
    for(int i=2;i<=k;i++){
        now+=a[i];
    }
    now%=2;
    if(now==valfirst)a[k+1]=0;
    else a[k+1]=1;

    for(int i=k+2;i<=n;i++){
        printf("? ");
        for(int j=2;j<=k;j++){
            printf("%d ",j);
        }
        printf("%d\n",i);fflush(stdout);

        int x=read();
        if(now==x)a[i]=0;
        else a[i]=1;
    }

    printf("! ");
    for(int i=1;i<=n;i++){
        printf("%d ",a[i]);
    }
    puts("");fflush(stdout);
    return 0;
}

E - Duplicate

题意

有一个由 0~9 组成的数字串。
现在规定对一个数字串的操作是对 i=1 ∣s∣−1i=1~|s|-1，新字符串中 si+1s_{i+1} 个 sis_i。
例如 132 操作后变为 11133。
给定一个数字串，判断经过多少次操作后长度会变为 1，或者判定无法到达。

解法

先考虑不可能的情况。如果有连续两个大于 1 的数，那么一定不可以。不妨考虑最极端的情况：22 -> 22 -> 22 …，这样的情况是无限循环，任何比这个大的情况都会无限循环。

那之后的情况一定都是 x 个 1→大于 1 的数→x 个 1→…\text{x 个 1} \rightarrow \text{大于 1 的数} \rightarrow \text{x 个 1} \rightarrow \dots 的循环。

从后往前看。不难发现，每一操作之后，大于 1 的数\text{大于 1 的数} 的数保持不变，而 x 个 1\text{x 个 1} 个数有所增加。找到规律之后，从后往前一次计算，保存当前操作了几次，计算出目前的一个 11 片段增长到多少了。

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
#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 = 1e6+5;
char s[N];
pii a[N];
const ll MOD = 998244353;

int main(){
    int n=read();
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)s[i]-='0';

    for(int i=1;i<n;i++){
        if(s[i]>1 && s[i+1]>1){
            puts("-1");
            return 0;
        }
    }

    int ind = 0;
    int cnt = 0;
    for(int i=1;i<=n;i++){
        if(s[i]>1){
            if(cnt>0){
                a[++ind]={1,cnt};
            }
            cnt = 0;
            a[++ind]={s[i],1};
        }
        else cnt++;
    }
    if(cnt>0)a[++ind]={1,cnt};


    ll ans = 0;
    for(int i=ind;i>1;i--){
        if(a[i].first>1){ // 2+
            ans=(ans+1)%MOD;
        }
        else{
            ll len = a[i].second;
            len += (ll)(a[i+1].first-1)*ans%MOD;
            ans = (ans+len)%MOD;
        }
    }
    
    if(a[1].first==1){
        ll len = a[1].second;
        len += (ll)(a[2].first-1)*ans%MOD;
        ans = (ans+len-1)%MOD;
    }
    
    printf("%lld\n",ans);
    return 0;
}

F - Flip Machines

题意

有 n (n≤40)n\ (n\le 40) 个硬币，正面数值为 aia_i，背面数值为 bib_i。
有 m (m≤105)m\ (m\le 10^5) 台机器，每台机器有两个数 xi,yix_i,y_i。如果这台机器被激活了，有 1/21/2 的概率将 xix_i 翻面，还有 1/21/2 的概率让 yiy_i 翻面。每次机器的结果都是独立的。

求出一种激活机器的方案，使得硬币上面的数值的期望最大。

解法

首先考虑激活 xi,yix_i,y_i。无论第 kk 个硬币被几台机器激活了，它正反面的概率总是 1/21/2。（证明略）
再考虑 xi=yix_i=y_i 的情况。这种情况下一定可以把它反面。因此，如果正面比较小，我们就先把它翻面了，否则不翻。

接下来我们考虑所有激活的机器的 ⋃{xi,yi}=I\bigcup\{x_i,y_i\}=I。那么最终的期望就是

E=∑i∉Iai+∑i∈Iai+bi2E=\sum_{i\notin I} a_i + \sum_{i\in I}\dfrac{a_i+b_i}{2}

我们考虑如何求出这些最好的激活机器方案。

我们把所有硬币分为两类。一类是背面大于正面的硬币（赚），一类是背面小于正面的硬币（亏）。

若一个机器两个硬币都是赚的，那么一定激活。
若一个机器两个硬币都是亏的，那么一定不激活。

接下来只用考虑一个赚和一个亏的所有机器了。

  1. 考虑枚举有哪些亏的硬币被激活了:
    对于这种亏硬币的激活情况下，要求出最大可以赚多少。直接贪心选出所有的能激活的赚硬币。
    复杂度 O(n2亏数量+m)O(n 2^{\text{亏数量}}+m)
  2. 考虑枚举有哪些赚的硬币被激活了：
    对于这种激活状态下，要求出最小要亏几个硬币才能达到这种激活状态。
    这个可以用一次状压 DP 求出。
    复杂度 O(n2赚数量+m)O(n 2^{\text{赚数量}}+m)

那么我们只要方法 1 和方法 2 中选出一个合适的，就可以在 O(nn/2+m)O(n^{n/2}+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
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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#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 = 45;
const int M = 1e5+5;
int a[N],b[N];
int x[M],y[M];

int id[N];
int goodid[N],badid[N];
int cntGood,cntBad;
bool ena[N];

int main(){
    int n=read(),m=read();
    for(int i=1;i<=n;i++){
        a[i]=read(),b[i]=read();
    }

    for(int i=0;i<m;i++){
        x[i]=read(),y[i]=read();
        if(x[i]==y[i]){
            if(a[x[i]]<b[x[i]])swap(a[x[i]],b[x[i]]);
        }
    }

    vector<int> good,bad;

    for(int i=1;i<=n;i++){
        if(a[i]<=b[i]){
            goodid[i]=cntGood;
            id[i]=1,cntGood++;
            good.push_back(i);
        }else{
            badid[i]=cntBad;
            id[i]=2,cntBad++;
            bad.push_back(i);
        }
    }

    // 还需要确定的机器 第一个是会赚的 第二个是会亏的
    vector<pii> machines; 
    for(int i=0;i<m;i++){
        if(x[i]==y[i])continue;

        if(id[x[i]]==id[y[i]]){
            if(id[x[i]]==1){
                ena[x[i]]=ena[y[i]]=1;
            }
        }
        else{
            if(id[x[i]]==2)swap(x[i],y[i]);
            machines.push_back({x[i],y[i]});
        }
    }

    // 会亏的比较少 枚举所有会亏的可能情况
    if(cntBad<=cntGood){
        int ans = 0;
        vector<ll> k(cntBad);// 这是把这个亏的激活能增加的赚的集合
        for(auto [p,q]:machines){
            k[badid[q]]|=(1ll<<p);
        }
        for(int S=0;S<(1<<cntBad);S++){
            int tans = 0;
            ll now = 0;
            for(int i=0;i<cntBad;i++){
                if(S&(1<<i)){
                    now |= (1ll<<bad[i])|k[i];
                }
            }

            
            for(int i=1;i<=n;i++){
                if(ena[i] || (now&(1ll<<i))){
                    // printf("ok = %d\n",i);
                    tans += a[i]+b[i];
                }
                else tans += a[i]*2;
            }
            ans = max(ans,tans);
        }
        printf("%f",ans/2.);
    }
    // 会赚的比较少 
    else{   
        vector<vector<int>> dp(cntBad+1,vector<int>((1<<cntGood),-1e9));
        dp[0][0]=0;

        vector<int> k(cntBad);// 这是把这个亏的激活能增加的赚的集合
        for(auto [p,q]:machines){
            k[badid[q]]|=(1<<goodid[p]);
        }


        for(int i=0;i<cntBad;i++){

            // printf()
            for(int S=0;S<(1<<cntGood);S++){
                dp[i+1][S]=max(dp[i+1][S],dp[i][S]);
                dp[i+1][S|k[i]]=max(dp[i+1][S|k[i]],
                                dp[i][S]-(a[bad[i]]-b[bad[i]]));
            }
        }

        int ans = 0;
        for(int S=0;S<(1<<cntGood);S++){
            int tans = 0;
            for(int i=1;i<=n;i++){
                tans += 2*a[i]; // 正面的
            }

            vector<int> sel(n+1);
            for(int i=0;i<cntGood;i++){
                if(S&(1<<i))sel[good[i]]=1;
            }
            tans += dp[cntBad][S]; // 激活亏的代价
            
            for(int i=1;i<=n;i++){
                if(sel[i] || ena[i]){ // 激活赚的收益
                    tans += b[i]-a[i];
                }
            }
            ans = max(ans,tans);
        }
        printf("%f",ans/2.);
    }
    return 0;
}