牛客小白月赛72

A.跳跃游戏

题目:

分析:

根据跳跃规则,只要中间存在高度介于起点和终点之间的平台即可让小Z从第一个平台跳到最后一个平台。

code:

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

const int N = 1e5 + 5;
int a[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    
    bool check = false;
    if (a[0] < a[n - 1])
        check = true;
    
    for (int i = 1; i < n - 1; i ++)
    {
        if (a[0] < a[i] && a[i] < a[n - 1])
        {
            check = true;
            break;
        }
    }
    
    if (check)
        cout << "YES";
    else
        cout << "NO";
    
    return 0;
}

B.数数

题目:

分析:

首先n最大只有4000,因此我们可以预处理前4000个数,看每一个数其因子数量是否为奇数,最后做一遍前缀和即可。

code:

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

const int N = 4e3 + 5;
bool st[N];
int s[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    for (int i = 1; i <= 4e3; i ++)
    {
        unordered_map<int, bool> mp;
        int cnt = 0;
        for (int j = 1; j * j <= i; j ++)
        {
            if (i % j == 0 && !mp[j])
            {
                cnt ++;
                mp[j] = true;
                int k = i / j;
                if (!mp[k])
                {
                    mp[k] = true;
                    cnt ++;
                }
            }
        }
        if (cnt & 1)
            st[i] = true;
    }
    
    for (int i = 1; i <= 4e3; i ++)
        s[i] = s[i - 1] + st[i];
    
    int t;
    cin >> t;
    
    while (t --)
    {
        int n;
        cin >> n;
        
        cout << s[n] << endl;
    }
    
    return 0;
}

C.操作数组

题目:

分析:

用b数组减a数组可以得到a序列的每一个数到b序列每一个数的距离,用S1和S2分别表示正距离和以及负距离的和,由于每次操作必然是让某个数+1让某个数-1,这两个数还不能相同,因此这种对称操作使得当且仅当S1+S2=0时有解并且最优解时S1。

code:

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

typedef long long LL;
const int N = 1e5 + 5;
LL a[N], b[N], c[N];

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i ++)
        cin >> a[i];
    
    for (int i = 0; i < n; i ++)
        cin >> b[i];
    
    for (int i = 0; i < n; i ++)
        c[i] = b[i] - a[i];
    
    LL cnt1 = 0, cnt2 = 0, cnt3 = 0;
    
    for (int i = 0; i < n; i ++)
    {
        if (c[i] > 0)
            cnt1 += c[i];
        if (c[i] < 0)
            cnt2 += c[i];
    }
    
    cnt3 = abs(cnt1 + cnt2);
    
    if (cnt3 == 0)
        cout << cnt1;
    else
        cout << -1;
    
    return 0;
}

D.遗迹探险

题目:


分析:

首先我们对最优解的选取分个类:
1.不使用传送门:最优解为从(1,1)-> (n,m)获得宝藏之和的最大值
2.使用传送门:对于传送门A,B。A在B的前面(这里前面所指代的位置关系参照代码里的排序规则)
①从A到B:最优解为(1,1)->(A.x,A.y)获得宝藏的之和的最大值 + (B.x,B.y)->(n,m)获得宝藏之和的最大值
②从B到A:最优解为(1,1)->(B.x,B.y)获得宝藏之和的最大值 + (A.x,B.y)->(n,m)获得宝藏之和的最大值
由于k并不是特别大,因此传送门的选取组合我们可以枚举。那么最终全局最优解就是上面三种情况取个max
现在考虑两个问题,如何求(1,1)->(x,y)的宝藏之和的最大值?如何求(x,y)->(n,m)宝藏之和的最大值?对于前一个问题实际上就是经典的数字三角形模型,而对于后一个问题实际上可以转化成求(n,m)->(x,y)宝藏之和的最大值,也可以用数字三角形模型做:
1.状态表示:定义f[i][j]表示从(1,1)->(i,j)获得的宝藏之和的最大值,g[i][j]表示从(n,m)->(i,j)获得的宝藏之和的最大值。
2.状态计算:
f[i][j] = max(f[i][j - 1], f[i - 1][j]) + w[i][j]
g[i][j] = max(g[i + 1][j], g[i][j + 1]) + w[i][j]

code:

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

typedef long long LL;
const int N = 1e3 + 5;
LL w[N][N];
LL f[N][N], g[N][N];
struct Node
{
    int x, y;
}node[N];

bool cmp(Node A, Node B)
{
    if (A.x != B.x)
        return A.x < B.x;
    else
        return A.y < B.y;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int n, m;
    cin >> n >> m;
    
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
            cin >> w[i][j];

    for (int i = 0; i <= N; i ++)
        for (int j = 0; j <= N; j ++)
            f[i][j] = g[i][j] = -2e16;
    
    for (int i = 1; i <= n; i ++)
    {
        for (int j = 1; j <= m; j ++)
        {
            if (i == 1 && j == 1)
                f[i][j] = w[i][j];
            else
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];
        }
    }
    
    for (int i = n; i >= 1; i --)
    {
        for (int j = m; j >= 1; j --)
        {
            if (i == n && j == m)
                g[i][j] = w[i][j];
            else
                g[i][j] = max(g[i + 1][j], g[i][j + 1]) + w[i][j];
        }
    }
    
    
    int t;
    cin >> t;
    
    while (t --)
    {
        int k;
        cin >> k;
        
        for (int i = 0; i < k; i ++)
            cin >> node[i].x >> node[i].y;
        
        sort(node, node + k, cmp);
        
        LL res = f[n][m];
        
        for (int i = 0; i < k; i ++)
        {
            for (int j = i + 1; j < k; j ++)
            {
                int a = node[i].x, b = node[i].y, c = node[j].x, d = node[j].y;
                
                res = max(res, max(f[a][b] + g[c][d], f[c][d] + g[a][b]));
            }
        }
        
        cout << res << endl;
    }
        
    return 0;
}

E.顶级厨师

题目:

分析:

首先我们分别对a序列和b序列从小到大排序,对于每一个询问,我们可以直接二分答案,对于那些禁止的组合我们再特殊处理一下即可。

code:

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

typedef long long LL;
const int N = 1e5 + 5, M = 1e6 + 5;
LL a[N], b[N], del[M];
int n, m, k, q;

LL check(LL mid)
{
    LL cnt = 0;
    
    for (LL i = 1, j = m; i <= n; i ++)
    {
        while (a[i] * b[j] > mid && j >= 1)
            j --;
        cnt += j;    
    }
    
    for (int i = 0; i < k; i ++)
    {
        if (del[i] <= mid)
            cnt --;
    }
    
    return cnt;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    cin >> n >> m >> k >> q;
    
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    
    for (int i = 1; i <= m; i ++)
        cin >> b[i];
    
    for (int i = 0; i < k; i ++)
    {
        int u, v;
        cin >> u >> v;
        
        del[i] = a[u] * b[v];
    }
    
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    
    while (q --)
    {
        int x;
        cin >> x;
        
        LL l = 0, r = 1e13;
        while (l < r)
        {
            LL mid = l + r >> 1;
            if (check(mid) >= x)
                r = mid;
            else
                l = mid + 1;
        }
        
        cout << l << endl;
    }
    
    return 0;
}

热门相关:帝少的专属:小甜心,太缠人   重生之至尊千金   横行霸道   朕是红颜祸水   最强装逼打脸系统