Random Nim Game

题目大意

有n堆石头，每堆有个石头，每次可以选择一堆移除随机数量石头，拿走最后一个石头的人获胜，问先手的获胜概率。

解题思路

当每堆都只有1个石头时，情况固定每个人都只会拿一个，因此可以确定谁必胜，即偶数堆后手胜，奇数堆先手胜。

反之，因为每个人拿的数量完全随机，对于超过1个石头的堆50%概率分别为先手拿走或后手拿走，最后获胜概率也是50%

时间复杂度：O（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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi=1;

void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    int cnt=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(a[i]==1){
            cnt++;
        }
    }
    if(cnt==n){
        cout<<(cnt%2!=0?"1":"0")<<'\n';
    }else{
        cout<<499122177<<'\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;
}

Medians Strike Back

题目大意

定义一个长度为n的序列的中位数：

当n为奇数时，中位数是升序排列最中间的数；当n为偶数时，中位数是升序排列最中间的两个数中出现次数多的那个，若出现次数相同，则是较小的那个。

定义一个序列的shikness是这个序列的中位数的出现次数。

定义一个序列的nitness是这个序列所有连续子序列上的最大shikness。

你需要构造一个长度为n的序列使得每个数在1~3范围内，使得nitness最小，输出最小的nitness

解题思路

这题我先尝试打表找规律，用了dfs暴力枚举序列每个数的三种情况别求每个情况的nitness取最小，发现n=1~3时答案为1，n=4~10时答案为2，n=11时答案为3，后面就因为时间复杂度太高跑不出结果，但打表的作用不止于此，我还找了每种情况nitness最小的构造来帮助我自己构造。输出发现，n=10的时候最优的情况有两种，1313221313和3131223131。于是我就顺着这个思路想，为什么这样可以最优，因为一段连续子序列中1和3的数量之差一定小于等于1，而当1和3数量很大时，只需要两个2就可以使这个序列的中位数不会取到1或3。例如，它的子序列131322131，排列后为111122333，中位数一定使2，nitness即2的数量，因此答案为2时，我只要让中间放两个2，左右两边封顶分别两个1和两个2交错排列，即可构造可以使得数量最大化。

考虑答案为3的时候怎么构造出最大长度，我们可以这样构造131313221313132，因为这时候答案为3，我们只能放3个2，必然有个2多出来，只能算作单独的一个贡献，而每个1313可以变成131313，与上述思想类似，如果跨越两个2构成的子序列得到的中位数一定为2数量不超过3，如果不跨越2，那么也最多为3。

再考虑答案为4的时候，这时候2可以有4个，那么我们可以在答案的2的基础上往两边扩展（当然也可以说是从答案为3的基础上），那么就可以从1313221313（答案为2）变成1313131322131313132213131313（答案为4），同样根据上面的思想这样可以使贡献最大化。

我这里推出了每个答案对应的最大n，再根据二分求出答案（当然也可以从1开始递推，因为赛时第一时间想到二分去找所有没有用递推了，可能递推更加清晰）

答案为k时，若k为偶数时，它能到的最大为

奇数时就是上一个偶数状态加上2*((l-2)/2+1)+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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi=1;
int n;

bool check(int x){
    return (x*x+3*x>=n);
}

int calc(int x){
    return x*x+3*x;
}

void solve(){
    cin>>n;
    if(n<=3){
        cout<<1<<'\n';
        return;
    }else if(n<=10){
        cout<<2<<'\n';
        return;
    }
    int l=0,r=1e6;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)){
            r=mid;
        }else{
            l=mid+1;
        }
    }
    if(l%2==1) l++;
    if(calc(l-2)+2*((l-2)/2+1)+1>=n){
        l--;
    }
    cout<<l<<'\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;
}

Three Operations

题目大意

给定一个数，每次可以进行下面三个操作中的一个，

①

②

③

求把x变成0的最小操作次数。

解题思路

每次把分别进行三次操作取操作后x最小的那个，并记录cnt，这里可以卡时，执行到一定次数后我们直接退出剩下全部操作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
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

bool multi=1;

void solve(){
    int x,a,b;
    cin>>x>>a>>b;
    int ans=0;
    int t=x;
    while(1){
        if(t==0) break;
        t=min({t-1,(int)(t+a)/2,(int)sqrt(t+b)});
        ans++;
        if(ans==1e3+10){
            ans+=t;
            break;
        }
    }
    cout<<ans<<'\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;
}

Minimal and Maximal XOR Sum

题目大意

给定一个长度为n的排列，你每次可以选择一段区间l~r进行翻转，代价是，求进行若干次翻转后得到递增序列的代价的异或和最小值和最大值。

解题思路

对于最小值，我们只需要两两交换，这样在异或中只会改变从低到高的第二个位且能达到交换效果，而每次交换相邻两个数能实现有序的奇偶性与逆序对数量的奇偶性相同。根据异或的性质，若偶数个2的异或和，则输出0，反之输出2。

对于最大值，我们可以先使每个位都到达1，直到那个位需要的翻转范围大于区间大小，那么任取区间长度分别为，其中k为满足的最大整数。翻转后与最小值思路类似，就算丢失二进制数中的1也应该尽量丢失低位，那么能交换且丢失尽量的的位应该也是从低到高第2位，因此同理再求翻转后的逆序对数量的奇偶性。

这里翻转可以O()实现，我们可以以一个点为轴，然后从左到右遍历，考虑这个点被翻转的奇偶性确定这个数是否要与轴对称的位置交换。

时间复杂度：

（归并排序求逆序对的时间复杂度）

参考代码

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

map<int,bool> mp;
const int N=1e5+10;

int tmp[N];

LL merge_sort(vector<int> &q,int l,int r){
    if(l>=r) return 0;
    int mid=l+r>>1;
    LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]) tmp[k++]=q[i++];
        else{
            tmp[k++]=q[j++];
            res+=mid-i+1;
        }
    }
    while(i<=mid) tmp[k++]=q[i++];
    while(j<=r) tmp[k++]=q[j++];
    for(int i=0;i<k;i++) q[l+i]=tmp[i];
    return res;
}

void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int minans=0;


    vector<int> c=a;

    int cnt1=merge_sort(c,1,n);


    int tmp=0;
    int maxans=0;
    while((1<<tmp)<=n){
        maxans+=(1<<tmp);
        tmp++;
    }
    int tans=maxans;
    tmp--;
    int t=(1<<tmp);
    vector<int> b=a;
    bool f=1;
    for(int i=1;i<=t/2;i++){
        if(mp[t/2-i+1]) f=!f;
        if(f==0)swap(b[i],b[t-i+1]);
    }
    int cnt2=0;
    for(int i=1;i<=n;i++){
        cnt2+=abs(b[i]-i);
    }
    vector<int> d=b;
    int cnttt=merge_sort(d,1,n);
    maxans^=((cnttt%2!=0?2:0));

    cout<<(cnt1%2==0?0:2)<<' '<<maxans<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T=1;
    if(multi) cin>>T;
    for(int i=0;;i++){
        if((1<<i)>(int)6e5+10) break;
        mp[(1<<i)]=true;
    }
    while(T--){
        solve();
    }

    return 0;
}