牛客小白月赛71

A.猫猫与广告

题目：

分析：

只需考虑c * d的矩阵竖着摆和横着摆两种情况。本题提示了考虑两矩阵对应边平行的情况，实际上可以证明倘若能斜着放，那么一定可以横着放或竖着放，证明方式可已通过构造三角形来证明a* b的矩阵的长宽一定小于c * d矩阵的长宽。

code:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    if (a > b) swap(a, b);
    if (c > d) swap(c, d);
    
    if ((a <= c && b <= d) || (a <= d && b <= c))
        cout << "YES";
    else
        cout << "NO";
    
    return 0;
}

B.猫猫与密信

题目：

分析：

由于只消失一个字符，因此可以对可能存在love的子串进行讨论：
①消失的不是字符i,则满足条件的子串有：lve,loe,lov
②消失的字符是i，则满足条件的子串只有：ove
所以从前往后枚举每一个字符，若其为i或者o则截取以其开头的长度为3的子串，看是否满足要求即可。

code:

#include <bits/stdc++.h>
using namespace std;

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    string s;
    cin >> s;
    
    bool flag = false;
    for (int i = 0; i < s.size(); i ++)
    {
        if (s[i] == 'l')
        {
            string s2 = s.substr(i, 3);
            if (s2 == "lve" || s2 == "loe" || s2 == "lov")
            {
                flag = true;
                break;
            }
        }
        else if (s[i] == 'o')
        {
            string s2 = s.substr(i, 3);
            if (s2 == "ove")
            {
                flag = true;
                break;
            }
        }
    }
    
    if (flag)
        cout << "YES";
    else
        cout << "NO";
    
    return 0;
}

C.猫猫与数列

题目：

分析：

这题的难点在处理溢出的问题。处理方式有很多，比如用long double或者int_128，这里介绍取对数的技巧。由于log(x)单调递增，因此我们不妨对an取log，根据其log值来判断大小关系。不过这里要处理精度的问题，我们可以让an-1 * log(an-2)与log(2M)比，若an比2M都要大那自然大于M，否则我们再直接计算an并和M比较，这时就不用担心溢出的问题。

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const double M = log(2e18);
const int N = 110;
LL a[N];

LL qmi(LL m, LL k)
{
    LL res = 1, t = m;
    
    while (k)
    {
        if (k & 1)
            res = res * t;
        t = t * t;
        k >>= 1;
    }
    
    return res;
}

int main()
{
    cin >> a[1] >> a[2];
    
    int n = 3;
    
    while(1)
    {
        if (a[n - 1] * log(a[n - 2]) > M)
        {
            n --;
            break;
        }
        else
        {
            a[n] = qmi(a[n - 2], a[n - 1]);
            if (a[n] > 1e18)
            {
                n --;
                break;
            }
            n ++;
        }
    }
    
    cout << n;
    
    return 0;
}

D.猫猫与主人

题目：

分析：

每个元素有两个维度的变量，考虑放到坐标系中去启发思考。

我们用三角形表示小猫，圆形表示主人，我们可以发现对于每一个小猫，满足条件的主人在其左上区域。因此我们不妨对小猫和主人按横坐标排序，然后维护每一个小猫左上区域内的满足条件的纵坐标值最大的主人。

code:

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
struct Node
{
    int a, b, idx;
}cat[N], p[N];
int ans[N];

bool cmp(Node A, Node B)
{
    if (A.a != B.a)
        return A.a < B.a;
    else if (A.b != B.b)
        return A.b < B.b;
    else
        return A.idx < B.idx;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++)
        cin >> cat[i].a;
    
    for (int i = 0; i < n; i ++)
    {
        cin >> cat[i].b;
        cat[i].idx = i;
    }
    
    for (int i = 0; i < m; i ++)
        cin >> p[i].b;

    for (int i = 0; i < m; i ++)
    {
        cin >> p[i].a;
        p[i].idx = i;
    }
    
    sort(cat, cat + n, cmp);
    sort(p, p + m, cmp);
    
    int Max = -0x3f3f3f3f;
    
    for (int i = 0, j = 0; i < n; i ++)
    {
        while (j < m && p[j].a <= cat[i].a)
        {
            Max = max(Max, p[j].b);
            j ++;
        }
        j --;
        if (Max >= cat[i].b)
        {
            ans[cat[i].idx] = Max;
        }
        else
            ans[cat[i].idx] = -1;
    }
    
    for (int i = 0; i < n; i ++)
        cout << ans[i] << " ";
    
    return 0;
}

E.猫猫与数学

题目：

分析：

①有解：
先考虑一般情况：由于两边都有c，因此需要转化一下。不妨设a > b,根据更相减损法得gcd(a + c, b + c) = gcd(a - b, b + c) ≠ 1。枚举a - b得所有非1因数设为x，根据x反解c，然后对所有c的解取个min即为答案。
特判a - b = 0，若a = 1则c取1，否则c取0
②无解：
显然当a - b = 1时无解。

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL a, b, ans = 1e16;

void check(LL x)
{   
    if (x == 1)
        return;
    if (b % x == 0)
        ans = min(ans, 0LL);
    else
        ans = min(ans, x - b % x);
}

int main()
{
    cin >> a >> b;
    
    if (a < b)
        swap(a, b);
    
    if (a - b == 1)
        cout << -1;
    else if (a == b)
    {
        if (a == 1)
            cout << 1;
        else 
            cout << 0;
    }
    else
    {
        LL d = a - b;
        LL M = sqrt(d) + 1;
        for (int i = 1; i <= M; i ++)
        {
            if (d % i == 0)
            {
                check(i);
                check(d / i);
            }
        }
        cout << ans;
    }
    
    return 0;
}

F.猫猫与宝石

题目：

分析：

推公式：

code:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int mod = 998244353, N = 2e5 + 5, M = (mod + 1) / 2;
LL a[N], b[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    LL n, s = 0;
    cin >> n;
    
    a[0] = b[0] = 1;
    for (int i = 1; i <= n; i ++)
    {
        a[i] = a[i - 1] * 2 % mod;
        b[i] = b[i - 1] * M % mod;
    }
    
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        s = (s + x) % mod;
        
        cout << (((a[i - 1] + (a[i - 2] * (i - 1) % mod)) % mod) * s % mod) * b[i] % mod << " ";
    }
    
    return 0;
}

原文链接：https://www.cnblogs.com/XiongTingyang/p/17352307.html