NOIP 2013 解题报告

1.

#include 
    #include 
    #include 
    using namespace std; int n,m,k,x; long long mul(long long x,long long y,long long mod) { if(y==0) return 0; if(y==1) return x%mod; long long res; res=mul(x,y>>1,mod); if((y&1)!=0) return(res+res+x)%mod; else return(res+res)%mod; } long long powermod(long long a,long long b,long long mod) { long long base=a,res=1; while(b!=0) { if(b&1!=0) res=mul(res,base,mod); base=mul(base,base,mod); b>>=1; } return res; } int main() { freopen("circle.in","r",stdin); freopen("circle.out","w",stdout); scanf("%d%d%d%d",&n,&m,&k,&x); int ans=(x+mul(m,powermod(10,k,n),n))%n; printf("%d\n",ans); return 0; }

2.

#include 
    #include 
    #include 
    using namespace std; #define MAXN  #define MOD  struct node { int v,t; }a[MAXN],b[MAXN]; short int cmp(node x,node y) { return x.v 
  
    int n,c[MAXN],ans= 
   0; 
   int t[MAXN]; 
   int lowbit( 
   int x) { 
    
   return x&(-x);} 
   void Add( 
   int x) { 
   for( 
   int i=x;i<=n;i+=lowbit(i)) ++t[i]; } 
   int Sum( 
   int x) { 
   int rec= 
   0; 
   for( ;x;x-=lowbit(x)) rec+=t[x]; 
   return rec; } 
   int main() { freopen( 
   "match.in", 
   "r",stdin); freopen( 
   "match.out", 
   "w",stdout); 
   scanf( 
   "%d",&n); 
   for( 
   int i= 
   1;i<=n;++i) { 
    
   scanf( 
   "%d",&a[i].v);a[i].t=i;} 
   for( 
   int i= 
   1;i<=n;++i) { 
    
   scanf( 
   "%d",&b[i].v);b[i].t=i;} sort(a+ 
   1,a+n+ 
   1,cmp); sort(b+ 
   1,b+n+ 
   1,cmp); 
   for( 
   int i= 
   1;i<=n;++i) c[a[i].t]=b[i].t; 
   for( 
   int i=n;i>= 
   1;i--) { ans+=Sum(c[i]); Add(c[i]); ans%=MOD; } 
   printf( 
   "%d\n",ans); 
   return 
   0; } 
  

#include 
    #include 
    #include 
    using namespace std; #define inf 0x7fffffff #define N 10010 #define M  int n,m,q,ne; int head[N]; struct data { int to,next,v; }e[M*2]; void add(int u,int v,int w) { ne++, e[ne].to=v, e[ne].v=w, e[ne].next=head[u], head[u]=ne; } void spfa(int x,int y) { int q[N],dis[N],t=0,w=1; int now,i; short int vis[N]; memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); q[0]=x, vis[x]=1, dis[x]=inf; while(t!=w) { now=q[t],t++; if(t==n) t=0; i=head[now]; while(i) { if(dis[e[i].to] 
  
    if(!vis[e[i].to]) { vis[e[i].to]= 
   1, 
   q[w]=e[i].to, w++; 
   if(w==n) w= 
   0; } } i=e[i]. 
   next; } vis[now]= 
   0; } 
   printf( 
   "%d\n",dis[ 
   y]); } 
   int main() { freopen( 
   "truck.in", 
   "r",stdin); freopen( 
   "truck.out", 
   "w",stdout); scanf( 
   "%d%d",&n,& 
   m); 
   for( 
   int i= 
   1;i<= 
   m;i++) { 
   int 
   x, 
   y,z; scanf( 
   "%d%d%d",& 
   x,& 
   y,&z); add( 
   x, 
   y,z);add( 
   y, 
   x,z); } scanf( 
   "%d",& 
   q); 
   while( 
   q--) { 
   int 
   x, 
   y; scanf( 
   "%d%d",& 
   x,& 
   y); spfa( 
   x, 
   y); } 
   return 
   0; } 
  

60分做法

#include 
    #include 
    #include 
    using namespace std; #define inf 0x7fffffff #define N 10010 #define M  int n,m,q,ne; int head[N],father[N]; struct data1 { int x,y,v; }ed[M]; struct data2 { int to,next,v; }e[M*2]; int find(int x) { 
  return x==father[x]?father[x]:father[x]=find(father[x]);} short int cmp(data1 a,data1 b) { 
  return a.v>b.v;} void add(int u,int v,int w) { ne++, e[ne].to=v, e[ne].v=w, e[ne].next=head[u], head[u]=ne; } void spfa(int x,int y) { int q[N],dis[N],t=0,w=1; int now,i; short int vis[N]; memset(vis,0,sizeof(vis)); memset(dis,-1,sizeof(dis)); q[0]=x; vis[x]=1; dis[x]=inf; while(t!=w) { now=q[t],t++; if(t==n) t=0; i=head[now]; while(i) { if(dis[e[i].to] 
  
    if(!vis[e[i].to]) { vis[e[i].to]= 
   1, 
   q[w]=e[i].to, w++; 
   if(w==n) w= 
   0; } } i=e[i]. 
   next; } vis[now]= 
   0; } 
   printf( 
   "%d\n",dis[ 
   y]); } 
   int main() { freopen( 
   "truck.in", 
   "r",stdin); freopen( 
   "truck.out", 
   "w",stdout); scanf( 
   "%d%d",&n,& 
   m); 
   for( 
   int i= 
   1;i<= 
   m;++i) {scanf( 
   "%d%d%d",&ed[i]. 
   x,&ed[i]. 
   y,&ed[i].v);} 
   sort(ed+ 
   1,ed+ 
   m+ 
   1,cmp); 
   for( 
   int i= 
   1;i<=n;++i) father[i]=i; 
   for( 
   int i= 
   1;i<= 
   m;++i) { 
   int 
   x=ed[i]. 
   x, 
   y=ed[i]. 
   y,v=ed[i].v; 
   if(find( 
   x)!=find( 
   y)) { father[find( 
   x)]=find( 
   y); add( 
   x, 
   y,v);add( 
   y, 
   x,v); } } scanf( 
   "%d",& 
   q); 
   for( 
   int i= 
   1;i<= 
   q;++i) { 
   int 
   x, 
   y; scanf( 
   "%d%d",& 
   x,& 
   y); spfa( 
   x, 
   y); } 
   return 
   0; } 
  

AC

#include 
    #include 
    #include 
    using namespace std; #define inf 0x7fffffff #define N 10010 #define M 50010 int n,m,q,cnt,tot,deep[N],head[N],f[N],fa[N][17],d[N][17]; short int vis[N]; struct edge { int x,y,v; }a[M]; struct e { int next,to,v; }e[M*2]; int find(int x) { 
  return f[x]==x?x:f[x]=find(f[x]);} bool cmp(edge a,edge b) { 
  return a.v>b.v;} void add(int u,int v,int w) { e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt; e[cnt].v=w; } void dfs(int x) { vis[x]=1; for(int i=1;i<=16;++i) { if(deep[x]<(1< 
  
    break; fa[x][i]=fa[fa[x][i- 
   1]][i- 
   1]; d[x][i]=min(d[x][i- 
   1],d[fa[x][i- 
   1]][i- 
   1]); } 
   for( 
   int i=head[x];i;i=e[i].next) { 
   if(vis[e[i].to]) 
   continue; fa[e[i].to][ 
   0]=x; d[e[i].to][ 
   0]=e[i].v; deep[e[i].to]=deep[x]+ 
   1; dfs(e[i].to); } } 
   int lca( 
   int x, 
   int y) { 
   if(deep[x] 
   
     int t=deep[x]-deep[y]; 
    for( 
    int i= 
    0;i<= 
    16;++i) 
    if(( 
    1< 
    
      for( 
     int i= 
     16;i>= 
     0;i--) { 
     if(fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];} } 
     if(x==y) 
     return x; 
     return fa[x][ 
     0]; } 
     int ask( 
     int x, 
     int f) { 
     int ans=inf; 
     int t=deep[x]-deep[f]; 
     for( 
     int i= 
     0;i<= 
     16;++i) { 
     if(t&( 
     1< 
     
       return ans; } 
      int main() { freopen( 
      "truck.in", 
      "r",stdin); freopen( 
      "truck.out", 
      "w",stdout); 
      memset(d,inf, 
      sizeof(d)); 
      scanf( 
      "%d%d",&n,&m); 
      for( 
      int i= 
      1;i<=n;++i) f[i]=i; 
      for( 
      int i= 
      1;i<=m;++i) 
      scanf( 
      "%d%d%d",&a[i].x,&a[i].y,&a[i].v); sort(a+ 
      1,a+m+ 
      1,cmp); 
      for( 
      int i= 
      1;i<=m;++i) { 
      int x=a[i].x,y=a[i].y; 
      int p=find(a[i].x),q=find(a[i].y); 
      if(p!=q) { f[p]=q; add(x,y,a[i].v); add(y,x,a[i].v); tot++; 
      if(tot==n- 
      1) 
      break; } } 
      for( 
      int i= 
      1;i<=n;++i) 
      if(!vis[i]) dfs(i); 
      for( 
      scanf( 
      "%d",&q);q;--q) { 
      int x,y; 
      scanf( 
      "%d%d",&x,&y); 
      if(find(x)!=find(y)) { 
       
      printf( 
      "-1\n"); 
      continue;} 
      else { 
      int t=lca(x,y); 
      printf( 
      "%d\n",min(ask(x,t),ask(y,t))); } } 
      return 
      0; } 
      
     
    
  

4.

#include 
    #include 
    #include 
    using namespace std; int n,x1=0,x2=0; long long ans=0; int main() { freopen("block.in","r",stdin); freopen("block.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) { scanf("%d",&x1); if(x1>x2) ans+=x1-x2; x2=x1; } printf("%I64d\n",ans); return 0; }

5.

#include 
    #include 
    #include 
    using namespace std; #define N  int n,a[N],ans; int main() { freopen("flower.in","r",stdin); freopen("flower.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&a[i]); short int flag=0;ans=1; for(int i=1;i<=n-1;++i) { if(a[i+1]>=a[i]&&flag!=1) flag=1,ans++; if(a[i+1]<=a[i]&&flag!=2) flag=2,ans++; } printf("%d\n",ans); return 0; }

#include 
    #include 
    #include 
    using namespace std; int n,m,p; short int mp[31][31]; short int mark[31][31][31][31]; int xx[4]={ 
  0,0,1,-1},yy[4]={ 
  1,-1,0,0}; struct data { int x,y,kx,ky; int step; }q[]; bool jud(int x,int y,int kx,int ky) { if(x<1||y<1||x>n||y>m||!mp[x][y]||!mp[kx][ky])return 0; if(mark[x][y][kx][ky])return 0; mark[x][y][kx][ky]=1; return 1; } void search() { memset(mark,0,sizeof(mark)); int t=0,w=0; int ex,ey,x,y,kx,ky; scanf("%d%d%d%d%d%d",&q[0].kx,&q[0].ky,&q[0].x,&q[0].y,&ex,&ey); if(ex==q[0].x&&ey==q[0].y){ 
  printf("0\n");return;} mark[q[0].x][q[0].y][q[0].kx][q[0].ky]=1; while(t<=w) { for(int i=0;i<4;++i) { x=q[t].x,y=q[t].y; kx=q[t].kx+xx[i],ky=q[t].ky+yy[i]; if(x==kx&&y==ky){ 
  x=q[t].kx;y=q[t].ky;} if(jud(x,y,kx,ky)) { w++; q[w].x=x;q[w].y=y; q[w].kx=kx;q[w].ky=ky; q[w].step=q[t].step+1; if(x==ex&&y==ey){ 
  printf("%d\n",q[w].step);return;} } } t++; } printf("-1\n"); return; } int main() { freopen("puzzle.in","r",stdin); freopen("puzzle.out","w",stdout); scanf("%d%d%d",&n,&m,&p); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&mp[i][j]); for(int i=1;i<=p;++i) { search(); } return 0; }