[关闭]
@KirinBill 2017-09-19T09:36:05.000000Z 字数 5769 阅读 627

2017.9.16 NOIP模拟赛

题解 套题

考试时,永远不要想着能AK。。。

目录


Crash的任务

rWQey.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. x=0;
  13. int pm=1; char c;
  14. do{c=getchar();}while(!isdigit(c) && c!='-');
  15. c=='-' ? pm=-1:x=c^'0';
  16. while(c=getchar(),isdigit(c))
  17. x=x*10+(c^'0');
  18. x*=pm;
  19. }
  20. template<typename type>
  21. void write(type x,char c=0){
  22. if(x<0) putchar('-'),x=-x;
  23. if(x>9) write(x/10);
  24. putchar(x%10|'0');
  25. if(c) putchar(c);
  26. }
  27. const int MAXN=100005,P=1e9+7;
  28. int n;
  29. int exa[MAXN],both[MAXN],dp[MAXN][2];
  30. inline int DP(){
  31. dp[1][0]=exa[1];
  32. dp[1][1]=both[1];
  33. for(int i=2,rest;i<=n;++i){
  34. rest=both[i-1]-1;
  35. rest= rest<0 ? 0:rest;
  36. dp[i][0]=(long long)dp[i-1][1]*(exa[i]+rest)%P;
  37. dp[i][0]=(dp[i][0]+(long long)dp[i-1][0]*(exa[i]+both[i-1])%P)%P;
  38. dp[i][1]=(long long)both[i]*(dp[i-1][0]+dp[i-1][1])%P;
  39. }
  40. return dp[n][0];
  41. }
  42. int main(){
  43. setIO("choose");
  44. read(n);
  45. for(int i=1;i<=n;++i)
  46. read(exa[i]);
  47. for(int i=1;i<n;++i)
  48. read(both[i]);
  49. write(DP());
  50. return 0;
  51. }

星际旅行

rWa7j.png
rWF17.png

思路

代码

  1. #include <cstdio>
  2. #include <cctype>
  3. #include <string>
  4. using std::string;
  5. inline void setIO(string file){
  6. string in=file+".in",out=file+".out";
  7. freopen(in.c_str(),"r",stdin);
  8. freopen(out.c_str(),"w",stdout);
  9. }
  10. template<typename type>
  11. inline void read(type &x){
  12. x=0;
  13. int pm=1; char c;
  14. do{c=getchar();}while(!isdigit(c) && c!='-');
  15. c=='-' ? pm=-1:x=c^'0';
  16. while(c=getchar(),isdigit(c))
  17. x=x*10+(c^'0');
  18. x*=pm;
  19. }
  20. template<typename type>
  21. void write(type x,char c=0){
  22. if(x<0) putchar('-'),x=-x;
  23. if(x>9) write(x/10);
  24. putchar(x%10|'0');
  25. if(c) putchar(c);
  26. }
  27. #include <algorithm>
  28. using std::sort;
  29. const int MAXN=1e5+5;
  30. int n,m;
  31. int ufs[MAXN];
  32. struct line{
  33. int u,v,w;
  34. line(int u=0,int v=0,int w=0):u(u),v(v),w(w){}
  35. friend bool operator< (const line &a,const line &b){
  36. return a.w<b.w;
  37. }
  38. }ed[MAXN*3];
  39. struct point{
  40. int x,y,z,id;
  41. static bool cmp_x(const point &a,const point &b){
  42. return a.x<b.x;
  43. }
  44. static bool cmp_y(const point &a,const point &b){
  45. return a.y<b.y;
  46. }
  47. static bool cmp_z(const point &a,const point &b){
  48. return a.z<b.z;
  49. }
  50. }p[MAXN];
  51. inline void ufs_init(int n){
  52. for(int i=1;i<=n;++i)
  53. ufs[i]=i;
  54. }
  55. int find_anc(int x){
  56. if(x==ufs[x]) return x;
  57. ufs[x]=find_anc(ufs[x]);
  58. return ufs[x];
  59. }
  60. inline void deal(){
  61. sort(p+1,p+n+1,point::cmp_x);
  62. for(int i=1;i<n;++i)
  63. ed[++m]=line(p[i].id,p[i+1].id,p[i+1].x-p[i].x);
  64. sort(p+1,p+n+1,point::cmp_y);
  65. for(int i=1;i<n;++i)
  66. ed[++m]=line(p[i].id,p[i+1].id,p[i+1].y-p[i].y);
  67. sort(p+1,p+n+1,point::cmp_z);
  68. for(int i=1;i<n;++i)
  69. ed[++m]=line(p[i].id,p[i+1].id,p[i+1].z-p[i].z);
  70. }
  71. inline long long Kruskal(){
  72. ufs_init(n);
  73. sort(ed+1,ed+m+1);
  74. long long ret=0;
  75. for(int i=1,j=0,lim=n-1,ufa,vfa;j<lim;++i){
  76. ufa=find_anc(ed[i].u);
  77. vfa=find_anc(ed[i].v);
  78. if(ufa!=vfa){
  79. ufs[ufa]=vfa;
  80. ret+=ed[i].w;
  81. ++j;
  82. }
  83. }
  84. return ret;
  85. }
  86. int main(){
  87. setIO("planet");
  88. read(n);
  89. for(int i=1;i<=n;++i){
  90. read(p[i].x),read(p[i].y),read(p[i].z);
  91. p[i].id=i;
  92. }
  93. deal();
  94. write(Kruskal());
  95. return 0;
  96. }

回家的路线

rWpZK.png
rWB2s.png

思路

我开始竟没有想到是,用了Dijkstra的思想A了,不过常数好大啊...

代码

  1. #include <cstdio>
  2. #include <queue>
  3. #include <algorithm>
  4. #include <cstring>
  5. using std::queue;
  6. using std::max;
  7. using std::min;
  8. const int MAXN=505,INF=1e9;
  9. int n,m;
  10. int dis[MAXN][MAXN];
  11. char mp[MAXN][MAXN];
  12. struct node{
  13. int x,y;
  14. node(int x=0,int y=0):x(x),y(y){}
  15. }s,t;
  16. inline void cal_dis(){
  17. static int last[MAXN];
  18. memset(dis,0x7f,sizeof(dis));
  19. memset(last,-0x3f,sizeof(last));
  20. for(int i=1;i<=n;++i){
  21. for(int j=1,maxd=-INF;j<=m;++j){
  22. if(mp[i][j]=='+') last[j]=i;
  23. maxd=max(maxd,last[j]+j);
  24. dis[i][j]=min(dis[i][j],i+j-maxd);
  25. }
  26. }
  27. memset(last,-0x3f,sizeof(last));
  28. for(int i=1;i<=n;++i){
  29. for(int j=m,maxd=-INF;j;--j){
  30. if(mp[i][j]=='+') last[j]=i;
  31. maxd=max(maxd,last[j]-j);
  32. dis[i][j]=min(dis[i][j],i-j-maxd);
  33. }
  34. }
  35. memset(last,0x3f,sizeof(last));
  36. for(int i=n;i;--i){
  37. for(int j=1,maxd=-INF;j<=m;++j){
  38. if(mp[i][j]=='+') last[j]=i;
  39. maxd=max(maxd,-last[j]+j);
  40. dis[i][j]=min(dis[i][j],-i+j-maxd);
  41. }
  42. }
  43. memset(last,0x3f,sizeof(last));
  44. for(int i=n;i;--i){
  45. for(int j=m,maxd=-INF;j;--j){
  46. if(mp[i][j]=='+') last[j]=i;
  47. maxd=max(maxd,-last[j]-j);
  48. dis[i][j]=min(dis[i][j],-i-j-maxd);
  49. }
  50. }
  51. }
  52. inline bool in_G(int x,int y){
  53. return x>0 && x<=n && y>0 && y<=m;
  54. }
  55. inline bool jud(int lim){
  56. static int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};
  57. static bool vis[MAXN][MAXN];
  58. static queue<node> que;
  59. if(dis[s.x][s.y]<lim) return false;
  60. while(que.size()) que.pop();
  61. memset(vis,false,sizeof(vis));
  62. que.push(s);
  63. vis[s.x][s.y]=true;
  64. node u;
  65. int x,y;
  66. while(que.size()){
  67. u=que.front();
  68. que.pop();
  69. for(int i=0;i<4;++i){
  70. x=u.x+dir[i][0],y=u.y+dir[i][1];
  71. if(in_G(x,y) && !vis[x][y] && dis[x][y]>=lim){
  72. if(x==t.x && y==t.y) return true;
  73. que.push(node(x,y));
  74. vis[x][y]=true;
  75. }
  76. }
  77. }
  78. return false;
  79. }
  80. inline int bin_chop(){
  81. int l=1,r=n+m,mid;
  82. while(l<=r){
  83. mid=l+r>>1;
  84. if(jud(mid)) l=mid+1;
  85. else r=mid-1;
  86. }
  87. return l-1;
  88. }
  89. int main(){
  90. freopen("path.in","r",stdin);
  91. freopen("path.out","w",stdout);
  92. scanf("%d%d",&n,&m);
  93. for(int i=1;i<=n;++i)
  94. scanf("%s",mp[i]+1);
  95. for(int i=1;i<=n;++i){
  96. for(int j=1;j<=m;++j){
  97. if(mp[i][j]=='V') s=node(i,j);
  98. else if(mp[i][j]=='J') t=node(i,j);
  99. }
  100. }
  101. cal_dis();
  102. printf("%d",bin_chop());
  103. return 0;
  104. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注