NOIP2013提高组解题报告-白红宇

NOIP2013提高组解题报告

阅读量：5323 次

发布时间：2019-06-14

本文共 7607 字，大约阅读时间需要 25 分钟。

T1 转圈游戏

快速幂

1 #include
      
        2 #include
       
         3 #include
        
          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<

View Code

T2 火柴排队

归并排序求逆序对

1 #include
      
        2 #include
       
         3 #include
        
          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         else28         {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
         
          >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

View Code

T3 货车运输

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

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

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            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]
          
           =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<

View Code

T1 积木大赛

1 #include
      
        2 #include
       
         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

View Code

T2 花匠

1 #include
      
        2 #include
       
         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))25             //除了第二个以外仅当上升(下降)序列变为下降(上升)序列才会多一株 26             {27                 ans++;28                 tmp=now-last;29             }30         last=now;31     }32     printf("%d\n",ans+1);33     return 0;34 }

View Code

T3 华容道

1 /*  2 对于一个指定块和一个空白块，有四种不同有效状态: 空白块在指定块的上下左右   3 对于每一个有效状态有4种后继状态：另外三个方向的状态、交换空白块和有效块   4 将有用状态与后继状态连边构图，边权为由有用状态到后继状态所需的最小步数   5 算出空白块移到指定块四周的步数   6 将算出的结果作为初始值，再在图中跑最短路   7 */  8 #include
      
         9 #include
       
         10 #include
        
          11 #include
         
           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
          
           q; 25 queue
           
            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\n");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\n",ans);130 }131 return 0;132 }