2024年码蹄杯本科院校赛道初赛(省赛)
赛时所写题,简单写一下思路,qwq
第一题:
输出严格次小值,
//#pragma GCC optimize(2)#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
#include<ctime>
#include<bitset>using namespace std;typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;#define fi first
#define se second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
#define pb push_backint const mod=1e9+7;
int const B=507;
//int const mod=998244353;
//int const base=131,mod=2e9+11;
int const N=2e5+7,M=2e6+7;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;int n,m,q,k;
int x,y,z;
int a[N];
string s,t;
vector<int>g[N];
struct Node{int w,x,y;bool operator<(const Node &o)const{return w<o.w;}
};void solve(){cin>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);int i=1;while(i<n&&a[i]==a[0]) i++;cout<<a[i];
} void init(){}int main()
{//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//init();int T=1;//cin>>T;//scanf("%d",&T);for(int i=1;i<=T;i++){solve();}return 0;
}
第二题:
思路:一段全是1可以直接累加答案,然后记录一个左右两端连续1个数的最大值
//#pragma GCC optimize(2)#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
#include<ctime>
#include<bitset>using namespace std;typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;#define fi first
#define se second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
#define pb push_backint const mod=1e9+7;
int const B=507;
//int const mod=998244353;
//int const base=131,mod=2e9+11;
int const N=2e5+7,M=2e6+7;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;int n,m,q,k;
int x,y,z;
int a[N];
string s,t;
vector<int>g[N];void solve(){cin>>n;int ans=0;int mx1=0,mx2=0;for(int i=0;i<n;i++){cin>>s; m=s.size();int cnt1=0,cnt2=0;for(int i=0;i<m&&s[i]=='1';i++){cnt1++;}for(int i=m-1;i>=0&&s[i]=='1';i--){cnt2++;}if(cnt1==m) ans+=m;else{mx1=max(mx1,cnt1);mx2=max(mx2,cnt2);}} cout<<ans+max(mx1,mx2)<<endl;
} void init(){}int main()
{//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//init();int T=1;//cin>>T;//scanf("%d",&T);for(int i=1;i<=T;i++){solve();}return 0;
}
第三题:
思路:每一步只能往下走,或者往右走,(x1,y2)在(x2,y2)左上角时无解,两点的距离大于n时也是无解的,总距离为n,可以选k1个向左(或者选k2个向右),C(n,k1)/C(n,k2),记得除法用逆元
//#pragma GCC optimize(2)#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
#include<ctime>
#include<bitset>using namespace std;typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;#define fi first
#define se second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
#define pb push_back//int const mod=1e9+7;
int const B=507;
int const mod=998244353;
//int const base=131,mod=2e9+11;
int const N=3e5+7,M=2e6+7;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;int fact[N],infact[N];
LL inv100;LL qpow(LL a,LL b,int p=mod){LL res=1;a%=p;while(b){if(b&1) res=res*a%p;a=a*a%p;b/=2;}return res;
}
LL C(int a,int b){if(b>a) swap(a,b);return 1LL*fact[a]*infact[a-b]%mod*infact[b]%mod;
}
LL lucas(LL a,LL b){if(a<mod&&b<mod) return C(a,b);return 1LL*lucas(a/mod,b/mod)*lucas(a%mod,b%mod);
}void solve(){int x1,x2,y1,y2,n,p,q;scanf("%d%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&n,&p,&q);LL k1=x2-x1,k2=y2-y1;if(x1>x2||y1>y2||k1+k2!=n) printf("0\n");else{LL t=C(n,k1); LL ans=t%mod*qpow(p*inv100,k1)%mod*qpow(q*inv100,k2)%mod;printf("%lld\n",ans);}
} void init(){inv100=qpow(100,mod-2);fact[0]=infact[0]=1;for(int i=1;i<N;i++){fact[i]=1LL*fact[i-1]*i%mod;infact[i]=1LL*infact[i-1]*qpow(i,mod-2)%mod;}
// for(int i=1;i<=10;i++){
// for(int j=0;j<=i;j++){
// cout<<C(i,j)<<" ";
// }
// cout<<endl;
// }
}int main()
{//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);init();int T=1;//cin>>T;scanf("%d",&T);for(int i=1;i<=T;i++){solve();}return 0;
}
第四题:
思路:缩点后,跑拓扑排序,记录缩点后每一个团的最小值
//#pragma GCC optimize(2)#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
#include<ctime>
#include<bitset>using namespace std;typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;#define fi first
#define se second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
#define pb push_backint const mod=1e9+7;
int const B=507;
//int const mod=998244353;
//int const base=131,mod=2e9+11;
int const N=2e5+7,M=2e6+7;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;int n,m,q,k;
int x,y,z;
int a[N];
string s,t;
vector<int>g[N];
int dfn[N],low[N],tot;
int stk[N],top;
bool instk[N];
int scc[N],sz[N],cnt;
int mi[N];
int inD[N];void tarjan(int x){low[x]=dfn[x]=++tot;stk[++top]=x; instk[x]=true;for(int y:g[x]){if(dfn[y]==0){tarjan(y);low[x]=min(low[x],low[y]);}else if(instk[y]){low[x]=min(low[x],dfn[y]);}}if(dfn[x]==low[x]){int y; cnt++;do{y=stk[top--]; instk[y]=false;scc[y]=cnt;sz[cnt]++;mi[cnt]=min(mi[cnt],a[y]);}while(y!=x);}
}
vector<PII>edge;void solve(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=0;i<m;i++){scanf("%d%d",&x,&y);edge.pb({x,y});g[x].pb(y);}memset(mi,0x3f,sizeof mi);for(int i=1;i<=n;i++)if(dfn[i]==0) tarjan(i);for(int i=1;i<=n;i++) g[i].clear();for(auto [x,y]:edge){if(scc[x]!=scc[y]){g[scc[x]].pb(scc[y]);inD[scc[y]]++;}}queue<int>q;for(int i=1;i<=cnt;i++){if(inD[i]==0){q.push(i);}}while(q.size()){int x=q.front(); q.pop();for(int y:g[x]){mi[y]=min(mi[y],mi[x]);if(--inD[y]==0) q.push(y);}}LL ans=0;for(int i=1;i<=n;i++) ans+=mi[scc[i]];cout<<ans<<"\n";for(int i=1;i<=n;i++) cout<<mi[scc[i]]<<" ";cout<<endl;
} void init(){}int main()
{//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//init();int T=1;//cin>>T;//scanf("%d",&T);for(int i=1;i<=T;i++){solve();}return 0;
}
第六题:
思路:离线处理,逆向思维,拆边改成建边,用并查集维护每一个小组的内出现的个数,合并时采用启发式合并
//#pragma GCC optimize(2)#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include<stack>
#include<cmath>
#include <unordered_set>
#include <unordered_map>
#include<set>
#include <map>
#include<ctime>
#include<bitset>using namespace std;typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int>PII;#define fi first
#define se second
#define ls u<<1
#define rs u<<1|1
#define all(ss) ss.begin(),ss.end()
#define pb push_backint const mod=1e9+7;
int const B=507;
//int const mod=998244353;
//int const base=131,mod=2e9+11;
int const N=4e5+7,M=4e5+7;
int const INF=0x3f3f3f3f;
LL const INFF=0x3f3f3f3f3f3f3f3f;int n,m,q,k;
int x,y,z;
int a[N];
bool vis[N]; //标记删除的边
struct Node{int opt,x,y;
}Q[M];
int fa[N];
PII edges[N];
int ans[M];int find(int x){return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}void solve(){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=n;i++) scanf("%d",a+i);for(int i=1;i<=m;i++) scanf("%d%d",&edges[i].fi,&edges[i].se);for(int i=1;i<=q;i++){int opt,x,y=0; scanf("%d%d",&opt,&x);if(opt==1) vis[x]=true;else{scanf("%d",&y);}Q[i]={opt,x,y};}vector<map<int,int>>mp(n+1);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=n;i++) mp[i][a[i]]++;for(int i=1;i<=m;i++){if(vis[i]) continue;int x=edges[i].fi,y=edges[i].se;int px=find(x),py=find(y);if(px!=py){if(mp[px].size()<mp[py].size()) swap(mp[px],mp[py]);fa[py]=px;for(auto [val,c]:mp[py]){mp[px][val]+=c;}}}for(int i=q;i>=1;i--){if(Q[i].opt==1){int x=edges[Q[i].x].fi,y=edges[Q[i].x].se;int px=find(x),py=find(y);if(px!=py){if(mp[px].size()<mp[py].size()) swap(mp[px],mp[py]);fa[py]=px;for(auto [val,c]:mp[py]){mp[px][val]+=c;}}}else{int x=Q[i].x,y=Q[i].y;int px=find(x);ans[i]=mp[px][y-a[x]]-(a[x]+a[x]==y);}}for(int i=1;i<=q;i++) if(Q[i].opt==2) printf("%d\n",ans[i]);
} void init(){}int main()
{//std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);//init();int T=1;//cin>>T;//scanf("%d",&T);for(int i=1;i<=T;i++){solve();}return 0;
}
相关文章:
2024年码蹄杯本科院校赛道初赛(省赛)
赛时所写题,简单写一下思路,qwq 第一题: 输出严格次小值, //#pragma GCC optimize(2)#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #incl…...

PHP蜜语翻译器在线文字转码解码源码
源码介绍 PHP蜜语翻译器在线文字转码解码源码 文字加密通话、一键转换、蜜语密码 无需数据库,可以将文字、字母、数字、代码、表情、标点符号等内容转换成新的文字形式,通过简单的文字以不同的排列顺序来表达不同的内容!支持在线加密解密 有多种加密展示…...
安卓浏览器区分启动、打开、分享
搞了几个钟头,终于全兼容了,分享有2种类型! void getDataFromIntent(Intent intent) {if (intent.getAction().equals(Intent.ACTION_VIEW)) {urln intent.getDataString();if (urln ! null) {if (urln.contains("\n"))urln url…...

C/C++ 数组负数下标
一 概述 在 C 中,数组是一块连续的内存空间,数组的下标通常用来定位这段内存中的特定元素。下标通常从 0 开始,最大到数组长度减 1。例如,一个有 10 个元素的数组,其有效下标范围是从 0 到 9。 当你尝试使用负数下标来…...
钓鱼网站开发原理(社会工程学)
钓鱼网站开发原理(社会工程学) 一、课程简介1、课程大纲2、课程目标3、知识储备 二、钓鱼网站简介1、什么是钓鱼网站2、开发&原理 三、PHP环境搭建1、简介2、自动安装MySQL/apache/PHP3、安装navicat 四、PDO表单入库案例1、语法2、显示登录表单3、入…...

如何优雅地使用 console.log 打印数组或对象
一、背景 使用 console.log 在控制台中打印数组或者对象时,很多时候它们的字段都是默认关闭的,需要手动一个个的点开,非常不直观且麻烦。 二、解决方案 使用 JSON.stringify() 的第三个参数 我们来看一下官方对于 JSON.stringify 的介绍 三、…...

模式分解的概念(下)-无损连接分解的与保持函数依赖分解的定义和判断、损失分解
一、无损连接分解 1、定义 2、检验一个分解是否是无损连接分解的算法 输入与输出 输入: 关系模式R(U,F),F是最小函数依赖集 R上的一个分解 输出: 判断分解是否为无损连接分解 (1&#x…...
vue3父组件获取子组件的实例对象
一,ref 在父组件的模板里,对子组件的标签定义ref属性,并且设置属性值,在方法里获取ref()获取实例对象。 父组件: <template><div ><div>我是父组件</div><<SonCom ref"sonComRe…...

主流框架选择:React、Angular、Vue的详细比较
目前前端小伙伴经常使用三种广泛使用的开发框架:React、Angular、Vue - 来设计网站 Reactjs:效率和多功能性而闻名 Angularjs:创建复杂的应用程序提供了完整的解决方案,紧凑且易于使用的框架 Vuejs:注重灵活性和可重用…...
交易者的意义是什么?
按照阿德勒的说法:人生的意义就是为社会创造价值,推动整个人类社会的发展进步。 我认同且秉持这种观点。 而在交易中,你是否直接或者间接为社会做贡献了呢?这个还真不好说。 但是做为职业交易者,你的存在价值&#…...
io_uring
转:[译] Linux 异步 I_O 框架 io_uring:基本原理、程序示例与性能压测(2020) 新一代异步IO框架 io_uring | 得物技术 干翻 nio ,王炸 io_uring 来了 !!(图解史上最全&a…...
构建高并发Web应用:基于Gunicorn、Flask和Docker的部署指南
目录 一 理解基础组件 什么是Flask? 什么是Gunicorn? 什么是Docker? 二 环境准备 三 构建Flask应用 创建项目结构 编写Flask应用 app/views.py 四 使用Gunicorn部署Flask应用 配置Gunicorn Gunicorn配置文件 五 使用Docker进行容器化部署 编写Dockerfile 构建…...
【Ruby简单脚本02】双色球系统
# frozen_string_literal: true require date # 生成中奖号码的工具 # 红球 1-32 篮球 1-15 def create_num nums [] 6.times do while true num rand(1..32) unless nums.include?(num) nums << num break end end end blue rand(1..15) nums…...

Netty ByteBuf 使用详解
文章目录 1.概述2. ByteBuf 分类3. 代码实例3.1 常用方法3.1.1 创建ByteBuf3.1.2 写入字节3.1.3 扩容3.1.2.1 扩容实例3.1.2.2 扩容计算新容量代码 3.1.4 读取字节3.1.5 标记回退3.1.6 slice3.1.7 duplicate3.1.8 CompositeByteBuf3.1.9 retain & release3.1.9.1 retain &a…...

怎样去掉卷子上的答案并打印
当面对试卷答案的问题时,一个高效而简单的方法是利用图片编辑软件中的“消除笔”功能。这种方法要求我们首先将试卷拍摄成照片,然后利用该功能轻松擦除答案。尽管这一方法可能需要些许时间和耐心,但它确实为我们提供了一个可行的解决途径。 然…...

海思SS928/SD3403开发笔记1——使用串口调试开发板
该板子使用串口可以调试,下面是win11 调试 该板子步骤 1、给板子接入鼠标、键盘、usb转串口 2、下载SecureCRT,并科学使用 下载地址: 链接:https://pan.baidu.com/s/11dIkZVstvHQUhE8uS1YO0Q 提取码:vinv 3、安装c…...
JSON数据操作艺术
在现代Web开发和数据交换场景中,JSON(JavaScript Object Notation)作为一种轻量级的数据交换格式,扮演着至关重要的角色。它以易于阅读的文本形式存储和传输数据对象,而这些对象的核心便是由属性名(键&…...

如何验证Rust中的字符串变量在超出作用域时自动释放内存?
讲动人的故事,写懂人的代码 在公司内部的Rust培训课上,讲师贾克强比较了 Rust、Java 和 C++ 三种编程语言在变量越过作用域时自动释放堆内存的不同特性。 Rust 通过所有权系统和借用检查,实现了内存安全和自动管理,从而避免了大部分内存泄漏。Rust 自动管理标准库中数据类…...

55.Python pip install 安装失败的一个情况Requirement already satisfied
1.问题 以前使用Pycharm 社区版开发的一个项目,今天使用PyCharm 专业版打开,原项目的虚拟环境从venv更换为.venv,然后重新安装插件。安装时,提示Requirement already satisfied: qt_material in c:\tools\python37\lib\site-packa…...

Axios进阶
目录 axios实例 axios请求配置 拦截器 请求拦截器 响应拦截器 取消请求 axios不仅仅是简单的用基础请求用法的形式向服务器请求数据,一旦请求的端口与次数变多之后,简单的请求用法会有些许麻烦。所以,axios允许我们进行创建axios实例、ax…...

【力扣数据库知识手册笔记】索引
索引 索引的优缺点 优点1. 通过创建唯一性索引,可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度(创建索引的主要原因)。3. 可以加速表和表之间的连接,实现数据的参考完整性。4. 可以在查询过程中,…...

家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1
每日一言 生活的美好,总是藏在那些你咬牙坚持的日子里。 硬件:OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写,"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...

ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...