$NOIP2013$ 题解报告
分类:
IT文章
•
2025-01-22 11:57:01
目录
$Luogu P1965$ 转圈游戏$( √ )$
$Luogu P1966$ 火柴排队$( √ )$
$Luogu P1967$ 货车运输$( √ )$
$Luogu P1969$ 积木大赛$( √ )$
$Luogu P1970$ 花匠$( √ )$
$Luogu P1979$ 华容道（ ）
$Luogu P1965$ 转圈游戏
题目传送门
快速幂$+$模拟
![]()
1 #include<bits/stdc++.h>
2 using namespace std;
3 int n,m,k,x,ans;
4 int quick(int a,int K){
5 int A=a,res=1;
6 while(K){
7 if(K&1)
8 res=res*A%n;
9 A=A*A%n;
10 K>>=1;
11 }
12 return res;
13 }
14 int main(){
15 scanf("%d%d%d%d",&n,&m,&k,&x);
16 ans=(x%n+m%n*quick(10,k)%n)%n;
17 printf("%d",ans);
18 return 0;
19 }
代码戳这里
$Luogu P1966$ 火柴排队
题目传送门
显然按大小匹配，求逆序对即可
![]()
1 #include<bits/stdc++.h>
2 #define ri register int
3 #define ll long long
4 #define rl register ll
5 #define go(i,a,b) for(ri i=a;i<=b;i++)
6 #define back(i,a,b) for(ri i=a;i>=b;i--)
7 #define g() getchar()
8 #define il inline
9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 il int fr(){
13 ri w=0,q=1;char ch=g();
14 while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
15 while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
16 return w*q;
17 }
18 const int N=100002;
19 const int mod=99999997;
20 int n,to[N],ans;
21 struct node{
22 int h,id;
23 }a[N],b[N];
24 il bool cmp(node x,node y){return x.h<y.h;}
25 il void sol(ri l,ri r){
26 if(l>=r)return;
27 ri mid=(l+r)>>1;
28 sol(l,mid);sol(mid+1,r);
29 ri i=l,j=mid+1,k=l;
30 int c[N];
31 while(i<=mid&&j<=r){
32 if(to[i]<=to[j]){c[k]=to[i];k++;i++;}
33 else{
34 c[k]=to[j];k++;j++;
35 ans=(ans+mid-i+1)%mod;
36 }
37 }
38 while(i<=mid)c[k]=to[i],k++,i++;
39 while(j<=r)c[k]=to[j],k++,j++;
40 go(i0,l,r)to[i0]=c[i0];return;
41 }
42 int main(){
43 //freopen(".in","r",stdin);
44 //freopen(".out","w",stdout);
45 n=fr();
46 go(i,1,n)a[i].h=fr(),a[i].id=i;
47 go(i,1,n)b[i].h=fr(),b[i].id=i;
48 sort(a+1,a+1+n,cmp);sort(b+1,b+1+n,cmp);
49 go(i,1,n)to[a[i].id]=b[i].id;
50 sol(1,n);pf("%d
",ans);
51 return 0;
52 }
代码戳这里
![]()
1 #include<bits/stdc++.h>
2 #define ri register int
3 #define ll long long
4 #define rl register ll
5 #define go(i,a,b) for(ri i=a;i<=b;i++)
6 #define back(i,a,b) for(ri i=a;i>=b;i--)
7 #define g() getchar()
8 #define il inline
9 #define pf printf
10 #define mem(a,b) memset(a,b,sizeof(a))
11 #define E(i,x) for(ri i=hd[x];i;i=e[i].nxt)
12 #define t(i) e[i].to
13 using namespace std;
14 il int fr(){
15 ri w=0,q=1;char ch=g();
16 while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();}
17 while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g();
18 return w*q;
19 }
20 const int M=50002;
21 const int N=10002;
22 const int INF=100002;
23 int n,m,q,fa[N],hd[N],ed,f[N][15],mn[N][15],dep[N];
24 bool vis[N];
25 struct node{
26 int x,y,w;
27 }d[M];
28 struct edge{
29 int nxt,to,w;
30 }e[N<<1];
31 il bool cmp(node a,node b){return a.w>b.w;}
32 il int find(ri a){return fa[a]==a?a:fa[a]=find(fa[a]);}
33 il void build(ri x,ri y,ri w){e[++ed]=(edge){hd[x],y,w};hd[x]=ed;return;}
34 il void Tree(ri x,ri ft){
35 dep[x]=dep[ft]+1;f[x][0]=ft;vis[x]=1;
36 go(i,1,14){
37 f[x][i]=f[f[x][i-1]][i-1];
38 mn[x][i]=min(mn[f[x][i-1]][i-1],mn[x][i-1]);
39 }
40 E(i,x){
41 if(t(i)==ft)continue;
42 mn[t(i)][0]=e[i].w;Tree(t(i),x);
43 }
44 return;
45 }
46 il int LCA(ri x,ri y){
47 if(dep[x]<dep[y])swap(x,y);
48 ri as=INF;
49 back(i,14,0)
50 if(dep[f[x][i]]>=dep[y])as=min(as,mn[x][i]),x=f[x][i];
51 if(x==y)return as;
52 back(i,14,0)
53 if(f[x][i]!=f[y][i]){
54 as=min(as,min(mn[x][i],mn[y][i]));
55 x=f[x][i];y=f[y][i];
56 }
57 as=min(as,min(mn[x][0],mn[y][0]));return as;
58 }
59 int main(){
60 //freopen(".in","r",stdin);
61 //freopen(".out","w",stdout);
62 n=fr();m=fr();
63 go(i,1,n)fa[i]=i;
64 go(i,1,m)d[i]=(node){fr(),fr(),fr()};
65 sort(d+1,d+1+m,cmp);ri num=0;
66 go(i,1,m){
67 ri x=d[i].x,y=d[i].y,w=d[i].w;
68 ri fx=find(x),fy=find(y);
69 if(fx==fy)continue;
70 fa[fx]=fy;build(x,y,w);build(y,x,w);
71 num++;if(num==n-1)break;
72 }
73 mem(mn,0x3f);Tree(1,0);
74 go(i,1,n)if(!vis[i])Tree(i,0);
75 q=fr();
76 while(q--){
77 ri x=fr(),y=fr();
78 ri fx=find(x),fy=find(y);
79 if(fx!=fy){puts("-1");continue;}
80 pf("%d
",LCA(x,y));
81 }
82 return 0;
83 }
