2023 icpc杭州(M,J,D,G,H)
文章目录
- [M. V-Diagram](https://codeforces.com/gym/104976/problem/M)
- [J. Mysterious Tree](https://codeforces.com/gym/104976/problem/J)
- [D.Operator Precedence](https://codeforces.com/gym/104976/problem/D)
- [G. Snake Move](https://codeforces.com/gym/104976/problem/G)
- [H. Sugar Sweet II](https://codeforces.com/gym/104976/problem/H)
M. V-Diagram
题意:
给一个V图,求一个连续子序列平均值最大的V图
首先,要保证是V字形,最小的和左右两个是一定要保留的,然后,如果某个小的选了,那么选比它大的肯定是提高平均值的,所以把V字形的一边全选了,至于为什么不把另一边也一起选了,是因为,有可能已经选的一边数非常大,而另一边数非常小,那么会拉低平均值,同理,只选另一边,以及选择整个V字形
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=3e5+10;
int a[N];
int n;
void solve() {cin>>n;int minn=2e9;for(int i=1;i<=n;i++) cin>>a[i],minn=min(minn,a[i]);double ans=0;int idx;for(int i=1;i<=n;i++){if(a[i]==minn){idx=i;break;}}double sum=0;for(int i=1;i<=idx+1;i++) sum+=a[i];ans=max(ans,sum/(idx+1));sum=0;for(int i=n;i>=idx-1;i--) sum+=a[i];ans=max(ans,sum/(n-idx+2));sum=0;for(int i=1;i<=n;i++) sum+=a[i];ans=max(ans,sum/n);printf("%.10f\n",ans);
}
signed main() {
// ios::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}
J. Mysterious Tree
题意:
一棵树,可能是链或者菊花,每次询问一条边存在性,确定是链还是菊 花。询问次数⌈n 2⌉+3
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n;
void solve() {cin>>n;if(n%2==0){for(int i=1;i<=n;i+=2){cout<<"? "<<i<<' '<<i+1<<endl;cout.flush();int x;cin>>x;if(x==1){if(i==1){cout<<"? "<<1<<' '<<3<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"? "<<1<<' '<<4<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"! "<<2<<endl;cout.flush();return;}else{cout<<"! "<<1<<endl;cout.flush();return;}}else{cout<<"? "<<2<<' '<<3<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"? "<<2<<' '<<4<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"! "<<2<<endl;cout.flush();return;}}}}else{cout<<"? "<<i<<' '<<1<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"? "<<i<<' '<<2<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"! "<<2<<endl;cout.flush();return;}else{cout<<"! "<<1<<endl;cout.flush();return;}}else{cout<<"? "<<i+1<<' '<<1<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"? "<<i+1<<' '<<2<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"! "<<2<<endl;cout.flush();return;}}}}}}cout<<"! "<<1<<endl;cout.flush();}else{for(int i=1;i<=n-1;i+=2){cout<<"? "<<i<<' '<<i+1<<endl;cout.flush();int x;cin>>x;if(x==1){if(i==1){cout<<"? "<<1<<' '<<3<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"? "<<1<<' '<<4<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"! "<<2<<endl;cout.flush();return;}else{cout<<"! "<<1<<endl;cout.flush();return;}}else{cout<<"? "<<2<<' '<<3<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"? "<<2<<' '<<4<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"! "<<2<<endl;cout.flush();return;}}}}else{cout<<"? "<<i<<' '<<1<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"? "<<i<<' '<<2<<endl;cout.flush();int x;cin>>x;if(x==1){cout<<"! "<<2<<endl;cout.flush();return;}else{cout<<"! "<<1<<endl;cout.flush();return;}}else{cout<<"? "<<i+1<<' '<<1<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"? "<<i+1<<' '<<2<<endl;cout.flush();int x;cin>>x;if(x==0){cout<<"! "<<1<<endl;cout.flush();return;}else{cout<<"! "<<2<<endl;cout.flush();return;}}}}}}cout<<"? "<<n<<' '<<1<<endl;cout.flush();int x;cin>>x;cout<<"? "<<n<<' '<<2<<endl;cout.flush();int y;cin>>y;cout<<"? "<<n<<' '<<3<<endl;cout.flush();int z;cin>>z;if(x==1&&y==1&&z==1){cout<<"! "<<2<<endl;cout.flush();}else {cout<<"! "<<1<<endl;cout.flush();}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}
D.Operator Precedence
题意:
构造2*n个数,满足
( a 1 a_1 a1 a 2 a_2 a2)+( a 3 a_3 a3 a 4 a_4 a4)+…( a 2 n − 1 a_{2n-1} a2n−1 a 2 n a_{2n} a2n)= a 1 a_1 a1( a 2 a_2 a2+ a 3 a_3 a3)( a 4 a_4 a4+ a 5 a_5 a5)…( a 2 n − 2 a_{2n-2} a2n−2+ a 2 n − 1 a_{2n-1} a2n−1) a 2 n a_{2n} a2n
且最终结果不等于0
构造题,往往用最特殊,最简单的,自己构造,肯定简单化而不是复杂化
由于中间全部乘起来,如果存在大于2的数,那么最后会非常非常大,不可控,所以构造若干个1相乘
设序列为x -1 2 -1 2…-1 2 y
所以x * y = -x-(n-2) * 2+2 * y
令y=1,则x=-x-2 * n + 4 +2
得2 * x= 6 - 2 * n
得 x =3 - n
由于所有数都不能为0,所以特判一下n为3的情况,直接抄样例
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int n;
void solve() {cin>>n;if(n==3){cout<<"1 -10 6 6 -10 1"<<endl;return;}cout<<3-n<<' ';for(int i=0;i<(2*n-2)/2;i++){cout<<-1<<' '<<2<<' ';}cout<<1<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}
G. Snake Move
题意:
给定n×m地图上的一条长度为k的贪吃蛇。每次操作可以控制贪吃蛇 移动一步或者缩短一格蛇身。对于每个位置,求从初始状态出发最少需要多少次操作使得蛇头到达该处,平方和模 2 64 2^{64} 264
首先分析一下操作,要么蛇头移动一格,身子往前补充原来的位置,蛇尾的位置就空出来了,要么蛇头不动,直接把蛇尾的位置空出来
假设只有蛇头,那么蛇头到任何位置只要跑一个最简单的最短路就可以了,但是由于每次移动只有蛇尾能空出来,所以对于不是蛇身的位置直接跑最短路,而蛇身的位置不能只是简单的最短路,蛇的第i截是在第k-i次之后才空出来,所以我们需要要取max(k-i+1,dist+1)
注意,模 2 64 2^{64} 264就是unsigned int long long
#include<bits/stdc++.h>
#define endl '\n'
//#define int long long
using namespace std;
typedef pair<int,int>PII;
typedef pair<int,PII>PIII;
const int N=3010;
int n,m,k;
int cnt[N][N];
long long dist[N][N];
char s[N][N];
bool vis[N][N];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
void dijkstra(int a,int b){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){dist[i][j]=1e18;}}dist[a][b]=0;priority_queue<PIII,vector<PIII>,greater<PIII>>heap;heap.push({0,{a,b}});while(heap.size()){auto t=heap.top();heap.pop();int d=t.first,x=t.second.first,y=t.second.second;if(vis[x][y]) continue;vis[x][y]=true;for(int i=0;i<4;i++){int tx=x+dx[i],ty=y+dy[i];if(tx<1||tx>n||ty<1||ty>m) continue;if(vis[tx][ty]||s[tx][ty]=='#') continue;if(dist[tx][ty]>max(d+1,cnt[tx][ty]+1)){dist[tx][ty]=max(d+1,cnt[tx][ty]+1);heap.push({dist[tx][ty],{tx,ty}});}}}
}
void solve() {cin>>n>>m>>k;int sta,stb;for(int i=1;i<=k;i++){int x,y;cin>>x>>y;cnt[x][y]=k-i;if(i==1) sta=x,stb=y;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>s[i][j];}}dijkstra(sta,stb);unsigned int long long ans=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(dist[i][j]==1e18) continue;ans+=dist[i][j]*dist[i][j];}}cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
// cin>>t;while(t--) {solve();}return 0;
}
H. Sugar Sweet II
题意:
n 个数a1,a2…an,有 n 个事件,每个事件形如:如果 ai<bi,则 ai = ai +wi,事件随机顺序发生,问每个数的期望
首先,事件是随机发生的,那么肯定和事件发生的顺序有关,我们来分析一下
如果a[i]<a[b[i]],那么事件一定会发生,因为a[b[i]]只能增不能减,所以不管事件的顺序是怎么样的,a[i]始终小于a[b[i]],所以a[i]必定能加上w[i],也就是说a[i]的期望就是a[i]+w[i]
如果a[i]>=a[b[i]]+w[b[i]],那么事件一定不会发生,因为就算先发生a[b[i]]+w[b[i]]这一事件,a[i]也不可能小于a[b[i]],所以a[i]的期望就是a[i]
如果a[b[i]]<=a[i]<a[b[i]]+w[b[i]],那么a[i]+w[i]这一事件发生当且仅当a[b[i]]+w[b[i]]这一事件发生,具有严格的依赖关系
trick:
如果出现严格的依赖关系,可以建图
如果a[i]+w[i]这一事件发生当且仅当a[b[i]]+w[b[i]]这一事件发生,那么连一条边,b[i]->i,建好图之后,当前事件发生当且仅当它前面的事件全部发生并且顺序必须是按照建图的顺序来的,假设它前面有x-1个事件,那么随便排列,只有一种是可以的,概率就是1/x!
所以我们预处理一下深度就可以了
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=5e5+10,mod=1e9+7;
int a[N],b[N],w[N];
int fac[N],ifac[N];
int dist[N];
int n;
int qmi(int a,int b){int res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}
vector<vector<int>>e(N);
void dfs(int u){for(auto v:e[u]){dist[v]=dist[u]+1;dfs(v);}
}
void solve() {cin>>n;for(int i=1;i<=n;i++) e[i].clear(),dist[i]=0;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) cin>>w[i];for(int i=1;i<=n;i++){if(a[i]<a[b[i]]) dist[i]=1;else if(a[i]>=a[b[i]]+w[b[i]]) dist[i]=0;else e[b[i]].push_back(i);}for(int i=1;i<=n;i++){if(dist[i]==1){dfs(i);}}for(int i=1;i<=n;i++){if(dist[i]==0) cout<<a[i]<<' ';else if(dist[i]==1) cout<<(a[i]+w[i])%mod<<' ';else cout<<((a[i]+w[i]*ifac[dist[i]])%mod+mod)%mod<<' ';}cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;//预处理阶乘以及阶乘的逆元fac[0]=ifac[0]=1;//0的阶乘是1,0的阶乘的逆元也是1for(int i=1;i<N;i++) fac[i]=fac[i-1]*i%mod;//预处理阶乘ifac[N-1]=qmi(fac[N-1],mod-2);//先求出fac[N-1]的逆元,由于(n+1)!=n!*(n+1)==>n!^(-1)=(n+1)!^(-1)*(n+1),所以也可以通过递推得到阶乘的逆元for(int i=N-2;i>=1;i--) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;cin>>t;while(t--) {solve();}return 0;
}
相关文章:
2023 icpc杭州(M,J,D,G,H)
文章目录 [M. V-Diagram](https://codeforces.com/gym/104976/problem/M)[J. Mysterious Tree](https://codeforces.com/gym/104976/problem/J)[D.Operator Precedence](https://codeforces.com/gym/104976/problem/D)[G. Snake Move](https://codeforces.com/gym/104976/probl…...
在CentOS 7上安装Alist
在CentOS 7上安装Alist 的步骤如下: 1. 卸载旧版本 如果你之前安装过旧版本的Docker,可以先卸载它: sudo yum remove docker docker-common docker-snapshot docker-engine2. 安装依赖包 确保你的系统是最新的,并安装必要的依…...

【C/C++】memcpy函数的模拟实现
零.导言 上一篇博客我们学习了memcpy函数,不妨我们现在尝试模拟实现memcpy函数的功能。 一.实现memcpy函数的要点 memcpy函数是一种C语言内存函数,可以按字节拷贝任意类型的数组,因此我们自定义的模拟函数需要两个无类型的指针参数ÿ…...
嵌入式开发之线程互斥
目录 互斥锁初始化-pthread_mutex_init 申请锁-pthread_mutex_lock 释放锁-pthread_mutex_unlock 同步 VS 互斥 临界资源:一次只允许一个任务(进程、线程)访问的共享资源,不允许多个任务同时访问的。 临界区:访问临界区的代码 互斥机制:mutex互斥锁,任务访问临界资…...
JavaScript 变量作用域与函数调用机制:var 示例详解
JavaScript 变量作用域与函数调用机制:var 示例详解 在 JavaScript 中,作用域和闭包是理解变量生命周期和行为的核心概念。通过以下这段代码,我们将详细分析如何在不同的作用域内使用 var 关键字,并解释相关的变量访问规则 代码解…...

Linux(CentOS)安装 JDK
1、下载 JDK 官网:https://www.oracle.com/ 2、上传 JDK 文件到 CentOS,使用FinalShell远程登录工具,并且使用 root 用户登录 3、解压 JDK 创建目录 /export/server mkdir -p /export/server 解压到目录 /export/server tar -zxvf jdk-17…...

AI产品经理实战手册:策略、开发与商业化指南
通过《AI产品经理手册》,将可以了解不同类型的AI,如何将AI整合到产品或业务中,以及支持创建AI产品或将AI集成到现有产品所需的基础设施。熟悉实践管理AI产品开发流程、评估和优化AI模型,以及应对与AI产品相关的复杂伦理和法律问题…...

【大语言模型】ACL2024论文-06 探索思维链COT在多模态隐喻检测中的应用
【大语言模型】ACL2024论文-06 探索思维链COT在多模态隐喻检测中的应用 目录 文章目录 【大语言模型】ACL2024论文-06 探索思维链COT在多模态隐喻检测中的应用目录摘要研究背景问题与挑战如何解决创新点算法模型1. 知识总结模块(Knowledge Summarization Module&…...
Linux之初体验
目录 第1关:1-Linux初体验 第2关:1-Linux常用命令 第3关:1-Linux 查询命令帮助语句 第4关:2--查询命令-locate 第5关:2--查询命令-which/whereis 第6关:2--查询命令-find 第7关:3-Linux文…...

现代化水电管理:Spring Boot在大学城的实践
2相关技术 2.1 MYSQL数据库 MySQL是一个真正的多用户、多线程SQL数据库服务器。 是基于SQL的客户/服务器模式的关系数据库管理系统,它的有点有有功能强大、使用简单、管理方便、安全可靠性高、运行速度快、多线程、跨平台性、完全网络化、稳定性等,非常…...

黑马官网2024最新前端就业课V8.5笔记---HTML篇
Html 定义 HTML 超文本标记语言——HyperText Markup Language。 标签语法 标签成对出现,中间包裹内容<>里面放英文字母(标签名)结束标签比开始标签多 /拓展 : 双标签:成对出现的标签 单标签:只有开…...

GS-Blur数据集:首个基于3D场景合成的156,209对多样化真实感模糊图像数据集。
2024-10-31,由韩国首尔国立大学的研究团队创建的GS-Blur数据集,通过3D场景重建和相机视角移动合成了多样化的真实感模糊图像,为图像去模糊领域提供了一个大规模、高覆盖度的新工具,显著提升了去模糊算法在真实世界场景中的泛化能力…...

Linux下Java的多种方式安装
Linux下Java的多种方式安装 博客: www.lstar.icu 开源地址 Gitee 地址: https://gitee.com/lxwise/iris-blog_parent Github 地址: https://github.com/lxwise/iris-blog_parent 序言 Java是一门面向对象的编程语言,不仅吸收了…...
Android Studio:connect time out
参考:Android Studio:connect time out_android studio connection timed out-CSDN博客...

A014-基于Spring Boot的家电销售展示平台设计与实现
🙊作者简介:在校研究生,拥有计算机专业的研究生开发团队,分享技术代码帮助学生学习,独立完成自己的网站项目。 代码可以查看文章末尾⬇️联系方式获取,记得注明来意哦~🌹 赠送计算机毕业设计600…...

数学期望和联合概率密度
数学期望的定义 数学期望是描述随机变量平均趋势的一个重要统计量。根据随机变量的类型(离散或连续),数学期望的定义有所不同。 离散型随机变量的数学期望: 若离散型随机变量 X X X取值为 x 1 , x 2 , … , x n , … x_1,x_2,\do…...

萤石私有化设备视频平台EasyCVR视频融合平台如何构建农业综合监控监管系统?
现代农业的迅速发展中,集成监控管理系统已成为提高农业生产效率和优化管理的关键工具。萤石私有化设备视频平台EasyCVR,作为一个具有高度可扩展性、灵活的视频处理能力和便捷的部署方式的视频监控解决方案,为农业监控系统的建设提供了坚实的技…...

【MongoDB】Windows/Docker 下载安装,MongoDB Compass的基本使用、NoSQL、MongoDB的基础概念及基础用法(超详细)
文章目录 Windows下载MongoDB Compass使用NoSQL的基本概念MongoDB常用术语MongoDB与RDBMS区别MongoDB的CRUD 更多相关内容可查看 Docker安装MongoDB可查看:Docker-安装MongoDB Windows下载 官网下载地址:https://www.mongodb.com/try/download/communi…...
微信小程序-自定义导航栏
一.自定义导航栏 1.JSON文件中配置"navigationStyle": “custom” "navigationStyle": "custom"2.给导航栏设置轮播图 <swiper class"custom-swiper" indicator-dots autoplay interval"2000"> <swiper-item>…...
vue中强制更新视图
vue3 中强制更新视图 方式 通过 $forceUpdate 与 vue2 相似 import {getCurrentInstance} from vueconst internalInstance getCurrentInstance() //操作数据后更新视图 internalInstance.ctx.$forceUpdate()通过 key 值改变更新 <compName :key"key" />co…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?
Pod IP 的本质与特性 Pod IP 的定位 纯端点地址:Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址(如 10.244.1.2)无特殊名称:在 Kubernetes 中,它通常被称为 “Pod IP” 或 “容器 IP”生命周期:与 Pod …...

论文阅读:LLM4Drive: A Survey of Large Language Models for Autonomous Driving
地址:LLM4Drive: A Survey of Large Language Models for Autonomous Driving 摘要翻译 自动驾驶技术作为推动交通和城市出行变革的催化剂,正从基于规则的系统向数据驱动策略转变。传统的模块化系统受限于级联模块间的累积误差和缺乏灵活性的预设规则。…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
webpack面试题
面试题:webpack介绍和简单使用 一、webpack(模块化打包工具)1. webpack是把项目当作一个整体,通过给定的一个主文件,webpack将从这个主文件开始找到你项目当中的所有依赖文件,使用loaders来处理它们&#x…...
shell脚本质数判断
shell脚本质数判断 shell输入一个正整数,判断是否为质数(素数)shell求1-100内的质数shell求给定数组输出其中的质数 shell输入一个正整数,判断是否为质数(素数) 思路: 1:1 2:1 2 3:1 2 3 4:1 2 3 4 5:1 2 3 4 5-------> 3:2 4:2 3 5:2 3…...

Ray框架:分布式AI训练与调参实践
Ray框架:分布式AI训练与调参实践 系统化学习人工智能网站(收藏):https://www.captainbed.cn/flu 文章目录 Ray框架:分布式AI训练与调参实践摘要引言框架架构解析1. 核心组件设计2. 关键技术实现2.1 动态资源调度2.2 …...