NOIP2013提高组DAY1题解

NOIP2013提高组DAY1题解T1:转圈游戏考察知识:数学算法难度:XX实现难度:XX分析:不难发现:位置为x的小伙伴移动m步后在(x+m)modn处重复m*10^k次,所以答案为:求m*10^k我们可以用快速幂,注意防溢出代码:#include<cstdio>longlongn,m,k,x;longlongq_pow(inta,intk){long…

大家好,欢迎来到IT知识分享网。

T1:转圈游戏

考察知识:数学

算法难度:XX 实现难度:XX

分析:

不难发现:位置为x的小伙伴移动m步后在(x+m)mod n处

重复m*10^k次,所以答案为:(x+m\times10^k) \,\,mod \,\,n

求m*10^k我们可以用快速幂,注意防溢出

代码:

#include<cstdio>
long long n,m,k,x;
long long q_pow(int a,int k){
    long long ret=1;
    while(k){
        if(k&1) ret=ret*a%n;
        a=a*a%n,k>>=1;
    } return ret;
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
    printf("%lld\n",(x+m*q_pow(10,k))%n);
    return 0;
}

T2:火柴排队

考察知识:逆序对、分治

算法难度:XXX+ 实现难度:XXX

分析:

虽然考察逆序对但是隐藏得比较深。

算法流程:

1.输入n

2.输入第一列数字:h1[1…n]

3.输入第二列数字:h2[1…n]

4.分别将h1[1..n],h2[1…n]离散化为a1[1…n],a2[1…n](即:a中的每个值对应h中从小到大排序后的位数值)

具体操作见代码(2-7行)

void ready(){
    memcpy(tmp,h1,sizeof(h1));
    sort(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++) a1[i]=lower_bound(tmp+1,tmp+n+1,h1[i])-tmp;
    memcpy(tmp,h2,sizeof(h2));
    sort(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++) a2[i]=lower_bound(tmp+1,tmp+n+1,h2[i])-tmp;
    for(int i=1;i<=n;i++) mp[a1[i]]=i;
    for(int i=1;i<=n;i++) a1[i]=mp[a2[i]];
}

5.现在a1[],a2[]分别相当于1…n的一个排列,我们再次离散化,将a1[i]离散化为i,这样,a1[]就是1…n递增的了,按离散化方法再对a2[]操作,储存在a1[]数组里面

具体操作见代码(8-9行)

6.求a1[]中逆序对数量即可

为什么这种算法是正确的呢?我们来数学分析一下:

因为\sum (a_i-b_i)^2\,=\,\sum(a_i^2+b_j^2-2a_ib_j)

其中\sum(a_i^2+b_j^2)为定值

所以我们考虑求\sum a_ib_j最大值:

由排序不等式:反序和≤乱序和≤顺序和

故当a_i,b_j有序时有\sum a_ib_j最大,即\sum (a_i-b_i)^2最小

证毕

最后是怎么求逆序对:大家最早学的应该是分治算法吧,之后可以用线段树或树状数组

其中:树状数组代码最为容易实现

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=100005,md=99999997;
int n,a1[maxn],a2[maxn],mp[maxn];
ll h1[maxn],h2[maxn],tmp[maxn];
void ready(){
    memcpy(tmp,h1,sizeof(h1));
    sort(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++) a1[i]=lower_bound(tmp+1,tmp+n+1,h1[i])-tmp;
    memcpy(tmp,h2,sizeof(h2));
    sort(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++) a2[i]=lower_bound(tmp+1,tmp+n+1,h2[i])-tmp;
    for(int i=1;i<=n;i++) mp[a1[i]]=i;
    for(int i=1;i<=n;i++) a1[i]=mp[a2[i]];
}
//--------BIT---------
#define lowbit(x) (x&(-x))
int C[maxn];
void update(int x){
    while(x<=n) C[x]++,x+=lowbit(x);
}
int query(int x){
    int ret=0;
    while(x>0) ret+=C[x],x-=lowbit(x);
    return ret;
}
//--------END BIT------
void solve(){
    ll ans=0;
    for(int i=n;i;i--){
        update(a1[i]);
        ans=(ans+query(a1[i]-1))%md;
    }
    cout<<ans<<endl;
}
int main(){
    std::ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h1[i];
    for(int i=1;i<=n;i++) cin>>h2[i];
    ready();
    solve();
    return 0;
}

T3:货车运输

考察知识:图的生成树,LCA

算法难度:XXX+ 实现难度:XXXX

分析:

如果图连通的话,显然这道题最大生成树+LCA就可以过了

但是图不一定连通,所以我们要添加一些不存在的边使它连通。

我们可以添加 1->j 的边其中 1<j<=n,边权为-1

这样预处理之后求LCA就可以了

代码:

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=10005;
//-------link-list edge---------
struct edge{
	int to,next,w;
}e[maxn*10];
int head[maxn],np;
void adde(int u,int v,int w){
	e[++np]=(edge){v,head[u],w};
	head[u]=np;
	e[++np]=(edge){u,head[v],w};
	head[v]=np;
}
//------edge betwheen two nodes-------
struct edg{
	int u,v,w;
}ed[maxn*10];
bool cmp(const edg& A,const edg& B){
	return A.w>B.w;
}
//--------------union set-------------
int f[maxn];
void init(int sz){
	for(int i=1;i<=sz;i++) f[i]=i;
}
int find(int x){
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
bool mer_judge(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy) return false;
	f[fx]=fy;
	return true;
}
/*----------divide line-----------*/
int n,m,sz,q;
int fa[maxn][15],dep[maxn],me[maxn][15];
void dfs(int i,int Fa,int w){
	fa[i][0]=Fa,dep[i]=dep[Fa]+1,me[i][0]=w;
	for(int k=1;k<15;k++)
		fa[i][k]=fa[fa[i][k-1]][k-1],
		me[i][k]=min(me[i][k-1],me[fa[i][k-1]][k-1]);
	for(int p=head[i];p;p=e[p].next){
		int j=e[p].to;
		if(j==Fa) continue;
		dfs(j,i,e[p].w);
	}
}
int lca_min(int x,int y){
	int ret=0x7ffffffa;
	if(dep[x]<dep[y]) swap(x,y);
	int a=dep[x]-dep[y];
	for(int i=14;i>=0;i--) if(a&(1<<i))
		ret=min(ret,me[x][i]),x=fa[x][i];
	if(x==y) return ret;
	for(int i=14;i>=0;i--) if(fa[x][i]!=fa[y][i])
		ret=min(ret,min(me[x][i],me[y][i])),x=fa[x][i],y=fa[y][i];
	ret=min(ret,min(me[x][0],me[y][0]));
	return ret;
}
void build(){
	int cnt=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
	sz=m;
	for(int i=2;i<=n;i++) ed[++sz]=(edg){1,i,-1};//预处理使图连通 
	sort(ed+1,ed+sz+1,cmp);
	init(n);
	for(int i=1;i<=sz;i++){
		if(mer_judge(ed[i].u,ed[i].v))
			adde(ed[i].u,ed[i].v,ed[i].w),cnt++;
		if(cnt==n-1) break;
	}
	dfs(1,0,0x7ffffffa);//lca前的预处理 
}
void solve(){
	int u,v;
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&u,&v);
		printf("%d\n",lca_min(u,v));//lca求经过边的最小值 
	}
}
int main(){
	build();
	solve();
	return 0;
}

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/11768.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信