[关闭]
@CQUPTacm 2017-03-26T05:53:29.000000Z 字数 9725 阅读 498

萌新集中营第四期

题解


题目

A Eddy's AC难题 (HDU - 2200)

题意:

    中文题。

题解:

    符号说明,以C(a,b)表示从a个东西中无顺序的选择b个的方法数,以A(a,b)表示从a个东西中有顺序的选择b个的方法数,以(a<=i<=b)Σ[y]表示y从i=a到i=b的求和。
    有很多种思路:
    <1>从这n个人中选择x(2<=x<=n)个人,然后把这x个人分成AC数少和AC数多的两部分,有x-1种分法,答案就是(2<=x<=n)Σ[C(n,x)]
    <2>枚举AC数少的那个部分AC数最多的人,那么比他少的所有人可选可不选,比他多的人至少选一个,答案就是(1<=x<n)Σ[2^(x-1)*(2^(n-x)-1)]
    而组合数也有多种方法来求:
    (1)通过定义公式C(a,b)=a!/(b!*(a-b)!),这种方法不常用,因为阶乘是非常大的,这道题就不能用这个办法。。。
    (2)由上面的公式可以看出C(a,b-1)=a!/((b-1)!*(a-b+1)!),所以C(a,b)=C(a,b-1)*(a-b+1)/b,这种方法避免了阶乘过大的问题,对于这道题而言是可行的,不过对于有取模的情况也是比较尴尬的
    (3)从a个东西中选择b个,相当于从前a-1个直接选b个然后不选第a个,或者从前a-1个中选b-1个,再选第a个,所以C(a,b)=C(a-1,b)+C(a-1,b-1),于是我们就可以通过打组合数表来求组合数,而且便于取模,唯一的问题就是当a、b很大的时候,时间复杂度是平方级的。。。ps:注意C(x,0)不论x取什么值,永远是1
    (4)在有取模,而且模数是大于a和b的质数的时候,通过求逆元,可以用定义公式求
    (5)还有一个神奇的东西叫Lucas
    (4)、(5)提到的两种方法,有兴趣的同学可以自行去了解。
    这里给出分别用(2)、(3)两种求组合数方法的方法<1>,还有方法<2>。
    (2)求组合数,方法<1>时间复杂度o(n^2),空间复杂度o(1)。
    (3)求组合数,方法<1>时间复杂度o(n^2),空间复杂度o(n^2)。
    方法<2>时间复杂度o(n),空间复杂度o(n)。

代码:

(2)求组合数,<1>求答案:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. long long c(int a,int b)
  5. {
  6. long long ans=1;
  7. for(int i=1;i<=b;i++)
  8. ans=ans*(a-i+1)/i;
  9. return ans;
  10. }
  11. int main()
  12. {
  13. int n;
  14. long long ans;
  15. while(~scanf("%d",&n))
  16. {
  17. ans=0;
  18. for(int x=2;x<=n;x++)
  19. ans+=c(n,x)*(x-1);
  20. printf("%lld\n",ans);
  21. }
  22. return 0;
  23. }

(3)求组合数,<1>求答案:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. long long c[105][105];
  5. int main()
  6. {
  7. for(int i=-0;i<=100;i++)
  8. {
  9. c[i][0]=1;
  10. for(int j=1;j<=i;j++)
  11. c[i][j]=c[i-1][j-1]+c[i-1][j];
  12. }
  13. int n;
  14. long long ans;
  15. while(~scanf("%d",&n))
  16. {
  17. ans=0;
  18. for(int x=2;x<=n;x++)
  19. ans+=c[n][x]*(x-1);
  20. printf("%lld\n",ans);
  21. }
  22. return 0;
  23. }

<3>求答案:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. long long mi2[105];
  5. int main()
  6. {
  7. mi2[0]=1;
  8. for(int i=1;i<=100;i++)
  9. mi2[i]=mi2[i-1]*2;
  10. int n;
  11. long long ans;
  12. while(~scanf("%d",&n))
  13. {
  14. ans=0;
  15. for(int x=1;x<n;x++)
  16. ans+=mi2[x-1]*(mi2[n-x]-1);
  17. printf("%lld\n",ans);
  18. }
  19. return 0;
  20. }

B RPG的错排 (HDU - 2068)

题意:

    中文题。

题解:

    错排数的定义:D(n)表示把n个数进行排列,每个数都不在自己原本的位置上的方案数。
    这道题思路其实很清晰,从n个人中选择超过一半的人待在自己的位置上,剩下的人都不待在自己的位置上,于是答案就是((n+1)/2<=x<=n)ΣC(n,x)*D(n-x)。
    组合数的部分上一题讲过了,重点说一下错排数怎么求。
    如果只有1个数,错排方案为0;如果有2个数,错排方案为1。这两点都很显然。那么如果有n(n>2)个数,我们先挑1个数x放在第1个位置,显然x不会等于1,然后我们考虑第x个位置放谁,有两种情况:
    (1)第x个位置放1,那么1和x就互换了位置,剩下n-2个数就重新错排,于是这种情况的方案数就等于从n个数中选一个不为1的数和1互换位置,剩下n-2个数错排,即(n-1)*D(n-2)
    (2)第x个位置放的数不为1,那么相当于我们把x和1等价起来,把这n-1个数重新错排,这个x同样有n-1中选择,所以方案数是(n-1)*D(n-1)
    所以当n>2,D(n)=(n-1)*(D(n-2)+D(n-1)),我们又知道D(1)和D(2)的值,就可以打错排表了。
    ps:D(0)是无意义的,在这道题里面也可以认为是1,表示全对的情况。
    时间复杂度o(n^2),空间复杂度o(n^2)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. long long c[30][30],d[30];
  5. int main()
  6. {
  7. for(int i=0;i<=25;i++)
  8. {
  9. c[i][0]=1;
  10. for(int j=1;j<=i;j++)
  11. c[i][j]=c[i-1][j-1]+c[i-1][j];
  12. }
  13. d[0]=1;
  14. d[1]=0;
  15. d[2]=1;
  16. for(int i=3;i<=25;i++)
  17. d[i]=(d[i-2]+d[i-1])*(i-1);
  18. int n;
  19. long long ans;
  20. while(scanf("%d",&n),n)
  21. {
  22. ans=0;
  23. for(int x=(n+1)/2;x<=n;x++)
  24. ans+=c[n][x]*d[n-x];
  25. printf("%lld\n",ans);
  26. }
  27. return 0;
  28. }

C Co-prime (HDU - 4135)

题意:

    给定A、B、N(1<=A<=B<=10^15,1<=N<=10^9),问区间[A,B]内有多少个数跟N互质。
    T(0<T<=100)组数据。

题解:

    首先我们用前缀和的思想把区间[A,B]变成[1,B]-[1,A-1]。然后我们只需要求从1到X有多少个数和N互质。按照互质的定义,我们很容易想到求每个数和N的最大公因数,看是不是1。但是很遗憾,这题A、B、N都很大。于是我们换个角度,从N入手,我们找到N的所有质因数,然后把1到X内所有含这些质因数的数都去掉就行了。这个过程中,为了避免含有多个质因数的数被重复删去,要用到容斥原理。
    容斥的写法很多,这里给出队列的方法。
    因为15!>10^9,所以我们可以认为N的质因数不超过15个。
    时间复杂度o(T*(sqrt(N)+2^15)),空间复杂度o(2^15)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<queue>
  4. using namespace std;
  5. int fac[20],nums;
  6. int len1,len2;
  7. long long q1[100005],q2[100005];
  8. queue <long long> v1,v2;
  9. void init(int x)
  10. {
  11. nums=0;
  12. for(int i=2;i*i<=x;i++)
  13. {
  14. if(x%i==0)
  15. {
  16. fac[nums++]=i;
  17. while(x%i==0) x/=i;
  18. }
  19. }
  20. if(x!=1)
  21. fac[nums++]=x;
  22. return;
  23. }
  24. long long ask(long long x)
  25. {
  26. if(nums)
  27. {
  28. long long ans=x-x/fac[0];
  29. len1=len2=1;
  30. q1[0]=x;
  31. q2[0]=x/fac[0];
  32. for(int i=1;i<nums;i++)
  33. {
  34. for(int j=0;j<len1;j++)
  35. {
  36. ans-=q1[j]/fac[i];
  37. v2.push(q1[j]/fac[i]);
  38. }
  39. for(int j=0;j<len2;j++)
  40. {
  41. ans+=q2[j]/fac[i];
  42. v1.push(q2[j]/fac[i]);
  43. }
  44. while(!v1.empty())
  45. {
  46. q1[len1++]=v1.front();
  47. v1.pop();
  48. }
  49. while(!v2.empty())
  50. {
  51. q2[len2++]=v2.front();
  52. v2.pop();
  53. }
  54. }
  55. return ans;
  56. }
  57. else
  58. return x;
  59. }
  60. int main()
  61. {
  62. int T;
  63. long long A,B;
  64. int N;
  65. scanf("%d",&T);
  66. for(int t=1;t<=T;t++)
  67. {
  68. scanf("%lld%lld%d",&A,&B,&N);
  69. init(N);
  70. printf("Case #%d: %lld\n",t,ask(B)-ask(A-1));
  71. }
  72. return 0;
  73. }

D sum (HDU - 5776)

题意:

    给定一个n(1<=n<=100000)个数的数列,第i个数为xi(1<=xi<=100),问是否存在某一段数字的和能被m(1<=m<=5000)整除。
    T(1<=T<=10)组数据。

题解:

    用前缀和的思想,我们很容易想到把一段数的和转化为两个前缀的差。然而枚举这两个前缀是n^2的复杂度,再考虑到多组,时间复杂度boom!
    这题求的是有没有和能被m整除,那么我们把每个数变化成它除以m的余数,能被m整除就意味着余数是0,也就是两个前缀的差是0,换句话说就是两个前缀相等。
    所以我们只需要看有没有多于1个前缀除以m的余数相同,或者有没有某个前缀除以m的余数直接是0,就可以得到答案了。
    ps:根据抽屉原理可以得出当n>=m的时候,一定存在能被m整除的一段数的和,然并卵。。。
    时间复杂度o(T*n)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int life[5005];
  6. int main()
  7. {
  8. int t,n,m,now,nowsum;
  9. bool flag=0;
  10. scanf("%d",&t);
  11. while(t--)
  12. {
  13. scanf("%d%d",&n,&m);
  14. nowsum=0;
  15. memset(life,0,sizeof(life));
  16. flag=0;
  17. for(int i=0;i<n;i++)
  18. {
  19. scanf("%d",&now);
  20. nowsum=(nowsum+now)%m;
  21. if(nowsum==0 || life[nowsum])
  22. flag=1;
  23. life[nowsum]++;
  24. }
  25. if(flag)
  26. printf("YES\n");
  27. else
  28. printf("NO\n");
  29. }
  30. return 0;
  31. }

E GCD & LCM (ZOJ - 1577)

题意:

    p和q为两个正整数,给出p和q的最大公因数x(2<=x<=100000)和最小公倍数y(2<=y<=100000),问p和q有多少种可能的组合。
    多组数据。

题解:

    可以把p表示为a*gcd(p,q),q表示为b*gcd(p,q),且gcd(a,b)=1。又因为lcm(p,q)=p*q/gcd(p,q)=a*b*gcd(p,q),所以a*b=lcm(p,q)/gcd(p,q),。
    得到a*b了之后,求a和b有多少种组合就简单了因为a*b=lcm(p,q)/gcd(p,q),所以a*b<=100000/2,我们可以枚举能整除a*b的a,来看b和a是不是互质。
    另一种思路是将a*b进行质因数分解,因为a和b互质,所以每种质因数只能属于a或者b,于是答案就是2^质因数个数。
    枚举a的方法时间复杂度o(y/x),空间复杂度o(1)。
    质因数分解的方法时间复杂度o(sqrt(y/x)),空间复杂度o(1)。

代码:

枚举a:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int gcd(int a,int b)
  5. {
  6. if(a%b==0)
  7. return b;
  8. else
  9. return gcd(b,a%b);
  10. }
  11. int ok(int x)
  12. {
  13. int ans=0;
  14. for(int i=1;i<=x;i++)
  15. {
  16. if(x%i==0 && gcd(i,x/i)==1)
  17. ans++;
  18. }
  19. return ans;
  20. }
  21. int main()
  22. {
  23. int x,y;
  24. while(~scanf("%d%d",&x,&y))
  25. {
  26. if(y%x==0)
  27. printf("%d\n",ok(y/x));
  28. else
  29. printf("0\n");
  30. }
  31. return 0;
  32. }

质因数分解:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int ok(int x)
  5. {
  6. int ans=1,nums=0;
  7. for(int i=2;i*i<=x;i++)
  8. {
  9. if(x%i==0)
  10. {
  11. nums++;
  12. while(x%i==0) x/=i;
  13. }
  14. }
  15. if(x!=1)
  16. nums++;
  17. while(nums--) ans=ans*2;
  18. return ans;
  19. }
  20. int main()
  21. {
  22. int x,y;
  23. while(~scanf("%d%d",&x,&y))
  24. {
  25. if(y%x==0)
  26. printf("%d\n",ok(y/x));
  27. else
  28. printf("0\n");
  29. }
  30. return 0;
  31. }

F The Factor (HDU - 5428)

题意:

    给出一个有n(1<=n<=100)个数的序列,第i个数为ai(1<=ai<=2*10^9),问这些数的乘积里面最小的因数个数超过2的数是多少,如果不存在输出-1。
    T(1<=T<=15)组数据。

题解:

    因为一个数的因数肯定包含1和本身,所以只要这个数由两个非1的正整数相乘得到,那么他肯定包括至少3个因数。于是我们只要将这个序列的每个数都进行质因数分解,从中找两个最小的因数乘起来就是答案。如果没有两个非1因数的话,那么就输出-1。
    ps:注意两个大质数相乘有可能会超过int的上限。
    时间复杂度o(T*n*sqrt(a)),空间复杂度o(sqrt(a)+n)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int ans1,ans2;
  5. void update(int x)
  6. {
  7. if(x<ans1)
  8. {
  9. ans2=ans1;
  10. ans1=x;
  11. }
  12. else
  13. {
  14. if(x<ans2)
  15. ans2=x;
  16. }
  17. }
  18. void go(int x)
  19. {
  20. int nums;
  21. for(int i=2;i*i<=x;i++)
  22. {
  23. if(x%i==0)
  24. {
  25. update(i);
  26. x/=i;
  27. if(x%i==0)
  28. update(i);
  29. while(x%i==0)
  30. x/=i;
  31. }
  32. }
  33. if(x!=1)
  34. update(x);
  35. return ;
  36. }
  37. int main()
  38. {
  39. int t,n,now;
  40. scanf("%d",&t);
  41. while(t--)
  42. {
  43. scanf("%d",&n);
  44. ans1=ans2=2000000005;
  45. for(int i=0;i<n;i++)
  46. {
  47. scanf("%d",&now);
  48. go(now);
  49. }
  50. if(ans2>2000000000)
  51. printf("-1\n");
  52. else
  53. printf("%lld\n",1LL*ans1*ans2);
  54. }
  55. return 0;
  56. }

G The Euler function (HDU - 2824)

题意:

    欧拉函数phi(n)表示小于n并且和n互质的数的个数,给出a和b(2<a<b<3000000),求(a<=x<=b)Σphi(x)。

题解:

    一如既往的前缀和思想,把区间和转化为两个前缀的差。
    欧拉函数的公式为phi(n)=n*(fac[1]-1)/fac[1]*(fac[2]-1)/fac[2]*...(fac[x]-1)/fac[x],其中fac[i]表示n的第i个质因数。
    很容易想到打素数表,然后暴力求欧拉函数的每一项再求前缀和。其实我们可以把这两者结合起来,在打素数表的过程中就顺便把求欧拉函数的事干了。
    ps:这题非常恶心,空间只能开的下一个long long数组,多开一个int就会mle。
    时间复杂度o(3000000),空间复杂度o(3000000)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. long long phi[3000005];
  5. int main()
  6. {
  7. for(int i=2;i<=3000000;i++)
  8. phi[i]=i;
  9. for(int i=2;i<=3000000;i++)
  10. {
  11. if(phi[i]==i)
  12. {
  13. for(int j=i;j<=3000000;j+=i)
  14. phi[j]=phi[j]/i*(i-1);
  15. }
  16. }
  17. for(int i=2;i<=3000000;i++)
  18. phi[i]+=phi[i-1];
  19. int a,b;
  20. long long sum=0;
  21. while(~scanf("%d%d",&a,&b))
  22. printf("%lld\n",phi[b]-phi[a-1]);
  23. return 0;
  24. }

H Raising Modulo Numbers (POJ - 1995)

题意:

    有A和B两个数列,各有H(1<=H<=45000)个数,求[(1<=i<=H)ΣAi^Bi]mod M(1<=M<=45000)的值。
    Z组数据。

题解:

    很暴力,其实就是求(1<=i<=H)Σ[Ai^Bi mod M]。但是Ai^Bi mod M的复杂度为Bi,再乘上一个H,就会Boom!
    所以我们要用快速幂来求Ai^Bi mod M。
    ps:因为M^2在int范围内,所以不需要担心爆int的问题。
    复杂度o(Z*H*log(Bi)),空间复杂度o(1)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int pows(int x,int y,int m)
  5. {
  6. int ans=1;
  7. while(y)
  8. {
  9. if(y%2)
  10. ans=(ans*x)%m;
  11. x=(x*x)%m;
  12. y/=2;
  13. }
  14. return ans;
  15. }
  16. int main()
  17. {
  18. int z;
  19. int a,b,ans,h,m;
  20. scanf("%d",&z);
  21. while(z--)
  22. {
  23. scanf("%d%d",&m,&h);
  24. ans=0;
  25. for(int i=0;i<h;i++)
  26. {
  27. scanf("%d%d",&a,&b);
  28. ans=(ans+pows(a%m,b,m))%m;
  29. }
  30. printf("%d\n",ans);
  31. }
  32. return 0;
  33. }

I Jzzhu and Sequences (CodeForces - 450B)

题意:

    当i>=2数列f满足f[i]=f[i-1]+f[i+1],且f[1]=x、f[2]=y(|x|,|y|<=10^9),求f[n] mod 1000000007(1<=n<=2*10^9)。

题解:

    看到f[i]=f[i-1]+f[i+1]可能会让人懵逼,不过移项一下其实就是f[i+1]=f[i]-f[i-1],所以f[i]=f[i-1]-f[i-2]。这其实就是一个变形的斐波那契数列。因为n很大所以顺序递推是行不通的,于是我们考虑使用矩阵快速幂。用一个矩阵表示线性变换,然后用快速幂的思路求矩阵的幂,最后把首项进行这个幂代表的线性变换,就是答案了。
    ps:MOD*MOD会爆int,所以要用long long,还有就是可能会出现负数,注意过程中的取模。思考一下我向量的初值的含义和线性变换矩阵的含义。顺便学习一下封装一个类的思想~
    时间复杂度o(log(n)),空间复杂度o(1)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. #define MOD 1000000007
  5. struct Mat
  6. {
  7. long long num[2][2];
  8. friend Mat operator *(Mat x1,Mat x2)
  9. {
  10. Mat ans;
  11. ans.num[0][0]=((x1.num[0][0]*x2.num[0][0]+x1.num[0][1]*x2.num[1][0])%MOD+MOD)%MOD;
  12. ans.num[0][1]=((x1.num[0][0]*x2.num[0][1]+x1.num[0][1]*x2.num[1][1])%MOD+MOD)%MOD;
  13. ans.num[1][0]=((x1.num[1][0]*x2.num[0][0]+x1.num[1][1]*x2.num[1][0])%MOD+MOD)%MOD;
  14. ans.num[1][1]=((x1.num[1][0]*x2.num[0][1]+x1.num[1][1]*x2.num[1][1])%MOD+MOD)%MOD;
  15. return ans;
  16. }
  17. }E;
  18. Mat pows(Mat X,int nums)
  19. {
  20. Mat nowans=E;
  21. while(nums)
  22. {
  23. if(nums%2)
  24. nowans=X*nowans;
  25. X=X*X;
  26. nums/=2;
  27. }
  28. return nowans;
  29. }
  30. int main()
  31. {
  32. E.num[0][0]=1;
  33. E.num[0][1]=0;
  34. E.num[1][0]=0;
  35. E.num[1][1]=1;
  36. Mat A,B;
  37. A.num[0][0]=0;
  38. A.num[0][1]=1;
  39. A.num[1][0]=-1;
  40. A.num[1][1]=1;
  41. int vec[2];
  42. int n;
  43. scanf("%d%d",&vec[0],&vec[1]);
  44. scanf("%d",&n);
  45. B=pows(A,n-1);
  46. vec[0]=((vec[0]*B.num[0][0]+vec[1]*B.num[0][1])%MOD+MOD)%MOD;
  47. printf("%d\n",vec[0]);
  48. return 0;
  49. }

J How many ways?? (HDU - 2157)

题意:

    中文题。

题解:

    很容易想到的其实是dp解法,不过这里提供一个用矩阵乘法来写的思路,其实原理也是dp,你们思考一下。主要是理解一下转移矩阵怎么定出来的~
    ps:这题的数据,直接暴力乘就好,不用快速幂。。。
    时间复杂度o(T*n^2*k),空间复杂度o(n^2)。

代码:

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. #define MOD 1000
  6. int n;
  7. struct Vec
  8. {
  9. int num[25];
  10. void init()
  11. {
  12. memset(num,0,sizeof(num));
  13. }
  14. friend int operator *(Vec x1,Vec x2)
  15. {
  16. int ans=0;
  17. for(int i=0;i<n;i++)
  18. ans=(ans+x1.num[i]*x2.num[i])%MOD;
  19. return ans;
  20. }
  21. };
  22. Vec A[25];
  23. Vec pows(Vec x)
  24. {
  25. Vec nowans;
  26. for(int i=0;i<n;i++)
  27. nowans.num[i]=A[i]*x;
  28. return nowans;
  29. }
  30. int main()
  31. {
  32. int m,s,t,T;
  33. int a,b,k;
  34. Vec ans;
  35. while(scanf("%d%d",&n,&m),n||m)
  36. {
  37. for(int i=0;i<n;i++)
  38. A[i].init();
  39. while(m--)
  40. {
  41. scanf("%d%d",&s,&t);
  42. A[t].num[s]=1;
  43. }
  44. scanf("%d",&T);
  45. while(T--)
  46. {
  47. scanf("%d%d%d",&a,&b,&k);
  48. ans.init();
  49. ans.num[a]=1;
  50. for(int i=0;i<k;i++)
  51. ans=pows(ans);
  52. printf("%d\n",ans.num[b]);
  53. }
  54. }
  55. return 0;
  56. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注