ABC-281解题报告

发表于 2022-12-11 分类于解题报告

B. Sandwich Number

题意：给你一个字符串，判断是否满足：首先为一个大写英文字符；然后为 $6$ 位数字，组成 $[100000,999999]$ 之间的数（即不能有前导零）；最后为一个大写英文字符。

对照题意模拟即可。实现上可以通过函数来简化重复步骤。

bool f(char c){
    return 'A'<=c&&c<='Z';
}
bool g(char c){
    return '0'<=c&&c<='9';
}
 
int main(){
    string s;
    cin>>s;

    bool ok=s.size()==8;
    if(ok){
        ok&=f(s[0]);
        ok&=f(s[7]);
        for(int i=1;i<=6;i++)ok&=g(s[i]);
        ok&=s[1]!='0';
    }
    if(ok)puts("Yes");
    else puts("No");
}

还有一个优化代码的方法为利用内置函数。C++ 内置了一些常用的判断字符的函数：

判断是否为数字：isdigit(c)
判断是否为大写字母：isupper(c)
判断是否为小写字母：islower(c)

C. Circular Playlist

题意：有一个 $n$ 首歌的歌单，第 $i$ 首歌的时长为 $a_i$ ，全部播放完后会从第一首重新播放。问第 $T$ 秒时播放到哪一首歌的哪个位置。保证第 $T$ 秒不是两首歌切换的时间。

首先处理完循环多少次完整的歌单。循环的部分对答案不会有影响，所以计算出这 $n$ 首歌的总时长 $s$ ，将 $T$ 对 $s$ 取模即可忽略掉循环的部分。对于剩下的部分，可以遍历每一首歌，累加当前时长，在加上当前歌后超过 $T$ 时输出；也可以遍历时减小剩余时长 $T$ ，当剩余时长小于当前歌时输出。

做法一

By Rubikun

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll N,T;cin>>N>>T;
    ll sum=0;
    vector<ll> A(N);
    for(int i=0;i<N;i++){
        cin>>A[i];
        sum+=A[i];
    }
    T%=sum;
    ll S=0;
    for(int i=0;i<N;i++){
        if(S+A[i]>T){
            cout<<i+1<<" "<<T-S<<"\n";
            return 0;
        }else{
            S+=A[i];
        }
    }
}

做法二

By SSRS

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  long long T;
  cin >> N >> T;
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  long long S = 0;
  for (int i = 0; i < N; i++){
    S += A[i];
  }
  T %= S;
  for (int i = 0; i < N; i++){
    if (T < A[i]){
      cout << i + 1 << ' ' << T << endl;
      break;
    }
    T -= A[i];
  }
}

E. Least Elements

题意：有一个长度为 $n$ 数组 $a$ ，有一个长度为 $m$ 的窗口，初始框住 $[1,m]$ ，每次右移一格直到 $[n-m+1,n]$ 。你需要对于每个位置回答，窗口内前 $k$ 小的数之和。

这个题显然可以用数状数组、权值线段树或主席树来维护，每次移动时把出去的删掉，进来的加上即可。但实际上只用 STL 也可以完成本题。

考虑维护两个 multiset（可重集） $L,R$ ， $L$ 表示当前窗口内前 $k$ 小的数， $R$ 表示当前窗口的其他数。

每次移动的时候，先判断删除的那个数在不在 $R$ 内：如果在则直接把 $R$ 中的删掉（因为删掉 $R$ 里的元素不会影响答案）；如果不在 $R$ 内而在 $L$ 内，将 $L$ 中的删掉并将 $R$ 中最小的元素扔到 $L$ 里。

然后考虑新加入的数：如果比 $L$ 的最大值要小，则把它扔进 $L$ 内，替换掉 $L$ 的最大值（旧的最大值扔到 $R$ 里）；否则直接扔到 $R$ 里。

每次在 $L$ 加入/删除元素时都更新当前 $L$ 的和即可。

By kotatsugame

#include<iostream>
#include<set>
using namespace std;
int N,M,K;
int A[2<<17];
int main()
{
    cin>>N>>M>>K;
    for(int i=0;i<N;i++)cin>>A[i];
    set<pair<int,int> >L,R;
    long Rs=0;
    for(int i=0;i<M-1;i++)
    {
        L.insert(make_pair(-A[i],i));
        auto it=L.end();it--;
        R.insert(*it);
        Rs+=it->first;
        L.erase(it);
        if(R.size()>K)
        {
            auto jt=R.begin();
            L.insert(*jt);
            Rs-=jt->first;
            R.erase(jt);
        }
    }
    for(int i=M-1;i<N;i++)
    {
        L.insert(make_pair(-A[i],i));
        auto it=L.end();it--;
        R.insert(*it);
        Rs+=it->first;
        L.erase(it);
        if(R.size()>K)
        {
            auto jt=R.begin();
            L.insert(*jt);
            Rs-=jt->first;
            R.erase(jt);
        }
        cout<<-Rs<<"\n";
        pair<int,int>d=make_pair(-A[i-(M-1)],i-(M-1));
        if(L.find(d)!=L.end())L.erase(L.find(d));
        else
        {
            Rs-=d.first;
            R.erase(R.find(d));
        }
    }
}

一个错解 By Jack2022

const int N=500005;
const int MAX=(1<<31)-1;
multiset<int> s,t;
int n,m,k;
int a[N];
int ans;
signed main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>n>>m>>k;
    C_in(a,n);
    for(int i=0;i<m;i++)
    {
        t.insert(a[i]);
    }
    for(int i=0;i<k;i++)
    {
        s.insert(*t.begin());
        ans+=*t.begin();
        t.erase(t.begin());
    }
    cout<<ans<<" ";
    for(int i=1;i<=n-m;i++)
    {
        bool cc=false;
        if(a[i-1]>=*t.begin())
        {
            t.erase(t.find(a[i-1]));
        }
        else
        {
            s.erase(s.find(a[i-1]));
            ans-=a[i-1];
            cc=true;
        }
        int now=a[i+m-1];
        t.insert(now);
        if(cc)
        {
            s.insert(*t.begin());
            ans+=*t.begin();
            t.erase(t.begin());
        }
        else
        {
            if(*t.begin()<*s.rbegin())
            {
                ans-=*s.rbegin();
                ans+=*t.begin();
                msit j=s.end();
                j--;
                t.insert(*j);
                s.erase(j);
                msit i=t.begin();
                t.erase(i);
                s.insert(*i);
            }
        }
        cout<<ans<<" ";
    }
    return 0;
}

这份代码的思路是完全没有问题的，他的错误在于，如果 $m=k$ ，则集合 $t$ 在任何时刻都没有元素，而他的代码有询问 t.begin() 的过程，在没有元素时就会出现一些问题。一组 hack 数据：

1 2	6 3 3 3 1 4 1 5 9

将主 for 循环里第一个 if(a[i-1]>=*t.begin()) 改为 if(!t.empty()&&a[i-1]>=*t.begin()) 即可。

除了使用 set，同样也可以使用 priority_queue 来维护。这个题的操作只会在 $L$ 的最大值和 $R$ 的最小值之间提取，所以 $L$ 向较大的一端开口（大根堆）， $R$ 向较小的一端开口（小根堆）即可。

By guud

#include <bits/stdc++.h>

using namespace std;
using PII = pair<int, int>;
const long long inf = 1e14;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    #ifdef LOCAL
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif

    int n, m, k;
    cin >> n >> m >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    priority_queue<PII, vector<PII>, greater<PII>> big;
    priority_queue<PII> small;
    long long ans = 0;
    for (int i = 0; i < m; i++) {
        if (i < k) {
            small.push({a[i], i});
            ans += a[i];
        } else {
            if (small.top().first <= a[i]) {
                big.push({a[i], i});
            } else {
                auto u = small.top();
                small.pop();
                big.push(u);
                ans -= u.first;
                small.push({a[i], i});
                ans += a[i];
            }
        }
    }

    vector<bool> vis(n);
    cout << ans << " ";
    for (int i = m; i < n; i++) {
        while (!big.empty() and vis[big.top().second]) big.pop();
        while (!small.empty() and vis[small.top().second]) small.pop();
        int t = i - m;
        // cout << i << endl;
        if (a[t] <= small.top().first) {
            ans -= a[t];
            if (!big.empty() and big.top().first < a[i]) {
                auto u = big.top();
                big.pop();
                small.push(u);
                ans += u.first;
                big.push({a[i], i});
            } else {
                small.push({a[i], i});
                ans += a[i];
            }
        } else {
            auto t = small.top();
            if (t.first <= a[i]) {
                big.push({a[i], i});
            } else {
                small.pop();
                big.push(t);
                ans -= t.first;
                small.push({a[i], i});
                ans += a[i];
            }
        }
        vis[t] = true;
        cout << ans << " ";
    }
    cout << '\n';
    return 0;
}