错误原因：想的太复杂
正解：
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;
}
举一反三：