首页 > 编程语言 >华中农业大学2023年十二届程序设计竞赛(补题)

华中农业大学2023年十二届程序设计竞赛(补题)

时间:2023-04-21 11:36:07浏览次数:59  
标签:int 华中农业大学 back next ++ num 补题 2023 push

题目地址

B.写信

题意:有n个信封和n封信,问全部装错有多少种可能

Solution

全错排问题,对于i=k的情况,我们可以从i=k-1和i=k-2转移过来

一种是k-1个全错排,然后从前面k-1个选出一个信封与第k个交换

另一种是任选一个j,有1<=j<=k-1放在k,这样除了k和j以外还有k-2个数进行全错位排列,

这样我们可以得到递推公式:
$$
D_n=(n-1)(D_{n-1}+D_{n-2})
$$
化简后就有:
$$
D_{n+1}=(n+1)
D_n+(-1)^{n+1}
$$
这题数据量很大,我们采用分段打表的方式来计算

如果采用上面的公式的话要打两个表,采用下面的话只用打一个

int t[150]={ //t[0]=1
1,824182295,933713113,474482547,930651136,251064654,637937211,229643390,307311871,448853213,322273426,398890147,194914852,884947442,154199209,881788023,389699639,733217502,601739182,372305477,213823357,713959988,498202615,196342945,324300550,154001751,974475946,540773759,467881322,257531902,598680559,367927849,971346692,94577421,617165552,128327758,503709458,253566817,820144401,13965056,82358069,805941568,533047638,69430220,686678173,297170813,34546238,323435423,499126069,487532712,468899710,790590914,581347156,955359050,700529992,518280890,98592091,64544225,988209678,422603955,40661679,174468756,573631136,757555557,710709955,775098981,499158883,969149294,880429710,42564126,333697951,522067888,579797877,528967798,717694718,309384913,31308092,316850320,220854491,878646494,963974981,377654637,705101053,542246848,466289530,750036412,819636314,688721174,464087273,517164631,256789690,482685016,276682441,473333947,340221393,762927538,624766601,984537252,977632075,34192646,402182971,
};

void table() //打表
{
	int y=1;
	int next;
	int xx=1e7;
	for(int i=3;i<=1e9+5;i++)
	{
		next=i*y%mod;
		if(i&1)next=(next-1+mod)%mod;
		else next=(next+1)%mod;
		if(i%xx==0)cout<<next<<",";
		y=next;
	}
}

void solve()
{
	int n;cin>>n;
	int tt=1e7;
	int pos=n/tt;
	int ans=t[pos];
	for(int i=pos*tt+1;i<=n;i++)
	{
		ans=(ans*(i))%mod;
		if(i&1)ans=(ans-1+mod)%mod;
		else ans=(ans+1)%mod;
	}
	cout<<ans<<"\n";
	table();
}

E.兔兔的金铲铲

题意:给出n个数,要求进行最少的交换操作,使得对于所有i(i为奇数),a[i]和a[i+1]差的绝对值为1

Solution

没啥难的,赛时卡别的题没做出来,直接离散化然后模拟一遍就行了

int a[N];
int cnt[N];
int p[N];
int vis[N];
void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cnt[i]=a[i];
	sort(cnt+1,cnt+n+1);
	for(int i=1;i<n;i++)
	{
		if(cnt[i+1]-cnt[i]!=1)
		{
			cout<<"-1\n";
			return;
		}else i++;
	}
	for(int i=1;i<=n;i++)
	{
		a[i]=lower_bound(cnt+1,cnt+1+n,a[i])-cnt;
	}
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	for(int i=1;i<=n;i++)p[a[i]]=i;
	int ans=0;
	for(int i=1;i<=n;i++)
	{
		int x=a[i]-1;
		if(a[i]&1)x=a[i]+1;
		if(a[i+1]==x)
		{
			i++;
			continue;
		}else
		{
			int pos=p[x];
			swap(p[a[i+1]],p[x]);
			swap(a[i+1],a[pos]);
			ans++;
			i++;
		}
	}
	cout<<ans<<"\n";
}

F.图的动态染色

题意:

给出n个点和m条边,初始所有的点都为红色,进行q次操作:

1 x y:给x和y加一条边(如果x和y已经有边或者x=y则直接无视)

2 x (r/g/b):将点x变为红/绿/蓝色

3 x (r/g/b):输出点x所在连通块中红/绿/蓝色的点个数和x相邻点中红/绿/蓝色的点个数

Solution

不会做,题解说是分治,把连边数大于一个值的点设为特殊点,给所有点加一个vector用来存周围的特殊点,每次操作时对特殊点进行更新,这样对特殊点查询时直接O(1)查询,对其他点就直接暴力,至于连通块,很容易想到并查集,剩下就好写了

int find(int x)
{
	return t[x]==x?x:t[x]=find(t[x]);
}

void merge(int u,int v)
{
	int a=find(u),b=find(v);
	if(a!=b)
	{
		t[a]=b;
		p[b][0]+=p[a][0];
		p[b][1]+=p[a][1];
		p[b][2]+=p[a][2];
	}
}

void solve()
{
	int n,m,q;cin>>n>>m>>q;
	for(int i=1;i<=n;i++)
	{
		t[i]=i;
		col[i]=0;
		p[i][0]=1;
		p[i][1]=p[i][2]=0;
	}
	int maxm=1000;
	for(int i=1;i<=m;i++)
	{
		int u,v;cin>>u>>v;
		
		e[u].push_back(v);
		e[v].push_back(u);
        num[u]++;
        num[v]++;
		st[u].insert(v);
		st[v].insert(u);
		merge(u,v);
	}
	
	for(int i=1;i<=n;i++)
	{
		for(auto it:e[i])
		{
			if(num[it]>=maxm)
			{
				k[i].push_back(it);
				cnt[it][col[i]]++;
			}
		}
	}
	
	
	while(q--)
	{
		int op;cin>>op;
		if(op==1)
		{
			int u,v;cin>>u>>v;
			if(u==v)continue;
			if(st[u].count(v))continue;
			if(st[v].count(u))continue;
			e[u].push_back(v);
			e[v].push_back(u);
			num[u]++;
        	num[v]++;
			st[u].insert(v);
			st[v].insert(u);
			
			if(num[u]==maxm)
			{
				for(auto it:e[u])
				{
					k[it].push_back(u);
					cnt[u][col[it]]++;
				}
			}else if(num[u]>maxm)
			{
				cnt[u][col[v]]++;
			}
			if(num[v]==maxm)
			{
				for(auto it:e[v])
				{
					k[it].push_back(v);
					cnt[v][col[it]]++;
				}
			}else if(num[v]>maxm)
			{
				cnt[v][col[u]]++;
			}
			
			merge(u,v);
		}else if(op==2)
		{
			int x;char c;cin>>x>>c;
			int next=0;
			if(c=='g')next=1;
			else if(c=='b')next=2;
			for(auto it:k[x])
			{
				cnt[it][col[x]]--;
				cnt[it][next]++;
			}
			int z=find(x);
			p[z][col[x]]--;
			p[z][next]++;
			col[x]=next;
			
		}else if(op==3)
		{
			int x;char c;cin>>x>>c;
			int next=0;
			if(c=='g')next=1;
			else if(c=='b')next=2;
			int z=find(x);
			int res=0;
			int ans=p[z][next];
			if(num[x]>=maxm)
			{
				cout<<p[z][next]<<" "<<cnt[x][next]<<"\n";
				continue;
			}
			
			
			for(auto it:e[x])
			{
				if(col[it]==next)res++;
			}
			cout<<ans<<" "<<res<<"\n";
			
		}
	}
}

H.神奇石子

题意:有2n个数,分别为a1,a2,...,an和b1,b2,...,bn,对于i∈[1,n],从ai和bi中选一个数,得到一个长为n的数组,求选到的数中最大数和最小数之差的最小值

Solution

我们把ai和bi中小的数放在ai上,然后按ai升序排序,假设最开始只选a1,a2,...,an,那么答案为an-a1,之后每次把ai和bi交换,然后判断交换后的最大值和最小值之差和原答案的大小,这里用set存下选的值,因为set默认升序

int a[N];
int b[N];
struct node
{
	int x,y;
	bool operator < (const node &t) const&{
		if(x != t.x)return x < t.x;
		else return y < t.y;
	}
}e[N];

void solve()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	multiset<int>st;
	for(int i=1;i<=n;i++)
	{
		e[i].x=a[i];
		e[i].y=b[i];
		if(e[i].x>e[i].y)swap(e[i].x,e[i].y);
		st.insert(e[i].x);
	}
	sort(e+1,e+1+n);
	int ans=e[n].x-e[1].x;
	
	for(int i=1;i<=n;i++)
	{
		auto it=st.find(e[i].x);
		st.erase(it);
		st.insert(e[i].y);
		int last=*(st.rbegin());
		int first=*(st.begin());
		ans=min(ans,last-first);
	}
	cout<<ans<<"\n";
}

M.认真思考?抓紧时间!

题意:给出一颗树,可以进行3种操作

1 x y:查寻节点x到y的路径上边权的平方和

2 x y z:将节点x到节点y的路径所经过的边的边权增加z

3 x y z:将节点x到节点y的路径所经过的边的边权修改为z

Solution

树链剖分+线段树,因为不会所以去oi wiki学了,然后和小e哥哥调了一晚上代码,最后发现初始化建树错了,太板子了我也不会讲了(

附上oi wiki的树链剖分讲解

int fa[N],son[N],sz[N],top[N],dfn[N],dep[N];
vector<int>e[N];
map<int,int> a[N];
int b[N];
int n,m;
int idx;

void dfs1(int x,int pre)  //第一次递归处理深度,父节点,树大小,重儿子
{
	dep[x]=dep[pre]+1;
	sz[x]=1;
	fa[x]=pre;
	int hson=0;
	for(auto it:e[x])
	{
		if(it==pre)continue;
		dfs1(it,x);
		//b[it]=a[x][it];
		sz[x]+=sz[it];
		if(sz[it]>hson)
		{
			hson=sz[it];
			son[x]=it;
		}
		
	}
}

void dfs2(int x,int t)  //第二次递归处理重链顶部节点和dfs序(在线段树中的编号)
{
	top[x]=t;
	dfn[x]=++idx;
	if(!son[x])return;
	dfs2(son[x],t);
	for(auto it:e[x])
	{
		if(it==fa[x]||it==son[x])continue;
		dfs2(it,it);
	}
}


int lz1[N<<2],lz2[N<<2],sum1[N<<2],sum2[N<<2];//区间加标记,区间赋值标记,区间和,区间平方和

/*int mo(int x)
{
	return (x%p+p)%p;
}*/

/*void pushdown(int l, int r, int o)
{
    int mid = (l + r) >> 1, ls = o << 1, rs = o << 1 | 1;
    if(lz2[o] != -1)
    {
        int &w = lz2[o];
         
        sum2[ls] = w * w % p * (mid - l + 1) % p;
        sum2[rs] = w * w % p * (r - mid    ) % p;
         
        sum1[ls] = w * (mid - l + 1) % p;
        sum1[rs] = w * (r - mid    ) % p;
         
        lz2[ls] = lz2[rs] = w;
        lz1[ls] = lz1[rs] = 0;
        w = -1;
    }
    if(lz1[o])
    {
        int &w = lz1[o];
        sum2[ls] = mo(sum2[ls] + 2 * sum1[ls] * w % p + (mid - l + 1) * w % p * w % p);
        sum2[rs] = mo(sum2[rs] + 2 * sum1[rs] * w % p + (r - mid    ) * w % p * w % p);
         
        sum1[ls] = mo(sum1[ls] + (mid - l + 1) * w % p);
        sum1[rs] = mo(sum1[rs] + (r - mid    ) * w % p);
         
        lz1[ls] = mo(lz1[ls] + w);
        lz1[rs] = mo(lz1[rs] + w);
         
        w = 0;
    }
}*/

void pushdown(int l,int r,int rt)  //加标记<乘标记<覆盖标记,所以覆盖后要清空加标记
{
	int mid=(l+r)>>1;
	if(lz2[rt]!=-1)
	{
		sum1[rt<<1]=(mid-l+1)*lz2[rt]%mod;
		sum1[(rt<<1)|1]=(r-mid)*lz2[rt]%mod;
		
		sum2[rt<<1]=((mid-l+1)*lz2[rt]%mod)*lz2[rt]%mod;
		sum2[(rt<<1)|1]=((r-mid)*lz2[rt]%mod)*lz2[rt]%mod;
		
		lz2[rt<<1]=lz2[(rt<<1)|1]=lz2[rt];
		lz2[rt]=-1;
		lz1[rt<<1]=lz1[(rt<<1)|1]=0;
	}
	if(lz1[rt])
	{
		
		
		sum2[rt<<1]=((sum2[rt<<1]+(sum1[rt<<1]*2%mod*lz1[rt]%mod))%mod+((mid-l+1)*lz1[rt])%mod*lz1[rt]%mod)%mod;
		sum2[(rt<<1)|1]=((sum2[(rt<<1)|1]+(sum1[(rt<<1)|1]*2%mod*lz1[rt]%mod))%mod+((r-mid)*lz1[rt])%mod*lz1[rt]%mod)%mod;
		
		sum1[rt<<1]=(sum1[rt<<1]+(mid-l+1)%mod*lz1[rt]%mod)%mod;
		sum1[(rt<<1)|1]=(sum1[(rt<<1)|1]+(r-mid)%mod*lz1[rt]%mod)%mod;
		
		lz1[rt<<1]=(lz1[rt<<1]+lz1[rt])%mod;
		lz1[(rt<<1)|1]=(lz1[(rt<<1)|1]+lz1[rt])%mod;
		lz1[rt]=0;
	}
}


void modify(int l,int r,int L,int R,int rt,int x,int op)
{
	if(l>r)return;
	if(L<=l&&r<=R)
	{
		if(op==2)
		{
			//sum2[rt] = mo(sum2[rt] + 2 * sum1[rt] * x % p + (r - l + 1) * x % p * x % p);
			sum2[rt]=((sum2[rt]+sum1[rt]*2%mod*x%mod)%mod+x*x%mod*(r-l+1)%mod)%mod;
			//sum1[rt] = mo(sum1[rt] + (r - l + 1) * x % p);
			sum1[rt]=(sum1[rt]+(r-l+1)%mod*x%mod)%mod;
			lz1[rt]=(lz1[rt]+x)%mod;
		}else
		{
			sum1[rt]=(r-l+1)*x%mod;
			sum2[rt]=x*x%mod*(r-l+1)%mod;
			lz2[rt]=x%mod;
			lz1[rt]=0;
		}
		return;
	}
	int mid=(l+r)>>1;
	pushdown(l,r,rt);
	if(L<=mid)modify(l,mid,L,R,rt<<1,x,op);
	if(R>mid)modify(mid+1,r,L,R,(rt<<1)|1,x,op);
	sum1[rt]=(sum1[rt<<1]+sum1[(rt<<1)|1])%mod;
	sum2[rt]=(sum2[rt<<1]+sum2[(rt<<1)|1])%mod;
}

int query(int l,int r,int L,int R,int rt)
{
	if(l>r)return 0;
	if(L<=l&&r<=R)
	{
		return sum2[rt];
	}
	int mid=(l+r)>>1;
	pushdown(l,r,rt);
	int res=0;
	if(L<=mid)res=(res+query(l,mid,L,R,rt<<1))%mod;
	if(R>mid)res=(res+query(mid+1,r,L,R,(rt<<1)|1))%mod;
	sum1[rt]=(sum1[rt<<1]+sum1[(rt<<1)|1])%mod;
	sum2[rt]=(sum2[rt<<1]+sum2[(rt<<1)|1])%mod;
	return res;
}



void solve()
{
	cin>>n>>m;
	memset(lz2,-1,sizeof(lz2));
	for(int i=1;i<n;i++)
	{
		int u,v,w;cin>>u>>v>>w;
		e[u].push_back(v);
		e[v].push_back(u);
		a[u][v]=a[v][u]=w;
	}
	dfs1(1,0);
	dfs2(1,1);
	
	
	for(int i=1;i<=n;i++)b[dfn[i]]=a[i][fa[i]];
	
	/*for(int i=1;i<=n;i++)cout<<b[i]<<" ";
	cout<<"\n";*/
	
	for(int i=1;i<=n;i++)modify(1,n,i,i,1,b[i],3);
	
	while(m--)
	{
		int op;cin>>op;
		if(op==1)
		{
			int x,y;cin>>x>>y;
			int res=0;
			
    		while(top[x]!=top[y])
   			{
        		if(dep[top[x]]<dep[top[y]])swap(x,y);
        		res=(res+query(1,n,dfn[top[x]],dfn[x],1))%mod;
        		x=fa[top[x]];
    		}
    		if(dep[x]<dep[y])swap(x,y);
			res=(res+query(1,n,dfn[y]+1,dfn[x],1))%mod;
			
			cout<<res<<"\n";
			
		}else 
		{
			int x,y,z;cin>>x>>y>>z;
			
			while(top[x]!=top[y])
   			{
        		if(dep[top[x]]<dep[top[y]])swap(x,y);
        		modify(1,n,dfn[top[x]],dfn[x],1,z,op);
        		x=fa[top[x]];
    		}
    		if(dep[x]<dep[y])swap(x,y);
			modify(1,n,dfn[y]+1,dfn[x],1,z,op);
		}
	}
	/*for(int i=1;i<=n;i++)
	{
		cout<<"x="<<i<<" top[x]="<<top[i]<<"\n";
		cout<<query(1,n,dfn[top[i]]+1,dfn[i],1)<<"\n";
	}*/
}

标签:int,华中农业大学,back,next,++,num,补题,2023,push
From: https://www.cnblogs.com/HikariFears/p/17339765.html

相关文章

  • PyCharm安装教程【2023年】
    PyCharm2023最新版本安装详细教程: 访问JetBrains的官方网站,下载PyCharm最新版本的安装程序。  双击下载的安装程序,在弹出的安装向导中点击“下一步”。 阅读许可协议,并同意协议条款。  选择安装路径。默认情况下,PyCharm会安装在C:\ProgramFiles\JetBrains\PyC......
  • 【2023-04-20】匆匆过后
    20:00雨打江南树。一夜花开无数。绿叶渐成阴,下有游人归路。与君相逢处。不道春将暮。把酒祝东风,且莫愁、匆匆去。                                                 ——......
  • 【2023.04.21】幸运的猫(上)
    此文用来记录我家黑猫旺来出生和黑猫的初见是在19年的9月份,那时的我暑假留校后,给自己留了两周的假期回家这个暑假我周游了整个福大,拍了可能有二三十只流浪猫吧,认识了学校的所有流浪猫但是这只黑猫反而是我返校第一次见,开学后学校人多,加上我事情比较多,因此只匆匆拍了几张照片......
  • 2023年4月21日-关于远程feign调用实现文件上传下载
    一、客户需求:做一个查询程序,客户提供一个excel模板,将查询结果保存到excel模板中,上传到文件服务,供客户下载使用。二、代码实现//服务A,文件上传@ApiOperation("上传文件-demo")@PostMapping(value="/uploadDemo/{busType}/{billId}")publicResBeanuploadFile(@PathVariabl......
  • 2023年4月21日08:29:28
    昨天学了一天怎么去写博客,进度什么的比较慢,但是我的收获很大,看懂了很多以前没有看懂的东西,很高兴。今天先把材料写好,然后再开始学习博客,争取在星期天的的00:00之前把博客写完。学博客的时候,要去理解,自己不要沉溺在刷课的快感中,你要真正学到 东西才是最重要的。理解它们跑的逻辑......
  • 2023.4.20每日会议
    今天完成了什么:今天完成了对于数据插入时进行确认时碰到的问题,现在已经可以成功的让用户确认及修改数据以及删除数据了遇到了哪些困难:在完成昨天碰到的问题之后,紧接着就转向了根据消费类型以及消费金额来生成相应的总账单图,不知如何下手,明天打算完成这部分明天打算做什么:完成根......
  • 2023.4.20每日总结
    今天完成了什么:今天完成了对于数据插入时进行确认时碰到的问题,现在已经可以成功的让用户确认及修改数据以及删除数据了遇到了哪些困难:在完成昨天碰到的问题之后,紧接着就转向了根据消费类型以及消费金额来生成相应的总账单图,不知如何下手,明天打算完成这部分明天打算做什么:完成根......
  • 2023/4/20
    百钱百鸡问题公鸡5r/只  母鸡3r每只 小鸡1r/3只 #include<stdio.h>intmain(){intg,m,x;for(g=0;g<=20;g++)     //注意不能用 i , j 控制循环for(m=0;m<=33;m++){x=100-g-m; if(5*g+3*m+x/3.0==100)    //注意是3.0 printf("%......
  • Abbyy FineReader是什么软件 2023年有免费Abbyy软件的吗
    在数字化时代,数据处理和转换变得非常重要,AbbyyFineReader就是一款专门用于处理、转换和识别图像和PDF文件的软件。在本文中,我们将会详细介绍AbbyyFineReader的功能以及适合使用该软件的电脑。                         ......
  • 2023.4.20
    1//1.10数制转换2//给定一个M进制的数x,实现对x向任意的一个非M进制的数的转换3#include<stdio.h>4#defineMAXCHAR1015//字符转换为数字6intchar_to_num(charch);7//数字转换为字符8charnum_to_char(intnum);9//其它进制转换为十进制10longsou......