A.排序查查查(easy)

查找区间第 $k$ 小的元素，由于数据范围为 $10^6$ ，需要使用时间复杂度为 $O(n log n)$ 的算法。可以使用树状数组，权值线段树等方式求解。这里给出线段树的实例。

#include <iostream>

using namespace std;

struct{
    int l,r;
    int v{};
} t[4000008];

void init(int p,int l,int r){
    t[p]={.l=l,.r=r};
    if(l==r){
        return;
    };
    int m=l+r>>1;
    init(p<<1,l,m);
    init(p<<1|1,m+1,r);
};

void fix(int p,int x,int v){
    if(t[p].l==x && t[p].r==x){
        t[p].v+=v;
        return;
    };
    int m=t[p].l+t[p].r>>1;
    if(x>m){
        fix(p<<1|1,x,v);
    }else{
        fix(p<<1,x,v);
    };
    t[p].v=t[p<<1].v+t[p<<1|1].v;
};

int ask(int p,int k){
    if(t[p].l==t[p].r){
        return t[p].r;
    };
    if(k>t[p<<1].v){
        return ask(p<<1|1,k-t[p<<1].v);
    };
    return ask(p<<1,k);
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,x,k;
    cin>>n;
    init(1,1,n);
    while(n--){
        cin>>x>>k;
        fix(1,x,1);
        cout<<ask(1,k)<<'\n';
    };
    return 0;
};

B.排序查查查(hard)

注意题意为每个亮度值 $v\;(1\le v\le M)$ 出现的次数。而不是出现过的 $v$ 。
一些明显的结论：

$X_i\!\le N$ 时，直接输出 $A_i$
$X_i$ 充分大时，会进入一个循环：在每个循环开始时，所有 $v\;(1\le v\le M)$ 出现的次数相同，因此在每次循环中，宿管会依次添加 $1,2,\ldots,M$ ，记所有 $v$ 出现的次数第一次相同的位置为 $X_0$
因为 $v$ 出现的次数不能减少，所以 $X_0=max\{v\,出现的次数\}\times M$
$X_i\!\gt X_0$ 时，输出其在上述循环中的位置，即 $((X_i-X_0-1)\bmod M)+1$

接下来处理 $N\lt X_i\le X_0$ 的情况。
考虑实例： $M=3$ , $A=(1,1,1)$ 完成操作后，最终 $A=(1,1,1,\color{blue}2,\color{blue}3,\color{blue}2,\color{blue}3,\color{blue}2,\color{blue}3,\color{red}1,\color{red}2,\color{red}3,\color{red}1,\color{red}2,\color{red}3,\ldots)$
可以看出，只需求解 $X_i$ 所在的循环，可以使用前缀和存储不同循环的分界 $x_0$ ，然后二分查找。接着使用线段树等方法输出此循环中的第 $((X_i-x_0-1)\bmod 循环中数的个数)+1$ 小的值即可。
注意需要先读入所有 $X_i$ 后升序排序离线处理。

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

using namespace std;

long long int a[500002];
struct{
    int l{},r{};
    int v{};
} t[2000002];

void init(int p,int l,int r){
    t[p].l=l;
    t[p].r=r;
    if(l==r){
        return;
    };
    int m=l+r>>1;
    init(p<<1,l,m);
    init(p<<1|1,m+1,r);
};

void fix(int p,int x,int v){
    if(t[p].l==x && t[p].r==x){
        t[p].v+=v;
        return;
    };
    int m=t[p].l+t[p].r>>1;
    if(x>m){
        fix(p<<1|1,x,v);
    }else{
        fix(p<<1,x,v);
    };
    t[p].v=t[p<<1].v+t[p<<1|1].v;
};

int ask(int p,int k){
    if(t[p].l==t[p].r){
        return t[p].r;
    };
    if(k>t[p<<1].v){
        return ask(p<<1|1,k-t[p<<1].v);
    };
    return ask(p<<1,k);
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    map<int,int> c0{};
    cin>>n>>m;
    init(1,1,m);
    for(int i=1;i<=m;i++){
        c0[i]=0;
    };
    for(int i=1;i<=n;i++){
        cin>>a[i];
        c0[a[i]]++;
    };
    map<int,vector<int>> m0{};
    for(auto [x,y]:c0){
        m0[y].push_back(x);
    };
    vector<int> t0{};
    for(auto [x,_]:m0){
        t0.push_back(x);
    };
    vector<long long int> vs{n};
    long long int tt{};
    for(int i=1;i<t0.size();i++){
        vs.push_back(vs[i-1]+(t0[i]-t0[i-1])*(tt+=m0[t0[i-1]].size()));
    };
    cin>>q;
    long long int x;
    vector<pair<long long int,int>> vr{};
    vector<int> rr(q);
    for(int i=0;i<q;i++){
        cin>>x;
        vr.push_back({x,i});
    };
    sort(vr.begin(),vr.end());
    int idx{};
    for(auto [x,y]:vr){
        if(x<=n){
            rr[y]=a[x];
            continue;
        };
        if(x>vs.back()){
            rr[y]=(x-vs.back()-1)%m+1;
            continue;
        };
        auto pt=upper_bound(vs.begin(),vs.end(),x-1);
        int ptc=pt-vs.begin();
        while(idx<ptc){
            for(int i:m0[t0[idx++]]){
                fix(1,i,1);
            };
        };
        rr[y]=ask(1,(x-*--pt-1)%t[1].v+1);
    };
    for(int i:rr){
        cout<<i<<'\n';
    };
    return 0;
};

C.炸鸡真好吃

将所有区间按左端点升序排序后合并即可。合并时间复杂度为 $O(n)$ 。

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

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,l,r;
    cin>>n;
    vector<pair<int,int>> v(n);
    for(int i=0;i<n;i++){
        cin>>l>>r;
        v[i]={l,r};
    };
    sort(v.begin(),v.end());
    int x{},y=-1,c{};
    for(auto [l,r]:v){
        if(l>y){
            c+=y-x+1;
            x=l;
            y=r;
            continue;
        };
        y=max(r,y);
    };
    cout<<(c+y-x+1);
    return 0;
};

D.数羊

需要计算最小的时间 $t_0\!\ge l$ ，使得在区间 $\left[l,t\right]$ 中PY累计计数达到 $c$ 次及以上。注意对于 $\forall t\ge t_0$ 也符合条件，因此可以使用二分求解。
计算次数时，对于 $b_i\!\ge l$ 的羊，其“咩”的次数为 $\left\lfloor\frac{t-b_i}{a_i}\right\rfloor+1$ 次。
对于 $b_i\!\lt l$ 的羊，需要考虑到 $l$ 可能不是其在 $t\ge l$ 时的第一次“咩”。可以通过将 $b_i$ 修正为在 $t\ge l$ 时的第一次“咩”的时间来处理。
这里给出直接计算求值的实例。也可以使用前缀“咩”的次数计算。

#include <iostream>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    unsigned long long int a[100002]{},b[100002]{},l0,r0,c;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    };
    for(int i=0;i<n;i++){
        cin>>b[i];
    };
    cin>>l0>>r0>>c;
    for(int i=0;i<n;i++){
        if(b[i]>=l0){
            continue;
        };
        // 对b[i]的修正。
        b[i]+=(l0-b[i]+a[i]-1ull)/a[i]*a[i];
    };
    auto l=l0,r=r0+1ull;
    while(l<r){
        auto m=l+r>>1;
        if([&]{
            auto v=0ull;
            for(int i=0;i<n;i++){
                if(m<b[i]){
                    continue;
                };
                v+=(m-b[i])/a[i]+1ull;
                // PY的数据并不强，这里即使没有在过程中检查，也不会溢出。
                if(v>=c){
                    return true;
                };
            };
            return false;
        }()){
            r=m;
        }else{
            l=m+1ull;
        };
    };
    if(r>r0){
        cout<<"-1";
    }else{
        cout<<r;
    };
    return 0;
};

E.记得开longlong

在 $10^9$ 内十进制表示只含 $4$ 和 $7$ 的数字并不多，可以使用DFS等方式预处理所有十进制表示只含 $4$ 和 $7$ 的数字，计算 $val(x)$ 时二分查找大于其的最小数字即可。

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int main(){
    long long int l,r;
    set<long long int> s{};
    cin>>l>>r;
    [f=[&](auto &&f,long long int x){
        if(x>100000000000){
            return;
        };
        s.insert(x);
        f(f,x*10ll+4ll);
        f(f,x*10ll+7ll);
    }]{
        f(f,4ll);
        f(f,7ll);
    }();
    long long int v{};
    for(auto i=l;i<=r;i++){
        auto j=*s.lower_bound(i);
        v+=(min(j,r)-i+1ll)*j;
        i=j;
    };
    cout<<v;
    return 0;
};

F.大创高手

求最少需要划分出多少个时间组，也就是求对于每个时间刻被活跃时间段覆盖次数的最大值，使用差分求解。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string st,fn;
    int a[1000002]{};
    cin>>n;
    while(n--){
        cin>>st>>fn;
        a[stoi(st.substr(0,2))*3600+stoi(st.substr(3,2))*60+stoi(st.substr(6,2))]++;
        a[stoi(fn.substr(0,2))*3600+stoi(fn.substr(3,2))*60+stoi(fn.substr(6,2))+1]--;
    };
    int v=a[0];
    for(int i=1;i<1000000;i++){
        v=max(v,a[i]+=a[i-1]);
    };
    cout<<v;
    return 0;
};

G.牛牛的set

原题名为集合问题，已经有很成熟的题解，见这里。

H.真心话大冒险

签到，注意此题为特殊判题（Special Judge），不要提交样例。

Special Judge（简称：spj，别名：checker）是当一道题有多组解时，用来判断答案合法性的程序．

I.吃饭爽爽爽

使用倍增的方式解题，即二进制优化。定义 $v_{i,j}$ 表示第 $i$ 个窗口的当前持有的餐盘经过 $2^j$ 次传递到达的窗口; $f_{i,j}$ 表示第 $i$ 个窗口的当前持有的餐盘经过 $2^j$ 次传递后加入的食物量。则初始状态 $v_{i,0}=A_i$ ， $f_{i,0}=i$ 。状态转移为 $v_{i,j}=v_{v_{i,j-1},j-1}$ ， $f_{i,j}=f_{v_{i,j-1},j-1}$ 。
注意不要移位过多次。C++20前移位的右操作数大于左操作数的位宽是未定义行为（UB）。

#include <iostream>

using namespace std;

int n,q,t,b,v[200002][40];
long long int f[200002][40];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>v[i][0];
        f[i][0]=i;
    };
    for(int i=1;i<40;i++){
        for(int j=1;j<=n;j++){
            f[j][i]=f[j][i-1]+f[v[j][i-1]][i-1];
            v[j][i]=v[v[j][i-1]][i-1];
        };
    };
    while(q--){
        cin>>t>>b;
        long long int c{};
        for(int i=0;i<32;i++){
            if((t>>i)&1){
                c+=f[b][i];
                b=v[b][i];
            };
        };
        cout<<c<<'\n';
    };
    return 0;
};

J.我想睡懒觉

正解使用队列让元素出队入队模拟循环。也可以使用下标。

正解（队列）by
循环下标

#include<iostream>
#include<queue>
using namespace std;
int main()
{
    int tot, outNum, nowNum = 1;
    queue<int> q;
    cin >> tot >> outNum;                        //读取数据
    for (int i = 1; i <= tot; i++)q.push(i);    //初始化队列
    while (!q.empty())                    //在队列不为空时继续模拟
    {
        if (nowNum == outNum)
        {
            cout << q.front() << " ";    //打印出局的人的编号
            q.pop();                    //出局
            nowNum = 1;                    //初始化现在的数字
        }
        else
        {
            nowNum++;
            q.push(q.front());            //排至队尾
            q.pop();
        }
    }
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,m;
    cin>>n>>m;
    int x=0,y=1;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        v[i]=i+1;
    };
    while(!v.empty()){
        if(y==m){
            cout<<v[x]<<' ';
            v.erase(v.begin()+x);
            if(x>=v.size()){
                x=0;
            };
            y=1;
            continue;
        };
        y++;
        if(++x>=v.size()){
            x=0;
        };
    };
    return 0;
};

K.啦啦操真好

将所有可能的值放入堆中，取出所有与堆顶的差距相等的值输出即可。注意如果 $a_{ij}$ 已经大于 $k$ ，则不能减小，其本身是可能的最接近 $k$ 的值。放入堆中时可以直接定义好行列排序的优先，这样在取出后不必再次排序。如果某个点多次入堆（如下代码所示），则需要在取出后去重。

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    long long int k{},c;
    priority_queue<pair<long long int,pair<int,int>>,vector<pair<long long int,pair<int,int>>>,greater<pair<long long int,pair<int,int>>>> q{};
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>c;
            if(!c){
                continue;
            };
            if(c>=k){
                q.push({c-k,{i,j}});
                continue;
            };
            q.push({k-(k/c*c),{i,j}});
            q.push({(k/c*c)+c-k,{i,j}});
        };
    };
    if(q.empty()){
        cout<<"-1";
        return 0;
    };
    set<pair<int,int>> s{};
    auto v=q.top().first;
    while(!q.empty()){
        auto [t,p]=q.top();
        if(t<=v){
            s.insert(p);
            q.pop();
            continue;
        };
        break;
    };
    for(auto [i,j]:s){
        cout<<i<<' '<<j<<'\n';
    };
    return 0;
};

HPU周赛1 - 20260327题解