首页 > 其他分享 >2023牛客多校7.17补题

2023牛客多校7.17补题

时间：2023-07-20 15:22:18浏览次数：39  
标签：ch int long 牛客 while 7.17 补题 && getchar

当时就做了两道签到题DJ，这两天补了四道简单题HKLM

D-Chocolate

题意：\(n × m\) 的巧克力，Kelin先手，Walk Alone后手，每人每次拿走一块左下角为\((1,1)\)的子矩形的巧克力，谁拿走 \((n, m)\) 处的巧克力谁输。

分析：这是一道结论题，只有\(1 × 1\)的时候后手赢，其余情况下都是先手赢。证明不会，当时就是随手推了\(1 × n\)、\(2 × n\)、\(3 × 3\)、\(3 × 4\)这些情况，发现都是先手赢，然后就大胆猜想出了结论。

J-Roulette

题意：Walk Alone 初始有 n 块钱，每次投入 x 元，有一半的概率输掉这 x 元，另一半概率赢得 2x 元。现在 Walk Alone 采取下述策略投注：如果上一把赢了，这一把投 \(x_i = 1\) 元；如果上一把输了，这一把投 \(x_i = 2x_{i−1}\) 元。问 Walk Alone 有多大概率拿到 n + m 元离开。

分析：容易发现只要赢一把就是赚1块钱，就是说不论前面连输多少把，对于一组“输输......输输赢”都是赚1块钱，因此总共要赢m把。但是直接算赢m把的概率不好算，考虑算输掉的概率，也就是说连输的情况下无法支付下一次应该投入的钱。假设现在手上有x块钱，考虑连输最多能输y把，则能够从x变成x+1块钱的概率就是\(1-2^{-y}\)。对于每个x，y都是可以预处理出的。例如\(x \epsilon [1,2]\)时\(y=1\)，\(x \epsilon [3,6]\)时\(y=2\)，规律就是\(x \epsilon [2^i-1,2^{i+1}-2]\)时\(y=i\).

算的时候分成三个部分计算贡献即可，\(n\)所在的区间、中间跨越的区间以及\(n+m\)所在的区间，然后特判\(n\)和\(n+m\)同属一个区间的情况。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
const int M=150005;
const int mod=998244353;
const int inf=1e9;
ll base[50];
ll quickpow(ll a,ll b){
	ll ret=1;
	while(b){
		if(b&1)ret=(1ll*ret*a)%mod;
		a=(1ll*a*a)%mod;
		b>>=1;
	}
	return ret;
}
int main(){
	//int n=read(),m=read();
	ll n,m;
	cin>>n>>m;
	base[0]=1;
	for(int i=1;i<=31;++i){
		base[i]=base[i-1]*2ll;
	}
	ll nn,mm;
	ll ans=1;
	//cout<<base[30]<<" "<<base[31]<<endl;
	//cout<<quickpow(2,mod-2)<<endl;
	for(nn=1;nn<=30;++nn){
		if(base[nn]-1<=n&&n<=base[nn+1]-2)break;
	}
	for(mm=1;mm<=30;++mm){
		if(base[mm]-1<=n+m&&n+m<=base[mm+1]-2)break;
	}
	if(nn==mm){
		ll cnt1=m;
		ans=(1ll*ans*quickpow(base[nn]-1,cnt1)%mod*quickpow(quickpow(base[nn],mod-2),cnt1)%mod)%mod;
	}
	else{
		ll cnt1=base[nn+1]-2-n+1;
		ans=(1ll*ans*quickpow(base[nn]-1,cnt1)%mod*quickpow(quickpow(base[nn],mod-2),cnt1)%mod)%mod;
		ll cnt2=n+m-(base[mm]-1);
		//cout<<cnt1<<" "<<cnt2<<endl;
		ans=(1ll*ans*quickpow(base[mm]-1,cnt2)%mod*quickpow(quickpow(base[mm],mod-2),cnt2)%mod)%mod;
		for(ll i=nn+1;i<=mm-1;++i){
			ans=(1ll*ans*quickpow(base[i]-1,base[i])%mod*quickpow(quickpow(base[i],mod-2),base[i])%mod)%mod;
		}	
	}
	cout<<ans<<endl;
	return 0;
}

H-Matches

题意：给定两个长度为 n 的序列\(a_i,b_i\)，现在可以选择其中一个序列交换其中的两个数字，问经过至多一次操作后最小的\(\sum_{i=1}^n|a_i-b_i|\)是多少。

分析：交换哪个序列都一样，需要自己分类讨论各种情况然后发现只有两种情况下的交换有意义。对于\((a_x,b_x),(a_y,b_y)\)，第一种情况就是\((a_x-a_y)(b_x-b_y)<0\)且两个区间是包含的关系，此时交换\(a_x\)和\(a_y\)，可以获得 \(2*\)[被包含的区间的长度] 的收益。第二种情况就是\((a_x-a_y)(b_x-b_y)<0\)且两个区间是相交的关系，此时交换\(a_x\)和\(a_y\)，可以获得 \(2*\)[区间相交长度] 的收益。

将所有的 \((a_i, b_i)\) 分为 \(a_i < b_i\) 与 \(a_i > b_i\) 两类，记为 S 和 T。对于T中每个元素，去S中二分查找满足上述两种情况的区间并计算收益值，找到最大收益值即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e6+5;
const int M=4e5+5;
const int mod=998244353;
const int inf=1e9;
int a[N],b[N];
int lg[N],f[N][25];
struct node{
	int l,r;
}S[N],T[N],SS[N];
vector<int>sx,sy,sl;
bool cmp(node x,node y){
	return x.l<y.l;
}
int main(){
	int n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i)b[i]=read();
	ll sum=0;
	int s=0,t=0;
	for(int i=1;i<=n;++i){
		sum+=abs(a[i]-b[i]);
		if(a[i]<b[i]){
			S[++s].l=a[i];
			S[s].r=b[i];
		}
		else if(a[i]>b[i]){
			T[++t].l=b[i];
			T[t].r=a[i];
		}
	}
	sort(S+1,S+s+1,cmp);
	int nowr=-(2*inf);
	for(int i=1;i<=s;++i){
		if(S[i].r<=nowr)continue;
		nowr=S[i].r;
		sx.push_back(S[i].l);
		sy.push_back(S[i].r);
		sl.push_back(S[i].r-S[i].l);
	}
//	for(int i=1;i<=s;++i){
//		sx.push_back(S[i].l);
//		sy.push_back(S[i].r);
//		sl.push_back(S[i].r-S[i].l);
//	}
	lg[0]=-1;
	for(int i=1;i<=sl.size();i++)
		f[i][0]=sl[i-1],lg[i]=lg[i>>1]+1;
	for(int j=1;j<=20;j++)
    	for(int i=1;i+(1<<j)-1<=sl.size();i++)
        	f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
	int ans=0;
	for(int i=1;i<=t;++i){
		int x=T[i].l,y=T[i].r;
		int ret=0;
        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)ret=max(ret,min(y,sy[l-1])-x);
        if(r<sx.size())ret=max(ret,y-max(x,sx[r]));
        if(r>l){
        	int k=lg[r-l];
    		ret=max(ret,max(f[l+1][k],f[r-(1<<k)+1][k]));
		}
        ans=max(ans,ret);
	}
	cout<<sum-2ll*ans<<endl;
	return 0;
}

K-Subdivision

题意：给定一个无向图 \(G(n, m)\)，可以向其中任意一条边中插入任意多个点，可以操作任意多次（也可以不操作）。问经过这样处理之后，从 1 号节点出发，至多走 k 步最多可以到多少个节点。

分析：构造出bfs树，无向图中的非树边可以插入任意多个点都不影响原来节点的深度，无向图中的树边如果其一端是叶子节点就可以插入若干点使得该叶子节点的深度变为k即可，否则保持不变。这样做的原因是保证原图中的合法点仍然合法（插入一个合法点而让原本合法的点变得不合法毫无意义）且插入的点所在边的深度尽可能大（其对原图对其它非树边的影响尽可能小）。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
const int M=4e5+5;
const int mod=998244353;
const int inf=1e9;
int n,m,k;
int vis[N],dep[N],p[N],out[N],fa[N];
vector<int>q[N];
void bfs(){
	int l=0,r=1;p[1]=1;
	vis[1]=1;
	while(l<r){
		int u=p[++l];
		for(int i=0;i<q[u].size();++i){
			int v=q[u][i];
			if(vis[v])continue;
			vis[v]=1;
			dep[v]=dep[u]+1; 
			p[++r]=v;
			++out[u];
			fa[v]=u;
		}
	}
}
int main(){
	n=read();m=read();k=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read();
		q[u].push_back(v);
		q[v].push_back(u);
	}
	bfs();
	ll ans=1;
	for(int u=2;u<=n;++u){
		if(!vis[u]||dep[u]>k)continue;
		int cnt=0;
		for(int i=0;i<q[u].size();++i){
			int v=q[u][i];
			if(fa[v]==u||fa[u]==v)continue;
			++cnt;
		}
		if(!out[u])cnt=max(cnt,1);	
		ans+=1ll*(k-dep[u])*cnt+1ll;
	}
	cout<<ans<<endl;
	return 0;
}

L-Three Permutations

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
const int M=4e5+5;
const int mod=998244353;
const ll inf=1e18;
int a[N],b[N],c[N];
int fa[N],fb[N],fc[N];
int abc[N],bca[N],cab[N];
int disa[N],disb[N],disc[N];
ll A[5],B[5];
int lena,lenb,lenc;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return d;
}
ll ex_intchina(){
    ll ans=A[1],M=B[1];
    for(int i=2;i<=3;i++){
		ll c=((A[i]-ans)%B[i]+B[i])%B[i];
		ll x,y,gcd=exgcd(M,B[i],x,y);
		if(c%gcd!=0)return -1;
		x=x*(c/gcd);//quickmul(x,c/gcd,b[i]);当前第i个方程的解
		ans+=x*M;//更新前i个方程组的解ans
		M*=B[i]/gcd;//更新M(所有模数的最小公倍数)
		ans=(ans%M+M)%M;
    }
    return ans;
}
ll solve(int x,int y,int z){
	A[1]=disa[x];B[1]=lena;
	A[2]=disb[y];B[2]=lenb;
	A[3]=disc[z];B[3]=lenc;
	if(A[1]==-1||A[2]==-1||A[3]==-1)return inf;
	ll now=ex_intchina();
	if(now==-1)return inf;
	else return now;
}
int main(){
	int n=read();
	for(int i=1;i<=n;++i)a[i]=read(),fa[a[i]]=i;
	for(int i=1;i<=n;++i)b[i]=read(),fb[b[i]]=i;
	for(int i=1;i<=n;++i)c[i]=read(),fc[c[i]]=i;
	for(int i=1;i<=n;++i)abc[i]=a[b[c[i]]];
	for(int i=1;i<=n;++i)bca[i]=b[c[a[i]]];
	for(int i=1;i<=n;++i)cab[i]=c[a[b[i]]];
	memset(disa,-1,sizeof(disa));
	memset(disb,-1,sizeof(disb));
	memset(disc,-1,sizeof(disc));
	lena=0,lenb=0,lenc=0;
	for(int i=1;disa[i]==-1;i=abc[i]){
		disa[i]=lena;
		++lena;
	}
	for(int i=1;disb[i]==-1;i=bca[i]){
		disb[i]=lenb;
		++lenb;
	}
	for(int i=1;disc[i]==-1;i=cab[i]){
		disc[i]=lenc;
		++lenc;
	}
	//cout<<lena<<" "<<lenb<<" "<<lenc<<endl;
	int q=read();
	while(q--){
		int x=read(),y=read(),z=read();
		ll ans1=solve(x,y,z);
		//cout<<ans1<<" ";
		ll ans2=solve(fc[z],fa[x],fb[y]);
		//cout<<ans2<<" ";
		ll ans3=solve(fc[fb[y]],fa[fc[z]],fb[fa[x]]);
		//cout<<ans3<<endl;
		ll ans=min(3ll*ans1,min(3ll*ans2+1ll,3ll*ans3+2ll));
		if(ans>=inf)cout<<"-1"<<endl;
		else cout<<ans<<endl;
	}
	return 0;
}

M-Water

题意:给两个容积分别为 A,B 的水杯，每次可以执行以下的四种操作之一：把其中一个水杯装满水。把其中一个水杯中的全部水倒掉。把其中一个水杯中现有的水全部喝完。把一个杯子中的水尽可能转移到另一个水杯中，水不溢出。求喝掉恰好 x 体积的水，最少要操作几次。

分析：记 \((r,s) = rA + sB\)，则两个杯子中的水和喝掉的水在任意时刻都能表示成 (r,s) 的形式，因此x不能被\(gcd(A,B)\)整除时无解，否则答案为\(max(2(r_0 + s_0), 2|r_0 − s_0| − 1)\)，其中\(r_0,s_0\)满足\(r_0A+s_0B=x\)。运用exgcd求出\((r,s)\)的特解然后移动到原点附近求上述式子的最小值即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=1e5+5;
const int M=4e5+5;
const int mod=998244353;
const ll inf=1e18;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return d;
}
int main(){
	int T=read();
	while(T--){
		ll A,B,x;cin>>A>>B>>x;
		ll x0,y0,d;
		d=exgcd(A,B,x0,y0);
		if(x%d!=0){
			cout<<"-1"<<endl;
			continue;
		}
		ll x1=x0*(x/d),y1=y0*(x/d);//一组特解 
		A/=d;B/=d;
		ll ans=inf;
		ll k0=-(x1/B);
		for(ll k=k0-1;k<=k0+1;++k){
			ll r=x1+k*B,s=y1-k*A;
			if(r>=0&&s>=0)ans=min(ans,2*(r+s));
        	else ans=min(ans,2*(abs(r)+abs(s))-1);
		} 
		k0=(y1/A);
		for(ll k=k0-1;k<=k0+1;++k){
			ll r=x1+k*B,s=y1-k*A;
			if(r>=0&&s>=0)ans=min(ans,2*(r+s));
        	else ans=min(ans,2*(abs(r)+abs(s))-1);
		}
		cout<<ans<<endl;
	}
	return 0;
}

标签：ch,int,long,牛客,while,7.17,补题,&&,getchar
From： https://www.cnblogs.com/PPXppx/p/17568382.html

相关文章

  • 牛客暑假多校 2023 第一场
    目录写在前面LH写在前面比赛地址：https://ac.nowcoder.com/acm/contest/57355。官方题解写得太好了都感觉没有自己整理的必要。简单写写有启发性的东西。我是垃圾。L发现进行三次操作后有：\[(x,y,z)\rightarrow(a_{b_{c_x}},b_{c_{a_{y}}},c_{a_{b_{z}}})\]每个位置仅......
  • 7.17~7.18 DP专场
    CF1814EChainChips好久没写这种题了~~不带修时，为了让总距离和最短，考虑让相邻的车互换位置，但如果单纯这样有可能剩下一辆车，那就让相邻的三辆车换一下。发现当车的个数\(x\ge4\)时，都可以拆成\(2\)辆或\(3\)辆车。对应到边就是只能选相邻的一条边或两条边。设\(dp_i\)......
  • 7.17-软件指令学习
      ......
  • 2023牛客多校第一场
    目录牛客多校第一场D题J题H题牛客多校第一场比赛地址：传送门D题题意：有一个\(n\timesm\)的网格，每格放了块巧克力。WalkAlone（懵哥）和Kelin轮流吃巧克力，Kelin先吃。每轮一个人能选择一个左下角为(1,1)的子矩形，把里面的巧克力吃光，且至少要吃一个，吃到最后一个巧克力的人......
  • “范式杯”2023牛客暑期多校训练营1 蒻蒟题解
    A.AlmostCorrect题意：给定一个01串，要求构造一系列排序操作(xi,yi)，使得经过这些排序操作后可以使与给定01串等长的所有其他01串完全排好序，而给定的01串无法完全排好序Solution构造题我们考虑到对0和1的位置进行统计，统计得出最左边的1的位置为l，最右边的0的位置为r我们进行三次......
  • 牛客网-活动礼品采购
    1.题目读题 小V负责一次活动礼品采购，每一款礼品的受欢迎程度（热度值）各不相同，现给出总金额以及各礼品的单价和热度值，且每个礼拜只采购一个，如何购买可以使得所有礼品的总热度值最高。（背包问题）输入：第一行是一个整数，表示总金额（不大于1000）第二行是一个长度为n的正整数数组，表示礼......
  • 7.17
    之前已经掌握到秘诀了所以明天都去的比较晚。昨天去场地模拟了几把，觉得还行也过了一把。就连的比较随意了。差不多完了40来分钟才到，来了刚好轮到我了。等着练完车回家，今天吃早饭了，不饿了。回来稍微带了一下就中午了，中午做了饭吃了点饭睡了个午觉，醒了写了会作业，看了会书，今天才开始......
  • 牛客网-手机屏幕解锁模式
    1.题目读题[编程题]手机屏幕解锁模式  手机屏幕解锁模式现有一个3x3规格的Android智能手机锁屏程序和两个正整数m和n，请计算出使用最少m个键和最多n个键可以解锁该屏幕的所有有效模式总数。其中有效模式是指：1、每个模式必须连接至少m个键和最多n个键；2、所有的......
  • 牛客网-报数
    1.题目读题[编程题]报数今年7月份迎来了新入职的大学生，现在需要为每个新同事分配一个工号。人力资源部同事小v设计了一个方法为每个人进行排序并分配最终的工号，具体规则是：将N（N<10000）个人排成一排，从第1个人开始报数；如果报数是M的倍数就出列，报到队尾后则回到队头继续报，直到所......
  • 牛客网-vivo智能手机产能
    1.题目读题vivo智能手机产能(AC)在vivo产线上，每位职工随着对手机加工流程认识的熟悉和经验的增加，日产量也会不断攀升。假设第一天量产1台，接下来2天(即第二、三天)每天量产2件，接下来3天(即第四、五、六天)每天量产3件……以此类推，请编程计算出第n天总共可以量产的手机数量。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99