2020ICPC南京站

K

K Co-prime Permutation

题意:给定n和k,让你构造n的排列,满足gcd(pi, i)=1的个数为k。

思路:因为x和x-1互质,1和任何数互质,任何数和它本身不互质

当k为奇数时,p1=1,后面k-1个数两两互换

当k为偶数时,后面k个数两两互换

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,k;
int a[N];
void solve()
{cin>>n>>k;if(k==0){cout<<-1<<'\n';return ;}int cnt=0;for(int i=1;i<=n;i++) a[i]=i;if(k&1){cnt=1;for(int i=2;i<=n&&cnt<k;i++){if(cnt&1) a[i]=i+1;else a[i]=i-1;cnt++;}}else{for(int i=1;i<=n&&cnt<k;i++){if(cnt%2==0) a[i]=i+1;else a[i]=i-1;cnt++;}}for(int i=1;i<=n;i++)cout<<a[i]<<" \n"[i==n];
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;
// 	cin>>_t;while(_t--) solve();system("pause");return 0;
}

L

Let's Play Curling

题意:给定n块红色石头,m块蓝色石头的位置。记红色石头的位置为a[i],蓝色石头的位置为b[i]。当红色石头到目标位置c的距离比蓝色所有石头到目标位置的距离都要小时,计一分,找到一个c点可以让红队尽可能多赢,输出红队尽可能多赢的次数。

思路:在两块蓝色石头之间一定存在一个位置满足条件,得分为两个蓝色石头之间红色石头的个数。

即求两个蓝色石头之间最多有几个红色石头。

排序后枚举蓝色石头的位置p,二分红色石头找到上下界。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int n,m;
void solve()
{cin>>n>>m;vector<int>a,b;for(int i=1;i<=n;i++){int x;cin>>x;a.push_back(x);}for(int i=1;i<=m;i++){int x;cin>>x;b.push_back(x);}b.push_back(0);b.push_back(1e9+10);sort(a.begin(),a.end());sort(b.begin(),b.end());int ans=0;for(int i=0;i<=m;i++){int l=upper_bound(a.begin(),a.end(),b[i])-a.begin();int r=lower_bound(a.begin(),a.end(),b[i+1])-a.begin();ans=max(ans,r-l);}if(ans==0) cout<<"Impossible\n";else cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

E

Evil Coordinate

题意:初始位置为(0, 0),给定陷阱位置(x, y)和操作字符串。让我们重排列操作字符串使得不陷入陷阱。

思路:设最终位置为(X, Y)若有解则(X, Y)与(x, y)至少有一维坐标不同,我们可以先走不同的那个方向,再走相同的那个方向。所以我们可以将相同操作排在一起,然后枚举UDLR的全排列就可以。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
int x,y;
string s;
int dir[4][2]={0,1,0,-1,-1,0,1,0};
char op[4]={'U','D','L','R'};
map<int,int>cnt;
string ans;
bool check(vector<int>v)
{ans.clear();int X=0,Y=0;for(int i=0;i<4;i++){for(int j=0;j<cnt[v[i]];j++){ans+=op[v[i]];X+=dir[v[i]][0];Y+=dir[v[i]][1];if(X==x&&Y==y) return 0;}}return 1;
}
void solve()
{cin>>x>>y;cin>>s;if(x==0&&y==0){cout<<"Impossible\n";return ;}cnt.clear();for(int i=0;i<s.length();i++)if(s[i]=='U') cnt[0]++;else if(s[i]=='D') cnt[1]++;else if(s[i]=='L') cnt[2]++;else cnt[3]++;vector<int>v={0,1,2,3};bool f=0;do{if(check(v)){f=1;break;}} while (next_permutation(v.begin(),v.end()));if(!f){cout<<"Impossible\n";return ;}else cout<<ans<<'\n';
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

F

Fireworks

题意:小明做一个烟花花费n的时间,点燃所有做好的烟花花费m的时间。每个烟花有p*10^{-4}的概率是完美的。求最优策略下最小时间花费。

思路:假设最优策略是每生产k个再一起点燃,那么释放一次成功的概率为1-(1-p)^k  (p=p*1e-4).

释放几次后得到完美的期望满足几何分布。

几何分布:在n次伯努利试验中, 试验k次才得到第一次成功的概率。详细的说,是:前k-1次皆失败, 第k次成功的概率。 期望E(x)=1/p;(概率论公式,不再赘述)

那么答案为E(x)*(nk+m)= (nk+m) / [1-(1-p)^k]

接下来三分寻找答案的最小值。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define PII pair<int,int>
typedef long long ll;
const int N=1e6+10;
const int inf=0x3f3f3f3f;using namespace std;
double n,m;
double p;
double qmi(double a,int k)
{double ret=1;while(k){if(k&1) ret=ret*a;k>>=1;a=a*a;}return ret;
}
double get(int k)
{double t=1.0-qmi(1.0-p,k);if(t==0) return (double)0x3f3f3f3f;return (k*n*1.0+m)/t;
}
void solve()
{cin>>n>>m>>p;p=p*1e-4;double ans=(double)0x3f3f3f3f3f3f3f3f;int l=1,r=1e9;while(r>l){int lmid=l+(r-l)/3,rmid=r-(r-l)/3;double f1=get(lmid),f2=get(rmid);ans=min(ans,min(f1,f2));if(f1<f2) r=rmid-1;else l=lmid+1;}printf("%.10f\n",ans);
}
signed main()
{//freopen("input.txt","r",stdin);//freopen("output.txt","w",stdout);//ios;int _t=1;cin>>_t;while(_t--) solve();system("pause");return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/119328.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

yum 、rpm、yumdownloader、repotrack 学习笔记

1 Linux 包管理器概述 rpm的使用&#xff1a; rpm -ivh filename.rpm#这列出该packageName&#xff08;包名&#xff09;安装的所有文件列表。 rpm -ql packageName #查询已安装的该packageName的详细信息&#xff0c;包括版本、发布日期等。 rpm -qi packageName #列出该pac…

如何在,Linux中安装Luajit2.*

1.文件下载The LuaJIT Project 2.将下载文件上传到对应的服务器&#xff1a;例如/opt 3.进入对应的文件夹 4.make PREFIX/usr/local&#xff0c;设置安装路径 5.make install&#xff0c;编译安装 6.进入安装目录&#xff0c;cd /usr/local/include/luajit-2.0 7.luajit -v…

【Stable Diffusion安装】支持python3.11 window版

前言 主要的安装步骤是参考B站播放量第一的视频&#xff0c;但是那位阿婆主应该是没有编程经验&#xff0c;只强调使用3.10&#xff0c;而python最新版本是3.11。 理论上来说&#xff0c;只是一个小版本的不同&#xff0c;应该是可以安装成功了。自己摸索了下&#xff0c;挺费…

C++智能指针之weak_ptr(保姆级教学)

目录 C智能指针之weak_ptr 概述 作用 本文涉及的所有程序 使用说明 weak_ptr的常规操作 lock(); use_count(); expired(); reset(); shared_ptr & weak_ptr 尺寸 智能指针结构框架 常见使用问题 shared_ptr多次引用同一数据&#xff0c;会导致两次释放同一内…

ChatGPT在医疗领域可应用于改善与患者的沟通

注意&#xff1a;本信息仅供参考&#xff0c;发布该内容旨在传递更多信息的目的&#xff0c;并不意味着赞同其观点或证实其说法。 自从ChatGPT在2022年末对公众开放以来&#xff0c;OpenAI的这款生成式AI聊天机器人在医疗领域展示出了巨大潜力。它已经通过了美国医学执照考试&a…

Paddle训练COCO-stuff数据集学习记录

COCO-stuff数据集 COCO-Stuff数据集对COCO数据集中全部164K图片做了像素级的标注。 80 thing classes, 91 stuff classes and 1 class ‘unlabeled’ 数据集下载 wget --directory-prefixdownloads http://images.cocodataset.org/zips/train2017.zip wget --directory-prefi…

“媒体+”时代正当时,ATEN以前瞻解决方案助推媒体融合纵深发展

自媒体融合概念提出以来,传统媒体与新媒体融合速度加快,两者的相互结合与优势互补为广电行业发展提供了新的契机,更加多元化、个性化、强互动的“媒体”传播格局已逐渐形成。 “媒体”理念的创建,对于广电行业而言无疑是一种积极的改革创新之举,然而“媒体”的发展也呈现出泛媒…

Python实现自动关键词提取

随着互联网的发展&#xff0c;越来越多的人喜欢在网络上阅读小说。本文将通过详细示例&#xff0c;向您介绍如何使用Python编写爬虫程序来获取网络小说&#xff0c;并利用自然语言处理技术实现自动文摘和关键词提取功能。 1. 网络小说数据抓取 首先&#xff0c;请确保已安装必…

Show that f(z)=1/z is analytic or not

See https://brainly.in/question/21838444

PaddleNLP使用Vicuna

LLaMA 模型 LLaMa 是一个大型语言模型&#xff0c;由 Meta 开源。它的全称是 Large Language Model Meta AI&#xff0c;参数量从 70 亿到 650 亿不等。例如&#xff0c;130 亿参数的 LLaMA 模型在大多数基准上可以胜过参数量达 1750 亿的 GPT-3&#xff0c;而且可以在单块 V1…

HTTP协议初识·中篇

加上目录&#xff0c;会出现导向不正确的情况&#xff0c;可能是bug&#xff0c;目录一长就容易出错&#xff1f; 本篇主要讲解了&#xff1a; 网页分离(网页代码和.c文件分离) html链接跳转 网页添加图片 确认并返回资源类型 填写正文长度属性 添加表单 临时重定向 补充知识&a…

Jdk8 动态编译 Java 源码为 Class 文件(三)

Jdk8 动态编译 Java 源码为 Class 文件 一.JDK版本二.工程介绍1.依赖2.启动类3.配置类&#xff08;用于测试依赖注入&#xff09;4.工具类1.Java 源码文件读取类2.SpringBoot 容器实例管理类 5.测试类1.抽象类2.接口类3.默认抽象实现4.默认接口实现 6.接口类1.测试接口2.类重载…

SpringWeb(SpringMVC)

目录 SpringWeb介绍 搭建 SpringWeb SpringWeb介绍 Spring Web是一个基于 Servlet API 构建的原始 web 框架&#xff0c;用于构建基于MVC模式的Web应用程序。在 web 层框架历经 Strust1&#xff0c;WebWork&#xff0c;Strust2 等诸多产品的历代更选 之后&#xff0c;目前业界普…

QT DAY4

一、使用鼠标时间完成组件的移动 #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include<QDebug> #include<QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widg…

LLMs:OpenAI官方重磅更新——新增GPT-3.5Turbo调和API更新功能

LLMs&#xff1a;OpenAI官方重磅更新——新增GPT-3.5Turbo调和API更新功能 导读&#xff1a;2023年8月22日&#xff0c;OpenAI官方发布&#xff0c;开发者现在可以使用自己的数据来定制适用于其用例的GPT-3.5 Turbo模型。GPT-3.5 Turbo的微调现在已经可用&#xff0c;GPT-4的微…

【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析&#xff1a;首先我们要知道后序遍历数组的最后一个元素必然是根节点&#xff0c;然后根据根节点在中序遍历数组中的…

【LeetCode-中等题】994. 腐烂的橘子

文章目录 题目方法一&#xff1a;bfs层序遍历 题目 该题值推荐用bfs&#xff0c;因为是一层一层的感染&#xff0c;而不是一条线走到底的那种&#xff0c;所以深度优先搜索不适合 方法一&#xff1a;bfs层序遍历 广度优先搜索&#xff0c;就是从起点出发&#xff0c;每次都尝…

Android GB28181客户端开发(1):GB28181协议简介

Android GB28181客户端开发(1):GB28181协议简介 公共安全视频监控联网系统信息传输、交换、控制技术要求(2016版) 源码请翻到文章结尾 介绍GB28181协议 GB28181协议是一种基于IP网络的远程视频监控系统,它定义了设备之间的通信协议和数据格式。GB28181协议的主要特点是支…

【Rust】001-基础语法:变量声明及数据类型

【Rust】001-基础语法&#xff1a;变量声明及数据类型 文章目录 【Rust】001-基础语法&#xff1a;变量声明及数据类型一、概述1、学习起源2、依托课程 二、入门程序1、Hello World2、交互程序代码演示执行结果 3、继续上难度&#xff1a;访问链接并打印响应依赖代码执行命令 三…

Collections和CollectionUtils集合操作

0.引入依赖 <dependency><groupId>org.apache.commons</groupId><artifactId>commons-collections4</artifactId><version>4.4</version> </dependency> 一.Collections用法&#xff1a; 01、排序操作 reverse(List list)…