小白月赛 Round 126 题解

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

A.小红打舞萌

难度：600

知识点：模拟，字符串

思路：我们只需要先比较数字大小，对于数字相同的判断是否有'+'即可。

参考代码:

#include<bits/stdc++.h>
using namespace std;
int jud(string s,string t){
    int j1=0,j2=0;
    if(s.back()=='+')s.pop_back(),j1=1;
    if(t.back()=='+')t.pop_back(),j2=1;
    if(stoi(s)<stoi(t))return 0;
    if(stoi(s)>stoi(t))return 1;
    return j1>j2;
}
int main(){
    int _;
    cin>>_;
    while(_--){
        string s,t;
        cin>>s>>t;
        if(jud(s,t))cout<<"Yes\n";
        else cout<<"No\n";
    }
    
}
// by qsmcgogo

B.小红写谱

难度：900

知识点：贪心

思路：我们只需要找到“间隔最大的不存在按键的区间长度”即可，答案为 减去这个数。因为我们可以第一个按键放其中一个，最后一个按键放另一个，由于它们之间的空隙中没有任何按键，这样最终答案一定是最小的。

参考代码：

void solve(){
    int n;
    cin >> n;
    vector<int> nums(10);
    for (int i = 1; i <= n; i++) {
        int num;
        cin >> num;
        nums[num - 1] = 1;
    }
    int mx = 0;
    int cnt = 0;
    for (int i = 0; i < 16; i++) {
        if (!nums[i % 8]) cnt++;
        else cnt = 0;
        mx = max(mx, cnt);
    }
    cout << 7 - mx << endl;
}
// by TRfirst

C.小红出勤

难度：1100

知识点：思维

思路：我们只需要找出“必玩”的歌曲中，每首歌游玩次数的最小值，这也就是我们“出勤次数”的最大值（因为我们如果出勤次数大于这个最小值，则会产生矛盾：这首歌至少有一次出勤是没玩到的）。然后我们根据“每次出勤最多游玩歌曲数量”，可以求出“出勤次数”的最小值。最后判断是否矛盾即可（即最小值不能大于最大值）。

参考代码：

void solve(){
    ll n, q, k;
    cin >> n >> q >> k;
    map<string, ll> mp;
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        cin >> mp[s];
        sum += mp[s];
    }
    ll mn = 2e9;
    for (int i = 1; i <= k; i++) {
        string s;
        cin >> s;
        mn = min(mn, mp[s]);
    }
    if (mn * q < sum) cout << -1 << endl;
    else {
        cout << (sum + q - 1) / q << " " << mn << endl;
    }
}
// by TRfirst

D.小红越级（easy）

难度：1300

知识点：差分，前缀和

思路：本题中，我们只需要保证优先选择“不会造成不舒适”的难度即可。那么本质就是：对于每首歌两个难度“不会造成不舒适”的并集，我们对这个并集（可能是一个区间或者两个相离的区间）做一个区间加 ，最后对差分数组求前缀和后即可知道每个位置最多可以选到多少首“不会不舒适”的歌。(由于区间长度很短，std跳过了差分后前缀和的过程)

参考代码：

void solve(){
    int n, q;
    cin >> n >> q;
    vector<int> nums(2e5 + 5);
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        map<int, int> mp;
        for (int i = -1; i <= 1; i++) mp[a + i] = 1, mp[b + i] = 1;
        for (auto [k, v] : mp) nums[k]++;
    }
    while (q--) {
        int k;
        cin >> k;
        cout << n - nums[k] << " ";
    }
    cout << endl;
}
// by TRfirst

E.小红做梦

难度：1600

知识点：枚举，二分/数学

思路：我们可以枚举“操作 ”的次数，然后通过二分或者数学的方式找到“最小的合法操作次数”，并做一个特判即可：也就是判断该次数下是否会使得 的前缀变成不小于 。对于这个特判，我们也枚举最终变成的每个不同长度的“好数”。这样单次询问最终的复杂度不会超过 ，常数非常小。

参考代码：

void solve(){
    ll n, a, b, c;
    cin >> n >> a >> b >> c;
    ll now = n * 10;

    auto work = [&](ll x) -> ll {
        ll fst = 1005, sec = 1011;
        while (1) {
            if (x > sec - 1);
            else if (x >= fst) return 0;
            else {
                ll num = (fst - x + c - 1) / c;
                if (num * c + x <= sec - 1) return num;
            }
            fst *= 10, sec *= 10;
        }
    };

    ll ans = 2e18;
    for (int i = 0; i <= log10(n) + 1; i++) {
        now /= 10;
        ans = min(ans, a * i + work(now) * b);
    }
    cout << ans << endl;
}
// by TRfirst

F.小红开机厅

难度：1700

知识点：解析几何，哈希

思路：首先我们需要计算共有多少合法点。稍微在草稿纸上玩一下就不难发现，对于中间的矩形区域（也就是 ），其曼哈顿距离之和都是相等的，都等于 。 也就是最小的曼哈顿距离之和。那么外部的怎么求呢？也很简单，对于曼哈顿距离之和等于 的点，数量等同于矩形的周长 （即每条边上的整点数量统计求和）。之后曼哈顿距离每增加 ，答案均会增加 。

我们只需要用map预处理出每个距离的点的数量（因为不能建在重复位置），之后即可快速求出答案了。

参考代码：

void solve(){
    int n;
    cin >> n;
    ll x_1, y_1, x_2, y_2;
    cin >> x_1 >> y_1 >> x_2 >> y_2;

    auto dis = [&](ll x, ll y) -> ll {
        return abs(x_1 - x) + abs(x_2 - x) + abs(y_1 - y) + abs(y_2 - y);
    };

    map<ll, int> mp;
    mp[dis(x_1, y_1)] += 2;
    vector<pair<ll, ll>> nums(n + 5);
    for (int i = 1; i <= n; i++) {
        cin >> nums[i].first >> nums[i].second;
        mp[dis(nums[i].first, nums[i].second)]++;
    }
    ll mid = dis(x_1, y_1);
    for (int i = 1; i <= n; i++) {
        ll sum = (abs(x_1 - x_2) + 1) * (abs(y_1 - y_2) + 1);
        ll ds = dis(nums[i].first, nums[i].second);
        if (mid != ds) sum = ((ds - mid) / 2 - 1) * 4 + (mid + 2) * 2;
        cout << sum - mp[ds] << " ";
    }
    cout << endl;
}
// by TRfirst

G.小红越级（hard）

难度：2000

知识点：双指针

思路：本题首先有个比较显然的结论：当前实力若小于等于两个难度的平均数，则优先选择低难度；否则优先选择高难度。

因此我们可以考虑先将所有歌排序（按两难度的平均数或者之和从小到大），然后双指针枚举小红的实力和当前的歌“是否需要切换难度”。当我们发现实力达到了这首歌的平均数时，即切换难度“从 到 ”。这样我们只需要维护“当前实力 左边有多少歌，当前实力 右边有多少歌”，当我们的实力加 的时候，就可以 得出最终“不舒适度”的变化了。需要注意的是，切换难度的时候，以上数据也要根据情况修改维护状态。

参考代码：

#include<bits/stdc++.h>
using namespace std;
pair<int,int>a[202020];
long long c[202020];
int dp[202020];
bool cmp(pair<int,int>a,pair<int,int>b){
    return a.first+a.second<b.first+b.second;
}
int check(int x,int y){
    return max(0,abs(x-y)-1);
}
int main(){
    int _;
    cin>>_;
    while(_--){
        int n,q,i;
        cin>>n>>q;
        long long res=0;
        for(i=1;i<=n;i++)dp[i]=0;
        int zuo=0,you=0;
        for(i=0;i<n;i++){
            cin>>a[i].first>>a[i].second;
            dp[a[i].first]++;
            if(a[i].first>1)res+=a[i].first-1,you++;
        }
        sort(a,a+n,cmp);
        c[0]=res;
        int j=0;
        for(i=1;i<=n;i++){
            res+=zuo-you;
            zuo+=dp[i-1];
            you-=dp[i+1];
            while(j<n&&a[j].first+a[j].second<=2*i){
                dp[a[j].first]--;
                dp[a[j].second]++;
                res+=check(a[j].second,i)-check(a[j].first,i);
                if(a[j].first<=i-1)zuo--;
                if(a[j].second>i+1)you++;
                j++;
            }
            c[i]=res;
        }
        for(i=0;i<q;i++){
            int x;
            cin>>x;
            cout<<c[x]<<" ";
        }
        cout << endl;
    }
}
// by qsmcgogo

头文件(B,C,D,E,F)

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define int long long
typedef long long ll;
typedef unsigned long long ull;
using i128 = __int128_t;
const int N = 0x7fffffff;
const int mod = 998244353;
const int X4[4] = {1, -1, 0, 0}, Y4[4] = {0, 0, 1, -1};
const int X8[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Y8[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int Xh[8] = {1, 2, 2, 1, -1, -2, -2, -1}, Yh[8] = {2, 1, -1, -2, -2, -1, 1, 2};
mt19937 rng(time(nullptr));



void solve(){
    
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _T = 1;
    cin >> _T;
    while (_T--){ 
        solve();
    }
    return 0;
}