欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-16 13:16:27
2020牛客暑期多校训练营(第六场)(2020.7.27)B、Binary Vector虽然题目没有看懂,但是本场MVP浩大师发现了规律,f(x)=2x−12xf(x−1)f(x)={2^{x}-1\over 2^x}f(x-1)f(x)=2x2x−1​f(x−1)。然后把程序打出来就AC了。#include using namespace std;typedef long long ll;const int MAXN = 2e7 + 10;const...

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

B、Binary Vector

虽然题目没有看懂,但是本场MVP浩大师发现了规律,f(x)=2x12xf(x1)f(x)={2^{x}-1\over 2^x}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("%d\n", ans[n]);
    }
    return 0;
}

C、Combination of Physics and Maths

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

#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("%.8lf\n", 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题又被浩大师想出了解法,但是不会写。

菜 我 菜

本文地址:https://blog.csdn.net/qq_36000896/article/details/107615667