ABC378 题解报告

2024/11/4 OI 题解比赛

闲话

这次评分如下：
\(\text{NaN}-199-251-631-1378-1402-2932\)
知道什么意思了吧（

T1

洛谷传送门
 AT传送门

题意

给你四个数 \(a,b,c,d\)，定义一次操作为：从剩下的数中中选出两个相同的数，并删除。问最多这样操作多少次。

思路

因为只有四个数。
我们可以暴力枚举每种情况，所以写起来并不是很麻烦。
这里就不放代码了。

扩展

假如说不止四个数呢？

现在改为 \(n\) 个数，每个数为 \(val_{i}\)
\(1 \le n \le 10^{5}\)
\(1 \le val_{i} \le 10^{18}\)

这样又该怎么做呢？

其实也是很简单的。
我们只需要统计每种数出现的次数，设为 \(cnt_{val_{i}}\)，因为每次只能删除相同的数，所以对于每种数，能贡献的答案就是 \(\left \lfloor \cfrac{cnt_{val_{i}}}{2} \right \rfloor\)。
因为值域很大，可以使用 map 来存储。
时间复杂度 \(O(n \log n)\)

代码

// Problem: A - Pairing
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int a[MAXN],ans;
map<int,int> mp;

signed main(){
    for(int i=1;i<=n;i++) read(a[i]);
    for(int i=1;i<=n;i++) mp[a[i]]++;
    for(int i=1;i<=n;i++){
        ans+=mp[a[i]]/2;
        mp[a[i]]=0;
    }
    cout<<ans;
    return 0;
}

原题中，把 \(n\) 设置为 \(4\) 即可。

T2

洛谷传送门
 AT传送门

题意

给定两个长度为 \(n\) 的数组 \(q\) 和 \(r\)。
有 \(Q\) 次询问，每次询问给出 \(t_{i}\) 和 \(d_{i}\)。
每次询问需要求出最小的自然数 \(val_{i}\)，使得 \(d_{i}+val_{i} \equiv r_{t_{i}} \pmod {q_{t_{i}}}\)。

思路

根据题意，\(val_{i}\) 一定小于 \(q_{t_{i}}\)，因此我们只需要分两种情况讨论即可。（以下的 \(d_{i}\) 和 \(r_{t_{i}}\) 均是模 \(q_{t_{i}}\) 意义下的）

\(d_{i} < r_{t_{i}}\) 时：答案为后者减去前者
否则答案为上面再加上 \(q_{t_{i}}\)

时间复杂度 \(O(Q)\)。

代码

// Problem: B - Garbage Collection
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,Q,r[MAXN],q[MAXN];

signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(q[i],r[i]);
    read(Q);
    for(int i=1;i<=Q;i++){
        int t,d;
        read(t,d);
        int val=d%q[t];
        if(val<=r[t]) cout<<d+(r[t]-val)<<'\n';
        else cout<<d+(r[t]+q[t]-val)<<'\n';
    }
    return 0;
}

T3

洛谷传送门
 AT传送门

题意

给定义一个长度为 \(n\) 的数组 \(a\)。求对于 \(a\) 中的任意一个元素 \(a_{i}\)，找到最大的 \(j < i\)，使得 \(a_{i} = a_{j}\)，若不存在这样的 \(j\)，则为 \(-1\)。

思路

直接顺着题意模拟就行了。

可以像我一样开一个 map 来存，因为值域较大（\(1 \le a_{i} \le 10^{9}\)）。

时间复杂度 \(O(n \log n)\)。

代码

// Problem: C - Repeating
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,val[MAXN];
map<int,int> mp;

signed main(){
    read(n);
    for(int i=1;i<=n;i++) read(val[i]);
    for(int i=1;i<=n;i++){
        if(mp.find(val[i])==mp.end()) cout<<-1;
        else cout<<mp[val[i]];
        cout<<' ';
        mp[val[i]]=i;
    }
    return 0;
}

T4

洛谷传送门
 AT传送门

题意

给定一个长 \(H \times W\) 的网格。网格中有些格子是障碍。现询问，从任意一个非障碍的格子开始，走恰好 \(K\) 步，不走障碍格和已经走过的格子，一共有多少种方案。

\(1 \le H,W \le 10\)
\(1 \le K \le 11\)

思路

如果使用 BFS 算法，暴力去做 \(H \times W\) 次的时间复杂度是 \(O(H^{2}W^{2})\) 的。（准确说应该是 \(HW\) 乘上这个点能在 \(K\) 步之内到达的点的数量）
但是因为可以上下左右走，只要不走重复和障碍即可，BFS 的话并不是很好去统计方案数。（也可能是我太菜了xwx）

注意到数据范围很小。可以使用 回溯算法 计算。
每次到一个点，先把这个点打上标记，然后查看周围四个点哪些点可以继续走。走到 \(K\) 步的时候，将答案增加 \(1\) 即可。
回溯的时候把标记取消了即可。

设一个点的方案数为 \(val_{i,j}\)，则时间时间复杂度至少为（因为会走错误路线）。
\[ O(\sum^{H}_{i=1}\sum^{W}_{j=1}val_{i,j}) \]

不妨跑一下极限数据，即 \(10 \times 10\) 的网格，走 \(11\) 步，并且没有障碍。我这里跑出来 DFS 函数也只会调用不到 \(7\times 10^{6}\) 次，因此时间复杂度是没有问题的。

代码

// Problem: D - Count Simple Paths
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int h,w,k,ans;
char g[MAXN][MAXN];
bool vis[MAXN][MAXN];

struct node{
    int x,y,dis;
};

void dfs(int x,int y,int dis){
    if(dis==k){
        ans++;
        return;
    }
    vis[x][y]=true;
    if(x!=1&&!vis[x-1][y]&&g[x-1][y]=='.') dfs(x-1,y,dis+1);
    if(x!=h&&!vis[x+1][y]&&g[x+1][y]=='.') dfs(x+1,y,dis+1);
    if(y!=1&&!vis[x][y-1]&&g[x][y-1]=='.') dfs(x,y-1,dis+1);
    if(y!=w&&!vis[x][y+1]&&g[x][y+1]=='.') dfs(x,y+1,dis+1);
    vis[x][y]=false;
}

signed main(){
    cin>>h>>w>>k;
    for(int i=1;i<=h;i++) for(int j=1;j<=w;j++) cin>>g[i][j];
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            if(g[i][j]=='#') continue;
            dfs(i,j,0);
        }
    }
    cout<<ans;
    return 0;
}

T5

洛谷传送门
 AT传送门

题意

给一个长为 \(n\) 的数组 \(a\)，求其所有子段和对 \(m\) 取模后的和。

\(1 \le n \le 2 \times 10^{5}\)
\(1 \le m \le 2 \times 10^{5}\)
\(1 \le a_{i} \le 10^{9}\)

思路

因为子段和可以转化为前缀和之差。
所以我们可以先对 \(a\) 数组做前缀和，记作 \(pre\) 数组。

考虑枚举右端点，每次统计所有以右端点结尾的子段的答案和。
先考虑暴力枚举左端点。设当前右端点为 \(r\)，左端点为 \(l\)。
有这么两种情况：

\(pre_{r}-pre_{l-1} \ge 0\)，这种情况直接统计答案即可。
\(pre_{r}-pre_{l-1} < 0\)，这种情况值加上 \(m\) 再统计即可。

时间复杂度 \(O(n^{2})\)，考虑优化。

现在我们实际上将 \(a_{i}\) 的范围变成了 \(0 \le a_{i} < m\)，而上面两种情况，其实就是对值小于等于 \(pre_{r}\) 的数统计一种答案，再对大于的统计另一种答案。
那么我们可以用树状数组来优化这一过程。

具体实现上：
我们可以开两个值域树状数组，一个存储值的和，记作 \(sum\)，一个存储值的个数，记作 \(cnt\)。
对于第一种情况，那就是 \(cnt_{pre_{r}} * pre_{r} - sum_{pre_{r}}\)，第二种情况是类似的，只是加上 \(cnt_{pre_{r}} * m\)。

时间复杂度 \(O(n \log V)\)

代码

// Problem: E - Mod Sigma Problem
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,m,ans,val[MAXN];

int lowbit(int u){
    return u&(-u);
}

struct node{
    int a[MAXN];
    void init(){
        for(int i=1;i<=2e5;i++) a[i]=0;
    }
    void update(int pos,int val){
        while(pos<=2e5){
            a[pos]+=val;
            pos+=lowbit(pos);
        }
    }
    int query(int pos){
        int res=0;
        while(pos){
            res+=a[pos];
            pos-=lowbit(pos);
        }
        return res;
    }
}t,cnt;


signed main(){
    read(n,m);t.init();cnt.init();
    for(int i=1;i<=n;i++) read(val[i]);
    for(int i=1;i<=n;i++) val[i]%=m;
    for(int i=1;i<=n;i++) val[i]=(val[i]+val[i-1])%m;
    t.update(1,1);cnt.update(1,1);
    for(int i=1;i<=n;i++){
        int z=val[i]+1;
        ans+=cnt.query(z)*(z)-t.query(z);
        ans+=(cnt.query(2e5)-cnt.query(z))*(m+z)-(t.query(2e5)-t.query(z));
        t.update(z,z);
        cnt.update(z,1);
    }
    cout<<ans;
    return 0;
}

T6

洛谷传送门
 AT传送门

题意

给定一棵 \(n\) 个点的无根树，从中任选 \(2\) 个点 \(i\) 和 \(j(i<j)\)，连接这两个点后，会构成一个环，若环上所有点的度数均为 \(3\)，那么这个连接方案是合法的，问有多少种合法的方案。（要求连接后的图是简单图）

\(3 \le n \le 2 \times 10^{5}\)

思路

连接树上两个点 \(i\) 和 \(j\) 后，形成的环上的点其实就是原本 \(i\) 到 \(j\) 的简单路径上的点，度数是原本这些点的度数，只有 \(i\) 和 \(j\) 的度数会增加 \(1\)。
因此，本质上求的是有多少条树上的简单路径，使得该路径的两端点度数为 \(2\)，该路径上其他点度数为 \(3\)。
而简单图的限制其实就是不能选相邻两个点，因为这样会造成重边，图就不是简单图了。

那么我们怎么去求这些满足条件的路径个数呢？

我们只需要找出所有极大的连通块，这些连通块内的点度数均为 \(3\)。那么对于每一个极大的连通块，与其相连的点中，任意两两度数为 \(2\) 的点，均可以构成一条路径。

怎么去求得这个答案呢？

可以考虑先将原本的树删掉部分点，只剩下度数为 \(2\) 和 \(3\) 的点。然后再去统计答案。这种方法我没写。

也可以像我一样。记录下每个内部点的度数均为 \(3\) 的极大连通块的编号，再看它周围有多少度数为 \(2\) 的点，统计一下，最后计算答案即可。使用 DFS 即可。具体可以看代码。

时间复杂度 \(O(n)\)

代码

// Problem: F - Add One Edge 2
// Contest: AtCoder - AtCoder Beginner Contest 378
// URL: https://atcoder.jp/contests/abc378/tasks/abc378_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=2e5+10;
const int mod1=1e9+7;
const int mod2=998244353;
const int inf_int=0x7f7f7f7f;
const long long inf_long=0x7f7f7f7f7f7f7f7f;
const double eps=1e-9;
char Buf[1<<23],*P1=Buf,*P2=Buf;
#define getchar() (P1==P2&&(P2=(P1=Buf)+fread(Buf,1,1<<23,stdin),P1==P2)?EOF:*P1++)
template<typename type>
inline void read(type &x){
    x=0;
    bool f=false;
    char ch=getchar();
    while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    if(f) x=-x;
}
template<typename type,typename... args>
inline void read(type &x,args&... y){
    read(x),read(y...);
}

int n,k,ans,cnt,tot[MAXN],belong[MAXN],head[MAXN],d[MAXN];
bool vis[MAXN];
struct node{
    int to,next;
}edge[MAXN<<1];

void build(int u,int v){
    edge[++k].to=v;
    edge[k].next=head[u];
    head[u]=k;
}

void dfs(int u){
    vis[u]=true;
    if(d[u]==3&&belong[u]==0) belong[u]=++cnt;
    //假如u这个点的度数是3，但是目前没有属于任意极大一个连通块，那么说明从它开始是一个极大连通块。
    for(int i=head[u];i;i=edge[i].next){
        int v=edge[i].to;
        if(d[u]==3&&d[v]==2) tot[belong[u]]++;
        //将符合条件的度数为2的点的个数记录下来
        if(vis[v]) continue;
        //注意: 一个度数为3的点的父亲的度数可能为2,这依然是需要统计的。
        //因此应该先统计，再判断是否访问过。
        if(d[v]==3&&d[u]==3) belong[v]=belong[u];
        //将与u相邻的点中度数为3的归到同一极大连通块中。
        dfs(v);
    }
}

signed main(){
    read(n);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        build(u,v);
        build(v,u);
        d[u]++;d[v]++;
    }
    dfs(1);
    for(int i=1;i<=cnt;i++) ans+=tot[i]*(tot[i]-1)/2;
    //统计答案
    cout<<ans;
    return 0;
}

T7

洛谷传送门
 AT传送门

不会捏 xwx
突然难度飙升到 2900，场切人数只有 18 人。
后来尝试看了一下题解，发现一堆不知道的东西，也就没管了xwx。
如果有人会的，欢迎来给我讲解（不是

LOADING

ABC378 题解报告

闲话

T1

题意

思路

扩展

代码

T2

题意

思路

代码

T3

题意

思路

代码

T4

题意

思路

代码

T5

题意

思路

代码

T6

题意

思路

代码

T7