1.
错误原因:想的太复杂
正解:
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; }
举一反三:
标签:NOIP2013,int,ll,long,day1,ans,return,复赛,mod From: https://www.cnblogs.com/zhanghx-blogs/p/17673936.html