[关闭]
@KirinBill 2017-10-05T12:35:27.000000Z 字数 4859 阅读 556

2017.10.2 NOIP模拟赛

题解 套题

目录


最大矩形

AtTMr.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. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <algorithm>
  30. using std::max;
  31. using std::sort;
  32. const int MAXN=100005;
  33. int n;
  34. int hi[MAXN];
  35. bool cmp(int a,int b){return a>b;}
  36. inline long long cal(){
  37. sort(hi+1,hi+n+1,cmp);
  38. int h=hi[1],w=1;
  39. long long ret=h;
  40. for(int i=2;i<=n;++i){
  41. h=hi[i];
  42. ++w;
  43. ret=max(ret,(long long)h*w);
  44. }
  45. return ret;
  46. }
  47. int main(){
  48. setIO("rectangle");
  49. int T;
  50. read(T);
  51. while(T--){
  52. read(n);
  53. for(int i=1;i<=n;++i)
  54. read(hi[i]);
  55. write(cal(),'\n');
  56. }
  57. return 0;
  58. }

确定小组

AtPUt.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. int pm=1; char c;
  13. do{
  14. c=getchar();
  15. if(c=='-') pm=-1;
  16. }while(!isdigit(c));
  17. x=c^'0';
  18. while(c=getchar(),isdigit(c))
  19. x=x*10+(c^'0');
  20. x*=pm;
  21. }
  22. template<typename type>
  23. void write(type x,char c=0){
  24. if(x<0) putchar('-'),x=-x;
  25. if(x>9) write(x/10);
  26. putchar(x%10|'0');
  27. if(c) putchar(c);
  28. }
  29. #include <cstring>
  30. #include <climits>
  31. #include <algorithm>
  32. using std::min;
  33. const int MAXN=1005;
  34. int n;
  35. int ans[MAXN];
  36. inline int lim(int x){return min(2,x);}
  37. inline bool jud(){
  38. //f[i]=前i个人的方案数
  39. static int f[MAXN];
  40. memset(f,0,sizeof(f));
  41. f[0]=1;
  42. for(int i=1;i<=n;++i){
  43. for(int j=i,belong_cnt=0;j;--j){
  44. if(ans[j]){
  45. if(belong_cnt && belong_cnt!=ans[j])
  46. break;
  47. else belong_cnt=ans[j];
  48. }
  49. if(!belong_cnt || i-j+1==belong_cnt)
  50. f[i]=lim(f[i]+f[j-1]);
  51. }
  52. }
  53. return f[n]==1;
  54. }
  55. int main(){
  56. setIO("group");
  57. int T;
  58. read(T);
  59. while(T--){
  60. read(n);
  61. for(int i=1;i<=n;++i)
  62. read(ans[i]);
  63. if(jud()) puts("1");
  64. else puts("0");
  65. }
  66. return 0;
  67. }

华容道游戏

AtxfF.png
AtFvM.png

思路

代码

  1. #include <cstdio>
  2. #include <queue>
  3. #include <set>
  4. using std::queue;
  5. using std::set;
  6. const int MAXN=7,MAXTP=9,n=5,m=4;
  7. int type[MAXTP];
  8. struct Graph{
  9. static const int mod=7;
  10. int c[MAXN][MAXN];
  11. int* operator[] (int i){return c[i];}
  12. long long hash(){
  13. long long ret=0;
  14. for(int i=1;i<=n;++i){
  15. for(int j=1;j<=m;++j)
  16. ret=ret<<3|type[c[i][j]];
  17. }
  18. return ret;
  19. }
  20. long long zip(){
  21. long long ret=0;
  22. for(int i=1;i<=n;++i){
  23. for(int j=1;j<=m;++j)
  24. ret=ret<<3|c[i][j];
  25. }
  26. return ret;
  27. }
  28. void unzip(long long a){
  29. for(int i=n;i;--i){
  30. for(int j=m;j;--j){
  31. c[i][j]=a&mod;
  32. a>>=3;
  33. }
  34. }
  35. }
  36. }G;
  37. inline bool win(Graph &G){
  38. return G[5][2]==2 && G[5][3]==2;
  39. }
  40. inline int BFS(){
  41. static int dirx[]={0,1,0,-1},diry[]={1,0,-1,0};
  42. static int judx[5][4]={{},{0,0,0,0},{1,1,0,0},{1,1,0,0},{0,0,0,0}};
  43. static int judy[5][4]={{},{0,0,0,0},{1,0,1,0},{0,0,0,0},{1,0,1,0}};
  44. static queue<int> step;
  45. static queue<long long> que;
  46. static set<long long> se;
  47. if(win(G)) return 0;
  48. se.clear();
  49. while(que.size()) que.pop(),step.pop();
  50. se.insert(G.hash());
  51. que.push(G.zip()),step.push(0);
  52. bool can;
  53. int now;
  54. long long hs;
  55. while(que.size()){
  56. G.unzip(que.front());
  57. que.pop();
  58. now=step.front();
  59. step.pop();
  60. for(int i=1;i<=n;++i){
  61. for(int j=1,id,col;j<=m;++j){
  62. col=G[i][j],id=type[G[i][j]];
  63. if(id==0) continue;
  64. can=true;
  65. for(int k=0;k<4;++k)
  66. can&=(G[i+judx[id][k]][j+judy[id][k]]==G[i][j]);
  67. if(!can) continue;
  68. for(int k=0;k<4;++k)
  69. G[i+judx[id][k]][j+judy[id][k]]=0;
  70. for(int k=0,x,y;k<4;++k){
  71. x=i+dirx[k],y=j+diry[k];
  72. can=true;
  73. for(int l=0;l<4;++l)
  74. can&=(G[x+judx[id][l]][y+judy[id][l]]==0);
  75. if(!can) continue;
  76. for(int l=0;l<4;++l)
  77. G[x+judx[id][l]][y+judy[id][l]]=col;
  78. if(win(G)) return now+1;
  79. hs=G.hash();
  80. if(!se.count(hs)){
  81. que.push(G.zip());
  82. se.insert(hs);
  83. step.push(now+1);
  84. }
  85. for(int l=0;l<4;++l)
  86. G[x+judx[id][l]][y+judy[id][l]]=0;
  87. }
  88. for(int k=0;k<4;++k)
  89. G[i+judx[id][k]][j+judy[id][k]]=col;
  90. }
  91. }
  92. }
  93. return -1;
  94. }
  95. inline void prepare(){
  96. for(int i=1;i<=n;++i){
  97. for(int j=1;j<=m;++j){
  98. if(G[i][j]>=3){
  99. if(G[i-1][j]==G[i][j] || G[i+1][j]==G[i][j])
  100. type[G[i][j]]=3;
  101. else if(G[i][j-1]==G[i][j] || G[i][j+1]==G[i][j])
  102. type[G[i][j]]=4;
  103. }
  104. else type[G[i][j]]=G[i][j];
  105. }
  106. }
  107. }
  108. int main(){
  109. freopen("huarong.in","r",stdin);
  110. freopen("huarong.out","w",stdout);
  111. for(int i=0,lim=n+1,tmp=m+1;i<=lim;++i)
  112. G[i][0]=G[i][tmp]=-1;
  113. for(int i=0,lim=m+1,tmp=n+1;i<=lim;++i)
  114. G[0][i]=G[tmp][i]=-1;
  115. int T;
  116. scanf("%d",&T);
  117. while(T--){
  118. for(int i=1;i<=n;++i){
  119. for(int j=1;j<=m;++j)
  120. scanf("%d",&G[i][j]);
  121. }
  122. prepare();
  123. printf("%d\n",BFS());
  124. }
  125. return 0;
  126. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注