noip2013普及组复赛答案_noip2020初赛

noip2013普及组复赛答案_noip2020初赛Prob.1转圈游戏找到循环节,然后快速幂。代码:#include<cstdio>#include<cstring>#include<iostream>usingnamespacestd;intpos[1000005],vis[1000000];intn,m,k,x,p,mod;intpow(…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

    • Prob.1 转圈游戏

找到循环节,然后快速幂。
代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int pos[1000005],vis[1000000];
int n,m,k,x,p,mod;
int pow(int a,int b){
	int now=1;
	while(b){
		if(b&1) now=1ll*now*a%mod;
		a=1ll*a*a%mod; 
		b>>=1; 
	}
	return now;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&k,&x);
	while(!vis[x]){
		vis[x]=1; pos[mod++]=x;
		x=(x+m)%n;
	}
	p=pow(10,k);
	printf("%d",pos[p]);
	return 0;
}

Jetbrains全家桶1年46,售后保障稳定

 

    • Prob.2 火柴排队

骚操作啊。我太菜了。
首先,(由于每一列的高度互不相同),我们把每一列分别按高度从小到大的顺序给以每个元素排名,
那么最小的距离和就是 两列中相同的排名两两对应 所计算出来的值。
证明的话,可以考虑交换两个组合的元素,发现计算出的权值只会变大。

为了把相同的名次对应,
所以就是要把两个序列都从小到大排序或者都从大到小排序么?
蠢蠢的我想到了上面这个东西,但显然错了,然后我就不知道如何搞了。

正解:
其实两列的交换是等价且相互的
也就是说,我们可以只通过对第一列进行交换达到相同名次对应的目的。

所以我们映射出第一个序列的每个元素在第二个序列中的出现的位置,得到一个新的序列,
求出这个新的序列的逆序对数就是答案了。
(这个题太强辣。%%%)
代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm> 
#define MAXN 100005
using namespace std;
const int mod=99999997;
int cc[MAXN],A[MAXN],B[MAXN],p[MAXN];
int n,ans;
void readwork(int *a){
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),cc[i]=a[i];
	sort(cc+1,cc+n+1);
	for(int i=1;i<=n;i++) a[i]=lower_bound(cc+1,cc+n+1,a[i])-cc;
}
void merge(int *a,int l,int r){
	static int tmp[MAXN];
	if(l==r) return;
	int mid=(l+r)>>1;
	merge(a,l,mid);
	merge(a,mid+1,r);
	int h=l,t=mid+1,pp=l;
	while(h<=mid&&t<=r){
		if(a[h]<a[t]) tmp[pp++]=a[h++];
		else ans=(1ll*ans+mid-h+1)%mod,tmp[pp++]=a[t++];
	}
	while(h<=mid) tmp[pp++]=a[h++];
	while(t<=r) tmp[pp++]=a[t++];
	for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main(){
	scanf("%d",&n);
	readwork(A); readwork(B);
	for(int i=1;i<=n;i++) p[B[i]]=i;
	for(int i=1;i<=n;i++) A[i]=p[A[i]];
	merge(A,1,n);
	printf("%d",ans);
	return 0;
}
    • Prob.3 货车运输

先是最大生成树,保证了路径的最小值最大;
然后在倍增,进行树上RMQ就好了。
代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct Cm_edge{
	int u,v,w;
	bool operator <(const Cm_edge &rtm){
		return w>rtm.w;
	}
}E[50005];
struct Lk_edge{
	int to,val,next;
}e[20005];
int head[10005],fa[10005],dep[10005],stm[10005][15],stf[10005][15];
int n,m,Q,ent=2;
void add(int u,int v,int w){
	e[ent]=(Lk_edge){v,w,head[u]};
	head[u]=ent++;
}
void cmin(int &a,int b){
	if(a>b) a=b;
}
int find(int u){
	return u==fa[u]?u:fa[u]=find(fa[u]);
}
void dfs(int u,int dad,int val){
	stf[u][0]=dad; stm[u][0]=val; dep[u]=dep[dad]+1;
	for(int k=1;k<=14;k++){
		stf[u][k]=stf[stf[u][k-1]][k-1];
		if(!stf[u][k]) break;
		stm[u][k]=min(stm[u][k-1],stm[stf[u][k-1]][k-1]);
	}
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v==dad) continue;
		dfs(v,u,e[i].val);
	}
}
int query(int u,int v){
	if(find(u)!=find(v)) return -1;
	int ans=INF;
	if(dep[u]>dep[v]) swap(u,v);
	for(int k=14;k>=0;k--){
		if(dep[stf[v][k]]<dep[u]) continue;
		cmin(ans,stm[v][k]); v=stf[v][k];
	}
	if(u==v) return ans;
	for(int k=14;k>=0;k--){
		if(stf[u][k]==stf[v][k]) continue;
		cmin(ans,stm[u][k]); cmin(ans,stm[v][k]);
		u=stf[u][k]; v=stf[v][k];
	}
	cmin(ans,stm[u][0]); cmin(ans,stm[v][0]);
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
	sort(E+1,E+m+1);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1,u,v,w,fu,fv;i<=m;i++){
		u=E[i].u,v=E[i].v,w=E[i].w;
		fu=find(u); fv=find(v);
		if(fu==fv) continue;
		fa[fv]=fu;
		add(u,v,w); add(v,u,w);
	}
	memset(stm,0x3f,sizeof(stm));
	dfs(1,0,INF);
	scanf("%d",&Q);
	for(int i=1,u,v;i<=Q;i++){
		scanf("%d%d",&u,&v);
		printf("%d\n",query(u,v));
	}
	return 0;
}

 

    • Prob.4 积木大赛

思路很巧妙的题。
之前想的是维护出每层的连续的段数和。实现很麻烦,而且复杂度堪忧。
正解:
    从左到右枚举,考虑当前的高度 h[i] :
    (可以想象成首先我们已经搭好了1~i-1,现在告诉你需要在第i列搭 h[i]的高度)
    如果 h[i-1]>=h[i] 那么显然,在我们搭好 i-1那一列是可以顺带把 第i列搭好。
    如果 h[i-1]<h[i]  那么高度h[i]的下面部分,即1~h[i-1],也可以在搭 i-1那一列是可以顺带搭好。
    剩下的 h[i]-h[i-1] 就要另外搭了,即贡献答案, ans+=h[i]-h[i-1]。
代码:

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
	int n,a=0,b=0,ans=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		a=b; scanf("%d",&b);
		if(a<b) ans+=b-a;
	}
	printf("%d",ans);
	return 0;
}

 

    • Prob.5 花匠

求最大拐点数,贪心做就好。
    考虑连续的三个数 a,b,c令 a<b 并且选了a,b
    1).如果b<c,那么不贡献答案,并弃掉b,改为选c,这样可以使得以后下降的范围相比b更大。
    2).如果b>c,那么显然该选择c,一是可以贡献一个答案(出现了拐点),二是使得以后上升的范围相比b更大。
代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<set> 

using namespace std;
int n,k,now,pre,ans=1;
int main(){
	scanf("%d",&n); scanf("%d",&pre); 
	for(int i=2;i<=n;i++){
		scanf("%d",&now);
		if(now>pre&&k!=1) k=1,ans++;
		if(now<pre&&k!=2) k=2,ans++;
		pre=now;
	}
	printf("%d",ans);
	return 0;
}
  • Prob.6 什么“华容道”吧,没做了。

转载于:https://www.cnblogs.com/zj75211/p/7811255.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/210145.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 循环单链表解决约瑟夫环_用链表解决约瑟夫环问题

    循环单链表解决约瑟夫环_用链表解决约瑟夫环问题已知有5个人围坐在一张圆桌的周围,从编号为3的人开始顺时针数数,数到2的那个人出列淘汰,然后从出列的下个一人继续数,依次循环,直到只剩下最后一个人。(使用循环链表实现约瑟夫环)代码如下:#include “pch.h”#include<string>#include<fstream>#include<Windows.h>#include <i…

  • Kali Linux 安装过程 超详细(图文并茂,通用版)

    Kali Linux 安装过程 超详细(图文并茂,通用版)从Kali2020.1版本新功能说起,在大致读过版本发布说明后,再进行安装,就不会有太大问题,不会频繁出错。然后给出了多种镜像下载途径,包括历史所有版本的镜像,供读者自行选择下载。最后开始正式安装,内容也是十分详细,图文并茂。在文章最后,介绍了默认安装的情况下,如果获取large版本,获取更多工具。最后介绍如何更新Kali,可升级至Kali2020.2版本。

  • pycharm2021激活码(破解版激活)

    pycharm2021激活码(破解版激活),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • matlab插值拟合案例,matlab插值与拟合

    matlab插值拟合案例,matlab插值与拟合《matlab插值与拟合》由会员分享,可在线阅读,更多相关《matlab插值与拟合(10页珍藏版)》请在人人文库网上搜索。1、实验2插值与拟合实验内容:1.三种插值方法2用Matlab计算插值3拟合的基本原理4用Matlab拟合曲线实验目的:掌握插值与拟合方法一、概念的引入1.插值与拟合在现实生活中的应用l机械制造:汽车外观设计l采样数据的重新建构:电脑游戏中场景的显示,…

  • 净推荐值(NPS)完整行动指南[通俗易懂]

    净推荐值(NPS)完整行动指南[通俗易懂]前言随着越来越多的SaaS公司想要提高客户忠诚度,使得衡量忠诚度的方法得到了发展,其中最受欢迎的方式之一就是净推荐值(NPS)。实际上,全球有55%的公司使用NPS来衡量客户满意度和忠诚度。净推荐值不是一个“虚荣指标”,当你与客户的工作发生交叉引用时,NPS可以用来推断客户实际上使用感到高兴的情况。你可以利用这些“行为模式”的见解来指导你的客户使用产品。因此,NPS可以指导新手入门和产品开发,帮助你减少客户流失并提高留存率。是否想知道如何衡量你的NPS?如何通过客户数据的交叉引用以指导产品.

  • 怎样重装系统win10(开机进不了windows系统)

    超级简单的方法重装win10系统重装系统操作步骤如果电脑系统还可以进入,那就没必要做U盘启动项,直接在现有的系统里重装win10。如果你的系统坏了,进不去了,这时你就要用U盘作为启动项安装系统。到Microsoft官网下载安装工具,用这个工具安装win10系统非常方便。利用此工具不仅可以在原有系统重装win10,也可以用来做U盘启动项。链接:link.重装系统操作步骤如果电脑系统还可以…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号