AtCoder ABC237题解

ABC237

对应地址，https://atcoder.jp/contests/abc237/tasks。

A - Not Overflow 链接地址

https://atcoder.jp/contests/abc237/tasks/abc237_a。

题目要求

给定一个整数 X X X，判断 X X X 是否在 int text{int} int 范围内。

简易题解

签到题。
我们可以使用 C++ 的 INT_MAX 和 INT_MIN。如果不知道这两个常数，可以自己定义。

AC代码

#include
using namespace std;
typedef long long LL;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    LL n;
    cin>>n;
    if (n>=INT_MIN && n<=INT_MAX){
        cout<<"Yesn";
    }else{
        cout<<"Non";
    }
    return 0;
}

时间复杂度

O ( 1 ) O(1) O(1)。

空间复杂度

O ( 1 ) O(1) O(1)。

B - Matrix Transposition 链接地址

https://atcoder.jp/contests/abc237/tasks/abc237_b。

题目要求

输出 H × W H times W H×W 矩阵的转秩矩阵。

简单题解

签到题。
本题的难点在于数据太大。根据题目要求
1 ≤ H , W ≤ 1 0 5 1 leq H,W leq 10^5 1≤H,W≤105
W × H ≤ 1 0 5 W times H leq 10^5 W×H≤105
我们没法直接定义出一个二维数组，因为这样定义，我们必然会得到 MLE text{MLE} MLE，本题只能用二维 vector text{vector} vector 来实现。
解决了数据存储问题，代码自然非常简单。

AC代码

#include
using namespace std;
typedef long long LL;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    LL h,w;
    cin>>h>>w;
    vector> a(h,vector(w));
    for (auto &x:a){
        for (auto &y:x){
            cin>>y;
        }
    }
    for (LL i=0; i 
时间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        H
       
       
        ∗
       
       
        W
       
       
        )
       
      
      
       O(H*W)
      
     
    O(H∗W)。 
空间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        H
       
       
        ∗
       
       
        W
       
       
        )
       
      
      
       O(H*W)
      
     
    O(H∗W)。 
C - kasaka 
链接地址 
https://atcoder.jp/contests/abc237/tasks/abc237_c。 
题目要求 
给一个长度为 
    
     
      
       
        n
       
      
      
       n
      
     
    n 的字符串 
    
     
      
       
        s
       
      
      
       s
      
     
    s，判断能否在开头增加若干（包含 
    
     
      
       
        0
       
      
      
       0
      
     
    0）个字符 
    
     
      
       
        a
       
      
      
       a
      
     
    a，使得字符串 
    
     
      
       
        s
       
      
      
       s
      
     
    s 变成回文字符串。 
简单题解 
我们可以使用双指针来解决这个问题。 
AC代码 
#include
using namespace std;
typedef long long LL;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    
    LL n=s.size();
    LL l=0, r=n-1;
    LL tl=0, tr=0;
    //定义第一个a
    while (l=0 && s[r]=='a') {
        r--;
        tr++;
    }
    
    if (tr 
时间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)。 
空间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)。 
D - LR insertion 
链接地址 
https://atcoder.jp/contests/abc237/tasks/abc237_d。 
题目要求 
给一个字符串 
    
     
      
       
        S
       
      
      
       S
      
     
    S，按照要求将数据 
    
     
      
       
        i
       
      
      
       i
      
     
    i 插入到数列 
    
     
      
       
        A
       
      
      
       A
      
     
    A 中。 
简单题解 
数据结构题。可以使用双向队列，也可以使用双指针来解决。
 通过观察输入样例 
    
     
      
       
        2
       
      
      
       2
      
     
    2，我们可以得到如下结论： 
碰到 ‘L’，我们从右边（队尾）插入数据。碰到 ‘R’，我们从左边（队头）插入数据。 
AC代码 
#include 
using namespace std;
typedef long long LL;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    LL n;
    cin>>n;
    string s;
    cin>>s;
#if 1
    vector a(n+1,0);
    LL l=0;
    LL r=n;
    for (LL i=0; i a;
    a.push_back(n);
    for (LL i=n-1; i>=0; i--){
        if (s[i]=='L'){
            a.push_back(i);
        }else{
            a.push_front(i);
        }
    }
#endif
    for (const auto &x:a){
        cout< 
时间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)。 
空间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)。 
E - Skiing 
链接地址 
https://atcoder.jp/contests/abc237/tasks/abc237_e。 
题目要求 
给一个无向图，高桥从顶点 
    
     
      
       
        1
       
      
      
       1
      
     
    1 出发，他能得到的最大快乐。 
简单题解 
图论的基础题，思路参考单源最短路问题。基本步骤如下： 
建边。从起点 
     
      
       
        
         1
        
       
       
        1
       
      
     1 出发，遍历所有边。并更新距离。查找所有距离中的最大值。 
AC代码 
数组版本 
#include
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+10;
const int M=2*N;
LL h[N];//头节点
LL dis[N];//距离
LL vis[N];//可见性控制
LL happy[N];//幸福度
//下面数据结构来描述图
LL e[M];
LL ne[M];
LL idx;

void add(LL u, LL v) {
    //建边 u->v
    e[idx]=v;
    ne[idx]=h[u];
    h[u]=idx;
    idx++;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //初始化
    memset(dis, -0x3f, sizeof dis);
    memset(h, -1, sizeof h);

    LL n,m;//n个顶点，m条边
    cin>>n>>m;
    for (LL i=1; i<=n; i++) {
        cin>>happy[i];
    }
    for (LL i=1; i<=m; i++) {
        LL u,v;
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }

    queue que;
    dis[1]=0;//起点距离为0
    que.push(1);
    while (que.size()) {
        LL x=que.front();
        que.pop();

        vis[x]=false;
        //以x为起点，遍历x的所有边
        for (LL i=h[x]; i!=-1; i=ne[i]) {
            LL y=e[i];//x->y
            LL c=happy[x]-happy[y];//从x->y的幸福度
            if (c<0) {
                c*=2;
            }
            if (dis[y] 
vector版本 
#include
using namespace std;
typedef long long LL;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    LL n,m;
    cin>>n>>m;
    vector> adj(n+1);
    vector dis(n+1, -9e18);//距离
    vector vis(n+1, false);//可见性
    vector happy(n+1);//幸福度
    //读取幸福度
    for (LL i=1; i<=n; i++) {
        cin>>happy[i];
    }
    //读取图
    for (LL i=0; i>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    queue que;
    dis[1]=0;//起点距离为0
    que.push(1);
    while (que.size()) {
        LL x=que.front();
        que.pop();

        vis[x]=false;
        //以x为起点，遍历x的所有边
        for (const auto &y:adj[x]) {
            LL c=happy[x]-happy[y];//从x->y的幸福度
            if (c<0) {
                c*=2;
            }
            if (dis[y] 
P.S.
 数组版本时间为 85ms。vector版本时间为 104ms。 
时间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        m
       
       
        )
       
      
      
       O(m)
      
     
    O(m)。 
空间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        m
       
       
        )
       
      
      
       O(m)
      
     
    O(m)。 
F - |LIS| = 3 
链接地址 
https://atcoder.jp/contests/abc237/tasks/abc237_f。 
题目要求 
给定整数 
    
     
      
       
        n
       
       
        ,
       
       
        m
       
      
      
       n,m
      
     
    n,m，求满足以下所有条件的数列总数。 
长度为 
     
      
       
        
         n
        
       
       
        n
       
      
     n。数字是 
     
      
       
        
         1
        
        
         ∼
        
        
         m
        
       
       
        1 sim m
       
      
     1∼m 构成。
     
      
       
        
         ∣
        
        
         L
        
        
         I
        
        
         S
        
        
         ∣
        
        
         =
        
        
         3
        
       
       
        |LIS|=3
       
      
     ∣LIS∣=3。 
简单题解 
读完题目，就知道是一个动态规划问题。 
AC代码 
#include
using namespace std;
typedef long long LL;
typedef pair PLL;

const LL MOD=998244353;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    LL n,m;
    cin>>n>>m;

    //找出所有位置
    vector> pos;
    for (LL i=0; i<=m; i++) {
        for (LL j=0; j<=m; j++) {
            for (LL k=0; k<=m; k++) {
                if (i>j || (i==j && i!=m)) {
                    continue;
                }
                if (j>k || (j==k && j!=m)) {
                    continue;
                }
                pos.push_back({i,j,k});
            }
        }
    }

    LL dpn = pos.size();
    vector trans;
    for (LL i=0; i dp(dpn, 0);
    dp.back()=1;
    for (LL i=0; i tmp(dpn, 0);
        for (const auto &x:trans) {
            tmp[x.second]=(tmp[x.second]+dp[x.first])%MOD;
        }
        swap(dp, tmp);
    }

    //遍历答案
    LL ans=0;
    for (LL i=0; i 
时间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        
         m
        
        
         3
        
       
       
        )
       
      
      
       O(m^3)
      
     
    O(m3)。 
空间复杂度 

    
     
      
       
        O
       
       
        (
       
       
        n
       
       
        )
       
      
      
       O(n)
      
     
    O(n)。 
G - Range Sort Query 
链接地址 
https://atcoder.jp/contests/abc237/tasks/abc237_g。 
题目要求 
给一个 
    
     
      
       
        N
       
      
      
       N
      
     
    N 个数构成的排列，一个整数 
    
     
      
       
        X
       
      
      
       X
      
     
    X。
 另外 
    
     
      
       
        Q
       
      
      
       Q
      
     
    Q 次查询，一下搞一个升序，一下搞一个降序。
 最终的操作结果是什么。 
简单题解 
使用线段树吧。这么复杂的操作。
 麻烦的是，我特么忘记了线段树的实现。
 哎，杀人诛心啊。太难过了。让我查查过去的代码。

AtCoder ABC237题解

C/C++/C#相关栏目本月热门文章