[关闭]
@wwwqeqeqeqe 2019-04-26T10:18:39.000000Z 字数 4908 阅读 863

Codeforces Round #553 (div.2)

codeforces

A Maxim and Biology

题目大意：

给你一个字符串，让你进行最少次数的改变，使得能在这个字符串中找到连续的ACTG。（Z变为A和A变为Z都算变换一次）

解题思路：

暴力搜索所有的字符，每次计算他及后面连续的四个字符变为ACTG所需要的最少次数，取最小即可。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int INF=0x3f3f3f3f;
  5. const int maxn=1e2+5;
  6. const char a[]={"ACTG"};
  8. int n;
  9. char s[maxn];
  11. int main()
  12. {
  13.     cin >> n;
  14.     cin >> s;
  15.     int ans=INF;
  16.     for(int i=0;i<n-3;i++)
  17.     {
  18.         int sum=0;
  19.         for(int j=i;j<i+4;j++)
  20.         {
  21.             if(s[j]>=a[j-i])
  22.             {
  23.                 sum+=min(s[j]-a[j-i],'Z'-s[j]+a[j-i]-'A'+1);
  24.             }
  25.             else
  26.             {
  27.                 sum+=min(a[j-i]-s[j],s[j]-'A'+'Z'-a[j-i]+1);
  28.             }
  29.         }
  30.         ans=min(ans,sum);
  31.     }
  32.     cout << ans << endl;
  33.     return 0;
  34. }

B Dima and a Bad XOR

题目大意：

给你一个由非负整数组成的n*m的矩阵，让你从矩阵的每一行中选取一个数出来，使这些选出来的数按位异或严格大于零。

解题思路：

先把每一行的第一个元素进行按位异或。再从第一行开始，查找是否存在一个数x，使这个数和这一行的第一个数不同。如果不存在这个数并且每一行第一个元素异或得到的结果为0，那么这个矩阵就不存在满足条件的取法。如果第一个元素按位异或结果不为0，则每行都去第一个元素，如果为0，就把之前找到的x用来替换x那一行的第一个数进行异或。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int maxn=500+5;
  6. int n,m;
  7. int mp[maxn][maxn];
  8. int x,y,ans;
  10. int main()
  11. {
  12.     cin >> n >> m;
  13.     x=-1,y=-1,ans=0;
  14.     for(int i=0; i<n; i++)
  15.     {
  16.         for(int j=0; j<m; j++)
  17.         {
  18.             cin >> mp[i][j];
  19.             if(x == -1 && j!=0 && mp[i][j]!=mp[i][0])
  20.             {
  21.                 x=i;
  22.                 y=j;
  23.             }
  24.         }
  25.         ans^=mp[i][0];
  26.     }
  27.     if(ans == 0 && x == -1)
  28.     {
  29.         cout << "NIE" << endl;
  30.     }
  31.     else
  32.     {
  33.         cout << "TAK" << endl;
  34.         if(ans != 0)
  35.         {
  36.             for(int i=0; i<n-1; i++)
  37.                 cout << 1 << " ";
  38.             cout << 1 <<endl;
  39.         }
  40.         else
  41.         {
  42.             if(x!=n-1)
  43.             {
  44.                 for(int i=0; i<n-1; i++)
  45.                 {
  46.                     if(x == i)
  47.                         cout << y+1 << " ";
  48.                     else
  49.                         cout << 1 << " ";
  50.                 }
  51.                 cout << 1 << endl;
  52.             }
  53.             else
  54.             {
  55.                 for(int i=0;i<n-1;i++)
  56.                     cout << 1 << " ";
  57.                 cout << y+1 << endl;
  58.             }
  59.         }
  60.     }
  61.     return 0;
  62. }

C Problem for Nazar

题目大意：

将数字分为偶数和奇数两种，数字的排列顺序不同于普通的排列方式，而是先取一个奇数，然后取两个偶数，再取四个奇数······以此类推。给你两个数l和r，计算出第l位到第r位所有数字的和。（1到10的排列顺序为1,2,4,3,5,7,9,6,8,10）

解题思路：

我们计算出前l-1和数的和以及前r个数的和，将他们两个相减便能够得到我们要的最终答案。在计算前k个数的和时，按照题目要求的排列方式，从第一个数1开始一直按照规则暴力计算我们一共选取了多少个奇数和多少个偶数，再通过等差数列求和公式，计算出前k个数的和。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const long long mod=1e9+7;
  6. long long l,r;
  8. long long cal(long long n)
  9. {
  10.     long long odd=0,even=0;
  11.     long long cnt=0,mark=0;
  12.     for(long long i=1;cnt<n;i*=2)
  13.     {
  14.         long long t=min(n-cnt,i);
  15.         cnt+=t;
  16.         if(mark == 0)
  17.             odd+=t;
  18.         else
  19.             even+=t;
  20.         mark ^=1 ;
  21.     }
  22.     odd%=mod;
  23.     even%=mod;
  24.     long long ans=(odd*odd)%mod+(even*even)%mod+even%mod;
  25.     return ans%mod;
  26. }
  28. int main()
  29. {
  30.    long long k=1;
  31.    cin >> l >> r;
  32.    cout << ((cal(r)-cal(l-1))%mod+mod)%mod << endl;
  33.    return 0;
  34. }

D Stas and the Queue at the Buffet

题目大意：

有N个人横向排队，每个人有两个值ai和bi，每个人有一个权值，这个权值是他左边的人的个数乘以ai和右边的人乘以bi的和。求所有人的这个权值的和的最小值。

解题思路：

将所有人按照ai-bi从小到大进行排序，越小的安排在越右边，最后求和。（不懂为啥这个题能放到D去）

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int maxn=1e5+5;
  6. int n;
  7. struct node
  8. {
  9.     long long l,r;
  10. };
  11. node a[maxn];
  13. bool cmp(node x,node y)
  14. {
  15.     return (x.r-x.l)<(y.r-y.l);
  16. }
  18. int main()
  19. {
  20.     cin >> n;
  21.     for(int i=0;i<n;i++)
  22.     {
  23.         cin >> a[i].l >> a[i].r;
  24.     }
  25.     sort(a,a+n,cmp);
  26.     long long ans=0;
  27.     for(int i=0;i<n;i++)
  28.     {
  29.         ans+=i*a[i].l+(n-i-1)*a[i].r;
  30.     }
  31.     cout << ans << endl;
  32.     return 0;
  33. }

E Number of Components

题目大意：

给你n个数，然后定义一个公式f(i,j)=k表示将i到j看成一个连通块时从i到j这些数字的连通块个数为k。求从f(1,1)到f(n,n)的和。

解题思路：

我们首先枚举每一个节点都是当前连通块的左节点。那么，当a[i-1]<a[i]时，a[i]作为该连通块的左起点可以取[a[i-1]+1,a[i]]，区间右边取值可以取[a[i],n]，总计有取法（a[i]-a[i-1]）*(n-a[i]+1)种。当a[i-1]>a[i]时，区间左取值可以取[a[i],a[i-1]-1],右边可以取值[1,a[i]]，总数为(a[i-1]-a[i])*a[i]。当a[i]=a[i-1]时，a[i]不可能作为左端点被取到。最后将每个点的权值相加。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int maxn=1e5+5;
  6. long long n;
  7. long long a[maxn];
  9. int main()
  10. {
  11.     cin >> n;
  12.     for(int i=1;i<=n;i++)
  13.     {
  14.         cin >> a[i];
  15.     }
  16.     a[0]=a[n+1]=n+1;
  17.     long long ans=0;
  18.     for(int i=1;i<=n;i++)
  19.     {
  20.         if(a[i-1]<a[i])
  21.             ans+=(a[i]-a[i-1])*(n-a[i]+1);
  22.         else if(a[i-1]>a[i])
  23.             ans+=a[i]*(a[i-1]-a[i]);
  24.     }
  25.     cout << ans << endl;
  26.     return 0;
  27. }

F Sonya and Informatics

题目大意：

给出n个只有0或1的数，以及一个数字k。接下来进行k次操作，每次操作交换这n个数中的两个数。询问在k次操作之后，这n个数为不下降序列的概率是多少?

解题思路：

很明显，因为这n个数只有0和1，那么，不下降序列只有可能为前面的数全为0，后面的数全为1。假设0个个数为a，1的个数为b，d[i][j]表示完成i次操作后，前a个数字中有j个0的操作数量。设最原始的数组中，前a个数字里有c个0.我们将d[0][c]初始化为1，那么，问题的答案就为d[k][a]/(d[k][0]+d[k][1]+d[k][2]+······+d[k][a])。
考虑转移方程，d[i][j]可以从d[i-1][j-1]，d[i-1][j]和d[i-1][j+1]转移而来。其中d[i-1][j]表示这次转移为0换0或者1换1或者交换的两个数的序号都不在前a个数内或douzai。d[i-1][j-1]表示前a个数中的1和后b个数中的0交换。d[i-1][j+1]表示前a个数中的0和后b个数中的1交换。所以得到转移方程为：
d[i][j]=d[i-1][j]*(C(a,2)+C(b,2)+j*(a-j)+(a-j)*(b-a+j))+d[i-1][j-1]*(a-j+1)*(a-j+1)+d[i-1][j+1]*(j+1)*(b-a+j+1)。
因为d[i][*]只和d[i-1][*]有关，所以我们可以使用矩阵快速幂来求d[i][*]。

代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long ll;
  5. const ll mod = 1e9 + 7;
  7. struct SquareMatrix
  8. {
  9.     SquareMatrix(int _n) : n(_n)
  10.     {
  11.         data.assign(_n, vector<ll>(_n, 0));
  12.     }
  13.     vector<ll> &operator[](int i)
  14.     {
  15.         return data[i];
  16.     }
  17.     const vector<ll> &operator[](int i) const
  18.     {
  19.         return data[i];
  20.     }
  21.     SquareMatrix operator*(const SquareMatrix &other) const
  22.     {
  23.         assert(n == other.n);
  24.         SquareMatrix ret(n);
  25.         for (int i = 0; i < n; ++i)
  26.         {
  27.             for (int j = 0; j < n; ++j)
  28.             {
  29.                 for (int k = 0; k < n; ++k)
  30.                 {
  31.                     ret[i][j] = (ret[i][j] + data[i][k] * other[k][j]) % mod;
  32.                 }
  33.             }
  34.         }
  35.         return ret;
  36.     }
  37.     vector<vector<ll>> data;
  38.     int n;
  39. };
  41. SquareMatrix quickpower(SquareMatrix m, int p)
  42. {
  43.     int n = m.n;
  44.     SquareMatrix ret(n);
  45.     for (int i = 0; i < n; ++i) ret[i][i] = 1;
  46.     while (p)
  47.     {
  48.         if (p & 1)
  49.         {
  50.             ret = ret * m;
  51.         }
  52.         m = m * m;
  53.         p >>= 1;
  54.     }
  55.     return ret;
  56. }
  58. ll quickpower(ll x, int p)
  59. {
  60.     ll ret = 1;
  61.     while (p)
  62.     {
  63.         if (p & 1)  ret = (ret * x) % mod;
  64.         x = (x * x) % mod;
  65.         p >>= 1;
  66.     }
  67.     return ret;
  68. }
  70. int main()
  71. {
  72.     int n, k;
  73.     cin >> n >> k;
  74.     vector<int> a(n);
  75.     int x = 0, y = 0, z = 0;
  76.     for (int i = 0; i < n; ++i)
  77.     {
  78.         cin >> a[i];
  79.         x += a[i] == 0;
  80.     }
  81.     y = n - x;
  82.     for (int i = 0; i < x; ++i)
  83.         z += a[i] == 0;
  84.     SquareMatrix m(x + 1);
  85.     for (int i = 0; i <= x; ++i)
  86.     {
  87.         m[i][i] = x * (x - 1) / 2 + y * (y - 1) / 2 + i * (x - i) + (x - i) * (y - x + i);
  88.         if (i - 1 >= 0) m[i][i - 1] = (x - i + 1) * (x - i + 1);
  89.         if (i + 1 <= x) m[i][i + 1] = (i + 1) * (y - x + i + 1);
  90.     }
  91.     m = quickpower(m, k);
  92.     ll ans = 0;
  93.     for (int i = 0; i <= x; ++i)
  94.         ans = (ans + m[i][z]) % mod;
  95.     ans = m[x][z] * quickpower(ans, mod - 2) % mod;
  96.     cout << ans << endl;
  97.     return 0;
  98. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注