当前位置: 首页 > news >正文

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年码蹄杯本科院校赛道初赛(省赛)

赛时所写题&#xff0c;简单写一下思路&#xff0c;qwq 第一题&#xff1a; 输出严格次小值&#xff0c; //#pragma GCC optimize(2)#include <iostream> #include <cstring> #include <algorithm> #include <vector> #include <queue> #incl…...

PHP蜜语翻译器在线文字转码解码源码

源码介绍 PHP蜜语翻译器在线文字转码解码源码 文字加密通话、一键转换、蜜语密码 无需数据库,可以将文字、字母、数字、代码、表情、标点符号等内容转换成新的文字形式&#xff0c;通过简单的文字以不同的排列顺序来表达不同的内容&#xff01;支持在线加密解密 有多种加密展示…...

安卓浏览器区分启动、打开、分享

搞了几个钟头&#xff0c;终于全兼容了&#xff0c;分享有2种类型&#xff01; 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 中&#xff0c;数组是一块连续的内存空间&#xff0c;数组的下标通常用来定位这段内存中的特定元素。下标通常从 0 开始&#xff0c;最大到数组长度减 1。例如&#xff0c;一个有 10 个元素的数组&#xff0c;其有效下标范围是从 0 到 9。 当你尝试使用负数下标来…...

钓鱼网站开发原理(社会工程学)

钓鱼网站开发原理&#xff08;社会工程学&#xff09; 一、课程简介1、课程大纲2、课程目标3、知识储备 二、钓鱼网站简介1、什么是钓鱼网站2、开发&原理 三、PHP环境搭建1、简介2、自动安装MySQL/apache/PHP3、安装navicat 四、PDO表单入库案例1、语法2、显示登录表单3、入…...

如何优雅地使用 console.log 打印数组或对象

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

模式分解的概念(下)-无损连接分解的与保持函数依赖分解的定义和判断、损失分解

一、无损连接分解 1、定义 2、检验一个分解是否是无损连接分解的算法 输入与输出 输入&#xff1a; 关系模式R&#xff08;U&#xff0c;F&#xff09;&#xff0c;F是最小函数依赖集 R上的一个分解 输出&#xff1a; 判断分解是否为无损连接分解 &#xff08;1&#x…...

vue3父组件获取子组件的实例对象

一&#xff0c;ref 在父组件的模板里&#xff0c;对子组件的标签定义ref属性&#xff0c;并且设置属性值&#xff0c;在方法里获取ref()获取实例对象。 父组件&#xff1a; <template><div ><div>我是父组件</div><<SonCom ref"sonComRe…...

主流框架选择:React、Angular、Vue的详细比较

目前前端小伙伴经常使用三种广泛使用的开发框架&#xff1a;React、Angular、Vue - 来设计网站 Reactjs&#xff1a;效率和多功能性而闻名 Angularjs&#xff1a;创建复杂的应用程序提供了完整的解决方案&#xff0c;紧凑且易于使用的框架 Vuejs&#xff1a;注重灵活性和可重用…...

交易者的意义是什么?

按照阿德勒的说法&#xff1a;人生的意义就是为社会创造价值&#xff0c;推动整个人类社会的发展进步。 我认同且秉持这种观点。 而在交易中&#xff0c;你是否直接或者间接为社会做贡献了呢&#xff1f;这个还真不好说。 但是做为职业交易者&#xff0c;你的存在价值&#…...

io_uring

转&#xff1a;[译] Linux 异步 I_O 框架 io_uring&#xff1a;基本原理、程序示例与性能压测&#xff08;2020&#xff09; 新一代异步IO框架 io_uring &#xff5c; 得物技术 干翻 nio &#xff0c;王炸 io_uring 来了 &#xff01;&#xff01;&#xff08;图解史上最全&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…...

怎样去掉卷子上的答案并打印

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

海思SS928/SD3403开发笔记1——使用串口调试开发板

该板子使用串口可以调试&#xff0c;下面是win11 调试 该板子步骤 1、给板子接入鼠标、键盘、usb转串口 2、下载SecureCRT&#xff0c;并科学使用 下载地址&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/11dIkZVstvHQUhE8uS1YO0Q 提取码&#xff1a;vinv 3、安装c…...

JSON数据操作艺术

在现代Web开发和数据交换场景中&#xff0c;JSON&#xff08;JavaScript Object Notation&#xff09;作为一种轻量级的数据交换格式&#xff0c;扮演着至关重要的角色。它以易于阅读的文本形式存储和传输数据对象&#xff0c;而这些对象的核心便是由属性名&#xff08;键&…...

如何验证Rust中的字符串变量在超出作用域时自动释放内存?

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

55.Python pip install 安装失败的一个情况Requirement already satisfied

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

Axios进阶

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

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...