牛客小白月赛53

第二次打妞妞月赛
三题下班，呜呜呜我好菜orz
https://ac.nowcoder.com/acm/contest/11230

A. Raining

按照题意模拟即可

#include <bits/stdc++.h>

using namespace std;

int main () {
    int a, b, c, d, x;
    cin >> a >> b >> c >> d >> x;
    a  = max (x-a, 0), d  = max (x-d, 0), c  = max (x-c, 0), b  = max (x-b, 0);
    cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
}

B. Kissing

结论题, 先对通项化简:\(i^2-((i+1)^2-4i)=i^2-(i-2)^2=2i-1\)
然后是等差数列求和公式,得\(n^2\)
会爆long long, 所以要随时取模

#include <bits/stdc++.h>

using namespace std;
const int mod = 998244353;
typedef long long ll;

int main () {
    ll n;
    cin >> n;
    cout << ((n%mod)*(n%mod))%mod;
}
//2*i-1

C. Missing

按照题意模拟+结构体排序输出
(一开始前面写的while(n--),结果一直没更新答案,看了半天,蠢死了呜呜呜)

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, string> psi;

int main () {
    string s;
    int n;
    cin >> s >> n;
    vector <psi> v;
    vector <string> ss;

    for (int i = 0; i < n; i ++) {
        string t;
        cin >> t;
        ss.push_back (t);
    }
    sort (ss.begin (), ss.end ());
    //for (auto i : ss)    cout << i << ' ';  cout << endl;

    for (int i = 0; i < n; i ++) {
        string t = ss[i];
        if (t.size() != s.size())   v.push_back ({0, t});
        else {
            int cnt = 0;
            for (int i = 0; i < s.size (); i ++)
                if (s[i] == t[i])   cnt ++;
            v.push_back ({cnt, t});
        }
    }
    //for (auto i : v)    cout << i.first << ' ' << ss[i.second] << endl;  cout << endl;

    sort (v.begin (), v.end (), greater<psi>());

    int maxn = v[0].first;
    //cout << maxn << endl;
    
    ss.clear();
    for (auto i : v) {
        if (i.first != maxn)    break;
        ss.push_back (i.second);
    }
    sort (ss.begin (), ss.end());
    for (auto i : ss)   cout << i << endl;

}
//不除
//如果「相似度」都为 0，请仍然按字典序输出所有字符串

D. Breezing

显然,a[i]取1或b[i]的时候是最优的
那么就可以dp(我连最简单的dp都不会)
定义一个二维dp数组f[N][2]:
f[i][0]表示以为i结尾,当前位置选取a[i]=1,时的最大可爱值
f[i][1]表示以为i结尾,当前位置选取a[i]=b[i],时的最大可爱值

正解:

#include <bits/stdc++.h>

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

int main () {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++)   cin >> a[i];
    for (int i = 2; i <= n; i ++) {
        f[i][0] = max (f[i-1][0], f[i-1][1] + abs (a[i-1] - 1));
        f[i][1] = max (f[i-1][0] + abs (a[i] - 1), f[i-1][1] + abs (a[i-1] - a[i]));
    }

    cout << max(f[n][0], f[n][1]);
}

原来的错误写法:贪心,一大一小
贪心有风险,要慎重www

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

using namespace std;

signed main () {
    int n;
    cin >> n;
    vector <int> a(n+1);
    for (int i = 1; i <= n; i ++)   cin >> a[i];
    int ans1 = 0, ans2 = 0;
    //偶数
    if (n % 2 == 0) {
        for (int i = 2; i <= n; i += 2)
            ans1 += (a[i] - 1) * 2, ans2 += (a[i-1] - 1) * 2;
        ans1 -= (a[n] - 1), ans2 -= (a[1] - 1);
    }

    else {
        for (int i = 2; i <= n; i += 2)
            ans1 += (a[i] - 1) * 2, ans2 += (a[i-1] - 1) * 2;
        ans2 -= (a[1] - 1), ans2 -= (a[n] - 1);        
        if (n == 3) ans2 = a[1] - 1 + a[3] - 1;
    }
    //cout << ans1 << ' ' << ans2 << endl;

    cout << max(max (ans1, ans2), 0ll);
}

//1   b[i]  1  b[i]....
//b[i]  1   b[i]  1...

E. Calling

原来的错误写法:嗯模拟

#include <bits/stdc++.h>

using namespace std;

void solve () {
    int n;
    int num[7];
    cin >> n;
    for (int i = 1; i <= 6; i ++)   cin >> num[i];

    // if ((n - num[4] - num[5] - num[6]) < 0) {cout << "No\n";  return ;}
    int res[7] = {0, 36*n, 9*n, 4*n, n, n, n};
    n -= num[6], res[5] = res[4] = n, res[3] -= num[6]*4, res[2] -= num[6]*9, res[1] -= num[6]*36;
    if (n < 0)  {cout << "No\n";  return ;}

    n -= num[5], res[4] -= n, res[3] -= num[5]*4, res[2] -= num[5]*9, res[1] -= num[5]*25;
    if (n < 0)  {cout << "No\n";  return ;}
    
    n -= num[4], res[3] -= num[4]*4, res[2] -= num[4]*4, res[1] -= num[4]*16;
    if (n < 0)  {cout << "No\n";  return ;}

    if (res[3] < num[3])    {cout << "No\n";  return ;}
    res[1] -= num[3]*9;
    int mod = num[3] % 4, cnt = num[3]/4;
    if (mod == 0)    res[2] -= cnt * 9;
    else if (mod == 3)  res[2] -= cnt * 8;
    else if (mod == 2)  res[2] -= cnt * 6;
    else if (mod == 1)  res[2] -= cnt * 4;

    if (res[2] < num[2])  {cout << "No\n";  return ;}
    res[1] -= num[2]*4;
    if (res[1] < num[1])  {cout << "No\n";  return ;}
    cout << "Yes\n";
}

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

F. Freezing