2022年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛-程序员宅基地

技术标签: 算法  比赛错题集  c++  

2022年中国高校计算机大赛-团队程序设计天梯赛(GPLT)上海理工大学校内选拔赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

1.Komorebi的数学课(快速幂)

2.Setsuna的K数列(进制)

3.G   天气预报 (二分+前缀和)

4.史东薇尔城(最短路径dijstra)


1.Komorebi的数学课(快速幂)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    cin>>n;
    ll m=n,ans=1,k=n;
    while(m){
        if(m%2==1){
            ans=ans*n;
            ans%=(k+2);
        }
        n=n*n;
        n%=(k+2);
        m/=2;
    }
    cout<<ans%(k+2);
    return 0;
}

例如:计算3的10次方时,

3^10=(3^2)^5  = 9^5 =9*9^4  =9*(81)^2……

遇到奇数幂时,先给ans乘上原来的数,再将原数平方,即做到log2n的时间复杂度

2.Setsuna的K数列(进制)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long mod=1e9+7;
ll ppow(ll k,ll i){//快速幂求次方
     ll ans=1;
    while(i){
        if(i%2==1){
            ans=ans*k;
            ans%=mod;
        }
        k=k*k%mod;
        i/=2;
    }
    return ans%mod;
}
int main(){
    ll sum=0;
      ll n,k;
    cin>>n>>k;
    ll i=0;
    while(n){//将n转化为二进制数按k进制还原
       
        int a=n%2; //cout<<a<<endl;
        ll b=ppow(k,i);
        sum+=a*b;
       // cout<<sum<<endl;
        sum%=mod;
        n/=2;
        i++;
    }
    cout<<sum;
    return 0;
}

思路:

不难发现, K 数列本质就是每一个 K 进制位只能取 0 1 ,这很像二进制,即第 n 个数就是
n 表示成二进制然后按 K 进制还原即可。
3.剪绳子

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int c[N],sum[N];
int mp[1000100];
int main(){
    mp[0]=0;
    mp[1]=1000000;
   int q;
    cin>>q;
    int k=2;
    while(q--){
        char e;
        cin>>e;
        if(e=='C'){
          double f;
            cin>>f;
            mp[k++]=f*100000+0.5;
        }
        else{
           double ll;
            cin>>ll;
            int l=ll*100000+0.5;
            sort(mp,mp+k);
           for(int i=0;i<k;i++){
              if(l>=mp[i]&&l<=mp[i+1]){
                  cout<<fixed<<setprecision(5)<<(mp[i+1]-mp[i])*1.0/100000<<endl;
                  break;
              }
           }
        }
    }
    return 0;
}

3.天气预报(二分加前缀和)

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+9;
ll aa[N],bb[N];
int n,a,b;
int check(ll i,ll j){//检查该区间的晴朗天数和坏天气天数是否满足要求
    ll p=aa[j]-aa[i-1];
    ll q=bb[j]-bb[i-1];
    if(p>=a&&q>=b)return 1;
    else return 0;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>a>>b;
    string s;
    cin>>s;
    ll ans=0;
    //cout<<s.size()<<endl;
    for(int i=1;i<=n;i++){//前缀和:当两个前缀和相减时就可以求出该段区间内有多少天晴朗,即判断是否满足情况
        aa[i]=aa[i-1];//对天气晴朗的情况求前缀和
        bb[i]=bb[i-1];//对下毒蛙的情况求前缀和
        if(s[i-1]=='0')aa[i]++;
        else bb[i]++;
    }
    /*
    以样例1为例
    5天内
    天晴:10101
    天坏:01011
    天晴前缀和:11223
    例:第三天到第一天有aa[3]-aa[1-1]=2-0=2天晴朗
    天坏前缀和:01122
    */
    if(a==0&&b==0)ans++;//特殊情况:当a和b均为0时,可以一天也不选
    for(int i=1;i<=n;i++){
        ll l=i,r=n;//左右两个指针
        while(l<r){//左右指针相遇跳出循环
            ll mid=(l+r)/2;//二分
            if(check(i,mid))r=mid;//若左端点到中间区间满足条件,右指针往左移,缩小满足条件数
            else l=mid+1;//否则左指针往右移,将满足天数的范围扩大
        }
        if(check(i,l))ans+=(n-l+1);//二分边界不一定满足,再次判断,若满足,则从l到n的i均满足,(往后只会比a,b天数更多,所以一定满足,都加到ans中)
    }
    cout<<ans<<endl;
    return 0;
}

4.史东薇尔城(最短路径)

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>p;
const ll N=1e6+10;
vector<p>h[N];
ll dist[N],st[N];
void dijstra(){
	memset(dist,0x3f,sizeof(dist));//初始化每个点到根节点的距离为无穷大
	priority_queue<p,vector<p>,greater<p> >q;
	q.push({0,1});//放入根节点
	dist[1]=0;//根节点距自己的距离为0
	while(!q.empty()){//队列为空时跳出循环
	     p now=q.top();q.pop();//取队头元素
	     int ne=now.second;//下一个距离自己最近的点名
		// int dis=now.first;//
		 if(st[ne])continue;
		 st[ne]=1;
	     for(auto it:h[ne]){//遍历该点周围连接的点
	     	if(dist[it.first]>dist[ne]+it.second){//松弛操作
	     		dist[it.first]=dist[ne]+it.second;//如果该点到根节点的距离大于,自己的前驱节点到根节点的距离加上到自己的距离,就更新
	     		q.push({dist[it.first],it.first});//把目前最新更新的点加入队列
			 }
		 }
	}
}
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int v,w,d;
		cin>>v>>w>>d;
		h[v].push_back({w,d});//建立图(连边加权值)
		h[w].push_back({v,d});//无向图,两点能相互到达
	}
	dijstra();//最短路径搜素
	int t;
	cin>>t;
	while(t--){
		int x,y;
		cin>>x>>y;
		cout<<dist[x]+dist[y]<<endl;
	}
	return 0;
} 

关于dijstta算法:Dijkstra算法详解(完美图解、趣学算法)_wjyGrit的博客-程序员宅基地_dijkstra算法

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_61094896/article/details/123762162

智能推荐

Springboot集成mqtt【demo】_springboot mtqq demo-程序员宅基地

文章浏览阅读1.3k次。项目目录如下启动类如下import org.eclipse.paho.client.mqttv3.MqttException;import org.springframework.boot.SpringApplication;import org.springframework.boot.autoconfigure.EnableAutoConfiguration;import org.springframework.boot.autoconfigure.SpringBootApplicatio_springboot mtqq demo

C语言中的popen()函数_c popen函数 resource temporarily unavailable-程序员宅基地

文章浏览阅读3.3w次,点赞10次,收藏66次。Linux中的popen()函数可以在程序中执行一个shell命令,并返回命令执行的结果。有两种操作模式,分别为读和写。在读模式中,程序中可以读取到命令的输出,其中有一个应用就是获取网络接口的参数。在写模式中,最常用的是创建一个新的文件或开启其他服务等。头文件:#include 函数原型:FILE *popen(const char *command, const char *type_c popen函数 resource temporarily unavailable

新手小白也能做短视频自媒体,掌握方法和技巧,稳定每天200多_每天200百条视频怎么做-程序员宅基地

文章浏览阅读323次。大周跟很多新手小伙伴一样,都是从一个什么都不懂的小白,一步一步走到今天的,也遇到过各种各样的问题,坚持下去你就能赢。前期做得比较多,现在每天不去操作,也能有100-200的稳定收益,所以说做短视频自媒体是越到后期越赚钱的,新手小伙伴们完全可以去尝试操作,不要害怕失败。我们前期的收益主要来源与播放量的收益,就是平台给的广告分成,粉丝用户看你的短视频作品时下方会有下拉广告,所以说你的收益是与播放量挂钩的。新手小白经常会出现作品被下架、扣分和重复度过高的问题,导致没有收益或被封号,今天大周分享几个我常用的小_每天200百条视频怎么做

HttpClient 四种请求访问代码 HttpGet HttpPost HttpPut HttpDelete_httpput putrequest = new httpput-程序员宅基地

文章浏览阅读4.9k次。逻辑:String url = "http://www.baidu.com";//将要访问的url字符串放入HttpPost中HttpPost httpPost = new HttpPost(url);//请求头 放置一些修改http请求头和cookiehttpPost.setHeader("Accept", "application/json");......//如果_httpput putrequest = new httpput

EG网关串口连接施耐德M340PLC应用案例-程序员宅基地

文章浏览阅读971次,点赞17次,收藏18次。设置步骤:点击需要报警的变量后面的【报警】→【新增】→填写报警信息与条件→【确定】。【寄存器类型】:在施耐德M340 PLC中,离散量的输入输出使用的是%M地址,模拟量使用的是%MW地址(Modbus寄存器对应关系可以参考下面案例的采集变量对照表)。步骤:点击【后台管理】(只有管理账号才有此权限)→【设备中心】→【EG设备管理】→【+新增】→填写设备信息→点击【保存】。Modbus参数设置完成后,把修改好的程序下载到PLC中,再打开【应用程序树】,点击【GVL】,将变量进行修改。

合成生物学|第一期:什么是合成生物学_如何理解合成生物学的层级结构?-程序员宅基地

文章浏览阅读5.9k次,点赞2次,收藏7次。这个系列是关于天津大学宋凯教授的《合成生物学导论》的学习笔记,将对合成生物学的概念、合成生物系统的设计、数学模拟与性能分析以及合成生物学基础与应用研究进行一个概括性记述,目的主要是通过合成生物学这个前沿方向了解学科交叉融合现状与方法以及掌握一些工程性方法与思路。1. 合成生物学的诞生:1953年,克里克和沃森发现了DNA双螺旋结构、开始了解读生物遗传密码的第一步;2003年,人类基因组计划..._如何理解合成生物学的层级结构?

随便推点

windows11,打不开IE浏览器,自动跳转到edge浏览器_res://ieframe.dll-程序员宅基地

文章浏览阅读3.7w次,点赞4次,收藏17次。目前的 暂时解决办法是,1. 打开 Edge浏览器,--设置2. 点击左上角 设置--默认浏览器3. Internet Explorer模式页面--添加 ‘自己需要IE浏览器打开的网址’,然后 就会在 Edge中,再次打开网址尝试;(次模式 会保存30天,30天后需 再次操作)..._res://ieframe.dll

Oracle12c 容器数据库详解_oracle fcpsb-程序员宅基地

文章浏览阅读1.9w次。如果是非生产环境,容器数据库CDB 这功能还可以。但是,如果生产使用CDB,也可以,但是感觉很鸡肋,一般上生产的,最好为非CDB 数据库。1, CDB 容器数据2, PDB 可插拔式数据库3,根容器 CDB$ROOT4, 种子可插拔数据库 PDB$SEED5, 克隆,通过 种子库(pdb$seed 不能修改,只读),pdb库,非CDB库,创建可插拔数据库。6,非CDB,ORACLE12C 没有创建..._oracle fcpsb

php simplexml_PHP的SimpleXML处理-程序员宅基地

文章浏览阅读347次。PHP版本5引入了SimpleXML,SimpleXML是一种用于读写XML的新应用程序编程接口(API)。 在SimpleXML中,表达式如下: $doc->rss->channel->item->title 从文档中选择元素。 只要您对文档的结构有所了解,这些表达式就很容易编写。 但是,如果您不确切知道感兴趣的元素出现在何处(例如Docbook,HTML和类似的叙..._php simplexml

php超链接颜色,html超链接默认字体颜色怎么清除-程序员宅基地

文章浏览阅读594次。方法:1、在body中使用link、alink、vlink属性来设置其他颜色,例“”。2、先使用“:link”、“:visited”、“:active”选择器选中a元素;然后使用color属性设置其他颜色。本教程操作环境:windows7系统、CSS3&&HTML5版、Dell G3电脑。为了突出超链接,超链接文字通常采用与其他文字不同的颜色,超链接文字的下端还会加一条横线。网页的..._php的href颜色

SourceInsight 4.0使用说明_cppcheck在sourceinsight上使用-程序员宅基地

文章浏览阅读1.8k次,点赞3次,收藏31次。Source Insight是一个面向项目开发的程序编辑器和代码浏览器,它拥有内置的对C/C++,C#和Java等程序的分析。能分析源代码并在工作的同时动态维护它自己的符号数据库,并自动显示有用的上下文信息。Options->Key Assignments 进入快捷键设置界面,找到自己想要设置的命令。如下图所示选择“Exit”命令,可以看到系统默认的快捷键是“Alt+F4”。_cppcheck在sourceinsight上使用

nginx 开启websocket支持_elang启用websocket-程序员宅基地

文章浏览阅读1.8k次。WebSocket是目前比较成熟的技术了,WebSocket协议为创建客户端和服务器端需要实时双向通讯的webapp提供了一个选择。其为HTML5的一部分,WebSocket相较于原来开发这类app的方法来说,其能使开发更加地简单。大部分现在的浏览器都支持WebSocket,比如Firefox,IE,Chrome,Safari,Opera,并且越来越多的服务器框架现在也同样支持WebSocket。在实际的生产环境中,要求多个WebSocket服务器必须具有高性能和高可用,那么WebSocket协议就需要_elang启用websocket

推荐文章

热门文章

相关标签