AtCoder Beginner Contest 380 A-E

🕗 发布于 2024-11-17 18:11 算法 Codeforces 题解 AtCoder 并查集

今天的封面原图画师DAIKA!! 队友最近老发去d了一下大家都来d
久违的单人场掉分了 D题被硬控一小时但是也学到了全新guess点早知道写EF的话应该反而有不小的概率开出来那么我们话不多说就进入正文吧

AtCoder Beginner Contest 380

A - 123233

题意

给一个长度为6的字符串，满足1个1,2个2，3个3就输出Yes

复盘

最后一个else忘加if甚至wa了一发

代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve()
{
    string s;
    cin>>s;
    int one=0,two=0,three=0;
    for(int i=0;i<s.size();i++)
    {
        if(s[i]=='1')
            one++;
        else if(s[i]=='2')
            two++;
        else if(s[i]=='3')
            three++;
    }
    if(one==1 and two==2 and three==3)
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
}

int main()
{
    int T=1;
    //scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

B - Hurdle Parsing

题意

输出每一段连续的-的个数

代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve()
{
    string s;
    cin>>s;
    vector<int> a;
    int now_cnt=0;
    for(int i=1;i<s.size()-1;i++)
    {
        if(s[i]=='-')
            now_cnt++;
        else
        {
            a.push_back(now_cnt);
            now_cnt=0;
        }
    }
    a.push_back(now_cnt);
    for(auto x:a)
        cout<<x<<" ";
    cout<<endl;
}

int main()
{
    int T=1;
    //scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

C - Move Segment

题意

将第k段连续的1放在紧接着第k-1段连续的1的后面

代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve()
{
    int n,k;
    scanf("%d%d",&n,&k);
    string s;
    cin>>s;
    vector<int> one,zero;
    for(int i=0;i<n;i++)
    {
        if(i==0 or s[i]!=s[i-1])
        {
            if(s[i]=='0')
            {
                zero.push_back(i);
            }
            else
            {
                one.push_back(i);
            }
        }
    }
    int cnt=0;
    if(s[0]=='0')
    {
        int i;
        for(i=one[k-1];i<n and s[i]!='0';i++)
        {
            s[i]='0';
            cnt++;
        }
        for(i=zero[k-1];i<zero[k-1]+cnt;i++)
        {
            s[i]='1';
        }
    }
    else
    {
        int i;
        for(i=one[k-1];i<n and s[i]!='0';i++)
        {
            s[i]='0';
            cnt++;
        }
        for(i=zero[k-2];i<zero[k-2]+cnt;i++)
        {
            s[i]='1';
        }
    }
    cout<<s<<endl;
}

int main()
{
    int T=1;
    //scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

D - Strange Mirroring

题意

对字符串做如下操作无限次

先把原本的字符串S大小写调换得到一个新的字符串T
将S更新为S+T

复盘

赛时写的是一个递归往前推的过程，不知道为什么一直RE，理论上不会的啊

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

//01101001100101101001011001101001

char change(char c)
{
    if(c>='a'&&c<='z')
        return c-'a'+'A';
    else
        return c-'A'+'a';
}

int pre[33]={0,0,1,1,0,
             1,0,0,1,
             1,0,0,1,
             0,1,1,0,
             1,0,0,1,
             0,1,1,0,
             0,1,1,0,
             1,0,0,1,};

map<ll,int> mp;
int zhao(ll x)
{
    if(mp[x]!=0)
        return mp[x];
    if(x<=32 && pre[x]==1)
        return mp[x]=1;
    if(x<=32 && pre[x]==0)
        return mp[x]=-1;
    //找到第一个小于等于x的2的幂
    ll now=1;
    while(now<=x)
        now*=2;
    now/=2;
    ll del=x-now-1;
    if(zhao(now-del)==1)
        return mp[x]=-1;
    else
        return mp[x]=1;
}

int main()
{
    string s;
    cin>>s;
    int len=s.size();
    int n;
    cin>>n;
    vector<ll> a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    vector<char> ans(n);
    for(int i=0;i<n;i++)
    {
        ll now=a[i];
        ll chu=now/len;
        ll yu=now%len;
        if(yu==0)
        {
            chu--;
            yu=len;
        }
        chu++;
        int status=zhao(chu);
        if(status==-1)
            ans[i]=s[yu-1];
        else
            ans[i]=change(s[yu-1]);
    }
    for(auto x:ans)
        cout<<x<<" ";
    cout<<endl;
    return 0;
}

思路

上面的代码虽然不对，但是看最前面的注释01101001100101101001011001101001，发现我要干什么了嘛，假设第一次重复是原始状态也就是0，第一次就是1，第二次是1，第三次是0，以此类推
如果你还没看出来的话，我们用二进制表示这些下标，分别是

跟二进制表示下1的个数有关，这也是我刚学到的全新guess点

代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

char change(char c)
{
    if(c>='a' and c<='z')
        return c-32;
    return c+32;
}

void solve()
{
    string s;
    cin>>s;
    vector<char> ans;
    int q;
    cin>>q;
    int len=s.size();
    while(q--)
    {
        ll t;
        cin>>t;
//        printf("%d\n",cnt);
        ll chu=t/len;
        ll yu=t%len;
        if(yu==0)
        {
            yu=len;
            chu--;
        }
        ll cnt=popcount((unsigned long long)(chu));
        if(cnt%2==0)
        {
            ans.push_back(s[yu-1]);
        }
        else
        {
            ans.push_back(change(s[yu-1]));
        }
    }
    for(auto x:ans)
    {
        cout << x << " ";
    }
}

int main()
{
    int T=1;
    //scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

E - 1D Bucket Tool

题意

一行中有 $N$ 个单元格，编号为 $1$ 至 $N$ 。
在每个 $\leq i < N$ 单元格中， $i$ 和 $i + 1$ 单元格相邻。
最初， $i$ 单元格被涂上了颜色 $i$ 。
给您 $Q$ 个查询。请按顺序处理它们。每个查询属于以下两种类型之一。

1 x c：将以下单元格重涂为颜色 $c$ ：通过重复移动到与当前单元格颜色相同的相邻单元格，从单元格 $x$ 到达的所有可到达单元格。
2 c:打印涂上颜色 $c$ 的单元格数量。

思路

一片方格一旦某一个瞬间变成了同一个颜色，那么后续永远都是同时变色了，我们可以维护一个set存储每片方格的隔断，给每个点都可以二分查找得到这一段，然后再一起修改，改完之后再往左往右更新隔断

代码

#include <bits/stdc++.h>
#define maxOf(a) *max_element(a.begin(),a.end())
#define minOf(a) *min_element(a.begin(),a.end())
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

void solve()
{
    int n,q;
    scanf("%d%d",&n,&q);
    vector<int> ans(n,1);
    set<pair<int,int>> st;
    for(int i=0;i<n;i++)
    {
        st.insert({i,i});
    }
    st.insert({-1,2e9});
    st.insert({n,2e9});
    while(q--)
    {
        int cmd;
        scanf("%d",&cmd);
        if(cmd==1)
        {
            int x,c;
            scanf("%d%d",&x,&c);
            x--;c--;
            auto it=st.lower_bound({x,2e9});
            auto[R,Rc]=*it;
            auto[L,Mc]=*--it;
            auto[_,Lc]=*--it;
            ans[Mc]-=R-L;
            ans[c]+=R-L;
            it++;
            it=st.erase(it);
            if(c==Rc)
                it=st.erase(it);
            if(c!=Lc)
                st.insert({L,c});
        }
        else
        {
            int c;
            scanf("%d",&c);
            c--;
            printf("%d\n",ans[c]);
        }
    }
}

int main()
{
    int T=1;
    //scanf("%d",&T);
    while(T--)
    {
        solve();
    }
    return 0;
}

原文地址：https://blog.csdn.net/swan416/article/details/143824650

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：2023 年 12 月青少年软编等考 C 语言二级真题解析
下一篇：如何在Mysql中生成0-23完整的小时数据

[产品管理-85]：《产品经理从入门到精通》- 创业公司的产品经理
目录一、概述1、创业公司产品经理的角色与定位2、创业公司产品经理的核心能力3、创业公司产品经理的实战技巧4、创业公司产品经理的挑战与应对策略二、创业公司的产品经理与大公司产品经理的比较1、工作环境与资
阅读更多2024-11-18
《TCP/IP网络编程》学习笔记 | Chapter 13：多种 I/O 函数
《TCP/IP网络编程》学习笔记 | Chapter 13：多种 I/O 函数
阅读更多2024-11-18
解决IntelliJ IDEA的Plugins无法访问Marketplace去下载插件
勾选并填入代理URL，可以先做检查连接：
阅读更多2024-11-18
STM32读写内部FLASH
本文是学习野火的指南针开发板过程的学习笔记，可能有误，详细请看B站野火官方配套视频教程（这个教程真的讲的很详细，请给官方三连吧）在STM32芯片内部有一个FLASH存储器，它主要用于存储代码，我们在电
阅读更多2024-11-18
【STM32】基于SPI协议读写SD，详解！
因为项目需要，使用stm32读写sd卡，这一块网上的资料很多，但是比较杂乱。有些是不能跑，有些是代码可以跑，但是相关的注释或者配置方法、流程不够清晰明确，于是花了几天时间，研究了几个成功案例之后，总结
阅读更多2024-11-18
Java基础（9）本地API
哈喽大家好啊，Java基础的学习马上就要告一段落了，今儿分享的是一些Java常用的本地API，让我们开始吧。
阅读更多2024-11-18
Spring gateway 路由配置在数据库
#spring gateway ServerRoute实体类。##spring gateway 查询动态路由mapper。##Spring gateway 动态路由Service。##spring g
阅读更多2024-11-18
i春秋-FUZZ（python模板注入、base64编码命令执行）
i春秋-FUZZ（python模板注入、base64编码命令执行）
阅读更多2024-11-18
Spring 4.3 源码导读
Spring 4 是一个功能强大的 Java 应用程序框架，广泛用于企业级应用开发。理解其核心代码有助于开发者更好地使用和优化 Spring 框架。
阅读更多2024-11-18
【Rabbitmq篇】RabbitMQ⾼级特性----消息确认
介绍RabbitMQ⾼级特性----消息确认
阅读更多2024-11-18