首页 > 其他分享 >NOIP2013提高组复赛day1解析

NOIP2013提高组复赛day1解析

时间:2023-09-02 17:35:49浏览次数:40  
标签:NOIP2013 int ll long day1 ans return 复赛 mod

1.

错误原因:想的太复杂

正解:

10^k轮,会使x号小伙伴变到(x+m*10^k)%n号,直接套用公式

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m,k,x;
ll quickPow(ll a,ll b,ll mod){
	ll ans=1;
	while(b){
		if(b&1)ans=((ans%mod)*(a%mod))%mod;
		a=((a%mod)*(a%mod))%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	cin>>n>>m>>k>>x;
	cout<<(x+(m%n)*quickPow(10,k,n))%n;
	return 0;
}

举一反三:

 

2.

错误原因:思路错误

正解:

这道题可以转化成为求逆序对的题,可以先把a和b都按升序排列,记录下标,再使用归并排序求解逆序对

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7,mod = 1e8-3;
struct node{
	int x,id;
}a[N],b[N];
ll aa[N],n,ans=0,t[N];
bool cmp(node x,node y){
	return x.x<y.x;
}
void merge(int l,int mid,int r){
	int i=l,j=mid+1,k=l;
	while(i<=mid&&j<=r){
		if(aa[i]>aa[j]){
			t[k++]=aa[j++];
			ans=(ans+mid-i+1)%mod;
		}else t[k++]=aa[i++];
	}
	while(i<=mid)t[k++]=aa[i++];
	while(j<=r)t[k++]=aa[j++];
	for(int i=l;i<=r;i++)aa[i]=t[i];
}
void mergesort(int l,int r){
	if(l<r){
		int mid=(l+r)/2;
		mergesort(l,mid);
		mergesort(mid+1,r);
		merge(l,mid,r); 
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].x,a[i].id=i;
	for(int i=1;i<=n;i++)cin>>b[i].x,b[i].id=i;
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
	for(int i=1;i<=n;i++)aa[a[i].id]=b[i].id;
	mergesort(1,n);
	cout<<ans%mod;
	return 0;
}

举一反三:

 

3.

错误原因:思路错误

正解:

这道题暴力做法复杂度太高,所以必须使用倍增的方法,先建出这张图的最大生成树,再使用多次dfs求解lca的倍增表,顺带记录深度dep,父节点t[x][0]等,使用lca来取最小值,就是答案

代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+39+7;
struct edg{
	int to,next,w;
}e[N];
struct edge{
	int x,y,z;
}E[N];
int n,m,q,head[N],cnt=0,fa[N],t[N][20],dep[N],dis[N][20];
bool vis[N];
void add(int x,int y,int z){
	e[++cnt]=(edg){y,head[x],z};
	head[x]=cnt;
}
bool cmp(edge a,edge b){
	return a.z>b.z;
}
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]); 
}
void dfs(int x){
	vis[x]=1;
	for(int i=1;i<=16;i++){
		t[x][i]=t[t[x][i-1]][i-1];
		dis[x][i]=min(dis[t[x][i-1]][i-1],dis[x][i-1]);
	}
	for(int i=head[x];~i;i=e[i].next){
		int y=e[i].to;
		if(!vis[y]){
			dep[y]=dep[x]+1;
			t[y][0]=x;
			dis[y][0]=e[i].w;
			dfs(y);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int tt=dep[x]-dep[y];
	for(int i=0;i<=16;i++){
		if(tt&(1<<i)){
			x=t[x][i];
		}
	}
	for(int i=16;i>=0;i--){
		if(t[x][i]!=t[y][i]){
			x=t[x][i];
			y=t[y][i];
		}
	}
	if(x==y)return x;
	return t[x][0];
}
int solve(int x,int y){
	int tt=dep[x]-dep[y];
	int ans=INT_MAX;
	for(int i=0;i<=16;i++){
		if(tt&(1<<i)){
			ans=min(ans,dis[x][i]);
			x=t[x][i];
		}
	}
	return ans;
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>E[i].x>>E[i].y>>E[i].z;
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(E+1,E+m+1,cmp);
	for(int i=1;i<=m;i++){
		int x=find(E[i].x),y=find(E[i].y);
		if(x!=y){
			fa[x]=y;
			add(E[i].x,E[i].y,E[i].z);
			add(E[i].y,E[i].x,E[i].z);
		}
	}
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			dep[i]=1;
			dfs(i);
		}
	}
	cin>>q;
	while(q--){
		int x,y;
		cin>>x>>y;
		if(find(x)!=find(y))cout<<-1<<'\n';
		else{
			int t=lca(x,y);
			cout<<min(solve(x,t),solve(y,t))<<'\n';
		}
	}
	return 0;
}

举一反三:

 

标签:NOIP2013,int,ll,long,day1,ans,return,复赛,mod
From: https://www.cnblogs.com/zhanghx-blogs/p/17673936.html

相关文章

  • py之路——day14-20230902:python内置方法
    作者:zb1、python内置方法:abs()方法:取绝对值all()方法:all(iterable),如果iterable中的所有元素都为空或True,则返回True,否则返回False#all()方法print(all([0,1,-2]))print(all([1,1,2]))print(all([]))D:\oldboy_py\venv\Scripts\python.exeD:/oldboy_py/day4-2023......
  • 超全面的JavaWeb笔记day10<Response&Request&路径&编码>
    1、Response2、Request3、路径4、编码请求响应流程图 response1、response概述response是Servlet.service方法的一个参数,类型为javax.servlet.http.HttpServletResponse。在客户端发出每个请求时,服务器都会创建一个response对象,并传入给Servlet.service()方法。response对象是用来......
  • Day12_文件的高级操作:控制文件指针移动
    1.文件高级操作:控制文件指针移动_12.模式0(参照物是文件开头位置)的示范: 3.模式1(参照物是当前指针所在位置)的示范:18.模式2(参照物是文件末尾位置,应该倒着移动)的示范: ......
  • Day12_文件操作的x模式和b模式
    1.x模式: 2.b模式: 3.b模式应用案例与文件循环读取_方式一: 4.b模式应用案例与文件循环读取_方式二:5.文本文件copy工具,读取写入新地址: ......
  • Day11_文件操作_1
    1.文件与文件模式介绍:2.打开文件: 3.文件内容的操作读写和文件关闭: 4.文件对象又称文件句柄,with连续读多个文件内容: ......
  • 20天 hot 100 速通计划-day19
    多维动态规划62.不同路径一个机器人位于一个mxn网格的左上角(起始点在下图中标记为“Start”)。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。问总共有多少条不同的路径?示例1:输入:m=3,n=7输出:28示例2:输入:m......
  • Day10_字符编码
    1.字符编码的发展史: 2.utf-8的总结_1: 3.utf-8的总结_2: ......
  • 低压电工证理论学习 Day1
    第一节电荷与电场电荷(Q)单位为库伦;电子(e)(负电荷)失去电子为带电正电荷,得到电子为带电负电荷。e=1.6×10的-19c。 电场电荷周围存在电场。F=QE,Q=电荷量,E=电场强度,F=电场力。电场强度E=F/Q=U/d,单位为V/m(伏每米)。空气电场强度超25~30KV/cm时,可能发生击穿放电。 电位与电压......
  • 每日一练 | 华为认证真题练习Day104
    1、下面关于免费ARP报文的作用描述错误的是()。A.在VRRP备份组中用来通告主备发生变换B.用于通告一个新的现AC地址:发送方更换网卡,AC地址发生改变,为了能够在AP表项老化前通告所有主机,发送方可以发送一个免费ARPC.用于检查重复的IP地址:正常情况下不会收到ARP回应,如果收到,则表明本网......
  • day127-springMVC的介绍与入门
    springMVC介绍与初始化介绍MVC是一种软件架构的思想,将软件按照模型、视图、控制器来划分M:Model,模型层,指工程中的JavaBean,作用是处理数据JavaBean分为两类:一类称为实体类Bean:专门存储业务数据的,如Student、User等一类称为业务处理Bean:指Service或Dao对象,专门用于处理......