2020牛客暑期多校训练营(第六场)(2020.7.27)

B、Binary Vector

虽然题目没有看懂，但是本场MVP浩大师发现了规律，$f(x)={2^{x}-1over 2^x}f(x-1)$f(x)=2x2x−1​f(x−1)。然后把程序打出来就AC了。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e7 + 10; const int MOD = 1e9 + 7; ll qpow(ll a, ll b) {     ll ans = 1; a %= MOD;     while (b)     {         if (b & 1) ans = (ans * a) % MOD;         a = (a * a) % MOD; b >>= 1;     }     return ans; } int ans[MAXN]; int main() {     ll p = 1, q = qpow(2, MOD - 2), now = 2, inv = q, ori = q;     for (int i = 1; i <= 2e7; ++i)     {         ans[i] = (p * q) % MOD;         now = (now * 2) % MOD;         p = (p * (now - 1)) % MOD;         inv = (inv * ori) % MOD;         q = (q * inv) % MOD;     }     for (int i = 2; i <= 2e7; ++i) ans[i] ^= ans[i - 1];     int t; cin >> t;     while (t--)     {         int n; scanf("%d", &n);         printf("%dn", ans[n]);     }     return 0; } 

C、Combination of Physics and Maths

看完题感觉像dp，结果是个贪心。因为和要尽可能大，那么对于第$i$i行的某个元素$j$j，在计算第$j$j列的压强时一定是把它上面所有的元素都加起来。然后对这一行元素取压强最大值就是该行的最大值。(如果取了不止一个，那么第二个取的元素的压强一定小于等于第一个元素，总压强变小，取一个更优。)然后把整个矩阵遍历一遍即可。

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e2 + 10; int main() {     int t; cin >> t;     while (t--)     {         int n, m; scanf("%d%d", &n, &m);         int a[MAXN][MAXN];         for (int i = 1; i <= n; ++i)             for (int j = 1; j <= m; ++j)                 scanf("%d", &a[i][j]);         double ans = 0;         int s[MAXN] = {0};         for (int i = 1; i <= n; ++i)         {             for (int j = 1; j <= m; ++j)                 s[j] += a[i][j], ans = max(ans, (double)s[j] / a[i][j]);         }         printf("%.8lfn", ans);     }     return 0; } 

E、Easy Construction

本题由浩大师提供。

#include<bits/stdc++.h> using namespace std; typedef long long ll; int main() {     ll n, k, i, j;     cin >> n >> k;     if(n == 1)     {     	cout << 1 << endl;     }     else if(((n + 1) * n / 2) % n != k)     {         cout << -1 << endl;     }     else     {         if(k > 0)         {         	cout << n << " ";         	cout << k;         	for(i = 1; i < k; i++)             {             	cout << " " << i << " " << n - i;         	}         	cout << endl;         }         else         {             cout << n;             for(i = 1; i <= n / 2; i++)             {                 cout << " " << i << " " << n - i;             }         }         cout << endl;     }     return 0; } 

赛后总结：

开场开K，然后看错题。比赛打了一半才知道K题什么意思，然后开始对着K罚坐。

K看错题WA了一发之后爬去开了C。一个贪心没想到想了很久。还是不够贪。要加强。

B题经典找规律。我找规律实在很弱，全靠队友~~% 浩大师 %~~带飞。感觉要去多找点规律题做一做。

G题又被浩大师想出了解法，但是不会写。

菜 我 菜

c/c++开发分享2020牛客暑期多校训练营(第六场)地址：https://blog.csdn.net/qq_36000896/article/details/107615667