AC修炼计划（AtCoder Beginner Contest 334）A~G

传送门：UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334) - AtCoder

A题是最最基础的语法题就不再讲解。

B - Christmas Trees

该题虽然分低，但我觉得还是很不错的。

给你 l 和 r ，设满足题意的数字是x则让你找在区间中有多少个x是x%k==a%k。我们要算出左右满足题意的两端点值，而后可以求出。左端点向上取整，右端点向下取整。

分别是l+=((x-l%m)%m+m)%m    以及r-=((r%m-x)%m+m)%m。

最后可以算出答案。

// #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;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,m;

void icealsoheat(){
    int a,l,r;
    cin>>a>>m>>l>>r;
    int x=a%m;

    l+=((x-l%m)%m+m)%m;
    r-=((r%m-x)%m+m)%m;
    if(l>r)cout<<"0";
    else cout<<(r-l)/m+1;


    

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

C - Socks 2

这题比较经典。看到绝对值我们首先就要想到拆绝对值，则有数量相等的正负数。2*n-k为偶数的话，我们就直接计算就可以了。若为奇数，我们可以提前预处理出前缀和而后遍历每一个数去除来求最小值。注意去除当前数，后面的后缀和应该变成相反数，才是最终答案。

// #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;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,m;
int k;
void icealsoheat(){
    cin>>n>>k;
    vector<int>a(n+5,2);
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        a[x]=1;
    }
    if((2*n-k)&1){
        int id=0;
        vector<int>sum(2*n+5,0);
        for(int i=1;i<=n;i++){
            id++;
            if(id&1){
                sum[id]=sum[id-1]-i;
            }
            else sum[id]=sum[id-1]+i;
            if(a[i]==2){
                id++;
                if(id&1)sum[id]=sum[id-1]-i;
                else sum[id]=sum[id-1]+i;
            }
        }
        int ans=MX;
        for(int i=1;i<=2*n-k;i++){
            ans=min(ans,sum[i-1]-(sum[2*n-k]-sum[i]));
        }
        cout<<ans;
    }
    else{
        int id=0;
        int ans=0;
        for(int i=1;i<=n;i++){
            id++;
            if(id&1)ans-=i;
            else ans+=i;
            if(a[i]==2){
                id++;
                if(id&1)ans-=i;
                else ans+=i;
            }
        }
        cout<<ans;
    }
    

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

D - Reindeer and Sleigh

前缀和加二分操作，太经典了就不多说了。

// #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;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,q;
int k;
int a[500005];
int sum[500005];
void icealsoheat(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        if(x<sum[1]){
            cout<<"0\n";
            continue;
        }
        int l,r,mid;
        l=1,r=n;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(sum[mid]<=x)l=mid;
            else r=mid-1;
        }
        cout<<l<<"\n";
    }
    

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

E - Christmas Color Grid 1

通过dfs求解出联通量的个数，而后暴力枚举每一个红色，情况还是挺好特判的，要用到逆元。

// #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;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,m;
int k;
string s[500005];
int kuai(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans%mod;
}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
void icealsoheat(){
    cin>>n>>m;
    vector<vector<int>>c(n+5,vector<int>(m+5,0));
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]='-'+s[i];
    }
    int an=0;
    auto dfs=[&](auto self,int x,int y)->void{
        for(int i=0;i<4;i++){
            int xx=dx[i]+x;
            int yy=dy[i]+y;
            if(xx>0&&xx<=n&&yy>0&&yy<=m&&c[xx][yy]==0&&s[xx][yy]=='#'){
                c[xx][yy]=an;
                self(self,xx,yy);
            }
        }
    };
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='#'&&!c[i][j]){
                an++;
                c[i][j]=an;
                dfs(dfs,i,j);
            }
        }
    }
    int sum=0;
    int cnt=0;
    // cout<<an<<"***\n";
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s[i][j]=='.'){
                sum++;
                set<int>q;
                for(int o=0;o<4;o++){
                    int xx=dx[o]+i;
                    int yy=dy[o]+j;
                    if(xx>0&&xx<=n&&yy>0&&yy<=m&&s[xx][yy]=='#'){
                        q.insert(c[xx][yy]);
                    }
                }
                if(!q.size())cnt+=an+1;
                else cnt+=an-q.size()+1;
                // cout<<cnt<<"---\n";
            }
        }
    }
    // cout<<cnt<<"+++"<<sum<<"+++\n";
    cout<<cnt%mod*kuai(sum,mod-2)%mod;

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

F - Christmas Present 2

这题感觉还是挺好的。首先想到是dp的思想，但暴力dp是O(n*n)的复杂度，显然，会t。而后我们开始想他的优化。我们想要算得的就是贡献值也就是从当前点回到家所产生的距离值和正常到下一个点儿的差（三角形任意两边之和大于第三边，所以正常情况是比回家的情况小的）。这个差值越小越好，同时我们还要保证两个回家的点儿之间差不超过k。我们用dp来迭代这个差值。优化dp的方式我们可以用单调队列的方式进行求解，以此来满足条件，并尽可能的使改变的值变少。

代码如下：

// #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;
const int MX=0x3f3f3f3f3f3f3f3f;
int n,k;
double s[500005];
double sum[500005];
double xx[500005];
double yy[500005];
double suan(double x1,double y1,double x2,double y2){
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void icealsoheat(){
    cin>>n>>k;
    double xe,ye;
    cin>>xe>>ye;
    for(int i=1;i<=n;i++)cin>>xx[i]>>yy[i],s[i]=suan(xx[i],yy[i],xe,ye);
    for(int i=2;i<=n;i++)sum[i]=sum[i-1]+suan(xx[i],yy[i],xx[i-1],yy[i-1]);
    vector<double>dp(n+5,0);
    int l=1,r=0;
    vector<int>id(n+5,0);
    #define d(i) dp[i]-sum[i+1]+s[i+1]

    for(int i=1;i<=n;i++){
        while(l<=r&&d(id[r])>d(i-1))r--;
        id[++r]=i-1;
        while(l<=r&&id[l]<i-k)l++;
        dp[i]=d(id[l])+s[i]+sum[i];
    }
    printf("%.10lf",dp[n]);

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

G - Christmas Color Grid 2

写的时候忘记了，其实也是很经典的双端强连通分量问题。也是很板子，双端强连通分量可以解决无向图中去掉一个点求剩下强两桶分量的问题。详情可以看AcWing 1183. 电力 - AcWing

代码如下：

#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;
const int MX=0x3f3f3f3f3f3f3f3f; 
int n,m;
// vector<string>s(500005);
string s[500005];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
int kuai(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans%mod;
}
int co[1000005];
int dfn[1000005];
int low[1000005];
int hh[1000005];
int num;
int top;
int col;
void icealsoheat(){
    int ans=0;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s[i];
        ans+=count(s[i].begin(),s[i].end(),'#');
    }
    int an=0;
    vector<vector<int>>c(n+5,vector<int>(m+5,0));
    vector<vector<int>>ve(1000005);
    auto dfs=[&](auto self,int x,int y)->void{

        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&s[xx][yy]=='#'&&c[xx][yy]==0){
                c[xx][yy]=an;
                // ve[x*m+y].push_back(xx*m+yy);
                // ve[xx*m+yy].push_back(x*m+y);
                self(self,xx,yy);
            }
        }
    };
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'&&c[i][j]==0){
                c[i][j]=++an;
                dfs(dfs,i,j);
            }
            if (s[i][j] == '#')
                for (int k = 0; k < 4; k ++ ){}
                    int av = i + dx[k], bv = j + dy[k];
                    if (av<0||av>=n||bv<0||bv>=m) continue;
                    if (s[av][bv]!='#') continue;
                    ve[i*m+j].push_back(av*m+bv);
                    ve[av*m+bv].push_back(i*m+j);
                }
        }
    }

    auto tarjan=[&](auto self,int u,int fa)->void{
        dfn[u]=low[u]=++num;
        int cnt=0;
        for(auto v:ve[u]){
            if(dfn[v]==0){
                self(self,v,u);
                low[u]=min(low[u],low[v]);
                if(dfn[u]<=low[v]){
                    cnt++;
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
        if(fa!=-1)cnt++;
        hh[u]=cnt;
    };

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'&&!dfn[i*m+j]){
                tarjan(tarjan,i*m+j,-1);
            }
        }
    }

    // cout<<ans<<"---\n";
    int chu=kuai(ans,mod-2)%mod;
    ans=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i][j]=='#'){
                ans+=an-1+hh[i*m+j];
                // cout<<an-1+hh[i*m+j]<<"++++\n";
                ans%=mod;
            }
        }
    }
    cout<<ans*chu%mod;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    int _yq;
    _yq=1;
    // cin>>_yq;
    while(_yq--){
        icealsoheat();
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/319648.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

深入解析JavaScript中构造函数和new操作符

深入解析JavaScript中构造函数和new操作符

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;《爱蹦跶的大A阿》 &#x1f525;当前正在更新专栏&#xff1a;《VUE》 、《JavaScript保姆级教程》、《krpano》 ​ ​ 目录 ✨ 前言 ✨ 正文 第一节:构造函数 第二节:new操作符 第三节:实例与原型 ✨ 结语 ✨ 前言…
阅读更多...
ssm基于java的自助医疗服务系统的设计与实现+jsp论文

ssm基于java的自助医疗服务系统的设计与实现+jsp论文

摘 要 现代经济快节奏发展以及不断完善升级的信息化技术&#xff0c;让传统数据信息的管理升级为软件存储&#xff0c;归纳&#xff0c;集中处理数据信息的管理方式。本自助医疗服务系统就是在这样的大环境下诞生&#xff0c;其可以帮助管理者在短时间内处理完毕庞大的数据信息…
阅读更多...
C#MQTT编程04--订阅报文

C#MQTT编程04--订阅报文

1、报文回顾 在MQTT中&#xff0c;消息传递模式是采用发布订阅模式&#xff08;Publish-Subscribe Pattern&#xff09;&#xff0c;它将发送消息的客户端&#xff08;发布者&#xff09;与接收消息的客户端&#xff08;订阅者&#xff09;解耦&#xff0c;使得两者不需要建立…
阅读更多...
【python】07.字符串和常用数据结构

【python】07.字符串和常用数据结构

字符串和常用数据结构 使用字符串 第二次世界大战促使了现代电子计算机的诞生&#xff0c;最初计算机被应用于导弹弹道的计算&#xff0c;而在计算机诞生后的很多年时间里&#xff0c;计算机处理的信息基本上都是数值型的信息。世界上的第一台电子计算机叫ENIAC&#xff08;电…
阅读更多...
冠军获奖经历：这一路我们不孤单！

冠军获奖经历：这一路我们不孤单！

Datawhale干货 获奖&#xff1a;元贞、小罗&#xff0c;Datawhale优秀学习者 前 言 大家好&#xff0c;我是 2023 寻找游戏大模王 AI 原生应用大赛的 Top1 荆轲刺秦王团队的小罗&#xff0c;很高兴能在这里与大家分享我们这次比赛的经验&#xff0c;同时也希望以后有机会可以和…
阅读更多...
华为常用的命令——display，记得点赞收藏！

华为常用的命令——display，记得点赞收藏！

华为设备提供了多条display命令用于查看硬件部件、接口及软件的状态信息。通常这些状态信息可以为用户故障处理提供定位思路。 常用的故障信息搜集的命令如下&#xff1a; 路由器常用维护命令表 交换机常用的故障信息搜集 关注 工 仲 好&#xff1a;IT运维大本营&#xff0c;获…
阅读更多...
函数栈桢的创建和销毁

函数栈桢的创建和销毁

函数栈桢的创建和销毁 一、解决的问题二、认识常用的寄存器及其指令操作三、函数栈桢解析三、回答问题 一、解决的问题 1.局部变量是怎么创建的&#xff1f;  2.为什么局部变量的值是随机值&#xff1f;  3.函数是怎么传参的&#xff1f;传参的顺序是怎样的&#xff1f;  4.…
阅读更多...
全新小白菜QQ云端机器人登录系统源码 /去除解密授权学习版源码

全新小白菜QQ云端机器人登录系统源码 /去除解密授权学习版源码

源码介绍&#xff1a; 全新小白菜QQ云端机器人登录系统源码&#xff0c;是一款经过全面解密的授权学习版源码。 这款源码已解除了授权版的限制&#xff0c;然而许多人可能对其用途并不了解。实际上&#xff0c;该源码主要面向群机器人爱好者设计。它是一个基于挂机宝机器人框…
阅读更多...
【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字

【位运算】【二分查找】【C++算法】100160价值和小于等于 K 的最大数字

作者推荐 【动态规划】【字符串】扰乱字符串 本文涉及的基础知识点 二分查找算法合集 位运算 LeetCode100160. 价值和小于等于 K 的最大数字 给你一个整数 k 和一个整数 x 。 令 s 为整数 num 的下标从1 开始的二进制表示。我们说一个整数 num 的 价值 是满足 i % x 0 且…
阅读更多...
css3背景与渐变

css3背景与渐变

css3背景与渐变 前言背景颜色background-color基础知识背景图片background-image基础知识背景图片的重复模式 背景尺寸background-sizecontain和cover是两个特殊的background-size的值 背景裁切 background-clip背景固定 background-attachment背景图片位置 background-positio…
阅读更多...
LeetCode 590. N 叉树的后序遍历

LeetCode 590. N 叉树的后序遍历

590. N 叉树的后序遍历 给定一个 n 叉树的根节点 root &#xff0c;返回 其节点值的 后序遍历 。 n 叉树 在输入中按层序遍历进行序列化表示&#xff0c;每组子节点由空值 null 分隔&#xff08;请参见示例&#xff09;。 示例 1&#xff1a; 输入&#xff1a;root [1,null,…
阅读更多...
虚拟机配置网络

虚拟机配置网络

1开启网络 右击打开属性配置ipv4 配置vm 配置系统 配置liunx网卡信息 vim /etc/sysconfig/network-scripts/ifcfg-ens33 打开电脑任务管理器
阅读更多...
1.13寒假集训

1.13寒假集训

晚上兼职下班回来才有时间写题&#xff0c;早上根本起不来 A: 解题思路&#xff1a;我第一开始以为只要满足两个red以上的字母数量就行&#xff0c;但是过不了&#xff0c;后面才发现是red字符串&#xff0c;直接三个三个判断就行。 下面是c代码&#xff1a; #include<io…
阅读更多...
【GitHub项目推荐--一行命令下载全网视频】【转载】

【GitHub项目推荐--一行命令下载全网视频】【转载】

项目地址&#xff1a;https://github.com/soimort/you-get 首先声明&#xff0c;请不要使用该项目从事违法活动哦~仅供学习使用&#xff01; 解决痛点 如果你上网的时候看了一些东西不错&#xff0c;想下载下来&#xff0c;或者在线观看喜欢的视频&#xff0c;但是没有找到网…
阅读更多...
基于Xilinx K7-410T的高速DAC之AD9129开发笔记（二）

基于Xilinx K7-410T的高速DAC之AD9129开发笔记（二）

引言&#xff1a;上一篇文章我们简单介绍了AD9129的基础知识&#xff0c;包括芯片的重要特性&#xff0c;外部接口相关的信号特性等。本篇我们重点介绍下项目中FPGA与AD9129互联的原理图设计&#xff0c;包括LVDS IO接口设计、时钟电路以、供电设计以及PCB设计。 LVDS数据接口设…
阅读更多...
openssl3.2 - quic服务的运行

openssl3.2 - quic服务的运行

文章目录 openssl3.2 - quic服务的运行概述笔记运行openssl编译好的quic服务程序todo - 如果自己编译quic服务工程END openssl3.2 - quic服务的运行 概述 在看 官方 guide目录下的工程. 都是客户端程序, 其中有quic客户端, 需要运行quic服务才行. openssl编译好的目录中有编译…
阅读更多...
基于Matlab/Simulink的MIL仿真验证解决方案

基于Matlab/Simulink的MIL仿真验证解决方案

文章目录 需求追溯 虚拟环境 模型检查 仿真验证 测试报告 参考文献 针对模型开发阶段的ECU算法&#xff0c;可以很直接地将其与虚拟车辆模型连接起来&#xff0c;通过MIL对其进行验证和确认。可以在开发过程的早期检测到设计错误和不正确的需求&#xff0c;也有助于安全地…
阅读更多...
UML-状态机图（状态图）

UML-状态机图（状态图）

UML-状态机图&#xff08;状态图&#xff09; 一、状态机图简介1、状态&#xff08;1&#xff09;简单状态&#xff08;2&#xff09;并发状态2、转移&#xff08;1&#xff09;判定决策点&#xff08;2&#xff09;同步&#xff08;分叉与汇合&#xff09; 3、事件4、动作5、活…
阅读更多...
C++ 输入用户名和密码 防止注入攻击

C++ 输入用户名和密码 防止注入攻击

1、问题解释&#xff1a;注入攻击 &#xff0c;无密码直接登录数据库 可视化展示 1.1、当你的数据库为&#xff1a;其中包含三个字段id user 以及md5密码 1.2、在使用C堆数据库信息进行访问的时候&#xff0c;使用多条语句进行查询 string sql "select id from t_user…
阅读更多...
Unity Shader 属性的定义

Unity Shader 属性的定义

Unity Shader 属性的定义 什么是材质球 人的衣服 什么是shader 决定材质跟灯光的作用 Property 若是把shader看作class&#xff0c;那么Property就可以看成成员变量 属性定义的通用格式 Properites{ Property[Property…] } ep:定义一个int&#xff1a; name("dis…
阅读更多...
最新文章

Copyright @ 2022~2023