2022杭电杯超级联赛01

1011-Random

来源: 杭电杯超级联赛1 算法: 概率论, 逆元 题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1044&pid=1011 补完: Yes 完成时间: August 24, 2022

题解

给随机数\([0,1]\), 则期望为\(1/2\), 给\(n\)次, 减去\(m\)次, 问最后所得值.直接计算即可.

若\(n<=m\)即删的次数比抽的次数多, 直接归零,

非则\(ans= (n-m)*1/2\).同余除法用逆元处理.

代码

#include<bits/stdc++.h>
using namespace std;

#define ll long long

const ll P = 1000000007;

ll Mul(ll a, ll b){
    return (a * b) % P;
}
ll Pow(ll a, ll n){
    ll ans = 1;
    while (n) {
        if (n & 1) ans = Mul(a, ans);
        a = Mul(a,a);
        n >>= 1;
    }
    return ans;
}
ll Div(ll a, ll b){
    b = Pow(b, P - 2);
    return Mul(a, b);
}

void solve() {
    ll n, m;
    cin>>n>>m;
    if(n<=m)printf("0\n");
    else printf("%lld\n",Div((n-m),2));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    cin>>T;// 无多组数据注释这一行
    while (T--) {
        solve();
    }
    return 0;
}

1012-Alice and Bob

来源: 杭电杯超级联赛1 算法: 博弈论 题目链接: https://acm.hdu.edu.cn/contest/problem?cid=1044&pid=1012 补完: Yes 完成时间: August 4, 2022

题目链接

题意简述

Alice和Bob玩游戏。黑板上有介于\(0\sim n\)之间的数字，给出每个数字的个数。任何时候，有数字\(0\)存在，Alice获胜。否则Alice可以把数字分成两组，然后Bob可以选择一组擦除，另一组所有数字\(-1\)。擦除所有的数字后，Bob获胜。

双方都使用最优的策略，问谁会获胜。

题目分析

首先，一开始有\(0\)，Alice获胜。

那么如果有\(1\)，Alice会尽量保护它不被Bob擦除，这样一轮之后\(1\)变成\(0\)了，Alice获胜。而同理Bob必须要擦除\(1\)。

那么如果有\(2\)个以及以上的数字\(1\)，Alice就能胜利，把它们分在两组里，Bob无论擦哪组，都有剩下的\(1\)变成\(0\)。

如果没有\(1\)和\(0\)，最小的数字从\(2\)开始，Alice要胜利的话需要多少个\(2\)呢？

\(2\)经过一轮变成\(1\)，再一轮变成\(0\)，如果分配\(2\)不均衡，Bob擦除比较多的那组就能防止Alice希望的\(2\)变成\(0\)，所以Alice应该尽量平分\(2\)。

需要\(2个1\)存在，就需要这一轮有\(4\)个以及以上的\(2\)存在，平均分到两堆之后，最少会有\(2个2\)被剩下，然后变成\(2个1\)，从而变成\(0\)。

以此类推，我们会需要\(8个3，16个4….2^i个i\)。

——

这是在比i小的数字都不存在的情况下的状况。如果存在呢？

譬如存在\(4个3\)和\(8个4\)的情况下，Alice均分它们一次，变成了\(2个2\)和\(4个3\)，再一次，\(1个1和2个2\)，再把\(1和2\)分开，就满足了胜利条件。

或者Alice把\(3和4\)分开，为了防止下一轮出现\(4个2\)，Bob必须删除\(4个3\)，但\(8个4\)变成\(8个3\)，同样达到了Alice的胜利条件。

总之，比较小的数字在分裂过程中拖了几轮，就让比较大的数字“降了几阶”。

就像\(8个4\)变成\(8个3\)一样。

或者换言之，小的数字可以成倍替代大的数字。这个情景里\(4个3\)相当于\(8个4\)。

所以从小的数字开始，判断i是否有\(2^i\)个，有则Alice宣告胜利，否则它的点数贡献到后面。

详细的写法不做展开（因为累乘炸long long光荣地写挂了）

————

已知累乘真的会写炸，不管是记录指数还是直接硬乘（也许高精度是可以救的但是谁没事干写高精度啊）

那我们只能，拿来除了！

上面例子，既可以认为是\(4个3\)相当于\(8个4\)，当然也可以认为\(8个4\)相当于\(4个3\)嘛。

也就是\(num_x\)个\(x\)相当于\(num_x/2\)个\(x-1\)。

并且这样除到最后可以直接通到\(0\)的位置，判断起来比对着\(2^i\)个\(i\)舒服多了。

完整代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int world[100005];
    int n;
    cin>>n;
    int flag=0;
    for(int i=0;i<=n;i++){
        cin>>world[i];
    }
    for(int i=n;i>=0;i--){
        world[i-1]+=world[i]/2;
    }
    if(world[0]==0)printf("Bob\n");
    else printf("Alice\n");
}
int main(){
    int T;
    cin>>T;
    while(T--)solve();
    return 0;
}