“范式杯”2023牛客暑期多校训练营1

D.Chocolate

题意:有n*m的矩阵,分成n*m块,每一块都有一块巧克力,然后A和B两个人,进行博弈,选择一个下标(i,j),将左上角(1,1)到(i,j)的巧克力全部吃掉,如果谁是最后一个吃完全部巧克力,那么就输了(每人至少吃一块巧克力),问最后谁赢

题解:首先考虑一种特殊情况,即1*n,先手除了最后一块,其它全部吃掉,也就是只留一块巧克力给后手,这样后手就输了,先手赢;如果一开始就只有一块巧克力,那么先手输,后手赢

然后考虑能不能把n*m的二维转化成以上一维的情况

先手可以一开始拿掉最左上角1*1的矩形,使得留给后手的矩形有缺口

后手拿到有缺口的矩形,可以将其继续变成有缺口的矩形或者完整的矩形

而先手每次都可以继续留给后手有缺口的矩形(即不是完整的矩形)

这样的话,最终就会演变成后手将其变成完整的1*n的矩形,故先手赢

所以,只有当n和m都等于1的时候,先手输,其它情况都是先手赢

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
signed main()
{
    int n,m;
    cin>>n>>m;
    if(n==1&&m==1) puts("Walk Alone");
    else puts("Kelin");
    return 0;
}

K.Subdivision 

如图,用bfs一层一层搜

首先自身算一个点

如果遇到叶子节点,就加k-dist[t],比如样例2,k为3,从顶点1搜到2,2是叶子节点,所以加上k-dist[1]即3-1=2

对于1,3,4,5这种结构

如果遇到已经搜过的点,比如顶点1搜到3搜到4然后搜5,发现5已经搜过了(因为5离顶点的距离近),然后加上k-dist[4]=3-2=1

从顶点1搜到5搜到4,发现4已经被搜过了,然后加上k-dist[5]=3-1=2

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int dist[N];
int p[N];
bool st[N],leaf[N];
int n,m,k;
vector<vector<int>>e(N);
int res;
void bfs()
{
    queue<int>q;
    q.push(1);
    dist[1]=0;
    st[1]=true;
    while(q.size()){
        int t =q.front();
        q.pop();
        if(dist[t]>k) break;//如果1到t的最短距离大于k,就没必要更新它的出点了,直接break
        res++;//点t算一个点
        leaf[t]=true;//先假设t是叶子节点,
        for(auto v:e[t]){
            if(p[t]==v) continue;//如果遍历到它的父节点,父节点是已经遍历过的,那么就continue,
            leaf[t]=false;//如果它的下一层有点和它相连,那么它就不是叶子节点
            //如果点v每标记过才更新,保证每一个点只搜一次
            if(!st[v]){
                p[v]=t;//标记父节点,是为了不往上搜,只往下搜
                dist[v]=dist[t]+1;
                q.push(v);
                st[v]=true;
            }
            else res+=k-dist[t];//如果v已经被搜过了,那么就加上k-dist[t]
         }
         if(leaf[t]&&t!=1) res+=k-dist[t];//如果t是叶子节点并且它不是顶点,那么就加上k-dist[t]
    }
}
void solve()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    bfs();
    cout<<res<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

H.Matches 

将正序区间放在S中,逆序区间放在T中,然后,sum记录所有区间长度的和 

然后排序一下S,使得区间左端点从小到大排序,然后由于r记录此前区间最大右端点,如果区间右端点小于等于r,那么就continue,不把它的区间左端点放入Sx中,以及不把它的区间右端点放入Sy中,以及不把距离放在len中,因为左端点本来就升序排序,右端点右小于等于r,那么该段区间就包含于前面的区间,而我们要求正序区间和逆序区间相交的最大长度,肯定选择范围大的区间,所以该段区间就没必要放进去了,这样导致我们存放的区间左端点是升序的,右端点也是升序的

然后遍历T中的每一个区间左端点即为x,右端点记为y,在S中二分

三种情况:

找到S中左端点大于x的第一个区间,赋值给l,如果l>0,因为l是从0开始的嘛,所以前面的一个区间的左端点是小于等于x的,那么就会产生重叠部分,长度为min(y,Sy[l-1])-x

找到S中右端点大于等于y的第一个区间,赋值给r,如果r

如果l小于r,因为l是左端点大于x的第一个区间,r是右端点大于等于y的第一个区间,因为横纵坐标均升序,所以区间l到区间r-1都是包含在[x,y]中的,所以*max_element(len.begin()+l,len.begin()+r)遍历[len.begin()+l,len.begin()+r)

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define int long long
const int N=1e6+10;
typedef pair<int,int>PII;
vector<PII>S,T;
int n;
int a[N],b[N];
signed main()
{
    cin>>n;
    int sum=0;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
        for(int i=0;i<n;i++){
            if(a[i]<b[i])S.push_back({a[i],b[i]});
            else if(b[i]<a[i])T.push_back({b[i],a[i]});
            sum+=abs(a[i]-b[i]);
    }
    sort(S.begin(),S.end());
    vector<int>Sx,Sy,len;
    int r=-0x3f3f3f3f;
    for(auto u:S){
    if(u.second<=r)continue;
    r=max(r,u.second);
    Sx.push_back(u.first);Sy.push_back(u.second);len.push_back(u.second-u.first);
    }
    int m=Sx.size();
    int ans=0;
    //二分
     for(auto v:T){
         int x=v.first,y=v.second;
         int l=upper_bound(Sx.begin(),Sx.end(),x)-Sx.begin();
         int r=lower_bound(Sy.begin(),Sy.end(),y)-Sy.begin();
         if(l>0)ans=max(ans,min(y,Sy[l-1])-x);
         if(r<m)ans=max(ans,y-max(x,Sx[r]));
         if(l<r)ans=max(ans,*max_element(len.begin()+l,len.begin()+r));
     }    
     cout<<sum-2*ans<<endl;
     return 0;
}

J.Roulette 

首先第一把投了1块钱,假设输了,然后第二把投2块钱,假设输了,第三把投4块钱,假设输了,第四把投8块钱,假设赢了,得16块钱,那么一共输了7块钱,投了8块钱,那么一共是赚了1块钱

假设一开始就赢一把,就是投一块钱赢一块钱

所以不管前面输了多少把,还是一把都没输,赢一把就是赚一块钱

那么以输输输...输赢为一个周期,赚一块钱,需要赚m块钱就需要m个周期

算一个周期赢一块钱的概率:先求出最多能连输多少把,记为r,那么2^r-1即为连输r把输的钱,

2^r-1

我们只要将本金为n时赢一块钱的概率*本金为n+1时赢一块钱的概率*....*本金为(n+m-1)赢1块钱的概率

但是其实有某些区间的概率时一样的,[2^r-1,2^r-2],在这个区间里都是最多输r把,所以赢1块钱的概率一样

题目中要求概率取模,概率可以写成a/b的形式,然后除法取模的话,要写成(a*b的逆元)再取模

AC代码:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define int long long
#define endl '\n'
using namespace std;
const int mod=998244353;
//快速幂,快速求(a^k)%mod
int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = res * a %mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}
//求逆元
int infact(int x) {
    return qmi(x, mod - 2);
}
void solve()
{
    int n,m;
    cin>>n>>m;//n表示本金,m表示要挣到的钱
    m+=n;//现在m表示要挣到多少钱
    int res=1;
    while(n<m){    
        int r=log2(n+1);//本金为n时最多能连输r把
        //算出同样也是最多连输r把的最大本金再+1为nn,当本金在区间[n,nn-1]时,获胜的概率是一样的,都是1-(0.5)^r
        int nn=min(m,(1ll<<(r+1))-1); 
        //首先概率是个分数,涉及除法,然后取模操作的话,除以一个数转变成乘以它的逆元
        //然后分数就转变成了另一个数(通过分母乘以分子的逆元得到),接下来就用得到的新的数来代替表示概率,记为powvalue
        //其中(1/2)可以直接用1*2^(mod-2)=2^(mod-2)代替
        //(1/2)^r=2^(-r+1)*2^(-1)=2^(-r+1)*2^(mod-2)=2^(mod-1-r)
        //mod+1-2^(mod-1-r)即为赢一块钱的概率(通过逆元换成了另一个数,但是在模操作下是等效的)
     int powvalue=mod+1-qmi(2,mod-1-r);
        res*=qmi(powvalue,nn-n);
        res%=mod;
        n=nn;
    }
    cout<<res<<endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}