[关闭]
@994495jj 2017-05-31T11:46:46.000000Z 字数 6251 阅读 981

FZU周练-0530老队员场题解

（ACM）数学----概率论 （ACM）数据结构----线段树 （ACM）动态规划----数位dp

题目链接

B. FZU 2103 Bin & Jing in wonderland（概率论）

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  24. double A[55];
  25. double p[25];
  26. double s[25];
  27. int a[30],cnt[25];
  29. double kpow(double a,ll k) {
  30.     double ans=1;
  31.     while(k) {
  32.         if(k&1) ans=ans*a;
  33.         a=a*a;
  34.         k>>=1;
  35.     }
  36.     return ans;
  37. }
  39. int main() {
  40.     ///init
  41.     A[0]=1;
  42.     for(int i=1;i<55;++i) A[i]=A[i-1]*i;
  44.     int T;scanf("%d",&T);
  45.     while(T--) {
  46.         ///
  47.         int n,k,r;scanf("%d%d%d",&n,&k,&r);
  49.         ///init
  50.         memset(cnt,0,sizeof(cnt));
  52.         ///read
  53.         for(int i=1;i<=n;++i) scanf("%lf",p+i),s[i]=s[i-1]+p[i];
  54.         for(int i=1;i<=r;++i) scanf("%d",a+i);
  56.         ///sort a
  57.         sort(a+1,a+1+r);
  59.         ///solve
  60.         double ans=A[k];
  61.         for(int i=1;i<=r;++i) {
  62.             if(a[i]!=a[1]) {
  63.                 ans=ans*p[a[i]];
  64.             }
  65.             ++cnt[a[i]];
  66.         }
  67.         for(int i=1;i<=n;++i) {
  68.             if(i!=a[1]&&cnt[i]) ans=ans/A[cnt[i]];
  69.         }
  70.         double res=0;
  71.         int to=k-(r-cnt[a[1]]);
  72.         for(int i=cnt[a[1]];i<=to;++i) {
  73.             double t=ans;
  74.             t=t*kpow(s[a[1]-1],to-i);
  75.             t=t*kpow(p[a[1]],i);
  76.             t=t/A[to-i];
  77.             t=t/A[i];
  78.             res=res+t;
  79.         }
  80.         printf("%.6lf\n",res);
  81.     }
  82.     return 0;
  83. }

D. FZU 2105 Digits Count（线段树）

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  24. const int N=1000005;
  25. char s[14];
  26. bool rev[4][N<<2];
  27. int a[N],sum[4][N<<2],lazy[4][N<<2];
  29. void build(int l,int r,int rt) {
  30.     for(int i=0;i<4;++i) lazy[i][rt]=-1,rev[i][rt]=0;
  31.     if(l==r) {
  32.         for(int i=0;i<4;++i) {
  33.             sum[i][rt]=(a[l]&1);
  34.             a[l]>>=1;
  35.         }
  36.         return ;
  37.     }
  38.     int m=(l+r)>>1;
  39.     build(lson);
  40.     build(rson);
  41.     for(int i=0;i<4;++i) sum[i][rt]=sum[i][rt<<1]+sum[i][rt<<1|1];
  42. }
  43. void DOWN(int i,int rt,int l,int r) {
  44.     int m=(l+r)>>1;
  45.     if(lazy[i][rt]!=-1) {
  46.         int c=lazy[i][rt];
  47.         if(c) {
  48.             sum[i][rt<<1]=m-l+1;
  49.             sum[i][rt<<1|1]=r-m;
  50.             lazy[i][rt<<1]=lazy[i][rt<<1|1]=1;
  51.             rev[i][rt<<1]=rev[i][rt<<1|1]=0;
  52.         } else {
  53.             sum[i][rt<<1]=sum[i][rt<<1|1]=0;
  54.             lazy[i][rt<<1]=lazy[i][rt<<1|1]=0;
  55.             rev[i][rt<<1]=rev[i][rt<<1|1]=0;
  56.         }
  57.         lazy[i][rt]=-1;
  58.     }
  59.     if(rev[i][rt]) {
  60.         sum[i][rt<<1]=m-l+1-sum[i][rt<<1];
  61.         sum[i][rt<<1|1]=r-m-sum[i][rt<<1|1];
  62.         rev[i][rt<<1]^=1;
  63.         rev[i][rt<<1|1]^=1;
  64.         rev[i][rt]=0;
  65.     }
  66. }
  67. void upd(int i,int L,int R,int c,int l,int r,int rt) {
  68.     if(R<l||r<L) return ;
  69.     if(L<=l&&r<=R) {
  70.         if(c==0) {
  71.             sum[i][rt]=0;
  72.             lazy[i][rt]=0;
  73.             rev[i][rt]=0;
  74.         } else if(c==1) {
  75.             sum[i][rt]=r-l+1;
  76.             lazy[i][rt]=1;
  77.             rev[i][rt]=0;
  78.         } else {
  79.             sum[i][rt]=r-l+1-sum[i][rt];
  80.             rev[i][rt]^=1;
  81.         }
  82.         return ;
  83.     }
  84.     DOWN(i,rt,l,r);
  85.     int m=(l+r)>>1;
  86.     upd(i,L,R,c,lson);
  87.     upd(i,L,R,c,rson);
  88.     sum[i][rt]=sum[i][rt<<1]+sum[i][rt<<1|1];
  89. }
  90. int qry(int L,int R,int l,int r,int rt) {
  91.     if(R<l||r<L) return 0;
  92.     if(L<=l&&r<=R) {
  93.         int ans=0;
  94.         for(int i=3;i>=0;--i) {
  95.             ans=ans*2+sum[i][rt];
  96.         }
  97.         return ans;
  98.     }
  99.     int m=(l+r)>>1;
  100.     for(int i=0;i<4;++i) DOWN(i,rt,l,r);
  101.     return qry(L,R,lson)+qry(L,R,rson);
  102. }
  103. int main() {
  104.     int T;scanf("%d",&T);
  105.     while(T--) {
  106.         ///
  107.         int n,m;scanf("%d%d",&n,&m);
  108.         ///read
  109.         for(int i=1;i<=n;++i) scanf("%d",a+i);
  110.         ///build
  111.         build(1,n,1);
  112.         ///solve
  113.         for(int i=1;i<=m;++i) {
  114.             int c,l,r;
  115.             scanf("%s",s);
  116.             if(s[0]=='A') {
  117.                 scanf("%d%d%d",&c,&l,&r);++l;++r;
  118.                 for(int j=0;j<4;++j) {
  119.                     if(c%2==0) upd(j,l,r,0,1,n,1);
  120.                     c>>=1;
  121.                 }
  122.             } else if(s[0]=='O') {
  123.                 scanf("%d%d%d",&c,&l,&r);++l;++r;
  124.                 for(int j=0;j<4;++j) {
  125.                     if(c&1) upd(j,l,r,1,1,n,1);
  126.                     c>>=1;
  127.                 }
  128.             } else if(s[0]=='X') {
  129.                 scanf("%d%d%d",&c,&l,&r);++l;++r;
  130.                 for(int j=0;j<4;++j) {
  131.                     if(c&1) upd(j,l,r,2,1,n,1);
  132.                     c>>=1;
  133.                 }
  134.             } else {
  135.                 scanf("%d%d",&l,&r);++l;++r;
  136.                 printf("%d\n",qry(l,r,1,n,1));
  137.             }
  138.         }
  139.     }
  140.     return 0;
  141. }

G. FZU 2108 Mod problem

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  24. const int N=1005;
  25. char a[N];
  26. int sta[N],L[N];
  27. ll b;
  29. ll kpow(ll a,ll k) {
  30.     ll ans=1;
  31.     while(k) {
  32.         if(k&1) ans=ans*a%b;
  33.         a=a*a%b;
  34.         k>>=1;
  35.     }
  36.     return ans;
  37. }
  39. //返回值：长度，值
  40. pll dfs(int l,int r) {
  41.     ll ans=0,len=0;
  42.     for(int i=r;i>=l;) {
  43.         if(a[i]=='['||a[i]==']') {
  44.             --i;
  45.             continue;
  46.         }
  47.         if(i>l&&a[i-1]==']') {
  48.             pll now=dfs(L[i-1],i-1);
  49.             int cnt=a[i]-'0';
  50.             while(cnt--) {
  51.                 ans=(ans+now.se%b*kpow(10,len)%b)%b;
  52.                 len=len+now.fi;
  53.             }
  54.             i=L[i-1];
  55.         } else {
  56.             ans=(ans+(a[i]-'0')%b*kpow(10,len)%b)%b;
  57.             ++len;--i;
  58.         }
  59.     }
  60.     return mp(len,ans);
  61. }
  63. int main() {
  64.     int T;scanf("%d",&T);
  65.     while(T--) {
  66.         ///read
  67.         scanf("%s",a);
  68.         cin>>b;
  70.         ///get l
  71.         int len=strlen(a),p=0;
  72.         for(int i=0;i<len;++i) {
  73.             if(a[i]=='[') sta[p++]=i;
  74.             if(a[i]==']') L[i]=sta[--p];
  75.         }
  77.         ///solve
  78.         cout<<dfs(0,len-1).se<<endl;
  79.     }
  80.     return 0;
  81. }

H. FZU 2109 Mountain Number（数位dp）

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  24. int dig[15],d[15][15][15];
  26. int dp(int po,int pre,int zero,int limit) {
  27.     if(po==-1) return 1;
  28.     if(!limit&&zero!=-1&&d[po][pre][zero]!=-1) return d[po][pre][zero];
  30.     int up=limit?dig[po]:9;
  31.     int ans=0;
  32.     for(int i=0;i<=up;++i) {
  33.         if(zero==-1) {
  34.             if(i) {
  35.                 ans=ans+dp(po-1,i,po,limit&&i==dig[po]);
  36.             } else {
  37.                 ans=ans+dp(po-1,i,zero,limit&&i==dig[po]);
  38.             }
  39.         } else {
  40.             if((zero-po)&1) {
  41.                 if(i>=pre) ans=ans+dp(po-1,i,zero,limit&&i==dig[po]);
  42.             } else {
  43.                 if(i<=pre) ans=ans+dp(po-1,i,zero,limit&&i==dig[po]);
  44.             }
  45.         }
  46.     }
  48.     if(!limit&&zero!=-1) d[po][pre][zero]=ans;
  49.     return ans;
  50. }
  52. int solve(int x) {
  53.     int po=0;
  54.     while(x) {
  55.         dig[po++]=x%10;
  56.         x/=10;
  57.     }
  58.     return dp(po-1,0,-1,1);
  59. }
  61. int main() {
  62.     int T;scanf("%d",&T);
  63.     memset(d,-1,sizeof(d));
  64.     while(T--) {
  65.         int l,r;scanf("%d%d",&l,&r);;
  66.         printf("%d\n",solve(r)-solve(l-1));
  67.     }
  68.     return 0;
  69. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注