AC修炼计划（AtCoder Beginner Contest 328）

news/2024/7/20 23:03:37 标签: 深度优先, 算法, 动态规划, c++

传送门：

Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328） - AtCoder

本章对于自己的提升：dfs的运用，带权并查集，以及状压dp。

A，B，C题比较简单，直接附上代码。

A - Not Too Hard

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int b[1000005];
int n,x;
void icealsoheat(){
    cin>>n>>x;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        ans+=b[i]<=x?b[i]:0ll;
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

B - 11/11

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int b[1000005];
int n,x;
void icealsoheat(){
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++){
        // if(b[i]>=i)ans++;
        int x=i%10;
        int an=i;
        bool f=0;
        while(an){
            if(an%10!=x){
                f=1;
                break;
            }
            an/=10;
        }
        if(f)continue;
        int bn=x;
        while(b[i]>=bn){
            ans++;
            bn=bn*10+x;
        }
    }
    cout<<ans;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

C - Consecutive

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int b[1000005];
int n,q;
string s;
int sum[1000005];
void icealsoheat(){
    cin>>n>>q;
    cin>>s;
    s=' '+s;
    for(int i=2;i<=n;i++){
        if(s[i]==s[i-1]){
            sum[i]=sum[i-1]+1;
        }
        else sum[i]=sum[i-1];
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        int ans=sum[r]-sum[l-1];
        if(s[l]>1&&s[l]==s[l-1]){
            ans--;
        }
        cout<<ans<<"\n";
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

D - Take ABC

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
// int b[1000005];
int n,q;
string s;
int sum[1000005];
void icealsoheat(){
    string s;
    cin>>s;
    vector<char>b;
    for(auto i:s){
        if(i!='C'||b.size()<2){
            b.push_back(i);
        }
        else{
            int id=b.size();
            if(b[id-1]=='B'&&b[id-2]=='A'){
                b.pop_back();
                b.pop_back();
            }
            else{
                b.push_back(i);
            }
        }


    }
    for(auto i:b){
        cout<<i;
    }

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

E - Modulo MST

这题要求是找边权经行取模后的（注意是取模后的数值）最小的最小生成树。此处的边的数量就未必是n-1了。我们需要用dfs把所有可能都跑一遍，并找到能把所有点能链接的最小生成树的最小的边权。（我没有想到会用这么暴力的写法，时间复杂度计算有待提高，赛时没有做出来）。在这里偷了jiangly的并查集板子。并查集用于查询到底有多少个点被取到了。应为他把并查集用了一个结构体进行递归，所以使得他的并查集可以迭代，很巧妙。

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;

int u[1000005];
int v[1000005];
int w[1000005];
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        // for(int i=1;i<=n;i++)f[i]=i;
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};
int n,m,k;
void icealsoheat(){
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
    }
    int ans=k;
    auto dfs=[&](auto self,int i,DSU dsu,int s)->void{
        if(i==m+1){
            bool f=0;
            for(int i=1;i<=n;i++){
                if(!dsu.same(i,1)){
                    f=1;
                    break;
                }
            }
            if(!f)ans=min(ans,s%k);
            return;
        }
        self(self,i+1,dsu,s);
        if(!dsu.same(u[i],v[i])){
            dsu.merge(u[i],v[i]);
            self(self,i+1,dsu,s+w[i]);
        }
    };
    dfs(dfs,1,DSU(n+5),0);
    cout<<ans;


    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

F - Good Set Query

这题是一道很典型的带权并查集的板子题，但我当时带权并查集忘却了，这里让我查漏补缺了。

代码如下：

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int n,q;
int w[1000005];
int pre[1000005];
// int a[1000005];
int find(int x){
    if(x==pre[x])return x;
    int t=pre[x];
    pre[x]=find(pre[x]);
    w[x]+=w[t];
    // pre[x]=find(pre[x]);
    return pre[x];
    
}

void icealsoheat(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)pre[i]=i;
    for(int i=1;i<=q;i++){
        int a,b,d;
        cin>>a>>b>>d;
        int xx=find(a);
        int yy=find(b);
        if(xx==yy&&w[a]-w[b]==d)cout<<i<<" ";
        else if(xx!=yy){
            pre[yy]=xx;
            w[yy]+=w[a]-d-w[b];
            cout<<i<<" ";
        }
    }

    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

G - Cut and Reorder

这题题目没看懂啥意思。

这里我看了大佬的题解Toyota Programming Contest 2023#7（AtCoder Beginner Contest 328） - 知乎 (zhihu.com)

这个数据一看到n<=22，就该第一时间想到，这很状压，但我思维太过浅薄，没有想到如何迭代状态。看了佬的题解才明白。

代码如下：

// #pragma GCC optimize(3)  //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PII;
const int mod=998244353;
int n,c;
int a[10005];
int b[10005];
void icealsoheat(){
    cin>>n>>c;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    vector<int>dp((1<<n)+5,0x3f3f3f3f3f3f3f3f);
    dp[0]=-c;
    for(int i=0;i<(1<<n);i++){
        int cnt=__builtin_popcount(i);
        for(int j=0;j<n;j++){
            if(!(i>>j&1)){
                int k=j;
                int sum=0;
                int ns=i;
                int id=0;
                while(k<n&&!(i>>k&1)&&cnt+id<n){
                    ns|=(1ll<<k);
                    sum+=abs(a[k]-b[cnt+id]);
                    id++;
                    k++;
                    // ns|=(1ll<<k);
                    dp[ns]=min(dp[ns],dp[i]+sum+c);
                }
            }
        }
    }
    cout<<dp[(1<<n)-1];
    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}


http://www.niftyadmin.cn/n/5198259.html

相关文章

Java基础-----String类

Java基础-----String类

文章目录 1. String字符串类1.1 简介1.2 创建String1.3 构造方法1.4 连接操作符1.5 常用方法1.6 案列1.6.1 检验邮箱地址是否正确1.6.2 比较验证码 1. String字符串类 1.1 简介 String不是基本数据类型&#xff0c;是一种引用类型String代表一组不可改变的Unicode字符序列。S…
阅读更多...
微信搜一搜有什么意想不到的功能？

微信搜一搜有什么意想不到的功能？

其实我们每天都在用的微信&#xff0c;还有很多你意想不到的功能&#xff0c;像是一些每天我们都会看到&#xff0c;但是却不常使用的功能。 “搜一搜”这个功能&#xff0c;其实它已经上线很久了&#xff0c;它不仅是一个搜索入口&#xff0c;还是非常强大的聚合性服务。 生僻…
阅读更多...
实现CAS自旋锁

实现CAS自旋锁

CAS 在高并发场景&#xff0c;可以使用加锁、CAS来保证原子性&#xff0c;但是加锁是很重量级的操作&#xff0c;CAS类似于乐观锁CAS &#xff08; Compare and swap &#xff09;比较并交换&#xff0c;是实现并发算法时常用到的技术&#xff0c;包含三个操作数&#xff1a;内…
阅读更多...
【人工智能时代的刑法体系与责任主体概述】

【人工智能时代的刑法体系与责任主体概述】

第一节&#xff1a;引言 随着科技的快速发展&#xff0c;人工智能 (Artificial Intelligence, AI) 正日益成为我们生活中不可或缺的一部分。从自动驾驶汽车到语音助手&#xff0c;从智能家居到金融机器人&#xff0c;AI 的广泛应用正不断改变着我们的生活方式和社会结构。然而…
阅读更多...
采购组件修改申请办理流程

采购组件修改申请办理流程

现有采购流程1 #mermaid-svg-qAesAhfW2IQBcef8 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qAesAhfW2IQBcef8 .error-icon{fill:#552222;}#mermaid-svg-qAesAhfW2IQBcef8 .error-text{fill:#552222;stroke:#5522…
阅读更多...
《明解C语言》第三版 （入门篇） 第六章练习答案

《明解C语言》第三版 （入门篇） 第六章练习答案

个别练习的解题方法很多本答案不是唯一答案 练习6-1 int main()//6-1(1) {int a, b, c, min;scanf("%d%d", &a, &b);min a<b?a:b;printf("最小值 %d", min);return 0; }方法二 int add(int x,int y)//6-1(2) {int min0;if(x>y) min y;…
阅读更多...
Python文本段落翻译

Python文本段落翻译

Python文本段落翻译 1、Translate库2、基本使用 1、Translate库 translate非标准库是Python中可以实现对多种语言进行互相翻译的库&#xff0c;translate可以将原始文本或段落翻译成我们需要的目标语言 translate支持多种语言&#xff0c;常见的例如&#xff1a; zh/zh-CN&…
阅读更多...
移动云电脑：摆脱传统桎梏，助推企业数字化转型

移动云电脑：摆脱传统桎梏，助推企业数字化转型

如今&#xff0c;随着“云”在企业数字化转型战略中的作用日益凸显&#xff0c;上云是企业数字化转型第一步&#xff0c;已成为业界共识。尤其对于中小企业而言&#xff0c;数字化转型更是一种生存之道。 实际上&#xff0c;企业数字化转型面临很多传统桎梏。例如&#xff0c;数…
阅读更多...
最新文章

Copyright @ 2022~2023