526互联

AtCoder Beginner Contest(abc) 328

发布时间 2023-11-15 12:16:39作者: mostimali



B - 11/11

难度: ⭐

题目大意

在某个世界一年有n个月, 每个月有di天, 问有多少个日期, 该日期和月份组成的数字都是一样的; eg: 11月的1日, 22月的22日;

解题思路

暴力就行;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=2e5+10;
int n,m;
int f[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x;
        if(i<10) y=i;
        else{
            if(i%10==i/10) y=i%10;
            else continue;
        }
        if(x>=y*10+y) m+=2;
        else if(x>=y) m++;
    }
    cout<<m;
    return 0;
}



C - Consecutive

难度: ⭐⭐

题目大意

给定一个字符串和m个询问, 每个询问都是一个区间, 问区间中有多少个连续两个相同字母的情况, "sss"看作2个;

解题思路

用前缀和来做就行, 注意边界问题;

神秘代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N=3e5+10;
int n,m;
int f[N];
signed main(){
    cin>>n>>m;
    string s;
    cin>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        if(s[i]==s[i+1]){
            f[i]=f[i-1]+1;
        }
        else f[i]=f[i-1];
    }
    while(m--){
        int l,r;
        cin>>l>>r;
        cout<<f[r-1]-f[l-1]<<endl;
    }
    return 0;
}



D - Take ABC

难度: ⭐⭐⭐

题目大意

给定一个字符串, 从前往后遍历, 如果遇到连续的"ABC"就可以清除这三个字母, 注意在清除后新生成的也算; 输出操作后的字符串;

解题思路

跟括号匹配一个思想, 我们用一个堆才存放字母, 如果当前字母是'C', 并且堆中前两个是'A'和'B', 那么就可以把他们删掉; 所以只需要判定'C'即可;

神秘代码

#include<bits/stdc++.h>
//#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 5e5 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx;
char f[N];
signed main(){
    string s;
    cin>>s;
    s=' '+s;
    for(int i=1;i<s.size();i++){
        if(s[i]=='C'){
            if(idx>=2&&f[idx-1]=='A'&&f[idx]=='B') idx-=2;
            else f[++idx]='C';
        }
        else f[++idx]=s[i];
    }
    for(int i=1;i<=idx;i++) cout<<f[i];
    return 0;
}



E - Modulo MST

难度: ⭐⭐⭐

题目大意

给定n个点和m条边以及边的权值, 问这个图取模后的最小生成树的边权和是多少;

解题思路

因为本题是问取模后的最小值, 所以不能用之前学过的算法; 因为数据范围很小, 所以可以考虑暴力枚举, 暴力枚举时我们可以借鉴prim的思想, 我们把结点1作为生成树的根节点, 然后我们dfs节点2~n, 对于每个节点, 我们从所有与它相连的节点中挑选一个作为它的父节点; dfs完第n个节点后我们就得检查一下当前得到的生成树是否合法, 需要检查两个点, 一是每个节点都可以到达根节点, 二是没有环; 第一点可以根据dfs中得到的父子关系进行寻找, 第二点只需要在寻找的时候打个标记即可;
在ac后我突然想到以上的过程可以用并查集来优化, 我们只需要把kruskal算法暴力一下, 我们还是从节点1开始dfs, 然后通过并查集把所有节点连到一起, 这样到最后就不需要检查了, 因为并查集会自动避免非法情况, 但是使用并查集会有一个隐藏的坑, 就是关于dfs的回溯问题, 因为大部分并查集的板子会修改在find函数中修改中间节点的父节点来压缩路径, 但是这样回溯时还需要一一修改, 所以我们可以修改为不压缩路径即可;
而且中间还有一个插曲, 我发现在dfs中p[find(u)] = find(i)改成p[u] = find(i)也可以ac, 在模拟后发现我的这种写法是从下往上去建立并查集的链, 所以每次dfs中u都是某条链中最靠上的节点(也就是这条链的祖宗节点), 所以这两种写法是一致的;

神秘代码

//朴素
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 100 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx, k;
int res = 1e17;
int p[N];
bool st[N][N];
int f[N][N];
bool check(){
    for(int i=2;i<=n;i++){
        int x=i;
        map<int,int> mp;
        mp[i]=1;
        while(1){
            if(!p[x]){
                if(x!=1) return false;
                break;
            }
            x=p[x];
            if(mp[x]) return false;
            mp[x]=1;
        }
    }
    return true;
}
void dfs(int u,int sum){
    if(u>n){
        if(check())res=min(res,sum);
        return;
    }
    for(int i=1;i<=n;i++){
        if(st[u][i]){
            p[u]=i;
            dfs(u+1,(sum+f[u][i])%k);
        }
    }
}
signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b] = f[b][a] = c;
        st[a][b] = st[b][a] = true;
    }
    dfs(2,0);
    cout<<res;
    return 0;
}

//并查集
#include<bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(false), cin.tie(0),cout.tie(0)
#define endl '\n'
using namespace std;
const int N = 100 + 10, mod = 998244353;
typedef pair<int, int> PII;
int n, m, idx, k;
int res = 1e17;
int p[N];
bool st[110][110];
int f[110][110];
int find(int u){
    if(p[u] != u) return find(p[u]);
    else return p[u];
}
void dfs(int u,int sum){
    if(u==n){
        res=min(res,sum%k);
        return;
    }
    for(int i=1;i<=n;i++){
        int a=find(u), b=find(i);
        if(st[u][i]&&a!=b){
            p[a]=b;
            dfs(u+1,sum+f[u][i]);
            p[a]=a;
        }
    }
}
signed main() {
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) p[i]=i;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        f[a][b] = f[b][a] = c;
        st[a][b] = st[b][a] = true;
    }
    dfs(1,0);
    cout<<res;
    return 0;
}



F - Good Set Query

难度: ⭐⭐⭐⭐

题目大意

解题思路

需要用到带权并查集...晚上补

神秘代码