牛客小白月赛99（A-F）

牛客小白月赛99_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ

A

签到题，不解释

#include<iostream>
using namespace std;
using ll = long long;
int main()
{
    int t; cin >> t;
    while(t--)
    {
        ll a, b, x, y; cin >> a >> b >> x >> y;
        ll res = b * y;
        if(x < y) res += a * x;
        else res += a * y;
        cout << res << endl;
    }
    return 0;
}

B

n % b = c        , 令 ,  k 属于 [ b, n ]，c 属于 [ 0, b), [0, k)

  n - k = c, ，每次 c 若取最大值，那么 k 取最小， k  每次取 n / 2 + 1.

#include<iostream>

using namespace std;
using ll = long long;

void slove()
{
    ll n; cin >> n;
    ll ans = 0;
    while(n)
    {
        ll k = n / 2 + 1;
        n %= k;
        ans++;
    }
    
    cout << ans << endl;
}


int main()
{
    int t; cin >> t;
    while(t--) slove();
    return 0;
}

C

起点是否能达终点，取决于终点属于的连通块周围是否可以被激光清除。对于终点的每一块连通块，将该点的上下左右 行 和 列标记，若起点可达这些标记行 列，即可达终点。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 1010;
typedef pair<int, int> PII;
int n, m;
int sx, sy, ex, ey;
int dy[] = {0, 1, 0, -1}, dx[] = {-1, 0, 1, 0};
char g[N][N];
bool stx[N], sty[N], st1[N][N], st2[N][N];
void bfs()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
            cin >> g[i][j];

    
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
            if(g[i][j] == 'S') { sx = i, sy = j; }
            else if(g[i][j] == 'E') { ex = i, ey = j; }
    
    queue<PII> q1;
    q1.push({ex, ey});
    st1[ex][ey] = true;
    
    while(q1.size())
    {
        PII t = q1.front(); q1.pop();
        int x = t.first, y = t.second;
        
        stx[x] = stx[x - 1] = stx[x + 1] = true;
        sty[y] = sty[y + 1] = sty[y - 1] = true;
        
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m) continue;  
            if(g[a][b] == '#' || st1[a][b]) continue;
            
            st1[a][b] = true;
            
            q1.push({a, b});
        }
    }
    queue<PII> q2;
    q2.push({sx, sy});
    st2[sx][sy] = true;
    
    while(q2.size())
    {
        PII t = q2.front(); q2.pop();
        int x = t.first, y = t.second;
        
        if(stx[x] || sty[y]) 
        {
            cout << "YES" << endl;
            return;
        }
        
        for(int i = 0; i < 4; i++)
        {
            int a = x + dx[i], b = y + dy[i];
            if(a < 1 || a > n || b < 1 || b > m) continue;
            if(g[a][b] == '#' || st2[a][b]) continue;
            st2[a][b] = true;
            q2.push({a, b});
        }
    }
    cout << "NO" << endl;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    bfs();
    return 0;
    
}

D

每个人眨眼的时刻为 ai 的倍数，确保每个人不眨眼，那么应该是不能被 ai 整除。

答案是质数还是合数？答案为质数。

设 x 为答案，且 x 为合数，那么 ai 不整除 x，令 y 为 x 的质因子，因为 x 为合数，所以一定存在一个小于它的质因子。y < x, 且 ai 不整除 x，那么 ai 也不整除 y。因为 y 小于 x，所以 y 更优。而y是质数，所以答案为质数。

所以可以先将所有的质数筛出来，并去除 ai，剩余的最小的质数即为答案。

#include<iostream>
#include<set>
using namespace std;

const int N = 2e5 + 10,  M = 3e6 + 10;
int a[N];
int primes[N];
bool st[M];
int count;
int get_primes(int n)  // 线性筛
{
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        if(cnt > count) break;  // 只筛 n + 1 个
        for(int j = 0; primes[j] <= n / i; j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;  // pj 一定是i的最小质因子
        }
    }
    return cnt;
}
void slove()
{
    cin >> count;
    for(int i = 0; i < count; i++) cin >> a[i];
    int cnt = get_primes(3e6);  // 1~3e6 的质数有 216816
    set<int> S;
    for(int i = 0; i < cnt; i++) S.insert(primes[i]);  
    
    for(int i = 0; i < count; i++)
        if(S.count(a[i])) S.erase(a[i]); 
    cout << *S.begin() << endl;
}

int main()
{
    int t; cin >> t;
    while(t--) slove();
    return 0;
}

E

一道简单的区间合并问题。每一块牌有一个倒塌范围，当后面的牌位于该范围之内，就能被推倒。计算每一个牌倒塌的范围，按照左端点升序排列，然后区间合并，存储一下每一次能推倒的个数。

#include<iostream>
#include<vector>
#include<algorithm>
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> PII;

int n, m;

void slove()
{
    cin >> n >> m;
    vector<int> h(n + 5, 0);
    vector<int> a(n + 5, 0);
    for(int i = 0; i < n; i++) cin >> h[i];
    for(int i = 0; i < n; i++) cin >> a[i];
    vector<PII> arr(n + 5, {2e9 + 10, 2e9 + 10});
    for(int i = 0; i < n; i++) arr[i] = {a[i], a[i] + h[i]};
    sort(arr.begin(), arr.begin() + n);
    vector<int> b;
    int res = 0;
    for(int i = 0; i < n; i++)
    {
        int j = i + 1;
        int temp = arr[i]._2;
        while(j <= n && arr[j]._1 <= temp) 
        {
            temp = max(temp, arr[j]._2);
            j++;
        }
        
        b.push_back(j - i);
        i = j - 1;
    }
    sort(b.begin(), b.end(), greater<int>());
    for(int i = 0; i < min(m, (int)b.size()); i++) res += b[i];
    cout << res << endl;
}

int main()
{
    int t; cin >> t;
    while(t--) slove();
    return 0;
}

F

机器人从起点到终点的距离 n 为必要距离，也就是必须要走的长度。当这个长度大于 t，那么就会提前爆炸，造成伤害为 0。

对于中间的墙壁，需要时机器人在墙壁之间来回移动，从而增加移动时间，增加爆炸伤害，有多种开启和关闭的方案，但是对于每一个大区间墙壁的操作增加的时间，都可以由小区间墙壁操作得到，只不过需要多操作几次。所以可以将所有墙壁在位置升序排列，每两个墙壁之间的区间就是最小区间。

将该区间的长度 * 2 加入容器中，每一次操作墙壁，机器人会多走 区间长度 * 2 的时间。
将操作增加的时间排序去重，然后就可以转化为完全背包问题

为了达到最大的爆炸伤害 t ，那么需要操作墙壁增加的时间 d = t - n。
每一个墙壁区间可以操作无限次。每一次增加的时间为 v。

集合表示 f[i, j]：在前 i 个区间中选，体积（增加的时间）能否恰好为 j。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

void slove()
{
    int n, m, t; cin >> n >> m >> t;
    vector<int> a(m, 0);
    for(int i = 0; i < m; i++) cin >> a[i];
    if(t < n) { cout << 0 << endl; return; }
    sort(a.begin(), a.end());
    
    vector<int> b(m - 1, 0);
    for(int i = 0; i <= m - 2; i++) b[i] = 2 * (a[i + 1] - a[i]);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    
    int d = t - n;
    vector<int> f(d + 1, 0);
    f[0] = 1;
    for(auto& v : b)
        for(int j = v; j <= d; j++)
            f[j] |= f[j - v];
    
    for(int i = d; i >= 0; i--)
        if(f[i]) { cout << i + n << endl; return; }
}

int main()
{
    int t; cin >> t;
    while(t--) slove();
    return 0;
}