1002.Random Nim Game

诈骗博弈题

题意

Nim是一种双人数学策略游戏，玩家轮流从不同的堆中移除棋子。在每一轮游戏中，玩家必须至少取出一个棋子，并且可以取出任意数量的棋子，条件是这些棋子都来自同一个棋子堆。走最后一步棋（即取出最后一块棋子）的人获胜。

现在更改游戏规则，在每个回合中，棋手必须选择一个棋子堆。假设他选择的堆包含 $x$ 个棋子，将从 $[1,x]$ 中随机一个整数 $y$ ，并从堆中移除 $y$ 个棋子

求先手获胜的概率，答案取模

解题思路

看起来很吓人的一道题（谁被吓退了我不说）//

考虑只有一个堆的情况
若只有 $1$ 个棋子，先手必胜
如果有 $2$ 个棋子，有 $\dfrac{1}{2}$ 的概率拿完获胜，有 $\dfrac{1}{2}$ 的概率余 $1$ 失败，综合胜率 $\dfrac{1}{2}$
$\vdots$
如果有 $x\ (x>1)$ 个棋子，有 $\dfrac{n-2}{n}$ 的概率转移到 剩余个数 $>1$ 的状态，有 $\dfrac{1}{n}$ 的概率拿完获胜，有 $\dfrac{1}{n}$ 的概率余 $1$ 失败。递归得到 $x>1$ 的状态下的综合胜率为 $\dfrac{1}{2}$

再考虑多堆的情况
如果所有堆的棋子数量均为 $1$ ，则当堆数 $n$ 为奇数时先手必胜
如果有某堆的数量多于 $1$ 个，那么必胜态将以 $\dfrac{1}{2}$ 的概率流转

综上所述，如果所有堆的棋子数量均为 $1$ ，则当堆数 $n$ 为奇数时先手必胜， $n$ 为偶数时先手必败，其余情况综合胜率 $\dfrac{1}{2}$

参考代码

1
2
3
4
5
6
7
8
9
10
void solve()
{
    ll n;cin >> n;ll mx=0,t;
    FORLL(i,1,n){
        cin >> t;
        mx=max(mx,t);
    }if(mx>1) cout << inv(2) << endl;
    else if(n%2) cout << 1 << endl;
    else cout << 0 << endl;
}

1004.Medians Strike Back

构造

题意

定义长度为 $n$ 的整数序列的中位数：

  1. 如果 $n$ 为奇数，则中位数是将序列排序后正中间的数
  2. 如果 $n$ 为偶数，则中位数是将序列排序后中间两个数中，出现次数较多的那个数，如果出现次数相同则取较小的那个数

定义序列的 $shikness$ ：该序列中位数出现的次数
定义序列的 $nitness$ ：该序列的所有连续子串的 $shikness$ 的最大值

给定一个正整数 $n$ ，构造长度为 $n$ 且仅含元素 $1,2,3$ 的序列，并使 $nitness$ 最小化，求出最小值

解题思路

构造找规律
$nitness_{min}=1$ 时，构造出最长序列为： $123$
$nitness_{min}=2$ 时，构造出最长序列为： $1313221313$
$nitness_{min}=3$ 时，构造出最长序列为： $131313222131313$
$nitness_{min}=4$ 时，构造出最长序列为： $1313131322131313132213131313$

如果序列中存在两个及以上的 $2$ ，那么 $2$ 是稳定作为中位数的，因此可以考虑以下构造方法：
连续 $n$ 对 $13$ 为一个单位子串//每个单位子串利用两个或三个连续的 $2$ 隔开，将得到以下格式的序列：$1313(n对)\cdots22\ 1313(n对)\cdots22\ 1313(n对)$

下面阐释这种构造方法的合法性

  1. 对于整个序列， $nitness=cnt_2=n$
  2. 对于含多个 $2$ 的子串， $2$ 稳定做中位数， $nitness<cnt_2=n$
  3. 对于仅含一个 $2$ 的子串，这个 $2$ 一定在单位子串的左边或右边，而单位子串的长度为 $2n$ ，因此加上 $2$ 后的长度为奇数，$2$ 稳定做中位数，$nitness=1$
  4. 对于不含 $2$ 的子串，其一定也是单位子串的子串，而单位子串中 $cnt_1=cnt3=n$ ，因此 $nitness\le n$

计数得到最长长度的通项公式： $len_i=2i(\lfloor \dfrac{i}{2} \rfloor+1)+i$

初始化长度数组，二分查找即可

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define N 500000
vector<ll> v(N);
void solve()
{
    ll n;cin >> n;
    cout << lower_bound(ALL(v),n)-v.begin() << endl;
}
/*----------Initialize----------*/
    v[0]=0;
    FORLL(i,1,N){
        v[i]=(i/2+1)*2*i+i;
        if(v[i]>1e11) break;
    }v.shrink_to_fit();
/*----------Initialize----------*/

1011.Three Operations

签到题

题意

给定正整数 $x,a,b$ 可以进行以下操作：

  1. $x\leftarrow x-1$
  2. $x\leftarrow \lfloor \dfrac{x+a}{2} \rfloor$
  3. $x\leftarrow \lfloor \sqrt{x+b} \rfloor$

求使得 $x$ 变为 $0$ 的最少操作次数

解题思路

每次比较三种操作后的 $x$ 最小即可

参考代码

1
2
3
4
5
6
7
8
9
void solve()
{
    ll x,a,b,t,re=0;cin >> x >> a >> b;
    while(x){
        t=min((x+a)/2,(ll)sqrt(x+b));
        if(t<x-1) {re++;x=t;}
        else {re+=x;break;}
    }cout << re << endl;
}

1013.Minimal and Maximal XOR Sum

归并排序、贪心

题意

给定一个长度为 $n$ 的排列 $p$ ，每次操作可以选定一段连续子序列 $p_{i,j}$ ，花费等同于元素个数的代价 $c=j-i+1$ ，使得这一段顺序反转
记使得排序变成自然排序（ $p_i=i$ ）所经过的一系列操作中，每一次的代价的异或和为 $x=c_1 \oplus c_2 \oplus \cdots \oplus c_i$
求 $x$ 的最大值和最小值

解题思路

排列的奇偶性定义为其所具有的逆序对数的奇偶性。任意一个n阶排列，可经过一系列对换转变为标准排列，且所做对换的次数与排列具有相同的奇偶性。

观察操作的特点可以得出，选定单一元素操作时，排列本身不发生改变，但产生 $1$ 点代价//这意味着所得结果 $x$ 的最后一个二进制位可以任意调整（和 $1$ 做异或）

考虑使得 $x$ 最小的操作方法
每次花费 $2$ 代价做对换，最小值 $x_{min}$ 一定会落在 $0$ 或 $2$ 上。根据对换次数与排列奇偶性的关系，判断排列逆序对数的奇偶性即可，可以使用归并排序进行逆序对计数

接下来考虑使得 $x$ 最大的操作方法
在排列 $p$ 已经有序的情况下，考虑如何操作花费代价可以使得异或和 $x$ 产生高位 $1$ ：先花费高代价 $c$ 反转某个长子序列，再连续花费 $2$ 代价做对换将序列恢复为有序

可以发现 $x$ 的最大可能二进制位数与 $n$ 相同，逐位考虑转 $1$ 记某位上的权重为 $2^m <n$ ，则反转 $2^m$ 个数后，恢复有序需要连续做对换的次数为 $2^m(2^m-1)/2$ ， $m\ge 2$ 时对换次数为偶数，即对最终的异或和 $x$ 无影响，这意味着按照上述策略可以将 $x$ 倒数第3位（权重为4）及以前的数位全部置1//

$m=1$ 时对换次数为 $1$ ，和反转 $2^1$ 个数的代价 $2$ 抵消，因此无法变更倒数第二位的值

综上所述，只需将 $x$ 调整为与 $n$ 具有相同二进制数的最大值，再判断倒数第二位即可//

时间复杂度

归并排序： $O(n\log n)$

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve()
{
    ll n;cin >> n;ll mn,mx;
    vector<ll> v(n);
    for(auto &x:v) cin >> x;
    ll cntinv=mergeSortAndCount(v,0,n-1);
    if(cntinv%2) mn=2;else mn=0;
    ll t=n,dig=0;while(t) {dig++;t/=2;}
    mx=(1<<dig)-1;
    if(mn==0) mx-=2;
    if(n==1) cout << "0 1" << endl;
    else cout << mn << ' ' << mx << endl;
}