[关闭]
@KirinBill 2017-10-19T13:33:31.000000Z 字数 5058 阅读 528

2017.10.19 NOIP模拟赛

题解 套题

目录


升职数

思路

代码

  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 <cstring>
  31. using std::sort;
  32. using std::unique;
  33. using std::lower_bound;
  34. const int MAXN=1e5+5;
  35. int n,tot;
  36. int he[MAXN],p[MAXN],id[MAXN],ans[MAXN];
  37. struct line{int to,nex;}ed[MAXN];
  38. class BIT{
  39. private:
  40. int c[MAXN];
  41. int lowbit(int x){return x&-x;}
  42. int qry(int r){
  43. int ret=0;
  44. for(;r;r-=lowbit(r))
  45. ret+=c[r];
  46. return ret;
  47. }
  48. public:
  49. void add(int l){
  50. for(;l<=tot;l+=lowbit(l))
  51. ++c[l];
  52. }
  53. int gsum(int l){return qry(tot)-qry(l);}
  54. }ta;
  55. inline void addE(int u,int v){
  56. static int cnt;
  57. ed[++cnt]=(line){v,he[u]};
  58. he[u]=cnt;
  59. }
  60. inline void decrete(){
  61. static int tmp[MAXN];
  62. memcpy(tmp,p,sizeof(tmp));
  63. sort(tmp+1,tmp+n+1);
  64. tot=unique(tmp+1,tmp+n+1)-tmp-1;
  65. for(int i=1;i<=n;++i)
  66. id[i]=lower_bound(tmp+1,tmp+tot+1,p[i])-tmp;
  67. }
  68. void DFS(int u){
  69. int pre=ta.gsum(id[u]);
  70. for(int i=he[u];i;i=ed[i].nex)
  71. DFS(ed[i].to);
  72. ans[u]=ta.gsum(id[u])-pre;
  73. ta.add(id[u]);
  74. }
  75. int main(){
  76. #ifdef DEBUG
  77. setIO("a");
  78. #endif
  79. read(n);
  80. for(int i=1;i<=n;++i)
  81. read(p[i]);
  82. decrete();
  83. for(int i=2,fa;i<=n;++i){
  84. read(fa);
  85. addE(fa,i);
  86. }
  87. DFS(1);
  88. for(int i=1;i<=n;++i)
  89. write(ans[i],'\n');
  90. return 0;
  91. }

盖楼房

思路

代码

  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 <cmath>
  31. using std::ceil;
  32. using std::min;
  33. using std::sqrt;
  34. const int MAXN=1e5+5;
  35. const double EPS=1e-12;
  36. int n;
  37. long long k;
  38. long long a[MAXN];
  39. inline bool jud(double lim){
  40. long long rest=k,c;
  41. for(int i=1;i<=n;++i){
  42. //lim*c^2+lim*c=a
  43. //c=ceil(-lim+sqrt(lim*lim+4*lim)/2/lim);
  44. c=ceil((-1+sqrt(1+4*a[i]/lim))/2);
  45. rest-=c;
  46. if(rest<0) return false;
  47. }
  48. return true;
  49. }
  50. inline long long bin_chop(){
  51. double l=1e-12,r=1e12,mid;
  52. while(r-l>EPS){
  53. mid=(l+r)/2;
  54. if(jud(mid)) r=mid;
  55. else l=mid;
  56. }
  57. mid=(l+r)/2;
  58. double ret=0;
  59. long long c,sum=0;
  60. for(int i=1;i<=n;++i){
  61. c=ceil((-1+sqrt(1+4*a[i]/mid))/2);
  62. ret+=(double)a[i]/c,sum+=c;
  63. }
  64. ret-=mid*(k-sum);
  65. return (long long)(ret+0.5);
  66. }
  67. int main(){
  68. #ifdef DEBUG
  69. setIO("b");
  70. #endif
  71. read(n),read(k);
  72. for(int i=1;i<=n;++i)
  73. read(a[i]);
  74. write(bin_chop());
  75. return 0;
  76. }

毕业照

思路

代码

  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. const int MAXN=55;
  32. int n;
  33. int a[MAXN];
  34. inline int DP(){
  35. //val in l~r,range is i~j
  36. static int dp[MAXN][MAXN][MAXN][MAXN];
  37. for(int i=1;i<=n;++i){
  38. for(int l=1;l<=a[i];++l){
  39. for(int r=a[i];r<=50;++r)
  40. dp[l][r][i][i]=1;
  41. }
  42. }
  43. for(int len=2;len<=n;++len){
  44. for(int i=1,j;n-i+1>=len;++i){
  45. j=i+len-1;
  46. for(int rge=1;rge<=50;++rge){
  47. for(int l=1,r;50-l+1>=rge;++l){
  48. r=l+rge-1;
  49. dp[l][r][i][j]=max(dp[l+1][r][i][j],dp[l][r-1][i][j]);
  50. dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i+1][j]+(a[i]==l));
  51. dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i][j-1]+(a[j]==r));
  52. dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][r][i+1][j-1]+(a[i]==r)+(a[j]==l));
  53. }
  54. }
  55. }
  56. }
  57. return dp[1][50][1][n];
  58. }
  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. write(DP());
  67. return 0;
  68. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注