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)


相关推荐

  • 基于阿里DDNS的ipv6 for windows版软件

    基于阿里DDNS的ipv6 for windows版软件基于阿里DDNS的ipv6forwindows版软件会搜到这篇帖子的同学,应该和我一样,满世界为自己的虚拟主机找寻ipv6的动态ddns程序吧?下面我先说说我的折腾故事:因为买了群晖,然后发现需要公网ip,但公网ip现在电信要钱了,开口100元一个月,挺黑的。没办法尝试了各种内网穿透,这类帖子网上很多,就不细说了,总之是各种折腾,各种不爽,最终选择了零遁伴侣做内网穿透还算稳定,速度也不错。…

  • 自定义美化博客园

    自定义美化博客园

  • 前端vscode必备插件推荐(墙裂推荐)「建议收藏」

    前端vscode必备插件推荐(墙裂推荐)「建议收藏」前言:vscode是一款强大的前端编辑软件,有些人说ws(webstorm)更好用,但是vs重在轻量级啊!!!而且根据自己的开发习惯安装适合自己的插件后,用起来简直不要太舒服了好嘛!!!首先呢,我先推荐的就是最基础的语言包,没办法,英语水平太捞了哈哈哈,弄起来后就舒服多了,汉语yyds~《Chinese(Simplified)(简体中文)Language》注释工具《ColorfulComments》不同的注释符能带来很多高亮的显示快速找到css定义位置并小窗口展示

  • android缩放动画中心缩放_缩放动画

    android缩放动画中心缩放_缩放动画ScaleAnimation:缩放动画同样,创建ScaleAnimation也有两种方式XML文件+Java代码Java代码方式XML文件+Java代码效果图:文件目录:res/anim/scale.xml

    2022年10月15日
  • 【转】C:经典技巧,不用临时变量,交换变量值

    【转】C:经典技巧,不用临时变量,交换变量值

  • 关于ModifyStyle ModifyStyleEx修改自定义控件的问题[通俗易懂]

    关于ModifyStyle ModifyStyleEx修改自定义控件的问题[通俗易懂]继承与MFC控件,比如CStaticCEdit等等,在自定义代码中许多人反映无法更改控件的外观属相,这是因为大部分人没有通知主窗体自定义控件的外观更改了,可以使用下列代码进行更改: ModifyStyle(WS_BORDER,0,SWP_DRAWFRAME); ModifyStyleEx(WS_EX_STATICEDGE|WS_EX_WINDOWEDGE|WS_EX_DLGMODALFRAME,                       WS_EX_CLIENTEDGE,SWP_DRAWFRAME);

发表回复

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

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