NOIP2013提高组 解题报告

D1

T1 转圈游戏

快速幂

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int n,m,k,x,ans=1;
 6 long long power(long long x,long long y)
 7 {
 8     if(y==0)return 1;
 9     if(y==1)return x%n;
10     long long m=y/2,ans;
11     bool r=y%2;
12     ans=power(x,y/2);
13     if(r)return ((ans*ans)%n*x)%n;
14     else return (ans*ans)%n;
15 }
16 int main()
17 {
18     freopen("circle.in","r",stdin);
19     freopen("circle.out","w",stdout);
20     cin>>n>>m>>k>>x;
21     ans=(power(10%n,k)*m+x%n)%n;
22     cout<<ans;
23     fclose(stdin);fclose(stdout);
24     return 0;
25 }
View Code


T2 火柴排队

归并排序求逆序对

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 const int mod=99999997;
 6 struct node{
 7     int num,id;
 8 }a[100001],b[100001];
 9 int n,ans;
10 int num[100001],tmp[100001];
11 inline int qread()
12 {
13     int x=0,j=1;
14     char ch=getchar();
15     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
16     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
17     return x*j;
18 }
19 inline void merge_array(int l,int r)
20 {
21     int m=(l+r)>>1,i=l,cnt=0;
22     int m2=m+1;
23     while(i<=m && m2<=r)
24     {
25         if(num[i]<=num[m2])
26             tmp[cnt++]=num[i++];
27         else
28         {
29             ans+=m-i+1;
30             ans%=mod;
31             tmp[cnt++]=num[m2++];
32         }
33     }
34     while(i<=m)
35         tmp[cnt++]=num[i++];
36     while(m2<=r)
37         tmp[cnt++]=num[m2++];
38     for(int i=0;i<cnt;i++)
39         num[l+i]=tmp[i];
40 }
41 void merge_sort(int l,int r)
42 {
43     if(l<r)
44     {
45         int m=(l+r)>>1;
46         merge_sort(l,m);
47         merge_sort(m+1,r);
48         merge_array(l,r);
49     }
50 }
51 bool cmp(const node &a,const node &b)
52 {
53     return a.num<b.num;
54 }
55 int main()
56 {
57 //    freopen("match.in","r",stdin);
58 //    freopen("match.out","w",stdout);
59     scanf("%d",&n);
60     for(int i=1;i<=n;i++)
61     {
62         a[i].num=qread();
63         a[i].id=i;
64     }
65     for(int i=1;i<=n;i++)
66     {
67         b[i].num=qread();
68         b[i].id=i;
69     }
70     sort(a+1,a+n+1,cmp);
71     sort(b+1,b+n+1,cmp);
72     for(int i=1;i<=n;i++)
73         num[a[i].id]=b[i].id;
74     merge_sort(1,n);
75     printf("%d
",ans);
76 //    fclose(stdin);fclose(stdout);
77     return 0;
78 }
View Code

T3 货车运输

要使得最大载重最大，就要使路径上的限重最大，所以可以用kruskal建最小生成树的方法建一棵最大生成树。

树上两点间的距离等于这两点到LCA的距离之和（这里是取min），用与求LCA中father数组一样的方法求出每个节点与向上跳2^j步到达的结点间的距离。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 using namespace std;
  6 const int N=1e4+7;
  7 struct Road{
  8     int u,v,w;
  9 }road[N*5];
 10 struct node{
 11     int v,w,nxt;
 12 }e[N*2];
 13 int n,m,Q,Enum;
 14 int fat[N],head[N],f[N][22],dis[N][22],deep[N];
 15 bool vis[N];
 16 int qread()
 17 {
 18     int x=0,j=1;
 19     char ch=getchar();
 20     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
 21     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
 22     return x*j;
 23 }
 24 void Insert(int u,int v,int w)
 25 {
 26     e[++Enum].v=v;
 27     e[Enum].w=w;
 28     e[Enum].nxt=head[u];
 29     head[u]=Enum;
 30 }
 31 int find(int x)
 32 {
 33     if(fat[x]!=x)fat[x]=find(fat[x]);
 34     return fat[x];
 35 }
 36 bool cmp(const Road &a,const Road &b)
 37 {
 38     return a.w>b.w;
 39 }
 40 void build(int x)
 41 {
 42     vis[x]=1;
 43     for(int i=head[x];i;i=e[i].nxt)
 44     {
 45         int v=e[i].v;
 46         if(vis[v])continue;
 47         f[v][0]=x;
 48         dis[v][0]=e[i].w;
 49         deep[v]=deep[x]+1;
 50         build(v);
 51     }
 52 }
 53 void find_father()
 54 {
 55     for(int j=1;j<=21;j++)
 56         for(int i=1;i<=n;i++)
 57         {
 58             f[i][j]=f[f[i][j-1]][j-1];
 59             dis[i][j]=min(dis[f[i][j-1]][j-1],dis[i][j-1]);
 60         }
 61 }
 62 int Lca(int a,int b)
 63 {
 64     if(deep[a]<deep[b])swap(a,b);
 65     int tmp=deep[a]-deep[b];
 66     for(int i=0;i<=21;i++)
 67         if(tmp&(1<<i))
 68             a=f[a][i];
 69     if(a==b)return a;
 70     for(int i=21;i>=0;i--)
 71         if(f[a][i]!=f[b][i])
 72         {
 73             a=f[a][i];
 74             b=f[b][i];
 75         }
 76     return f[a][0];
 77 }
 78 int query(int a,int b)//查询树上两点间的距离 
 79 {
 80     int ans=0x3f3f3f3f;
 81     int tmp=deep[a]-deep[b];
 82     for(int i=0;i<=21;i++)
 83         if(tmp&(1<<i))
 84         {
 85             ans=min(ans,dis[a][i]);
 86             a=f[a][i];
 87         }
 88     return ans;
 89 }
 90 int main()
 91 {
 92 //    freopen("truck.in","r",stdin);
 93 //    freopen("truct.out","w",stdout);
 94     scanf("%d%d",&n,&m);
 95     for(int i=1;i<=m;i++)
 96     {
 97         road[i].u=qread();
 98         road[i].v=qread();
 99         road[i].w=qread();
100     }
101     for(int i=1;i<=n;i++)
102         fat[i]=i;
103     sort(road+1,road+m+1,cmp);
104     for(int i=1;i<=m;i++)//最大生成树 
105     {
106         int r1=find(road[i].u);
107         int r2=find(road[i].v);
108         if(r1!=r2)
109         {
110             fat[r2]=r1;
111             Insert(road[i].u,road[i].v,road[i].w);
112             Insert(road[i].v,road[i].u,road[i].w);
113         }
114     }
115     memset(dis,0x3f,sizeof(dis));
116     for(int i=1;i<=n;i++)
117         if(!vis[i])
118             build(i);
119     find_father();
120     scanf("%d",&Q);
121     int u,v;
122     while(Q--)
123     {
124         u=qread();v=qread();
125         if(find(u)!=find(v))
126             printf("-1
");
127         else
128         {
129             int lca=Lca(u,v);
130             printf("%d
",min(query(u,lca),query(v,lca)));
131         }
132     }
133 //    fclose(stdin);fclose(stdout);
134     return 0;
135 }
View Code

D2

T1 积木大赛

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,h[100500],ans;
 5 int main()
 6 {
 7     cin>>n;
 8     for(int i=1;i<=n;i++)
 9         cin>>h[i];
10     ans=h[1];
11     for(int i=1;i<n;i++)
12         if(h[i]<h[i+1])
13             ans+=h[i+1]-h[i];
14     cout<<ans;
15     return 0;
16 }
View Code

T2 花匠

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n,m,ans,now,last,tmp;
 5 int h[100001];
 6 inline int qread()
 7 {
 8     int x=0,j=1;
 9     char ch=getchar();
10     while(ch<'0' || ch>'9'){if(ch=='-')j=-1;ch=getchar();}
11     while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*j;
13 }
14 int main()
15 {
16     scanf("%d",&n);
17     for(int i=1;i<=n;i++)
18         h[i]=qread();
19     last=h[1];
20     for(int i=2;i<=n;i++)
21     {
22         now=h[i];
23         if(now!=last)
24             if(!tmp || (tmp>0 && now<last) || (tmp<0 && now>last))
25             //除了第二个以外仅当上升(下降)序列变为下降(上升)序列才会多一株 
26             {
27                 ans++;
28                 tmp=now-last;
29             }
30         last=now;
31     }
32     printf("%d
",ans+1);
33     return 0;
34 }
View Code

T3 华容道

  1 /*
  2 对于一个指定块和一个空白块，有四种不同有效状态: 空白块在指定块的上下左右 
  3 对于每一个有效状态有4种后继状态：另外三个方向的状态、交换空白块和有效块 
  4 将有用状态与后继状态连边构图，边权为由有用状态到后继状态所需的最小步数 
  5 算出空白块移到指定块四周的步数 
  6 将算出的结果作为初始值，再在图中跑最短路 
  7 */
  8 #include<iostream>
  9 #include<cstdio>
 10 #include<queue>
 11 #include<cstring>
 12 using namespace std;
 13 const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
 14 struct Point{
 15     int x,y;
 16 }nxt,cnt;
 17 struct node{
 18     int v,w,nxt;
 19 }e[3601*5];
 20 int n,m,Q,Enum;
 21 int pre_dis[31][31],dis[3601],head[3601];
 22 //pre_dis表示空白块与指定块的一个有效状态，到另外三个有效状态的最小距离 
 23 bool a[31][31],vis[3601];
 24 queue<Point>q;
 25 queue<int>k;
 26 void Insert(int u,int v,int w)
 27 {
 28     e[++Enum].v=v;
 29     e[Enum].w=w;
 30     e[Enum].nxt=head[u];
 31     head[u]=Enum;
 32 }
 33 int turn(int i,int j)
 34 {
 35     return (i-1)*m+j-1<<2;
 36 }
 37 void bfs(int ex,int ey,int px,int py,int d)
 38 //空白块移动到其他块的最小距离 
 39 {
 40     memset(pre_dis,-1,sizeof(pre_dis));
 41     pre_dis[px][py]=1;//指定块 
 42     pre_dis[ex][ey]=0;//空白块 
 43     cnt.x=ex;cnt.y=ey;
 44     q.push(cnt);
 45     while(!q.empty())
 46     {
 47         cnt=q.front();
 48         q.pop();
 49         for(int i=0;i<=3;i++)
 50         {
 51             nxt.x=cnt.x+dx[i];nxt.y=cnt.y+dy[i];
 52             if(a[nxt.x][nxt.y] && pre_dis[nxt.x][nxt.y]==-1)
 53             {
 54                 pre_dis[nxt.x][nxt.y]=pre_dis[cnt.x][cnt.y]+1;
 55                 q.push(nxt);
 56             }
 57         }
 58     }
 59     if(d==4)return;
 60     int tmp=turn(px,py);
 61     for(int i=0;i<=3;i++)
 62         if(pre_dis[px+dx[i]][py+dy[i]]>0)//当前有效状态与后继状态连边 
 63             Insert(tmp+d,tmp+i,pre_dis[px+dx[i]][py+dy[i]]);
 64     Insert(tmp+d,turn(ex,ey)+(d+2)%4,1);//空白块与指定块交换 
 65 }
 66 void SPFA(int sx,int sy)
 67 {
 68     memset(dis,-1,sizeof(dis));
 69     for(int i=0;i<=3;i++)
 70         if(pre_dis[sx+dx[i]][sy+dy[i]]!=-1)
 71         {
 72             int tmp=turn(sx,sy)+i;
 73             dis[tmp]=pre_dis[sx+dx[i]][sy+dy[i]];
 74             k.push(tmp);
 75         }
 76     while(!k.empty())
 77     {
 78         int u=k.front();
 79         k.pop();
 80         vis[u]=0;
 81         for(int i=head[u];i;i=e[i].nxt)
 82         {
 83             int v=e[i].v;
 84             if(dis[v]==-1 || dis[v]>dis[u]+e[i].w)
 85             {
 86                 dis[v]=dis[u]+e[i].w;
 87                 if(!vis[v])
 88                 {
 89                     vis[v]=1;
 90                     k.push(v);
 91                 }
 92             }
 93         }
 94     }
 95 }
 96 int main()
 97 {
 98     scanf("%d%d%d",&n,&m,&Q);
 99     for(int i=1;i<=n;i++)
100         for(int j=1;j<=m;j++)
101             scanf("%d",&a[i][j]);
102     for(int i=1;i<=n;i++)
103         for(int j=1;j<=m;j++)
104             if(a[i][j])
105             {
106                 if(a[i-1][j])bfs(i-1,j,i,j,0);
107                 if(a[i][j+1])bfs(i,j+1,i,j,1);
108                 if(a[i+1][j])bfs(i+1,j,i,j,2);
109                 if(a[i][j-1])bfs(i,j-1,i,j,3);
110             }
111     int ex,ey,sx,sy,tx,ty,ans;
112     while(Q--)
113     {
114         ans=0x3f3f3f3f;
115         scanf("%d%d%d%d%d%d",&ex,&ey,&sx,&sy,&tx,&ty);
116         if(sx==tx && sy==ty)
117         {
118             printf("0
");
119             continue;
120         }
121         bfs(ex,ey,sx,sy,4);
122         SPFA(sx,sy);
123         int tmp=turn(tx,ty);
124         for(int i=0;i<=3;i++)
125             if(dis[tmp+i]!=-1)
126                 ans=min(ans,dis[tmp+i]);
127         if(ans==0x3f3f3f3f)
128             ans=-1;
129         printf("%d
",ans);
130     }
131     return 0;
132 }
View Code
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/1078713946t/p/7693063.html