大家好,欢迎来到IT知识分享网。
T1:转圈游戏
考察知识:数学
算法难度:XX 实现难度:XX
分析:
不难发现:位置为x的小伙伴移动m步后在(x+m)mod n处
重复m*10^k次,所以答案为:
求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[]中逆序对数量即可
为什么这种算法是正确的呢?我们来数学分析一下:
因为
其中为定值
所以我们考虑求最大值:
由排序不等式:反序和≤乱序和≤顺序和
故当有序时有最大,即最小
证毕
最后是怎么求逆序对:大家最早学的应该是分治算法吧,之后可以用线段树或树状数组
其中:树状数组代码最为容易实现
代码:
#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