[关闭]
@KirinBill 2017-09-24T07:37:59.000000Z 字数 6060 阅读 1191

2017.9.23 NOIP模拟赛

题解 套题

NOIP出啥主席树...

目录


平均数

5He1y.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <climits>
  4. #include <cstring>
  5. using std::min;
  6. using std::max;
  7. const int MAXN=100005;
  8. const double EPS=1e-5;
  9. int n;
  10. int a[MAXN];
  11. long long k;
  12. double sum[MAXN];
  13. inline void pre_sum(double k){
  14. sum[0]=0;
  15. for(int i=1;i<=n;++i)
  16. sum[i]=sum[i-1]+a[i]-k;
  17. }
  18. template<typename type>
  19. long long mge_sort(int l,int r,type a[]){
  20. static type tmp[MAXN];
  21. if(l==r) return 0;
  22. int mid=l+r>>1;
  23. long long ret=mge_sort(l,mid,a)+mge_sort(mid+1,r,a);
  24. int cur=l-1,lp=l,rp=mid+1;
  25. while(lp<=mid && rp<=r){
  26. if(a[lp]>a[rp]){
  27. tmp[++cur]=a[rp++];
  28. ret+=mid-lp+1;
  29. }
  30. else tmp[++cur]=a[lp++];
  31. }
  32. while(lp<=mid) tmp[++cur]=a[lp++];
  33. while(rp<=r) tmp[++cur]=a[rp++];
  34. memcpy(a+l,tmp+l,(r-l+1)*sizeof(type));
  35. return ret;
  36. }
  37. inline long long notp_cnt(){return mge_sort(0,n,sum);}
  38. inline double bin_chop(double l,double r){
  39. double mid;
  40. while(r-l>EPS){
  41. mid=(l+r)/2;
  42. pre_sum(mid);
  43. if(notp_cnt()>=k) r=mid;
  44. else l=mid;
  45. }
  46. return (l+r)/2;
  47. }
  48. int main(){
  49. freopen("ave.in","r",stdin);
  50. freopen("ave.out","w",stdout);
  51. scanf("%d%lld",&n,&k);
  52. int l=INT_MAX,r=INT_MIN;
  53. for(int i=1;i<=n;++i){
  54. scanf("%d",&a[i]);
  55. l=min(l,a[i]),r=max(r,a[i]);
  56. }
  57. printf("%.4lf",bin_chop(l,r));
  58. return 0;
  59. }

涂色游戏

5HIXX.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. using std::max;
  5. const int MAXN=105,P=998244353;
  6. int n,m,p,q;
  7. int f[MAXN][MAXN],C[MAXN][MAXN];
  8. struct matrix{
  9. int c[MAXN][MAXN];
  10. matrix(){memset(c,0,sizeof(c));}
  11. int* operator[] (int i){return c[i];}
  12. matrix& operator*= (matrix a){
  13. matrix b=*this;
  14. memset(c,0,sizeof(c));
  15. for(int i=1;i<=p;++i){
  16. for(int j=1;j<=p;++j){
  17. for(int k=1;k<=p;++k)
  18. c[i][j]=(c[i][j]+(long long)a[i][k]*b[k][j]%P)%P;
  19. }
  20. }
  21. return *this;
  22. }
  23. void be_unit(){
  24. for(int i=1;i<=p;++i)
  25. c[i][i]=1;
  26. }
  27. }ans,trans;
  28. inline int pow(int x,int y){
  29. int ret=1;
  30. for(;y;y>>=1,x=(long long)x*x%P){
  31. if(y&1) ret=(long long)ret*x%P;
  32. }
  33. return ret;
  34. }
  35. inline int inv(int x){return pow(x,P-2);}
  36. inline matrix pow(matrix x,int y){
  37. matrix ret;
  38. ret.be_unit();
  39. for(;y;y>>=1,x*=x){
  40. if(y&1) ret*=x;
  41. }
  42. return ret;
  43. }
  44. inline void pre_tab(){
  45. C[0][0]=1;
  46. for(int i=1;i<=p;++i){
  47. C[i][0]=C[i][i]=1;
  48. for(int j=1;j<i;++j)
  49. C[i][j]=(C[i-1][j-1]+C[i-1][j])%P;
  50. }
  51. f[0][0]=1;
  52. for(int i=1;i<=n;++i){
  53. for(int j=1;j<=p;++j)
  54. f[i][j]=((long long)f[i-1][j-1]*(p-j+1)%P+(long long)f[i-1][j]*j%P)%P;
  55. }
  56. }
  57. inline void deal_mat(){
  58. for(int i=1;i<=p;++i){
  59. for(int j=1;j<=p;++j){
  60. for(int k=max(q,max(i,j));k<=p;++k)
  61. trans[i][j]=(trans[i][j]+(long long)C[i][i+j-k]*C[p-i][k-i]%P)%P;
  62. trans[i][j]=(long long)trans[i][j]*f[n][j]%P*inv(C[p][j])%P;
  63. }
  64. }
  65. ans=pow(trans,m-1);
  66. }
  67. int main(){
  68. freopen("color.in","r",stdin);
  69. freopen("color.out","w",stdout);
  70. scanf("%d%d%d%d",&n,&m,&p,&q);
  71. pre_tab();
  72. deal_mat();
  73. int sum=0;
  74. for(int i=1;i<=p;++i){
  75. for(int j=1;j<=p;++j)
  76. sum=(sum+(long long)f[n][i]*ans[i][j]%P)%P;
  77. }
  78. printf("%d",sum);
  79. return 0;
  80. }

序列

5Hn2G.png
5H68g.png

思路

代码

  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <cstring>
  4. using std::sort;
  5. const int MAXN=100005;
  6. int n,m,q;
  7. int a[MAXN];
  8. struct query{
  9. int l,r,x;
  10. friend bool operator< (const query &a,const query &b){
  11. return a.x<b.x;
  12. }
  13. }qry[MAXN];
  14. class CMT{
  15. private:
  16. int cnt;
  17. int rt[MAXN];
  18. struct node{int ls,rs,cnt;}d[MAXN*50];
  19. int cpy_nd(int u){
  20. d[++cnt]=d[u];
  21. return cnt;
  22. }
  23. void sgl_mdf(int pre,int &now,int l,int r,int val,int x){
  24. now=cpy_nd(pre);
  25. d[now].cnt+=x;
  26. if(l==r) return;
  27. int mid=l+r>>1;
  28. if(val<=mid) sgl_mdf(d[pre].ls,d[now].ls,l,mid,val,x);
  29. else sgl_mdf(d[pre].rs,d[now].rs,mid+1,r,val,x);
  30. }
  31. void rge_mdf(int pre,int &now,int l,int r,int lp,int rp,int x){
  32. now=cpy_nd(pre);
  33. if(lp<=l && r<=rp){
  34. d[now].cnt+=x;
  35. return;
  36. }
  37. int mid=l+r>>1;
  38. if(lp<=mid) rge_mdf(d[pre].ls,d[now].ls,l,mid,lp,rp,x);
  39. if(rp>mid) rge_mdf(d[pre].rs,d[now].rs,mid+1,r,lp,rp,x);
  40. }
  41. long long geq_cnt(int pre,int now,int l,int r,int val){
  42. if(val<=l) return d[now].cnt-d[pre].cnt;
  43. int mid=l+r>>1;
  44. long long ret=0;
  45. if(val<=mid) ret+=geq_cnt(d[pre].ls,d[now].ls,l,mid,val);
  46. if(val<=r) ret+=geq_cnt(d[pre].rs,d[now].rs,mid+1,r,val);
  47. return ret;
  48. }
  49. long long qry(int pre,int now,int l,int r,int val){
  50. if(l==r) return d[now].cnt-d[pre].cnt;
  51. int mid=l+r>>1;
  52. long long ret=d[now].cnt-d[pre].cnt;
  53. if(val<=mid) ret+=qry(d[pre].ls,d[now].ls,l,mid,val);
  54. else ret+=qry(d[pre].rs,d[now].rs,mid+1,r,val);
  55. return ret;
  56. }
  57. public:
  58. void clear(){
  59. cnt=0;
  60. memset(rt,0,sizeof(rt));
  61. memset(d,0,sizeof(d));
  62. }
  63. void ist(int pre,int now,int val){sgl_mdf(rt[pre],rt[now],1,n,val,1);}
  64. void ist(int pre,int now,int lp,int rp){rge_mdf(rt[pre],rt[now],1,n,lp,rp,1);}
  65. long long geq_cnt(int l,int r,int val){return geq_cnt(rt[l-1],rt[r],1,n,val);}
  66. long long qry(int l,int r,int val){return qry(rt[l-1],rt[r],1,n,val);}
  67. void cpy_his(int pre,int now){rt[now]=rt[pre];}
  68. }T;
  69. inline void deal_qry(){
  70. T.clear();
  71. sort(qry+1,qry+m+1);
  72. for(int i=1,j=1;i<=n;++i){
  73. T.cpy_his(i-1,i);
  74. while(qry[j].x==i && j<=m){
  75. T.ist(i,i,qry[j].l,qry[j].r);
  76. ++j;
  77. }
  78. }
  79. }
  80. int main(){
  81. freopen("seq.in","r",stdin);
  82. freopen("seq.out","w",stdout);
  83. scanf("%d%d%d",&n,&m,&q);
  84. for(int i=1;i<=n;++i){
  85. scanf("%d",&a[i]);
  86. T.ist(i-1,i,a[i]);
  87. }
  88. long long ans=0;
  89. for(int i=1;i<=m;++i){
  90. scanf("%d%d%d",&qry[i].l,&qry[i].r,&qry[i].x);
  91. ans+=T.geq_cnt(qry[i].l,qry[i].r,qry[i].x);
  92. }
  93. printf("%lld\n",ans);
  94. deal_qry();
  95. long long p,v;
  96. for(int i=1;i<=q;++i){
  97. scanf("%lld%lld",&p,&v);
  98. p^=ans,v^=ans;
  99. if(a[p]<v) ans+=T.qry(a[p]+1,v,p);
  100. else if(a[p]>v) ans-=T.qry(v+1,a[p],p);
  101. a[p]=v;
  102. printf("%lld\n",ans);
  103. }
  104. return 0;
  105. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注