Codeforces Round 952 (Div. 4) c++题解(A-H1)
开头 :
这场没打,今天vp了一下,写了A-G,然后就去吃饭了!
比赛链接 :
Dashboard - Codeforces Round 952 (Div. 4) - Codeforces
A
直接交换,输出即可
inline void solve(){string a , b ; cin >> a>> b ;char c = a[0] ;a[0] = b[0] ;b[0] = c ;cout << a << " " << b << endl ;
}
B
数据范围小,模拟那个过程即可;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '\n'
#define pair<int,int> PII ;
#define x first
#define y second
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i<(e);++i)
#define all(v) v.begin(), v.end()
#define pb push_back
const LL INF = 1e18 ;
const int mod = 1e9+7;
const int N = 2e5+10;
int dx[4] = {0, 1, 0, -1}, dy[5] = {1, 0, -1, 0};LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}LL qmi(int m, int k, int p){int res = 1 % p, t = m;while (k){if (k&1) res = res * t % p;t = t * t % p;k >>= 1;}return res;}inline void solve(){int n ; cin >> n ;int ans = 0 ,yss = 1 ;rep(i,2,n+1){int x = i ;int res = 0 ;while(x<=n){res += x ;x += i ;}if(res>ans) {ans = res ;yss = i ;}}cout << yss << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
C
也是模拟遍历,先用前缀和预处理一下;
如果ma * 2 = b[i],表示a[1,i]是满足题目条件的;
inline void solve(){int n ; cin >> n ;rep(i,1,n) cin >> a[i] ;rep(i,1,n) b[i] = b[i-1] + a[i] ;int ans = 0 ;// ma // b[i]-ma = maLL ma = 0 ;rep(i,1,n){ma = max(ma,a[i]) ;if(ma*2==b[i]) ans ++ ;}cout << ans << endl;
}
D
因为所有点都是关于中心点对称分布的,直接求横坐标,纵坐标的平均数就是答案了
inline void solve(){int n ,m ; cin >> n >> m ;vector<vector<char>> a(n+1,vector<char>(m+1)) ;vector<PII> b ;rep(i,1,n)rep(j,1,m){cin >> a[i][j] ;if(a[i][j]=='#') b.pb({i,j}) ;}int sz = b.size() ;int xx , yy ;if(sz==1){xx = b[0].x ; yy = b[0].y ;cout << xx << " " << yy << endl ;return ;}LL xs = 0 , ys = 0 ; for(auto& bc : b){int xc = bc.x , yc = bc.y ;xs += xc ;ys += yc ; }xx = xs / sz ;yy = ys / sz ;cout << xx << " " << yy << endl ;
}
E
直接暴力即可,遍历其中两条边,复杂度(2000^2) ;
对于每个满足条件的长宽高i,j,k(也就是i*j*k==s),在S中的移动范围分别是[i,x],[j,y],[k,z];
然后相乘即可;
inline void solve(){LL x , y , z , s ; cin >> x >> y >> z >> s ;LL ans = 0 ;rpL(i,1,x){rpL(j,1,y){LL k = s / (i*j) ;if(s%(i*j)==0 && k<=z){LL res = (x-i+1)*(y-j+1)*(z-k+1) ;ans = max(ans,res) ;}}}cout << ans << endl;
}
F
一个非常明显的二分答案,但是用堆也可以做;
(可能这场题多的原因);
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i<=(e);++i)
#define all(v) v.begin(), v.end()
#define pb push_back
const LL INF = 1e18 ;
const int mod = 1e9+7;
const int N = 2e5+10;
int dx[4] = {0, 1, 0, -1}, dy[5] = {1, 0, -1, 0};LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}LL qmi(int m, int k, int p){int res = 1 % p, t = m;while (k){if (k&1) res = res * t % p;t = t * t % p;k >>= 1;}return res;}int h , n ;
int a[N] , c[N] ;bool pd(LL m){LL dmg = 0 ;rep(i,1,n){dmg += a[i] * ((m+c[i]-1) / c[i]) ;if(dmg>=h) return true ;}return dmg>=h ;
}inline void solve(){cin >> h >> n ;LL sum = 0 ;rep(i,1,n) cin >> a[i] , sum += a[i];rep(i,1,n) cin >> c[i] ;if(sum>=h){cout << 1 << endl ;return ;}LL l = 1 , r = 2e12 ;while(l+1<r){LL m = (l+r)>>1 ;if(pd(m)) r = m ;else l = m ; // cout << l << endl ;}cout << r << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
G
- D(n) : 表示数位和;
- D(k*n) = k*D(n) : 那么n的所有数位上的数x在*k之后不能够进位
- --> 能够推出x<=[9/k] ps : []代表下取整
- 然后计算[10^l,10^r)中有多少个数n满足这个条件
- 对于每一个数位,有t=[9/k]+1 种选择,有r个数位,res=t^r
- ans = t^r-t^l
用快速幂优化一下 :
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '\n'
#define PII pair<int,int>
#define x first
#define y second
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i<=(e);++i)
#define all(v) v.begin(), v.end()
#define pb push_back
const LL INF = 1e18 ;
const int Mod = 1e9+7;
const int N = 2e5+10;
int dx[4] = {0, 1, 0, -1}, dy[5] = {1, 0, -1, 0};LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}LL qmi(LL m, LL k, LL p){LL res = 1 % p, t = m;while (k){if (k&1) res = res * t % p;t = t * t % p;k >>= 1;}return res;}inline void solve(){
// D(n) : 表示数位和
// D(k*n) = k*D(n) : 那么n的所有数位上的数x在*k之后不能够进位
// --> 能够推出x<=[9/k] ps : []代表下取整
// 然后计算[10^l,10^r)中有多少个数n满足这个条件
// 对于每一个数位,有t=[9/k]+1 种选择,有r个数位,res=t^r
// ans = t^r-t^lLL l , r , k ; cin >> l >> r >> k ;if(k>=10){cout << 0 << endl ;return ;}int p = floor(1.0*9/k)+1 ;LL ans = (qmi(p,r,Mod) - qmi(p,l,Mod)) % Mod ;if(ans<0) ans += Mod ;cout << ans << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
H
用并查集记录关于每个点的连通块 ;
然后遍历每一行,每一列来求将这一行/列全改为#,之后的连通块的大小,找到最大的;
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef unsigned long long ULL ;
#define PI acos(-1)
#define endl '\n'
#define PII pair<int,int>
#define no do { cout << "No" << endl; return; } while(0)
#define yes do { cout << "Yes" << endl; return; } while (0)
#define lowbit(x) ((x) & -(x))
#define rep(i, s, e) for (int i=(s);i<=(e);++i)
#define all(v) v.begin(), v.end()
#define pb push_back
const LL INF = 1e18 ;
const int mod = 1e9+7;
const int N = 2e5+10;
int dx[4] = {0, 1, 0, -1}, dy[5] = {1, 0, -1, 0};LL gcd(LL a, LL b) {return b ? gcd(b, a % b) : a;
}LL qmi(int m, int k, int p){int res = 1 % p, t = m;while (k){if (k&1) res = res * t % p;t = t * t % p;k >>= 1;}return res;}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);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)];}
};inline void solve(){int n ,m ; cin >> n >> m ;vector<string> s(n) ;rep(i,0,n-1) cin >> s[i] ;int sz = n * m ;DSU dsu(sz) ;rep(i,0,n-1){rep(j,0,m-1){if(i+1<n&&s[i][j]=='#'&&s[i+1][j]=='#'){//对行进行扩展 dsu.merge(i*m+j,(i+1)*m+j);//合并 }if(j+1<m&&s[i][j]=='#'&&s[i][j+1]=='#'){dsu.merge(i*m+j,i*m+j+1);//合并 }}}int ans = 0 ;vector<int> vis(sz,-1) ;rep(r,0,n-1){int res = 0 ;rep(i,0,m-1){//修改一行 if(s[r][i]=='.') res ++ ;//修改成#的数目 for(int xx=max(0,r-1);xx<=min(n-1,r+1);xx++){//找上下两行的联通块 if(s[xx][i]=='#'){int u=dsu.find(xx*m+i);if(vis[u]!=r){vis[u] = r ;res += dsu.size(u);}}}}ans = max(ans,res) ;}vis.assign(sz,-1) ;for(int c=0;c<m;c++){int res = 0 ;for(int i=0;i<n;i++){if(s[i][c]=='.') res++ ;for(int y=max(0,c-1);y<=min(m-1,c+1);y++){if(s[i][y]=='#'){int u = dsu.find(i*m+y);if(vis[u]!=c){vis[u] = c ;res += dsu.size(u) ;}}}}ans = max(ans,res) ;}cout << ans << endl ;
}signed main(){IOSint _ = 1;cin >> _;while(_ --) solve();return 0;
}
相关文章:
Codeforces Round 952 (Div. 4) c++题解(A-H1)
开头 : 这场没打,今天vp了一下,写了A-G,然后就去吃饭了! 比赛链接 : Dashboard - Codeforces Round 952 (Div. 4) - Codeforces A 直接交换,输出即可 inline void solve(){string a , b ; cin >> a>> b ;char c a[0] ;a…...

人工智能将成为数学家的“副驾驶”
人工智能将成为数学家的“副驾驶” 数学传统上是一门独立的科学。1986年,安德鲁怀尔斯为了证明费马定理,退到书房里呆了7年。由此产生的证明往往很难让同事们理解,有些至今仍有争议。但近年来,越来越多的数学领域被严格地分解为各…...

自适应巡航控制技术规范(简化版)
自适应巡航控制技术规范(简化版) 1 系统概述2 功能需求3 性能需求4 功能激活条件5 功能抑制条件6 系统局限性1 系统概述 ACC 自适应巡航系统可自动控制纵向跟车距离,减轻驾驶员的工作量,即驾驶员无需频繁的踩制动和油门便可完成部分的驾驶任务,但责任主体仍然是驾驶员,驾…...

【AI】文心一言的使用分享
在数字化时代,人工智能(AI)技术的飞速发展正在改变我们的生活。文心一言,作为这一浪潮中的佼佼者,以其卓越的自然语言处理能力和广泛的应用场景,给我带来了前所未有的使用体验。在这篇分享中,我…...
Java学习-MyBatis学习(四)
代码下载 解决字段名与属性名不一致 ①使用别名emp_name empName解决字段名和属性名不一致 <select id"getAllEmpOld" resultType"Emp"><!--①使用别名emp_name empName解决字段名和属性名不一致-->select eid,emp_name empName,age,sex,em…...

多源最短路径算法 -- 弗洛伊德(Floyd)算法
1. 简介 Floyd算法,全名为Floyd-Warshall算法,亦称弗洛伊德算法或佛洛依德算法,是一种用于寻找给定加权图中所有顶点对之间的最短路径的算法。这种算法以1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特弗洛伊德的名字命名。 2. 核心思…...

同三维T80005EH4 H.265 4路高清HDMI编码器
同三维T80005EH4 H.265 4路高清HDMI编码器 4路HDMI输入2路3.5音频输入,第1路和第2路HDMI可支持4K30,其它支持高清1080P60 产品简介: 同三维T80005EH4 4路HDMI高清H.265编码器采用最新高效H.265高清数字视频压缩技术,具备稳定…...

焦化行业排放平台简介
在当今社会,环保事业日益受到人们的关注。焦化行业作为重要的工业领域之一,其排放问题一直是环保工作的重点。为了有效控制焦化行业的排放,实施焦化行业排放平台成为了必不可少的措施。朗观视觉小编将详细探讨焦化行业排放平台的实施范围&…...

『原型资源』Axure自带图标库不够用,第三方经典图标库来袭
今天小编为大家带来第三方经典图标库,己确认内容可用现推荐给大家。直接上手就可不用自己画哈~ 获取原型文档请与班主任联系! 先睹为快,合适再拿走不谢: 图标太多,截取部分给大家参考o(* ̄︶ ̄*…...

修改版的VectorDBBench更好用
原版本VectorDBBench的几个问题 在这里就不介绍VectorDBBench是干什么的了,上官网即可。 1.并发数设置的太少 2.测试时长30秒太长 3.连接milvus无用户和密码框,这个是最大的问题 4.修改了一下其它参数 由于很多网友发私信问一些milvus的相关技术问…...

六西格玛培训都培训哪些内容 ?
天行健六西格玛培训的内容通常涵盖多个方面,旨在帮助学员全面理解和应用六西格玛管理方法。以下是详细的培训内容概述: 一、六西格玛基础知识 引入六西格玛的概念、原理和历史,包括DMAIC(定义、测量、分析、改进、控制࿰…...
K8S环境部署Prometheus
K8S环境部署Prometheus 记录在K8S 1.18版本环境下部署Prometheus 0.5版本。 1. 下载kube-prometheus仓库 git clone https://github.com/coreos/kube-prometheus.git cd kube-prometheus笔者安装的K8S版本是1.18 ,prometheus选择配套的分支release-0.5࿱…...
在linux系统上挂载新硬盘
服务器的硬盘空间不够了,自己重新安装了一个硬盘,需要挂载,因为只是用来存放数据,所以不需要分区,直接挂载就可以 #查看当前所有硬盘 sudo fdisk -l #用于显示文件系统的磁盘空间使用情况 df -h发现一个/dev/nvme0n1 …...
1004.最大连续1的个数
给定一个二进制数组 nums 和一个整数 k,如果可以翻转最多 k 个 0 ,则返回 数组中连续 1 的最大个数 。 示例 1: 输入:nums [1,1,1,0,0,0,1,1,1,1,0], K 2 输出:6 解释:[1,1,1,0,0,1,1,1,1,1,1] 粗体数字…...
【机器学习300问】116、什么是序列模型?序列模型能干什么?
一、序列模型是什么? 序列模型是机器学习领域中专门设计来处理具有时间顺序或序列结构数据的模型。这类模型能够理解和学习数据中的顺序依赖关系,因此非常适合诸如自然语言处理、语音识别、音乐生成、时间序列预测等任务。 看了上面的定义,似…...

kafka 快速上手
下载 Apache Kafka 演示window 安装 编写启动脚本,脚本的路径根据自己实际的来 启动说明 先启动zookeeper后启动kafka,关闭是先关kafka,然后关闭zookeeper 巧记: 铲屎官(zookeeper)总是第一个到,最后一个走 启动zookeeper call bi…...
Python记忆组合透明度语言模型
🎯要点 🎯浏览器语言推理识别神经网络 | 🎯不同语言秽语训练识别数据集 | 🎯交互式语言处理解释 Transformer 语言模型 | 🎯可视化Transformer 语言模型 | 🎯语言模型生成优质歌词 | 🎯模型不确…...

如何保证数据库和缓存的一致性
背景:为了提高查询效率,一般会用redis作为缓存。客户端查询数据时,如果能直接命中缓存,就不用再去查数据库,从而减轻数据库的压力,而且redis是基于内存的数据库,读取速度比数据库要快很多。 更新…...
Java基础 - 多线程
多线程 创建新线程 实例化一个Thread实例,然后调用它的start()方法 Thread t new Thread(); t.start(); // 启动新线程从Thread派生一个自定义类,然后覆写run()方法: public class Main {public static void main(String[] args) {Threa…...
云顶之弈-测试报告
一. 项目背景 个人博客系统采用前后端分离的方法来实现,同时使用了数据库来存储相关的数据,同时将其部署到云服务器上。前端主要有四个页面构成:登录页、列表页、详情页以及编辑页,以上模拟实现了最简单的个人博客系统。其结合后…...

接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...

华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...

Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...