ABC457

A

问题陈述(DeepL翻译)

给你一个长度为 $N$ 的序列 $A = (A_1, A_2, \cdots , A_N)$ 。
然后，给出一个介于 $1$ 和 $N$ 之间的整数 $X$ 。
输出值 $A_X$ 。

思路：

存储$A$数组，输出$A_X$即可。

Code

int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
cin>>x;
cout<<a[x];

B

问题陈述(DeepL翻译)

给你 $N$ 序列 $A_1, A_2, \ldots, A_N$ 。
序列 $A_i$ 的长度为 $L_i$ 和 $A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i})$ 。
之后，给出整数 $X$ 和 $Y$ 。输出 $A_{X,Y}$ 的值。

• $L_i$ 的总和最多为 $2 \times 10^5$ 。

思路：

与A题一样存储$A$数组，输出$A_{X,Y}$，由于入方式比较怪异，不过限制了总输入量，可以完全存入。
需要开一个二维数组，但是开$N*L_{max}$的大小会超出空间上限，因此采用vector存数据。

Code

cin>>n;
for(int i=1;i<=n;i++)
{
    int x;
    cin>>x;
    a[i].assign(x+2,0);
    for(int j=1;j<=x;j++)
    {
        int tem;
        cin>>tem;
        a[i][j]=tem;
    }
}
cin>>x>>y;
cout<<a[x][y];

C

问题陈述

给定整数 $N$ 和 $K$ 以及 $N$ 个整数序列 $A_1, A_2, \ldots, A_N$ 和一个长度为 $N$ 的整数序列 $C = (C_1, C_2, \ldots, C_N)$ 。整数序列 $A_i$ 的长度为 $L_i$ 和 $A_i = (A_{i,1}, A_{i,2}, \ldots, A_{i,L_i})$ 。可以保证 $\displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i$ 。
用下面的步骤从 $A$ 和 $C$ 构造一个整数序列 $B = (B_1, B_2, \ldots, B_{\sum_{i=1}^N C_iL_i})$ .

• 设 $B$ 是长度为 $0$ 的整数序列。
• 按此顺序对 $i = 1, 2, \ldots, N$ 进行如下操作：
  • 执行 $C_i$ 次：将 $A_i$ 追加到 $B$ 的末尾。

求出 $B_K$ 的值。
部分数据范围

• $\displaystyle \sum_{i=1}^N L_i \le 2 \times 10^5$
• $1 \le C_i \le 10^9$
• $\displaystyle 1 \le K \le \sum_{i=1}^N C_iL_i$

分析：

首先要了解题意，与B题一样给出了一个二维数组$A$，要我们构造出一个数组$B$，构造方式为顺序将$A$的第$i$行复制$C_i$次，输出$B_K$。
考虑数据范围 ，这个K可能很大，最大为多大呢？令所有的$C_i=10^9$，提出$C$后，$K_{max}=10^9*(2*10^5)=2*10^{14}$，必须使用long long存储。

思路：

使用一个$cnt$计数，作为目前$B$的下标，对于每一行$A_i$，如果$cnt+C_i*L_i<K$时，说明答案$B_K$不在这一行，更新$cnt$为$cnt+C_i*L_i$，进入下一行。
当$cnt+C_i*L_i>=K$时,说明答案已经出现。我们要找到第$K$个，令$K=cnt+X$，将$A_i$行复制$C_i$次后的数组中的第X个即为答案，由于是循环数组，令$X=k*L_i+r$，答案即为$A_{i,r}$，注意到当$r=0$时，实际上答案为$A_{i,L_i}$，特殊处理一下即可。

Code

cin>>N>>K;
for(int i=1;i<=N;i++)
{
    int L;
    cin>>L;
    a[i].assign(L+1,0);
    a[i][0]=L;
    for(int j=1;j<=L;j++)
    {
        int tem;
        cin>>tem;
        a[i][j]=tem;
    }
}
for(int i=1;i<=N;i++)
{
    cin>>C[i];
}
int cnt=0;
for(int i=1;i<=N;i++)
{
    if(cnt+a[i][0]*C[i]<K)
    {
        cnt+=a[i][0]*C[i];
        continue;
    }
    else
    {
        int tem=(K-cnt)%a[i][0];
        if(tem==0)tem=a[i][0];
        cout<<a[i][tem];
        break;
    }
}

D

问题陈述

给你一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 和一个整数 $K$ 。
您可以在 $0$ 和 $K$ 之间（包括首尾两次）进行以下运算。

• 选择一个满足 $1 \le i \le N$ 的整数 $i$ ，将 $i$ 加到 $A_i$ 中。

求运算后序列 $\displaystyle \min_{1 \le i \le N} A_i$ 的最大可能值。

分析：

题目要求你进行至多$K$次操作，将$A$数组的第$i$位增加$i$，即令$A_i=A_i+i$，使$A$中的最小值变得最大。

思路：

首先考虑进行$K$次肯定是更优的，如果进行$K-1$次，那就应该对目前$A$的最小值再进行一次操作从而得出更优答案。
显而易见的贪心策略,每次寻找$A$的最小值并且增加$i$，最后输出$A$的最小值。如果采用数组存储，则时间复杂度为$O(N*K)$。如果采用优先队列存储二元组$(A_i,i)$，取出存入K次，时间复杂度为$O(K\log N)$。贪心策略的复杂度显然是无法满足该题的。
对于这种最大化最小值的题目，合格的ACMer应该首先想到二分答案。
考虑其答案是否具有单调性，设$X$，在进行$K$次操作后，满足任意$i$，都有$A_i>=X$，那么$X$为可能的答案。假设真正的答案为$ans$，当$X<ans$时，该条件均成立，而当$X>ans$时，条件不成立。因此可以采用二分答案求解。
check函数写法：
对于一个$X$，我们遍历数组$A$，每次将该$A_i$增大至大于等于$X$，记录消耗的次数，如果所需次数大于$K$，则$X$取大了，我们需要选择更小的$X$。

Code

bool check(int x)
{
    int cnt=K;
    for(int i=1;i<=N;i++)
    {
        int tem=a[i].first;
        if(a[i].first>=x)return 1;
        int q=(x-a[i].first)/a[i].second;
        tem+=q*a[i].second;
        if(tem<x)q++;
        cnt-=q;
        if(cnt<0)return 0;
    }
    return 1;
}

void sol()
{
    cin>>N>>K;
    for(int i=1;i<=N;i++)
    {
        int x;
        cin>>x;
        pair<int,int>tem=make_pair(x,i);
        a[i]=tem;
    }
    sort(a+1,a+N+1);
    int l=a[1].first,r=2e18;
    int ans=l;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid))
        {
            ans=mid;
            l=mid;
        }
        else
        {
            r=mid-1;
        }
    }
    cout<<ans;
}

好了，赛时写到这里就结束了，E题最终没有通过

补题

E

问题陈述

有 $N$ 个单元格排列成一行。从左边 $(1 \le i \le N)$ 起的第 $i$ 个单元格称为单元格 $i$ 。
一共有 $M$ 块布。铺布 $i$ $(1 \le i \le M)$ 覆盖了 $L_i$ 至 $R_i$ 单元格。
回答 $Q$ 个问题。对于 $q$ -th 查询 $(1 \le q \le Q)$ ，给出了整数 $S_q$ 和 $T_q$ ，因此请回答下面的问题。

• 确定是否可能从 $M$ 块布中恰好选择两块布并铺好，从而满足以下条件。
  • $S_q$ 至 $T_q$ 单元格至少有一块布覆盖，其他单元格没有任何布覆盖。

分析：

给了$M$个区间$[L_i,R_i]$，范围为$N$，有$Q$次询问，让你选择2个区间刚好覆盖$[S,T]$。

思路：

对于每一个询问区间$[S,T]$，我们先寻找一个区间$[L_i,R_i]$，记为区间$i$，其中$L_i=S$,否则无法覆盖，输出No。
再考虑第二个区间$[L_j,R_j]$，记为区间$j$：我们要覆盖区间$[S,T]$，则必然有$R_i=T$或$L_i=T$。

• 当$R_i=T$时，那么区间$j$可为$[S,T]$的任意子区间。
• 当$R_j=T$时，需要两个区间覆盖整个$[S,T]$，则要满足$R_i+1<=L_j$。

本题的有很多的细节需要处理，比如需要保证第二个区间和第一个区间不是同一个区间，需要预处理判断是否存在第二个区间包含在$[S,T]$内。理论的时间复杂度为$O(Q)$
Ps：本体的数据比较水，遍历第二个区间也能过，最坏复杂度为$O(Q*N)$。比如我的代码就这么过了。

int N,M,Q;
vector<pair<int,int> >l[maxn],r[maxn];

bool check(int s,int t)
{
    if(l[s].empty()||r[t].empty())return 0;
    auto ans1=lower_bound(l[s].begin(),l[s].end(),make_pair(-t,1ll));
    if(ans1==l[s].end())return 0;
    if(ans1->first==-t)
    {
        for(int i=s;i<=t;i++)
        {
            if(l[i].empty())continue;
            if(l[i].back().first>=-t&&l[i].back().second!=ans1->second)
            {
                return 1;
            }
        }
        return 0;
    }
    else
    {
        auto ans2=lower_bound(r[t].begin(),r[t].end(),make_pair(s,1ll));
        if(ans2==r[t].end())return 0;
        if(ans2->first<=(1-ans1->first))return 1;
        else return 0;
    }
}

void sol()
{
    cin>>N>>M;
    for(int i=1;i<=M;i++)
    {
        int tl,tr;
        cin>>tl>>tr;
        l[tl].push_back(make_pair(-tr,i));
        r[tr].push_back(make_pair(tl,i));
    }
    for(int i=1;i<=N;i++)
    {
        if(l[i].size())
        {
            sort(l[i].begin(),l[i].end());
        }
        if(r[i].size())
        {
            sort(r[i].begin(),r[i].end());
        }
    }
    cin>>Q;
    while(Q--)
    {
        int s,t;
        cin>>s>>t;
        if(check(s,t))
        {
            cout<<"Yes\n";
        }
        else
        {
            cout<<"No\n";
        }
    }
}

G

问题陈述

有 $N$ 个苹果落在一条数线上。苹果 $i$ 在时间 $T_i$ 落在坐标 $X_i$ 处。
你想在数线上放置一些机器人来收集所有的 $N$ 苹果。机器人可以放置在任意坐标上。
每个机器人从时间 $0$ 开始运行，并能以最多 $1$ 的速度沿数字线自由移动。多个机器人可以同时占据同一坐标。当且仅当每个机器人在时间 $T_i$ 时位于坐标 $X_i$ 时，它才能收集苹果 $i$ 。
求收集所有苹果所需的最少机器人数量。

分析：

给定了$N$对数据$T_i$和$X_i$，苹果会在$T_i$时出现在$X_i$处，每个机器人可以以1的速度在一维坐标上运动，问需要多少机器人才能获得所有苹果。

思路：

赛时根据$D$题的启发，而答案确实是单调的，所以是有可能实现的，因此考虑了贪心策略，但是根据正解是最小链覆盖问题，好像真的写不出来吧。。？
假设一个机器人已经接住了第$i$个苹果，想要接第$j$个苹果，且$T_j>T_i$那么需要满足的条件为 $T_j-T_i>=|X_j-X_i|$ ，拆开绝对值并移项后为$T_j-X_j>=T_i-X_i$并且$T_j+X_j>=T_i+X_i$。那么我们定义二元组A($T-X$,$T+X$)，机器人收集了$A_i$的苹果后，想要收集$A_j$苹果的话，就需要满足$A_i<=A_j$。那么这个机器人可以收集最多多少个苹果呢？如果只有一个机器人，这就是一个典型的求$A$的最长-不下降-子序列问题（LIS），而我们要求的是最少多少个机器人，那就变成了$A$的最小链覆盖问题。由Dilworth定理知道最小链覆盖数 = 最长反链。因此本题就是求最长反链长度，也就是求$A$的最长下降子序列。时间复杂度就是LIS的复杂度$O(N\log N)$。

Code

int N;
struct S
{
    int t,x;
}a[maxn];
vector<int>ans;

bool cmp(S x,S y)
{
    if(x.t==y.t)return x.x<y.x;
    return x.t<y.t;
}

void sol()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        int t,x;
        cin>>t>>x;
        a[i].t=t+x;
        a[i].x=t-x;
    }
    sort(a+1,a+1+N,cmp);
    for(int i=1;i<=N;i++)
    {
        int pos=lower_bound(ans.begin(),ans.end(),-a[i].x)-ans.begin();
        if(pos==ans.size())
        {
            ans.push_back(-a[i].x);
        }
        else ans[pos]=-a[i].x;
    }
    cout<<ans.size();
}

感悟

终于写完了！第一次写题解花费了非常长的时间，感觉应该写的过于详细…？可能吧
也是终于体会到了写一篇题解有多么复杂，我目前而言是不愿意用太多术语写题解的，但是这也导致表达思路的话会十分复杂，可能以后就不会再这么写也没什么时间这么写了。
希望我能继续坚持下去，加油！