2024年码蹄杯本科院校赛道初赛(省赛)

2024-06-22 19:04

本文主要是介绍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年码蹄杯本科院校赛道初赛(省赛)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085143

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

【专题】2024飞行汽车技术全景报告合集PDF分享(附原数据表)

原文链接: https://tecdat.cn/?p=37628 6月16日,小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞,这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示,公司准备量产,并计划今年四季度开启预售小鹏汇天分体式飞行汽车,探索分体式飞行汽车城际通勤。阅读原文,获取专题报告合集全文,解锁文末271份飞行汽车相关行业研究报告。 据悉,业内人士对飞行汽车行业

高效录音转文字:2024年四大工具精选!

在快节奏的工作生活中,能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候,一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具! 365在线转文字 直达链接:https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具,它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件,只

2024网安周今日开幕,亚信安全亮相30城

2024年国家网络安全宣传周今天在广州拉开帷幕。今年网安周继续以“网络安全为人民,网络安全靠人民”为主题。2024年国家网络安全宣传周涵盖了1场开幕式、1场高峰论坛、5个重要活动、15场分论坛/座谈会/闭门会、6个主题日活动和网络安全“六进”活动。亚信安全出席2024年国家网络安全宣传周开幕式和主论坛,并将通过线下宣讲、创意科普、成果展示等多种形式,让广大民众看得懂、记得住安全知识,同时还

2024/9/8 c++ smart

1.通过自己编写的class来实现unique_ptr指针的功能 #include <iostream> using namespace std; template<class T> class unique_ptr { public:         //无参构造函数         unique_ptr();         //有参构造函数         unique_ptr(

论文翻译:arxiv-2024 Benchmark Data Contamination of Large Language Models: A Survey

Benchmark Data Contamination of Large Language Models: A Survey https://arxiv.org/abs/2406.04244 大规模语言模型的基准数据污染:一项综述 文章目录 大规模语言模型的基准数据污染:一项综述摘要1 引言 摘要 大规模语言模型(LLMs),如GPT-4、Claude-3和Gemini的快

免费也能高质量!2024年免费录屏软件深度对比评测

我公司因为客户覆盖面广的原因经常会开远程会议,有时候说的内容比较广需要引用多份的数据,我记录起来有一定难度,所以一般都用录屏工具来记录会议内容。这次我们来一起探索有什么免费录屏工具可以提高我们的工作效率吧。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  录屏软件录屏功能就是本职,这款录屏工具在录屏模式上提供了多种选项,可以选择屏幕录制、窗口

论文翻译:ICLR-2024 PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS

PROVING TEST SET CONTAMINATION IN BLACK BOX LANGUAGE MODELS https://openreview.net/forum?id=KS8mIvetg2 验证测试集污染在黑盒语言模型中 文章目录 验证测试集污染在黑盒语言模型中摘要1 引言 摘要 大型语言模型是在大量互联网数据上训练的,这引发了人们的担忧和猜测,即它们可能已

轻松录制每一刻:探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧?现在的市面上有不少免费录屏的软件了。别看如软件是免费的,它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单,打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦

梳理2024年,螺丝钉们爱用的3款剪辑软件

这年头,视频到处都是,就跟天上的星星一样数不清。不管你是公司里的新面孔,还是职场上的老狐狸,学会怎么剪视频,就好比找到了赢的秘诀。不管是给上司汇报工作,展示你的产品,还是自己搞点小视频记录生活,只要是剪辑得漂亮,肯定能一下子吸引大家的目光,让人记得你。咱们今天就来侃侃现在超火的三款视频剪辑工具,尤其是PR剪辑,你肯定听说过,这货在剪辑界可是大名鼎鼎,用它剪视频,既专业又麻利。 NO1. 福昕轻松