牛客小白月赛58 题解

牛客小白月赛58 A - E

历史最高rk……然而蒟蒻依旧不会dp…..orz

https://ac.nowcoder.com/acm/contest/41173

A - 双子爆破者

直接套公式

#include <bits/stdc++.h>

using namespace std;

void solve () {
    double M, m, v;
    cin >> M >> m >> v;
    cout << fixed << setprecision (3) << 1.0*m*v/(M-m) << endl;
}

int main () {
    int t;
    cin >> t;
    while (t --)    solve ();
}

B - 牛原子

模拟题，但是读题读了贼久

题意：按照 1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p 的顺序进行原子排列，s类电子亚层容量为 2，p 类电子亚层容量为 6，d 类电子亚层容量为 10，f 类电子亚层容量为 14，排满了就放下一层。最后要按照数字升序，字母“spdf” 的顺序来排列。

嗯模拟即可

#include <bits/stdc++.h>
#define ll long long

using namespace std;
//spdf
string s[] = {"1s", "2s", "2p", "3s", "3p", "4s", "3d", "4p", "5s", "4d", "5p", "6s", "4f", "5d", "6p", "7s", "5f", "6d", "7p"};
//string s[] = {"1s", "2s", "2p", "3s", "3p", "3d", "4s", "4p", "4d", "4f", "5s", "5p", "5d", "5f", "6s", "6p", "6d", "7s", "7p"};
map<char, int> mp = {{'s', 1}, {'p', 2}, {'d', 3}, {'f', 4}};

bool cmp (string a, string b) {
    if (a[0] != b[0])   return a[0] < b[0];
    return mp[a[1]] < mp[b[1]];
}

void solve () {
    int n;
    scanf ("%d", &n);
    vector <string> v;
    for (int i = 0; i < 19; i++) {
        int dx = 0;
        if (s[i][1] == 's')     dx = 2;
        else if (s[i][1] == 'p')    dx = 6;
        else if (s[i][1] == 'f')    dx = 14;
        else    dx = 10;
        if (n - dx >= 0)    n -= dx, v.push_back (s[i] + to_string(dx));
        else    v.push_back (s[i] + to_string(n)), n = 0;
        if (n <= 0) break;
    }
    sort (v.begin (), v.end (), cmp);
    for (auto i : v)    cout << i << ' ';
    cout << endl;
}

signed main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

//s类电子亚层容量为 2，p 类电子亚层容量为 6，d 类电子亚层容量为 10，f 类电子亚层容量为 14
//1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p

C- 牛牛

因为读不懂题B先出的C

题意：就相当于在n个数当中挑出2个数，使得剩下的数之和 % m == 0，简单做一下公式变换即得：

由(sum-ai-aj) % 10 = 0得，sum-ai 同余于 aj (mod m)

即，枚举 ai，找到一个满足上述条件的 aj 即可，注意 i 不等于 j

用map查找 nlogn

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 2e5 + 5;
int a[N];

void solve () {
    map <int, int> s;
    int n, m;
    ll sum = 0;
    scanf ("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf ("%d", &a[i]);
        sum += a[i];
        s[a[i] % m] ++;
    }
    for (int i = 1; i <= n; i++) {
        ll x = (sum - a[i]) % m;
        if (s[x]) { //并且不能是自身
        if (s[x] == 1 && (a[i] % m == x))   continue;
            ll ans = sum % m;
            if (ans == 0)   ans = m;
            printf ("%lld\n", ans);
            return ;
        }
    }
    printf ("0\n");
}

signed main () {
    int t;
    scanf ("%d", &t);
    while (t --)    solve ();
}

//剔除两张，剩下的要是10的倍数

D - 数学考试

按照题意进行背包dp

因为空间限制很严格，所以要滚动数组

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e4 + 5, M = 5e3 + 5;
int f[M][2], n, k, ans; //空间要求很严格所以要滚动数组

void solve () {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int a, b, q, w;
        cin >> a >> b >> q >> w;
        for (int j = 0; j <= k; j++)    f[j][i & 1] = 0;
        for (int j = 0; j <= k; j++) {
            int dx = f[j][(i-1) & 1];
            if (j <= b)     dx += a * j;
            //三种策略
            if (j + q <= k)     f[j + q][i & 1] = max (f[j + q][i & 1], dx);
            if (j - w >= 0)     f[j - w][i & 1] = max (f[j - w][i & 1], dx);
            f[j][i & 1] = max (f[j][i & 1], dx); //无条件转移
        }
    }
    for (int j = 0; j <= k; j++)    ans = max (ans, f[j][n & 1]);
    cout << ans;
}

signed main () {
    solve ();
}

E - 法力无边

学习牛客竞赛官方题解

【技巧】位运算经典map + 前缀和

**转换为加法 —— 异或：%2；同或 %2 + 1 **

如此，就可以利用前缀和，即 M[i][j]=((ai+...+aj) + j-i) % 2 = 1

化成比较好看的通项性质，则有：(sum[j]+j) 同余 (sum[i-1] + i-1) (mod 2)

可令 d[i] = sum[i] - i，则有 d[j] 同余 d[i-1] (mod 2)

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 25;
int sum[N][2], n, m;

void solve () {
    cin >> n >> m;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x;  cin >> x;
        for (int j = 0; j < m; j++) {
            if ((x >> j) & 1)   sum[j][1] ++;
            else    swap (sum[j][0], sum[j][1]), sum[j][0] ++;
            ans += (1 << j) * sum[j][1];
        }
    }
    cout << ans;
}

signed main () {
    solve ();
}

Sakana~

牛客小白月赛58 A-E