【NOIp】NOIp2014

- 日理万妓 2023-08-17 16:49 246阅读 0赞

NOIp 2014

day 1 T1 生活大爆炸版石头剪刀布

标签：模拟

code(巨丑

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <iostream>
  2.  2 #include <cstdio>
  3.  3 using namespace std;
  4.  4 int main(){
  5.  5     int n,na,nb,x,y,xa[201],xb[201],i,j,a,ans,bns;
  6.  6     cin>>n>>na>>nb;
  7.  7     for(i=1;i<=na;i++){
  8.  8         cin>>x;
  9.  9         xa[i]=x;
  10. 10     }
  11. 11     for(j=1;j<=nb;j++){
  12. 12         cin>>y;
  13. 13         xb[j]=y;
  14. 14     }
  15. 15     ans=0;bns=0;
  16. 16     i=0;j=0;
  17. 17     for(a=1;a<=n;a++){
  18. 18         i++;j++;
  19. 19         if(i>na)i=1;
  20. 20         if(j>nb)j=1;
  21. 21         if(xa[i]==0&&xb[j]==1)bns++;
  22. 22         if(xa[i]==0&&xb[j]==2)ans++;
  23. 23         if(xa[i]==0&&xb[j]==3)ans++;
  24. 24         if(xa[i]==0&&xb[j]==4)bns++;
  25. 25         if(xa[i]==1&&xb[j]==0)ans++;
  26. 26         if(xa[i]==1&&xb[j]==2)bns++;
  27. 27         if(xa[i]==1&&xb[j]==3)ans++;
  28. 28         if(xa[i]==1&&xb[j]==4)bns++;
  29. 29         if(xa[i]==2&&xb[j]==0)bns++;
  30. 30         if(xa[i]==2&&xb[j]==1)ans++;
  31. 31         if(xa[i]==2&&xb[j]==3)bns++;
  32. 32         if(xa[i]==2&&xb[j]==4)ans++;
  33. 33         if(xa[i]==3&&xb[j]==0)bns++;
  34. 34         if(xa[i]==3&&xb[j]==1)bns++;
  35. 35         if(xa[i]==3&&xb[j]==2)ans++;
  36. 36         if(xa[i]==3&&xb[j]==4)ans++;
  37. 37         if(xa[i]==4&&xb[j]==0)ans++;
  38. 38         if(xa[i]==4&&xb[j]==1)ans++;
  39. 39         if(xa[i]==4&&xb[j]==2)bns++;
  40. 40         if(xa[i]==4&&xb[j]==3)bns++;
  41. 41     }
  42. 42     cout<<ans<<" "<<bns;
  43. 43     return 0;
  44. 44 }

T1

day 1 T2 联合权值

标签：dp

转化：

step 1: 无向图，n个点，n-1条边 => 一棵树

step 2: 距离为2 => 和同一个点相连

枚举每一个点，取任意两点组合得到乘积最大值和sum

对于一个点，线性扫过所有与他相连的点，然后动态更新目前的和与目前这些点中的最大值

再到下一个点时，将下一个点的权值与这两个值相乘

code

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 namespace gengyf{
  4.  4 #define int long long
  5.  5   inline int read(){
  6.  6     int x=0,f=1;char s=getchar();
  7.  7     while(s<'0'||s>'9'){
  8.      if(s=='-')f=-1;s=getchar();}
  9.  8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
  10.  9     return f*x;
  11. 10   }
  12. 11   const int mod=10007;
  13. 12   const int maxn=2e5+10;
  14. 13   struct edge{
  15. 14     int nxt,to;
  16. 15   }e[maxn*2];
  17. 16   int head[maxn],cnt,n,w[maxn];
  18. 17   inline void add(int from,int to){
  19. 18     e[++cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;
  20. 19   }
  21. 20   int ans,maxx;
  22. 21   int main(){
  23. 22     n=read();
  24. 23     for(int i=1;i<n;i++){
  25. 24       int u,v;
  26. 25       u=read();v=read();
  27. 26       add(u,v);add(v,u);
  28. 27     }
  29. 28     for(int i=1;i<=n;i++){
  30. 29       w[i]=read();
  31. 30     }
  32. 31     for(int i=1;i<=n;i++){
  33. 32       int max1=0,max2=0,t1=0,t2=0;
  34. 33       for(int j=head[i];j;j=e[j].nxt){
  35. 34         if(w[e[j].to]>max1){
  36. 35           max2=max1;max1=w[e[j].to];
  37. 36         }
  38. 37         else if(w[e[j].to]>max2)max2=w[e[j].to];
  39. 38         t1=(t1+w[e[j].to])%mod;
  40. 39         t2=(t2+w[e[j].to]*w[e[j].to])%mod;
  41. 40       }
  42. 41       t1=t1*t1%mod;
  43. 42       ans=(ans+t1-t2+mod)%mod;
  44. 43       if(maxx<max1*max2)maxx=max1*max2;
  45. 44     }
  46. 45     printf("%lld %lld",maxx,ans);
  47. 46     return 0;
  48. 47   }
  49. 48 }
  50. 49 signed main(){
  51. 50   gengyf::main();
  52. 51   return 0;
  53. 52 }

T2

day 1 T3 飞扬的小鸟

标签：dp

上升 -> 完全背包 单位时间上升是可以叠加的

下降 -> 01背包 单位时间只能下降1次

转移：

<1>上升

<2>飞到顶上

<3>下降

<4>有柱子

上升：$f[i][j]=min(f[i][j],min(f[i-1][j-lift[i-1],f[i][j-lift[i-1]])+1)$

code

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include<bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 #define MAXN 1<<30
  4.  4 struct Pipe{
  5.  5     int pos,up,bottom;
  6.  6 }pipe[10010];
  7.  7 int n,m,k,lift[10010],down[10010],f[10010][1010];
  8.  8 bool cmp(Pipe a,Pipe b){
  9.  9     return a.pos<b.pos;
  10. 10 }
  11. 11 int main(){
  12. 12     scanf("%d%d%d",&n,&m,&k);
  13. 13     for(int i=0;i<=n-1;i++){
  14. 14         scanf("%d%d",&lift[i],&down[i]);
  15. 15     }
  16. 16     for(int i=1;i<=k;i++){
  17. 17         scanf("%d%d%d",&pipe[i].pos,&pipe[i].bottom,&pipe[i].up); 
  18. 18     }
  19. 19     sort(pipe+1,pipe+k+1,cmp);
  20. 20     for(int i=0;i<=n;i++)
  21. 21         for(int j=0;j<=m;j++){
  22. 22             f[i][j]=MAXN;
  23. 23         }
  24. 24     for(int i=1;i<=m;i++)f[0][i]=0;
  25. 25     int nump=1;
  26. 26     for(int i=1;i<=n;i++){
  27. 27         int lower=1,upper=m;
  28. 28         if(pipe[nump].pos==i){
  29. 29             upper=pipe[nump].up-1;
  30. 30             lower=pipe[nump++].bottom+1; 
  31. 31         }
  32. 32         for(int j=1;j<=upper;j++){
  33. 33             for(int k=j-lift[i-1];k<=m;k++){
  34. 34                 if(k>j-lift[i-1]&&j<m)break;
  35. 35                 if(k>=1)f[i][j]=min(f[i][j],min(f[i-1][k],f[i][k])+1);
  36. 36             }
  37. 37         }
  38. 38         for(int j=lower;j<=upper;j++){
  39. 39             if(j+down[i-1]<=m){
  40. 40                 f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);
  41. 41             }
  42. 42         }
  43. 43         for(int j=1;j<=lower-1;j++)f[i][j]=MAXN;
  44. 44     }
  45. 45     int minn=MAXN;
  46. 46     bool flag=false;
  47. 47     for(int i=n;i>=1;i--){
  48. 48         for(int j=1;j<=m;j++){
  49. 49             if(f[i][j]!=MAXN){
  50. 50                 flag=true;
  51. 51                 minn=min(minn,f[i][j]);
  52. 52             }
  53. 53         }
  54. 54         if(flag){
  55. 55             if(i==n){
  56. 56                 printf("1\n%d",minn); 
  57. 57                 return 0;
  58. 58             }
  59. 59             else{
  60. 60                 for(int j=k;j>=1;j--){
  61. 61                     if(i>=pipe[j].pos){
  62. 62                         printf("0\n%d",j);
  63. 63                         return 0;
  64. 64                     }
  65. 65                 }
  66. 66             }
  67. 67         }
  68. 68     }
  69. 69     printf("0\n0");
  70. 70     return 0;
  71. 71 }

T3

day 2 T1 无线网络发射器选址

标签：模拟，二维前缀和

枚举每一个点，更新最大值+统计答案个数

code

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 namespace gengyf{
  4.  4 #define ll long long
  5.  5   inline int read(){
  6.  6     int x=0,f=1;char s=getchar();
  7.  7     while(s<'0'||s>'9'){
  8.      if(s=='-')f=-1;s=getchar();}
  9.  8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
  10.  9     return f*x;
  11. 10   }
  12. 11   int a[130][130],n,d,s[130][130],ans,cnt;
  13. 12   int main(){
  14. 13     d=read();n=read();
  15. 14     for(int i=1;i<=n;i++){
  16. 15       int x,y,num;
  17. 16       x=read();y=read();num=read();
  18. 17       a[x][y]=num;
  19. 18     }
  20. 19     for(int i=0;i<=128;i++)
  21. 20       for(int j=0;j<=128;j++){
  22. 21         s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
  23. 22       }
  24. 23     for(int i=0;i<=128;i++)
  25. 24       for(int j=0;j<=128;j++){
  26. 25         int x1,x2,y1,y2;
  27. 26         x1=max(i-d,0);y1=max(j-d,0);
  28. 27         x2=min(i+d,128);y2=min(j+d,128);
  29. 28         int tmp=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
  30. 29         if(tmp==ans)cnt++;
  31. 30         else if(tmp>ans){
  32. 31           cnt=1;ans=tmp;
  33. 32         }
  34. 33       }
  35. 34     printf("%d %d",cnt,ans);
  36. 35     return 0;
  37. 36   }
  38. 37 }
  39. 38 signed main(){
  40. 39   gengyf::main();
  41. 40   return 0;
  42. 41 }

T4

day 2 T2 寻找道路

标签：图论，最短路

对于要求1可以反向建图dfs标记能到终点的点

如果标记的点，如果它的出边有未被标记的，则不合法，取消标记

对于要求2在标记的点中跑最短路

code

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 namespace gengyf{
  4.  4 #define ll long long
  5.  5 inline int read(){
  6.  6     int x=0,f=1;char s=getchar();
  7.  7     while(s<'0'||s>'9'){
  8.      if(s=='-')f=-1;s=getchar();}
  9.  8     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
  10.  9     return f*x;
  11. 10 }
  12. 11 const int maxn=1e4+10;
  13. 12 vector<int>G[maxn];
  14. 13 queue<int>q;
  15. 14 bool v[maxn],vis[maxn];
  16. 15 int n,m,ans[maxn],s,t;
  17. 16 int main(){
  18. 17     n=read();m=read();
  19. 18     for(int i=1;i<=m;i++){
  20. 19         int a,b;a=read();b=read();
  21. 20         if(a==b)continue;
  22. 21         G[b].push_back(a);
  23. 22     }
  24. 23     s=read();t=read();
  25. 24     v[t]=1;q.push(t);
  26. 25     while(!q.empty()){
  27. 26         int x=q.front();
  28. 27         q.pop();
  29. 28         for(int i=0;i<G[x].size();i++){
  30. 29             if(!v[G[x][i]]){
  31. 30                 v[G[x][i]]=1;
  32. 31                 q.push(G[x][i]);
  33. 32             }
  34. 33         }
  35. 34     }
  36. 35     memcpy(vis,v,sizeof(v));
  37. 36     for(int i=1;i<=n;i++){
  38. 37         if(!v[i]){
  39. 38             for(int j=0;j<G[i].size();j++){
  40. 39                 if(vis[G[i][j]])vis[G[i][j]]=0;
  41. 40             }
  42. 41         }
  43. 42     }
  44. 43     q.push(t);
  45. 44     while(!q.empty()){
  46. 45         int x=q.front();
  47. 46         q.pop();
  48. 47         for(int i=0;i<G[x].size();i++){
  49. 48             if(vis[G[x][i]]){
  50. 49                 q.push(G[x][i]);
  51. 50                 vis[G[x][i]]=0;
  52. 51                 ans[G[x][i]]=ans[x]+1;
  53. 52             }
  54. 53         }
  55. 54     }
  56. 55     if(ans[s]==0)puts("-1");
  57. 56     else printf("%d",ans[s]);
  58. 57     return 0;
  59. 58 }
  60. 59 }
  61. 60 signed main(){
  62. 61   gengyf::main();
  63. 62   return 0;
  64. 63 }

T5

day 2 T3 解方程

标签：数学

秦九韶算法O(n)

枚举[1,m]代入函数f(x)看是否为0，注意取模

code

ContractedBlock.gif ExpandedBlockStart.gif

  1. 1 #include <bits/stdc++.h>
  2.  2 using namespace std;
  3.  3 namespace gengyf{
  4.  4 #define ll long long
  5.  5 const int p=1e9+7;
  6.  6 const int maxn=1e6+10;
  7.  7 inline ll read(){
  8.  8     ll x=0,f=1;
  9.  9     char c=getchar();
  10. 10     while(c<'0'||c>'9'){
  11.      if(c=='-')f=-1;c=getchar();}
  12. 11     while(c>='0'&&c<='9'){x=((x*10)+c-'0')%p;c=getchar();}
  13. 12     return x*f;
  14. 13 }
  15. 14 ll sum,a[110],n,m,ans[maxn],cnt;
  16. 15 bool t=1;
  17. 16 bool calc(ll x){
  18. 17     sum=0;
  19. 18     for(ll i=n;i>=1;i--){
  20. 19         sum=((a[i]+sum)*x)%p;
  21. 20     }
  22. 21     sum=(sum+a[0])%p;
  23. 22     return !sum;
  24. 23 }
  25. 24 int main(){
  26. 25     n=read();
  27. 26     m=read();
  28. 27     for(ll i=0;i<=n;i++){
  29. 28         a[i]=read();
  30. 29     }
  31. 30     for(ll i=1;i<=m;i++){
  32. 31         if(calc(i)){
  33. 32             t=false;
  34. 33             cnt++;
  35. 34             ans[cnt]=i;
  36. 35         }
  37. 36     }
  38. 37     if(t){
  39. 38         cout<<cnt<<endl;
  40. 39         return 0;
  41. 40     }
  42. 41     printf("%lld\n",cnt);
  43. 42     for(int i=1;i<=cnt;i++){
  44. 43         printf("%lld\n",ans[i]);
  45. 44     }
  46. 45     return 0;
  47. 46 }
  48. 47 }
  49. 48 signed main(){
  50. 49   gengyf::main();
  51. 50   return 0;
  52. 51 }

T6

1658269-20190923195217433-55350986.png

4102年的题真友好

转载于:https://www.cnblogs.com/gengyf/p/11573558.html

发表评论

表情：
评论列表 （有 0 条评论，246人围观）

还没有评论，来说两句吧...

相关阅读

    相关 岁月走过，2014

    若能持之以恒，又何必三更睡五更起 —题记 　　伴随着新年钟声的响起，我们告别了2014年，迎来了崭新的2015年。一年的悠悠岁月就如同手中的细沙，无声无息的悄然流逝。

    深藏阁楼爱情的钟深藏阁楼爱情的钟/ 0 赞/ 311 阅读

    相关 2014年底总结

    这是第一次写年底总结，其实每年一直都有年底写总结的想法，可总是手头的事情很多，最终计划赶不上变化，最后写总结的想法就不了了之了。今天手头上没有什么工作，趁着现在有些空闲的时间，

    布满荆棘的人生布满荆棘的人生/ 0 赞/ 322 阅读

    相关 2014 小结

    转自：http://wuduoyi.com/note/2014/ 今年是我变化最大的一年，尽管在技术上的折腾变少了，但在团队建设及产品设计方面都学到很多。 FEX 团队

    素颜马尾好姑娘i素颜马尾好姑娘i/ 0 赞/ 290 阅读

    相关 2014面试题

    1.讲讲spring 2.为什么使用springmvc，不使用ssh 3.说说使用的设计模式 4.说说sql优化的常用方法 5.如果一单例对象要在集群环境下，怎么实现

    ゝ一世哀愁。ゝ一世哀愁。/ 0 赞/ 255 阅读