[关闭]
@KirinBill 2017-10-23T11:39:21.000000Z 字数 5663 阅读 497

2017.10.23 NOIP模拟赛

题解 套题

目录


clique

WSSrN.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. using std::unique;
  33. using std::lower_bound;
  34. const int MAXN=200005;
  35. int n,tot;
  36. int crete[MAXN<<1];
  37. struct node{
  38. int pos,w;
  39. bool operator< (const node &that)const{return pos<that.pos;}
  40. }d[MAXN];
  41. class valSegT{
  42. #define ls (u<<1)
  43. #define rs (ls|1)
  44. private:
  45. int sz[MAXN<<3];
  46. int decrete(int x){
  47. return lower_bound(crete+1,crete+tot+1,x)-crete;
  48. }
  49. void upd(int u){
  50. sz[u]=max(sz[ls],sz[rs]);
  51. }
  52. int qry(int u,int l,int r,int lp,int rp){
  53. if(lp<=l && r<=rp) return sz[u];
  54. int mid=l+r>>1,ret=0;
  55. if(lp<=mid) ret=qry(ls,l,mid,lp,rp);
  56. if(rp>mid) ret=max(ret,qry(rs,mid+1,r,lp,rp));
  57. return ret;
  58. }
  59. void ist(int u,int l,int r,int pos,int x){
  60. if(l==r){
  61. sz[u]=max(sz[u],x);
  62. return;
  63. }
  64. int mid=l+r>>1;
  65. if(pos<=mid) ist(ls,l,mid,pos,x);
  66. else ist(rs,mid+1,r,pos,x);
  67. upd(u);
  68. }
  69. public:
  70. int qry(int rp){return qry(1,1,tot,1,decrete(rp));}
  71. void ist(int pos,int x){ist(1,1,tot,decrete(pos),x);}
  72. #undef ls
  73. #undef rs
  74. }T;
  75. inline void decrete(){
  76. sort(crete+1,crete+crete[0]+1);
  77. tot=unique(crete+1,crete+crete[0]+1)-crete-1;
  78. }
  79. int main(){
  80. setIO("clique");
  81. read(n);
  82. for(int i=1;i<=n;++i){
  83. read(d[i].pos),read(d[i].w);
  84. crete[++crete[0]]=d[i].pos-d[i].w;
  85. crete[++crete[0]]=d[i].pos+d[i].w;
  86. }
  87. decrete();
  88. sort(d+1,d+n+1);
  89. int ans=0;
  90. for(int i=1,tmp;i<=n;++i){
  91. tmp=1+T.qry(d[i].pos-d[i].w);
  92. ans=max(ans,tmp);
  93. T.ist(d[i].pos+d[i].w,tmp);
  94. }
  95. write(ans);
  96. return 0;
  97. }

mod

WSPc7.png
WSXSe.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. const int MAXN=100005;
  32. int n;
  33. int a[MAXN];
  34. class segT{
  35. private:
  36. struct node{
  37. int l,r,ls,rs,max;
  38. long long sum;
  39. }d[MAXN<<2];
  40. int new_nd(){
  41. static int cnt=1;
  42. return ++cnt;
  43. }
  44. void upd(int u){
  45. int ls=d[u].ls,rs=d[u].rs;
  46. d[u].max=max(d[ls].max,d[rs].max);
  47. d[u].sum=d[ls].sum+d[rs].sum;
  48. }
  49. void mdf(int u,int pos,int x){
  50. if(d[u].l==d[u].r){
  51. d[u].sum=d[u].max=x;
  52. return;
  53. }
  54. int mid=d[u].l+d[u].r>>1;
  55. if(pos<=mid) mdf(d[u].ls,pos,x);
  56. else mdf(d[u].rs,pos,x);
  57. upd(u);
  58. }
  59. long long qry(int u,int lp,int rp){
  60. if(lp<=d[u].l && d[u].r<=rp)
  61. return d[u].sum;
  62. int mid=d[u].l+d[u].r>>1;
  63. long long ret=0;
  64. if(lp<=mid) ret=qry(d[u].ls,lp,rp);
  65. if(rp>mid) ret+=qry(d[u].rs,lp,rp);
  66. return ret;
  67. }
  68. void mod(int u,int lp,int rp,int p){
  69. if(d[u].max<p) return;
  70. if(d[u].l==d[u].r){
  71. d[u].max=d[u].sum=d[u].max%p;
  72. return;
  73. }
  74. int mid=d[u].l+d[u].r>>1;
  75. if(lp<=mid) mod(d[u].ls,lp,rp,p);
  76. if(rp>mid) mod(d[u].rs,lp,rp,p);
  77. upd(u);
  78. }
  79. void build(int u,int l,int r){
  80. d[u].l=l,d[u].r=r;
  81. if(l==r){
  82. d[u].sum=d[u].max=a[l];
  83. return;
  84. }
  85. int mid=l+r>>1;
  86. d[u].ls=new_nd();
  87. build(d[u].ls,l,mid);
  88. d[u].rs=new_nd();
  89. build(d[u].rs,mid+1,r);
  90. upd(u);
  91. }
  92. public:
  93. void build(){build(1,1,n);}
  94. void mdf(int pos,int x){mdf(1,pos,x);}
  95. long long qry(int lp,int rp){return qry(1,lp,rp);}
  96. void mod(int lp,int rp,int p){mod(1,lp,rp,p);}
  97. }T;
  98. int main(){
  99. setIO("mod");
  100. int m;
  101. read(n),read(m);
  102. for(int i=1;i<=n;++i)
  103. read(a[i]);
  104. T.build();
  105. for(int i=1,opt,a,b,c;i<=m;++i){
  106. read(opt),read(a),read(b);
  107. if(opt==1) write(T.qry(a,b),'\n');
  108. else if(opt==3) T.mdf(a,b);
  109. else{
  110. read(c);
  111. T.mod(a,b,c);
  112. }
  113. }
  114. return 0;
  115. }

number

WSBos.png

思路

代码

  1. #include <cstdio>
  2. #include <climits>
  3. const int MAXK=65;
  4. int k;
  5. long long m;
  6. unsigned long long C_tab[MAXK][MAXK];
  7. inline void pre_tab(){
  8. C_tab[0][0]=1;
  9. for(int i=1;i<=64;++i){
  10. C_tab[i][0]=1;
  11. for(int j=1;j<=i;++j)
  12. C_tab[i][j]=C_tab[i-1][j-1]+C_tab[i-1][j];
  13. }
  14. }
  15. inline unsigned long long C(int n,int m){
  16. if(n<0 || m<0) return 0;
  17. else return C_tab[n][m];
  18. }
  19. inline unsigned long long cal(unsigned long long x){
  20. unsigned long long ret=0;
  21. int cnt=0;
  22. for(int i=63;i>=0;--i){
  23. if(x&1ULL<<i){
  24. ret+=C(i,k-cnt);
  25. ++cnt;
  26. }
  27. }
  28. if(cnt==k) ++ret;
  29. return ret;
  30. }
  31. inline long long bin_chop_l(){
  32. unsigned long long l=1,r=LLONG_MAX,mid;
  33. while(l<=r){
  34. mid=l+r>>1;
  35. if(cal(mid<<1)-cal(mid)>=m)
  36. r=mid-1;
  37. else l=mid+1;
  38. }
  39. return l;
  40. }
  41. inline long long bin_chop_r(){
  42. unsigned long long l=1,r=LLONG_MAX,mid;
  43. while(l<=r){
  44. mid=l+r>>1;
  45. if(cal(mid<<1)-cal(mid)<=m)
  46. l=mid+1;
  47. else r=mid-1;
  48. }
  49. return r;
  50. }
  51. int main(){
  52. freopen("number.in","r",stdin);
  53. freopen("number.out","w",stdout);
  54. pre_tab();
  55. int t;
  56. scanf("%d",&t);
  57. unsigned long long l,r;
  58. for(int i=1;i<=t;++i){
  59. scanf("%lld%d",&m,&k);
  60. if(m==1 && k==1) puts("-1");
  61. else{
  62. l=bin_chop_l();
  63. r=bin_chop_r();
  64. printf("%lld %lld\n",l,r);
  65. }
  66. }
  67. return 0;
  68. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注