[关闭]
@KirinBill 2017-10-10T07:16:06.000000Z 字数 4012 阅读 1121

2017.10.10 NOIP模拟赛

题解 套题

目录


排队

AKlL1.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. const int MAXN=5005;
  30. int n;
  31. int cnt[MAXN],ans[MAXN];
  32. int main(){
  33. #ifdef DEBUG
  34. setIO("a");
  35. #endif
  36. read(n);
  37. for(int i=1;i<=n;++i)
  38. read(cnt[i]);
  39. for(int i=1;i<=n;++i){
  40. for(int j=1,k=0;j<=n;++j){
  41. if(ans[j]) continue;
  42. if(++k==cnt[i]+1){
  43. ans[j]=i;
  44. break;
  45. }
  46. }
  47. }
  48. for(int i=1;i<=n;++i)
  49. write(ans[i],' ');
  50. return 0;
  51. }

蛋糕

AKmFu.png
AKCwd.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 <cmath>
  30. #include <algorithm>
  31. using std::abs;
  32. using std::max;
  33. const int MAXXY=5005;
  34. int n,m,x,y,ans,cntx,cnty;
  35. int posx[MAXXY],posy[MAXXY];
  36. int main(){
  37. #ifdef DEBUG
  38. setIO("b");
  39. #endif
  40. int T;
  41. read(T);
  42. while(T--){
  43. read(n),read(m);
  44. read(x),read(y);
  45. for(int i=1;i<=x;++i)
  46. read(posx[i]);
  47. for(int i=1;i<=y;++i)
  48. read(posy[i]);
  49. cntx=cnty=0;
  50. for(int i=1;i<=x;++i){
  51. if(abs(posx[i])<=m) ++cntx;
  52. }
  53. for(int i=1;i<=y;++i){
  54. if(abs(posy[i])<=m) ++cnty;
  55. }
  56. ans=0;
  57. if((!cntx || !cnty) && (cntx || cnty)) ans+=max(cntx-1,cnty-1);
  58. cntx=max(cntx-1,0),cnty=max(cnty-1,0);
  59. ans+=(x+1)*(y+1)-cntx*cnty;
  60. write(ans,'\n');
  61. }
  62. return 0;
  63. }

差异

AKcAa.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. #include <iostream>
  31. #include <cmath>
  32. using std::__gcd;
  33. using std::ostream;
  34. using std::cout;
  35. using std::abs;
  36. const int MAXN=200005;
  37. int n,tot;
  38. int a[MAXN],lp[MAXN],rp[MAXN];
  39. long long sum[MAXN];
  40. struct frac{
  41. long long up,dwn;
  42. frac(long long up=0,long long dwn=1):up(up),dwn(dwn){
  43. if(this->dwn<0) this->up=-this->up,this->dwn=-this->dwn;
  44. long long gcd=__gcd(abs(this->up),abs(this->dwn));
  45. this->up/=gcd,this->dwn/=gcd;
  46. }
  47. friend bool operator> (frac a,frac b){
  48. long long lcm=a.dwn*b.dwn/__gcd(a.dwn,b.dwn);
  49. a.up*=lcm/a.dwn;
  50. b.up*=lcm/b.dwn;
  51. return a.up>b.up;
  52. }
  53. friend ostream& operator<< (ostream &out,frac &a){
  54. write(a.up,'/');
  55. write(a.dwn);
  56. return out;
  57. }
  58. }ans[MAXN];
  59. int main(){
  60. #ifdef DEBUG
  61. setIO("c");
  62. #endif
  63. read(n);
  64. for(int i=1;i<=n;++i)
  65. read(a[i]);
  66. lp[1]=rp[1]=1,sum[1]=a[1];
  67. tot=1;
  68. long long tmp;
  69. for(int i=2;i<=n;++i){
  70. ++tot;
  71. lp[tot]=rp[tot]=i;
  72. sum[tot]=a[i];
  73. while(tot>1 && frac(sum[tot-1],rp[tot-1]-lp[tot-1]+1)>frac(sum[tot],rp[tot]-lp[tot]+1)){
  74. sum[tot-1]+=sum[tot];
  75. rp[tot-1]=rp[tot];
  76. --tot;
  77. }
  78. }
  79. for(int i=1;i<=tot;++i){
  80. for(int j=lp[i];j<=rp[i];++j)
  81. ans[j]=frac(sum[i],rp[i]-lp[i]+1);
  82. }
  83. for(int i=1;i<=n;++i)
  84. cout<<ans[i]<<' ';
  85. return 0;
  86. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注