2020ICPC南京站

这篇具有很好参考价值的文章主要介绍了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的时间。每个烟花有的概率是完美的。求最优策略下最小时间花费。

思路:假设最优策略是每生产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]

接下来三分寻找答案的最小值。文章来源地址https://www.toymoban.com/news/detail-690455.html

#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;
}

到了这里,关于2020ICPC南京站的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (C语言)数据结构算法-病毒感染检测(BF算法&&KMP算法)

    病毒感染检测: 医学研究者最近发现了某些新病毒,得知它们的DNA序列都是环状的。为了快速检测出患者是否感染了相应的病毒,研究者将患者的DNA和病毒的DNA均表示成一些字母组成的字符串序列,然后检测某种病毒DNA序列是否在患者的DNA序列中出现过,如果出现过,则此人

    2024年02月08日
    浏览(49)
  • 数据结构——排序算法(C语言)

    本篇将详细讲一下以下排序算法: 直接插入排序 希尔排序 选择排序 快速排序 归并排序 计数排序 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某写的大小,按照递增或递减0排列起来的操作。 稳定性的概念 假定在待排序的记录序列中,存在多个

    2024年02月08日
    浏览(66)
  • C语言数据结构与算法

    冒泡排序 例题 顺序表下的 冒泡排序 注意:冒泡排序 稳定,最多执行n(n-1)/2次 选择排序不稳定,平均比较次数n(n-1)/2 直接插入排序,是在有序基础上,速度最快且稳定的排序方法。 希尔排序是 不稳定的 顺序查找 二分查找(非递归) 二分查找(递归) 数组 链表 查询 快 慢

    2024年02月06日
    浏览(74)
  • 南京邮电大学算法与设计实验二:贪心算法(最全最新,与题目要求一致)

    三、实验原理及内容 实验原理: 1 、用贪心法实现求两序列的一般背包问题。要求掌握贪心法思想在实际中的应用,分析一般背包的问题特征,选择算法策略并设计具体算法,编程实现贪心选择策略的比较,并输出最优解和最优解值。 2 、用贪心法求解带时限的 ( 单位时间

    2024年02月05日
    浏览(51)
  • 南京邮电大学汇编语言程序设计实验一(汇编语言语法练习与代码转换)

    排除语法错误:给出的是一个通过比较法完成8位二进制数转换成十进制数送屏幕显示功能的汇编语言源程序,但有很多语法错误。要求实验者按照原样对源程序进行编辑,汇编后,根据TASM给出的信息对源程序进行修改,知道没有语法错误为止。然后进行链接,并执行相应可

    2024年02月08日
    浏览(62)
  • C语言 数据结构--栈 括号匹配算法

    今天这一期使用栈来完成括号匹配算法 ① 栈结构 ② 初始化栈 ③ 入栈 ④ 出栈 ⑤ 判断栈是否为空 ⑤ 括号匹配 完整代码: 结果: (1)括号序列为char str[]={\\\'(\\\',\\\'{\\\',\\\'[\\\',\\\']\\\',\\\'}\\\',\\\')\\\'}; (2)括号序列为char str1[]={\\\'{\\\',\\\'(\\\',\\\'}\\\',\\\']\\\'};    

    2024年02月05日
    浏览(54)
  • C语言 数据结构与算法 I

    因为之前写算法都是用C++,也有了些C++基础,变量常量数据类型就跳过去吧。 首先是环境,学C++时候用Clion,C语言也用它写吧~ 新建项目,选C执行文件,语言标准。。。就先默认C99吧,反正是测试环境,应该问题不大 直接运行一手 嗯。。JB家的新UI。。真是。。。。。。。一

    2024年02月09日
    浏览(42)
  • 数据结构与算法——排序(C语言实现)

    ✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅✅ ✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨ 🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿🌿 🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟🌟 🌟🌟 追风赶月莫停留 🌟🌟 🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀🍀 🌟🌟 平芜尽处是春山

    2024年04月09日
    浏览(59)
  • 数据结构和算法——用C语言实现所有图状结构及相关算法

    本文所有代码均在仓库中,这是一个完整的由纯C语言实现的可以存储任意类型元素的数据结构的工程项目。 首先是极好的工程意识,该项目是一个中大型的CMake项目,结构目录清晰,通过这个项目可以遇见许多工程问题并且可以培养自己的工程意识。 其次是优秀的封装性(

    2024年02月06日
    浏览(222)
  • 【学习笔记】数据结构算法文档(类C语言)

    1.1.1 线性表的顺序存储表示 1.1.2 顺序表中基本操作的实现 1.1.2.1 初始化 1.1.2.2 取值 1.1.2.3 查找 1.1.2.4 插入 1.1.2.5 删除 1.1.2.6 计数 1.2.1 单链表的定义和表示 ★ 关于结点 1.2.2 单链表基本操作的实现 1.2.2.1 初始化 1.2.2.2 取值 1.2.2.3 查找 1.2.2.4 插入 1.2.2.5 删除 1.2.2.6 前插法创建单

    2024年02月07日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包