首页 > 其他分享 >“范式杯”2023牛客暑期多校训练营1 蒻蒟题解

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

时间：2023-07-19 11:47:36浏览次数：42  
标签：max return int 题解 多校 牛客 ans 排序 mx

A.Almost Correct

题意：给定一个01串，要求构造一系列排序操作(xi,yi)，使得经过这些排序操作后可以使与给定01串等长的所有其他01串完全排好序，而给定的01串无法完全排好序

Solution

构造题

我们考虑到对0和1的位置进行统计，统计得出最左边的1的位置为l，最右边的0的位置为r

我们进行三次排序

第一次排序：对l和所有其他的1的位置进行排序，对r和所有其他的0的位置进行排序

第二次排序：对除了l和r以外的数进行排序

第三次排序：将l和r不断靠拢直到变为0000...0010111111..111的情况

如果l和r上有一个数是不对的话，那么最后经过一系列操作肯定可以排好序

如果l和r上都是对的话，考虑其他的0和1，如果当中出现了一个错误的0/1，那么经过第一次排序，将会使得l和r上面出现错误的数

void solve()
{
    int n;cin>>n;
    string s;cin>>s;
    vector<int>s0,s1;
    for(int i=0;i<s.length();i++)
    {
        if(s[i]=='0')s0.push_back(i+1);
        else s1.push_back(i+1);
    }
    int r=s0.back(),l=*(s1.begin());
    //cout<<l<<r<<"\n";
    vector<pii>ans;
    for(auto it:s0)if(it!=r)ans.push_back({min(it,r),max(it,r)});
    for(auto it:s1)if(it!=l)ans.push_back({min(it,l),max(it,l)});
     
 
    for(int i=1;i<=n;i++)
    {
        if(i==l||i==r)continue;
        for(int j=i+1;j<=n;j++)
        {
            if(j==l||j==r)continue;
            ans.push_back({i,j});
        }
    }
     
    for(int i=s0.size()+1;i<r;i++)ans.push_back({i,r});
    for(int i=n;i>r;i--)ans.push_back({r,i});
     
    for(int i=s0.size();i>l;i--)ans.push_back({l,i});
    for(int i=1;i<l;i++)ans.push_back({i,l});
     
    cout<<ans.size()<<"\n";
    for(auto &[x,y]:ans)
    {
        cout<<x<<" "<<y<<"\n";
    }
}

D.Chocolate

题意：有一个矩阵巧克力，长n宽m，懵哥和Kelin轮流选一个点（i,j)，吃掉所有x<=i,y<=j的部分，吃掉最后一块巧克力的人输掉，Kelin先吃，问谁会赢

Solution

结论题

当n=1且m=1时懵哥获胜，否则Kelin获胜

证明也很好证

n=1,m=1的不用说

n=1,m!=1或者n!=1,m=1的也不用说

看n>1和m>1的情况

我们假设Kelin先吃(n-1,m-1)的部分，这时候懵哥为了获胜肯定只会选择某一边上的一部分，那么他吃的剩下多少，我们就使得另一边也剩多少，最后懵哥必定吃掉最后一块巧克力

void solve()
{
    cin>>n>>m;
    if(n==1&&m==1)cout<<"Walk Alone\n";
    else cout<<"Kelin\n";
}

H.Matches

题意：给出两个数组a和b，令

\[sum=\sum_{i=1}^{n}|a_i-b_i| \]

可以进行最多一次交换操作，交换同数组内的两个数，问sum最小是多少

Solution

我们定义a[i]和b[i]与a[j]和b[j]两对数的大小关系相同的为正序，不相同的为反序

通过计算会使得答案变小的操作只有交换反序相交和反序包络的情况，即相互反序且有交集的

我们考虑把(a[i],b[i])都放到一个数组里排序，将它们按第一关键字左端点升序和第二关键字右端点升序排序

我们从头到尾开始遍历，并记录一下反序的最大的右端点mx

先以b[i]>a[i]为正序，如果当前的是正序，那么就与mx右端点比较，看是包络还是相交，并更新最大的变化值，如果是反序则更新mx

再以a[i]>b[i]为正序，重复上述操作即可

int a[N];
int b[N];
int n;
struct node
{
    int x,y,z;
     
    bool operator < (const node&t)const &{
        if(x!=t.x)return x<t.x;
        return y<t.y;
    }
};
 
vector<node>v;
 
void solve()
{
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)
    {
        sum+=abs(a[i]-b[i]);
        if(a[i]<b[i])v.push_back({a[i],b[i],0});
        else if(a[i]>b[i])v.push_back({b[i],a[i],1});
    }
    int mx=-1e18;
    int temp=0;
    sort(v.begin(),v.end());
    for(auto it:v)
    {
        if(it.z==1)mx=max(mx,it.y);
        else if(mx>it.y)
        {
            temp=max(temp,2*(it.y-it.x));
        }else
        {
            temp=max(temp,2*(mx-it.x));
        }
        //cout<<mx<<" "<<it.x<<" "<<it.y<<" "<<temp<<"\n";
    }
    //cout<<sum-temp<<"\n";
    mx=-1e18;
    for(auto it:v)
    {
        if(it.z==0)mx=max(mx,it.y);
        else if(mx>it.y)
        {
            temp=max(temp,2*(it.y-it.x));
        }else
        {
            temp=max(temp,2*(mx-it.x));
        }
    }
    cout<<sum-temp<<"\n";
}

J.Roulette

题意：懵哥赌博，每次赌赢的概率都是0.5，他最开始有n元，想获得额外的m元，假设懵哥花了x块钱赌下一轮

如果懵哥赌赢了，他将获得2x元，并且下一次只会花1块钱

如果懵哥赌输了，他下次会花2x元

懵哥第一轮会花1元，并且会在获得n+m元时停止赌博

问懵哥额外获得n+m元的概率是多少

Solution

通过题意其实可以知道，无论输了多少次，如果当前赢了一把，其实就是在没输之前的情况下额外获得了一块钱而已

假设当前的钱数可以让他输x[i]次（即输了x[i]次后就无法赌了）

那么答案概率就是

\[ans=\prod_{i=1}^{m}(1-(\frac{1}{2})^{x[i]}) \]

对于x[i]相同的我们可以预处理一下，然后对分子分母进行计算即可

void solve()
{
	a[0]=1;
	for(int i=1;i<=31;i++)a[i]=a[i-1]*2;
    cin>>n>>m;
    int sum=0;
    int cnt=0;
    int now=1;
    m=n+m;
    while(sum+now<=n)
    {
    	sum+=now;
    	now*=2;
    	cnt++;
    }
    int fz=1,fm=1;
    while(n<m)
    {
    	int pos=min(sum+now-1,m-1);
    	fz=(fz*ksm(a[cnt]-1,pos-n+1))%mod;
    	fm=(fm*ksm(a[cnt],pos-n+1))%mod;
    	cnt++;
    	sum+=now;
    	now*=2;
    	n=pos+1;
    }
    cout<<(fz*((ksm(fm,mod-2))%mod))%mod<<"\n";
}

K.Subdivision

题意：给出一个n个点m条边的无向图，每个边的长度为1，可以进行任意次以下操作

选择一个边(u,v)并删除，新加一个点w，新加两条边(u,w)和(w,v)，新加的边长度也为1

问最后与节点1距离不大于k的点有多少个

Solution

首先bfs遍历一遍图，这样保证每个点的距离是最小的，且是一颗树形的

我们把距离k以内的点的个数加入到答案的贡献内，现在考虑进行操作增加的贡献

现在我们看距离k以内的点相邻的边只有一条的，如果它的距离小于k，那么可以通过对它唯一相邻的边进行操作从而增加对答案的贡献

然后就是看其他的边了，因为我们最开始遍历呈现为一颗树形，且通过之前的操作已经使得整棵树不能在进行操作了，所以我们可以对除了树上以外的边进行操作

我们假设当前边连接的两个点的深度分别是dis[i]和dis[j]，那么其对应可以增加k-dis[i]和k-dis[j]个有效点

vector<int>e[N];
void add(int u,int v)
{
	e[u].push_back(v);
	e[v].push_back(u);
}
typedef pair<int,int> pii;
int d[N];
int vis[N];
struct node
{
	int x,y,z;
};
void solve()
{
	int n,m,k;cin>>n>>m>>k;

	int ans=0;
	set<pii>st;
	for(int i=1;i<=m;i++)
	{
		int u,v;cin>>u>>v;
		st.insert({min(u,v),max(u,v)});
		add(u,v);
	}
	queue<node>q;
	q.push({0,1,0});
	while(q.size())
	{
		node t=q.front();
		q.pop();
		if(vis[t.y])continue;
		vis[t.y]=1;
		if(t.z!=0)
		{
			st.erase({min(t.y,t.z),max(t.y,t.z)});
		}
		d[t.y]=t.x;
		for(auto it:e[t.y])
		{
			q.push({t.x+1,it,t.y});
		}
	}

	for(int i=1;i<=n;i++)
	{
		if(d[i]>k)continue;
		if(d[i]==0&&i!=1)continue;
		ans++;
		if(e[i].size()==1&&i!=1&&d[i]!=k)
		{
			ans+=k-d[i];
			d[i]=k;
		}
		//cout<<ans<<"\n";
	}
	for(auto it:st)
	{
		//cout<<"1\n";
		if(d[it.first]==0&&it.first!=1)continue;
		ans+=max(0LL,k-d[it.first])+max(0LL,k-d[it.second]);
	}
	cout<<ans<<"\n";
}

L.Three Permutations

题意：有三个长为n的数组a,b,c，最开始有三个数x=1，y=1，z=1，每隔一秒这三个数会变成a[y],b[z],c[x]，进行q次询问，每一次查询最开始的x,y,z需要最少多少秒才能变成x',y',z'

Solution

中国剩余定理

解线性同余方程

考虑到x,y,z每一秒变成的数与其他数有关，我们来看每隔三秒的情况

如果当前是x,y,z，那么下一轮将会变成a[b[c[x]]],b[c[a[y]]],c[a[b[z]]]

这样我们可以预处理多少轮以后x,y,z会变回1,1,1，以及每个数最少需要多少轮，可以获得关于x,y,z的三个同余方程，通过中国剩余定理我们可以得到一个同余方程，这个同余方程即我们需要的答案

int a[N];
int b[N];
int c[N];
int ia[N];
int ib[N];
int ic[N];
 
int exgcd(int a, int b, int &x, int &y) {
    if(!b)  
    { 
        x = 1; 
        y = 0;
        return a;
    }
    int ans = exgcd(b, a%b, x, y); 
    int t = x;
    x = y;
    y = t - a / b * y;
    return ans; 
}
 
pii excrt(pii l,pii r)
{
    int r1=l.first,m1=l.second;
    int r2=r.first,m2=r.second;
    if(r1==-1||r2==-1)return {-1,-1};
    int x,y;
    int g=exgcd(m1,m2,x,y);
    if((r2-r1)%g)return {-1,-1};
    int bg=m2/g;
    x*=((r2-r1))/g;
    x=(x%bg+bg)%bg;
    int L=(m1/g*m2);
    int R=r1+x*m1;
    return {R,L};
}
 
 
 
struct node
{
    int x,y,z;
};
 
int na[N];
int nb[N];
int nc[N];
 
int disa[N];
int disb[N];
int disc[N];
 
int lena=0,lenb=0,lenc=0;
 
const int inf=1e18;
 
int get(int x,int y,int z)
{
    if(disa[x]==-1||disb[y]==-1||disc[z]==-1)return inf;
    pii A={disa[x],lena};
    pii B={disb[y],lenb};
    pii C={disc[z],lenc};
    /*cout<<A.first<<" "<<A.second<<"\n";
    cout<<B.first<<" "<<B.second<<"\n";
    cout<<C.first<<" "<<C.second<<"\n";*/
    B=excrt(B,C);
    A=excrt(A,B);
    //cout<<A.first<<" "<<A.second<<"\n";
    if(A.first==-1)return inf;
    else return A.first;
    //return 1;
}
 
 
void solve()
{
    memset(disa,-1,sizeof(disa));
    memset(disb,-1,sizeof(disb));
    memset(disc,-1,sizeof(disc));
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)cin>>c[i];
     
    for(int i=1;i<=n;i++)ia[a[i]]=i;
    for(int i=1;i<=n;i++)ib[b[i]]=i;
    for(int i=1;i<=n;i++)ic[c[i]]=i;
     
    for(int i=1;i<=n;i++)na[i]=a[b[c[i]]];
    for(int i=1;i<=n;i++)nb[i]=b[c[a[i]]];
    for(int i=1;i<=n;i++)nc[i]=c[a[b[i]]];
     
     
    for(int i=1;disa[i]==-1;i=na[i],lena++)disa[i]=lena;
    for(int i=1;disb[i]==-1;i=nb[i],lenb++)disb[i]=lenb;
    for(int i=1;disc[i]==-1;i=nc[i],lenc++)disc[i]=lenc;
     
    int q;cin>>q;
    while(q--)
    {
        int x,y,z;cin>>x>>y>>z;
        get(x,y,z);
        int ans1=get(x,y,z);
        int ans2=get(ic[z],ia[x],ib[y]); //先往前走再走一步
        int ans3=get(ic[ib[y]],ia[ic[z]],ib[ia[x]]); //先往前走再走两步
        int ans=min({ans1*3,ans2*3+1,ans3*3+2});
        cout<<(ans>=inf?-1:ans)<<"\n";
    }
     
}

M.Water

题意：有一个容积为A和B的容器，现在可以进行以下操作

1.使其中一个容器装满水

2.倒掉其中一个容器的所有水

3.喝光一个容器中的所有水

4.将一个容器中的水转移到另一个，直到其中一个容器的水空或者另一个容器装满

问最少要进行多少次操作，才能使得恰好喝下x单位的水

Solution

我们可以令x=rA+sB

我们可以发现有两种情况，一种是r和s都大于0的情况，这样我们只需进行2(r+s)次操作：A装r次水，A喝r次水，B装s次水，B喝s次水

另一种是r和s有一个小于0的，具体证明看https://zhuanlan.zhihu.com/p/644323896

大致意思：

令A>B，r>0，s<0

可以看成喝下(r+s)杯(A+B)和(-s)杯(A-B)的

A+B的贡献就是2(r+s)

A-B的进行以下操作：

1.装满A

2.A转移到B

3.喝光A中的（即A-B单位的水）

4.倒掉B中的

其实除了最后一个以外其他的都要进行(-s)次操作，最后一个只用进行(-s-1)次，因为最后一次可以不用倒掉，那么就有贡献3*(-s)+(-s-1)即-4s-1

将两者贡献相加即2r-2s-1即2|r|+2|s|-1

通过扩展欧几里得可以得到r和s的一个答案

通过一系列操作使得(r,s)为离原点最小的一个点，并且更新答案，然后再对其周围的点进行更新即可

int exgcd(int a, int b, int &x, int &y) {
	if(!b)  
	{ 
		x = 1; 
		y = 0;
		return a;
	}
	int ans = exgcd(b, a%b, x, y); 
	int t = x;
	x = y;
	y = t - a / b * y;
	return ans; 
}

void solve()
{
	int a,b,c,x,y;cin>>a>>b>>c;
	int g=exgcd(a,b,x,y);
	if(c%g)
	{
		cout<<"-1\n";
		return;
	}
	a/=g;
	b/=g;
	c/=g;
	x*=c;
	x=(x%b+b)%b;
	y=(c-x*a)/b;;
	int ans=1e18;
	for(int i=-10;i<=10;i++)
	{
		int r=x+i*b,s=y-i*a;
		if(r>=0&&s>=0)ans=min(ans,2*(r+s));
		else ans=min(ans,2*(abs(r)+abs(s))-1);
	}
	cout<<ans<<"\n";
}

标签：max,return,int,题解,多校,牛客,ans,排序,mx
From： https://www.cnblogs.com/HikariFears/p/17565155.html

相关文章

  • 【SP21463 题解】
    Descirption给定\(n\timesm\)的矩阵，求最大子矩阵的面积满足每一行每一列都构成等差数列。Solution我们另\(up_{i,j}\)表示最小的\(k\)满足\((i,k),(i,k+1),\cdots,(i,j)\)构成等差数列，可以用\(\mathcalO(nm)\)求出。对于一个矩阵的左上角\((a,b)\)，右下......
  • 2023 杭电多校 Day1
    1009签到，队友哥切的，没看1002\(f(x,0/1/2)\)表示当前点没有覆盖/覆盖/放置观察点子树内最小代价，简单转移即可。f[x][1]=1e18;f[x][2]=a[x];f[x][0]=0;for(inty:e[x])if(y!=fx){ dfs(y,x); statici64g[3]; g[0]=g[1]=g[2]=1e18; g[1]=f[......
  • 2023杭电多校第一场
    手还是有点生(随便写点东西.jpg1001实际上把链找出来之后就可以把树扔了(然后在某个位置上出现的点它的出现位置就可以表示为$k*dis+b$，$b$是位置对于$S$的每个数字，找它在$T$的位置，能拿到两个同余方程，形如$x=t_1(modn)$和$x=t_2(modm)$找最小正整数解即可。代码是学弟......
  • 2023杭电多校第一场
    目录1002CityUpgrading1005CyclicallyIsomorphic1009Assertion比赛地址：传送门1002CityUpgrading思路：树形DP类似题：洛谷P2458保安站岗1005CyclicallyIsomorphic思路：最小表示法+判断最小表示法模板：洛谷P1368【模板】最小表示法1009Assertion鸽巢原理，不记......
  • 牛客网-活动礼品采购
    1.题目读题 小V负责一次活动礼品采购，每一款礼品的受欢迎程度（热度值）各不相同，现给出总金额以及各礼品的单价和热度值，且每个礼拜只采购一个，如何购买可以使得所有礼品的总热度值最高。（背包问题）输入：第一行是一个整数，表示总金额（不大于1000）第二行是一个长度为n的正整数数组，表示礼......
  • BZOJ 1461 题解
    考虑设计一个哈希函数\(hash(x)=f(x)\timesbase^x\)。其中\(f(x)\)表示\(\sum_{j=1}^{i-1}[j<i]\)。然后类似于滑动窗口计算区间哈希值，加入一个数就计算贡献，减去一个数就计算这个数产生了贡献，两个东西都可以树状数组维护，那么愉快做完了。#include<bits/stdc++.h>#de......
  • P5494 题解
    来一发\(O(\logn)\)线性空间的解法。考虑通过只维护线段树叶子节点的虚树的方法压缩空间，考虑记录下每个节点的编号，然后通过异或完求最低位的\(1\)的方式求出LCA的深度，然后记录下LCA右端点的编号。在回收节点的时候可以释放储存右端点编号的空间，但是这里为了方便就不这样......
  • UNR #7 Day2 T1 火星式选拔题解
    放一个比赛链接先考虑打完暴力后\(k=1\)的特殊性质。当队列容量为\(1\)时，队中的人\(i\)会被第一个满足\(i\leqj\)且\(b_i\leqa_j\)的人淘汰，并且队列中的人会变成\(j\)，考虑倍增加速这个过程，令\(f_{i,j}\)表示第\(i\)个人进队后淘汰过程发生\(2^j\)次后队......
  • P6684 题解
    真的卡不动了，但是我感觉我的思路还是有一些价值的，就来写一篇题解吧。考虑使用回滚莫队（不增）来维护，当区间删去一个点时相当于全局加入一条边，这个询问的本质是询问是否是二分图，所以考虑扩展值域并查集，这里使用路径压缩加按秩合并，记录下修改，在回滚时全部还原。总复杂度是\(O(n\sqr......
  • 「JOISC 2019 Day4」蛋糕拼接 3 题解
    先考虑这个式子：\(\sum_{j=1}^{M}|C_{k_{j}}-C_{k_{j+1}}|\)一定是在\(C\)有序时取到，具体证明很简单各位读者自己证明。那么现在式子变成：\(\sum{V}+2\times({C_{\max}-C_{\min}})\)这个时候一个常见的技巧是将\(C\)排序。这个时候就可以定义状态：\(dp_{i,j}=\s......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99