NOIp 2011

Day1 T1 铺地毯

标签:模拟

code

 1 #include <cstdio> 2 #include <cstdlib> 3 using namespace std; 4 int main() 5 { 6     int n,x,y,a[10001],b[10001],g[10001],k[10001]; 7     scanf("%d",&n); 8     for(int i=1;i<=n;++i) 9       scanf("%d %d %d %d",&a[i],&b[i],&g[i],&k[i]);10     scanf("%d %d",&x,&y);11     for(int i=n;i>=1;--i)12     if(x>=a[i]&&x<=a[i]+g[i]&&y>=b[i]&&y<=b[i]+k[i])13     {14         printf("%d\n",i);15         exit(0);16     }17     printf("-1\n");18     return 0;19 }

Day1 T2 选择客栈

标签:数据结构

一看静态区间最小值,想到st表

用st表维护区间内最小值是不是小于等于p,vector维护每种颜色的第i个在color数组中的位置

code

 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4   inline int read(){ 5     int x=0,f=1;char s=getchar(); 6     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 7     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 8     return f*x; 9   }10 #define ll long long11   const int maxn=2e5+10;12   int n,k,p,a[maxn][21],ans,x;13   vector<int>co[60];14   int query(int l,int r){15     int k=log2(r-l+1);16     return max(a[l][k],a[r-(1<<k)+1][k]);17   }18   int main(){19     n=read();k=read();p=read();20     for(int i=1;i<=n;i++){21       x=read();a[i][0]=(read()<=p)?1:0;22       co[x].push_back(i);23     }24     for(int j=1;j<=21;j++)25       for(int i=1;i+(1<<j)-1<=n;i++){26         a[i][j]=max(a[i][j-1],a[i+(1<<(j-1))][j-1]);27       }28     for(int t=0;t<k;t++){29       int i=0,j=1;30       for(;j<co[t].size();j++){31         if(query(co[t][j-1],co[t][j])){32           ans+=(ll)(co[t].size()-j)*(j-i);33           i=j;34         }35       }36     }37     printf("%d",ans);38     return 0;39   }40 }41 signed main(){42   gengyf::main();43   return 0;44 }

Day1 T3 Manya游戏

标签:模拟,搜索

啥也不说了,考验码力的时候到了

code

  1 #include <bits/stdc++.h>  2 using namespace std;  3 namespace gengyf{  4 #define ll long long  5   inline int read(){  6     int x=0,f=1;char s=getchar();  7     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}  8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}  9     return f*x; 10   } 11   int n,map[10][10],ans[10][5],last[10][10][10],del[10][10]; 12   bool remove(){ 13     int flag=0; 14     for(int i=1;i<=5;i++) 15       for(int j=1;j<=7;j++){ 16         if(i-1>=1&&i+1<=5&&map[i][j]==map[i-1][j]&&map[i][j]==map[i+1][j]&&map[i][j]){ 17           del[i-1][j]=1;del[i+1][j]=1;del[i][j]=1;flag=1; 18         } 19         if(j-1>=1&&j+1<=7&&map[i][j]==map[i][j+1]&&map[i][j]==map[i][j-1]&&map[i][j]){ 20           del[i][j]=1;del[i][j+1]=1;del[i][j-1]=1;flag=1; 21         } 22       } 23     if(!flag)return 0; 24     for(int i=1;i<=5;i++) 25       for(int j=1;j<=7;j++){ 26         if(del[i][j]){ 27           del[i][j]=0; 28           map[i][j]=0; 29         } 30       } 31     return 1; 32   } 33   bool check(){ 34     for(int i=1;i<=5;i++){ 35       if(map[i][1])return 0; 36     } 37     return 1; 38   } 39   void copy(int x){ 40     for(int i=1;i<=5;i++) 41       for(int j=1;j<=7;j++){ 42         last[x][i][j]=map[i][j]; 43       } 44   } 45   void update(){ 46     for(int i=1;i<=5;i++){ 47       int tmp=0; 48       for(int j=1;j<=7;j++){ 49         if(map[i][j]==0)tmp++; 50         else { 51           if(!tmp)continue; 52           map[i][j-tmp]=map[i][j]; 53           map[i][j]=0; 54         } 55       } 56     } 57   } 58   void move(int i,int j,int k){ 59     int tmp=map[i][j]; 60     map[i][j]=map[i+k][j];map[i+k][j]=tmp; 61     update(); 62     while(remove())update(); 63   } 64   void dfs(int x){ 65     if(check()){ 66       for(int i=1;i<=n;i++){ 67         if(i!=1)printf("\n"); 68         for(int j=1;j<=3;j++){ 69           printf("%d ",ans[i][j]); 70         } 71       } 72       exit(0); 73     } 74     if(x==n+1)return ; 75     copy(x); 76     for(int i=1;i<=5;i++) 77       for(int j=1;j<=7;j++){ 78         if(map[i][j]){ 79           if(i+1<=5&&map[i][j]!=map[i+1][j]){ 80             move(i,j,1); 81             ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=1; 82             dfs(x+1); 83             for(int i=1;i<=5;i++) 84               for(int j=1;j<=7;j++){ 85                 map[i][j]=last[x][i][j]; 86               } 87             ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1; 88           } 89         } 90         if(i-1>=1&&map[i-1][j]==0){ 91           move(i,j,-1); 92           ans[x][1]=i-1;ans[x][2]=j-1;ans[x][3]=-1; 93           dfs(x+1); 94           for(int i=1;i<=5;i++) 95             for(int j=1;j<=7;j++){ 96               map[i][j]=last[x][i][j]; 97             } 98           ans[x][1]=-1;ans[x][2]=-1;ans[x][3]=-1; 99         }100       }101   }102   int main(){103     n=read();104     for(int i=1;i<=5;i++){105       for(int j=1;j<=8;j++){106         int x=read();107         if(x==0)break;108         map[i][j]=x;109       }110     }111     memset(ans,-1,sizeof(ans));112     dfs(1);113     printf("-1");114     return 0;115   }116 }117 signed main(){118   gengyf::main();119   return 0;120 }

Day2 T1 计算系数

标签:数论

先看a=1,b=1的部分分

n次方和的系数就是杨辉三角 -> 50pts

再看100%数据

拿出草稿纸一波推导->戳

每一项的系数就是杨辉三角的值再乘(a^n)再乘(b^m),可以用快速幂实现

code

 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define int long long 5   inline int read(){ 6     int x=0,f=1;char s=getchar(); 7     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 9     return f*x;10   }11   const int maxn=2001;12   const int mod=1e4+7;13   int a,b,k,m,n,f[maxn][maxn],ans;14   int qpow(int a,int b){15     int tmp=1,base=a;16     while(b){17       if(b&1)tmp=tmp*base%mod;18       base*=base;base%=mod;19       b>>=1;20     }21     return tmp;22   }23   int main(){24     scanf("%lld%lld%lld%lld%lld",&a,&b,&k,&n,&m);25     f[1][1]=1;26     for(int i=2;i<=k+1;i++)27       for(int j=1;j<=i;j++){28         f[i][j]=f[i-1][j-1]%mod+f[i-1][j]%mod;29         f[i][j]%=mod;30       }31     ans=f[k+1][k-n+1]%mod*qpow(a,n)*qpow(b,m)%mod;32     printf("%lld",ans);33     return 0;34   }35 }36 signed main(){37   gengyf::main();38   return 0;39 }

Day2 T2 聪明的质检员

标签:二分

可以发现,W越大,能选的越少,W越小,能选的越多,满足二分性质

Y的值为各个区间和,前缀和优化

当w[i]>=W时会选上,这时数目的前缀和+1,价值的前缀和+v[i]

code

 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define int long long 5   inline int read(){ 6     int x=0,f=1;char s=getchar(); 7     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 9     return f*x;10   }11   const int inf=2147483647;12   const int maxn=2e5+10;13   int n,m,s,maxx=-1,minn=inf;14   int pren[maxn],prev[maxn],w[maxn],v[maxn],l[maxn],r[maxn];15   int sum,y,ans=inf;16   bool check(int mid){17     sum=0;y=0;18     memset(pren,0,sizeof(pren));19     memset(prev,0,sizeof(prev));20     for(int i=1;i<=n;i++){21       if(w[i]>=mid){22         pren[i]=pren[i-1]+1;23         prev[i]=prev[i-1]+v[i];24       }25       else {26         pren[i]=pren[i-1];27         prev[i]=prev[i-1];28       }29     }30     for(int i=1;i<=m;i++){31       y+=(pren[r[i]]-pren[l[i]-1])*(prev[r[i]]-prev[l[i]-1]);32     }33     sum=llabs(y-s);34     if(y>s) return true;35     else return false;36   }37   int main(){38     n=read();m=read();s=read();39     for(int i=1;i<=n;i++){40       w[i]=read();v[i]=read();41       maxx=max(maxx,w[i]);42       minn=min(minn,w[i]);43     }44     for(int i=1;i<=m;i++){45       l[i]=read();r[i]=read();46     }47     int l=minn-1,r=maxx+2;48     ans=0x3f3f3f3f3f3f3f3f;49     while(l<=r){50       int mid=(l+r)>>1;51       if(check(mid)){52         l=mid+1;53       }54       else r=mid-1;55       if(sum<ans) ans=sum;56     }57     printf("%lld",ans);58     return 0;59   }60 }61 signed main(){62   gengyf::main();63   return 0;64 }

Day2T3 观光公交

标签:贪心

滴,您的智商余额不足,请充值～

这题是在班会课上想明白的

我们把每个乘客的上下车站点看成区间

step 1:

先考虑如果你只有一个加速器会放到哪

肯定放在被覆盖次数最多的[i,i+1)

step 2:

如果只有一个人,在2号点上车,1号点和2号点的距离为1

但这个人在第10分钟才来,你还是只有一个加速器,那完全可以不放对吧

因为不管你放还是不放,都要等到第10分钟才能再出发往后开

step 3:

所以我们发现了贪心策略

<1>找到被覆盖次数最多的那一段,放一个加速器

<2>如果放了加速器之后还是需要等下一个站点到的人,就不放

code(有注释)

 1 #include <bits/stdc++.h> 2 using namespace std; 3 namespace gengyf{ 4 #define ll long long 5   inline int read(){ 6     int x=0,f=1;char s=getchar(); 7     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 9     return f*x;10   }11   const int maxn=1e3+10;12   const int maxm=1e4+10;13   int n,m,k,d[maxn],last[maxn],sum[maxm],ans;14   int f[maxn],maxx,g[maxn];15   //f[i]每个站点能影响的最远站点16   //last[i]最后一个人到i站的时间17   //g[i]车到i站点的最早时间18   struct node{19     int t,l,r;20   }a[maxm];21   void drive(int x){22     while(x--){23       f[n]=f[n-1]=n;24       int mark=0;maxx=-1;25       for(int i=n-2;i>=1;i--){26         if(g[i+1]<=last[i+1]){//如果需要等下一个乘客,影响+127           f[i]=i+1;28         }29         else f[i]=f[i+1];30       }31       for(int i=1;i<=n-1;i++){32         int tmp=sum[f[i]]-sum[i];//最多影响的人数33         if(tmp>maxx&&d[i]>0){34           maxx=tmp;mark=i;//标记最需要减少时间的点35         }36       }37       ans-=maxx;d[mark]--;//更新装一个加速器后对答案和边的贡献38       for(int i=2;i<=n;i++){//更新39         g[i]=max(g[i-1],last[i-1])+d[i-1];40       }41     }42   }43   int main(){44     n=read();m=read();k=read();45     for(int i=1;i<=n-1;i++){46       d[i]=read();47     }48     for(int i=1;i<=m;i++){49       a[i].t=read();a[i].l=read();a[i].r=read();50     }51     for(int i=1;i<=m;i++){52       last[a[i].l]=max(last[a[i].l],a[i].t);//最后一个到该站点的时间53       sum[a[i].r]++;54     }55     g[1]=last[1];56     for(int i=1;i<=n;i++){57       sum[i]+=sum[i-1];//到该站点的总人数58     }59     for(int i=2;i<=n;i++){//车到i站点的最少时间60       g[i]=max(g[i-1],last[i-1])+d[i-1];61     }62     for(int i=1;i<=m;i++){63       ans+=g[a[i].r]-a[i].t;//不需要加速器的答案64     }65     drive(k);66     printf("%d",ans);67     return 0;68   }69 }70 signed main(){71   gengyf::main();72   return 0;73 }

6道题的NOIp就是没有4道的好写啊