CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)A~E

比赛连接：Dashboard - CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) - Codeforces

 A. Beautiful Sequence

题意：

 t(1≤t≤500)组测试每组给定大小为n(1≤n≤100) 的序列，判断它是否存在一个子序列是好序列。一个序列是好序列当且仅当至少存在一个ai=i。

思路：

考虑到从原序列抽取一些数形成的子序列下标i只可能比原来小，如果原来存在一个i>=a[i]，存在一种选择方法使得子序列下标i减小到a[i]，否则不可能构造出来。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<iomanip>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const db pi=acos(-1.0);
const int N=110,M=2*N;
int a[N];
inline void solve()
{
	int n;
	cin>>n;
	rep(i,1,n+1) cin>>a[i];
	rep(i,1,n+1){
		if(i>=a[i]){
			cout<<"YES"<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

B. Candies

题意：

 t(1≤t≤1e4)组测试每组给定n(2≤n≤1e9) ，有两种操作，第一种是将x变为2*x-1，第二种是将x变为2*x+1，输出将1变为n的操作序列，最多不超过40次。

思路：

操作后的数只能变为奇数，故n为偶数时一定不能构造。n为奇数，考虑如何使n变为1，如果把n写为二进制形式，第一种逆操作相当于将n加一再右移一位，第二种为将n减一再右边移动一位，所以可以找到一种操作：每一次看n的最后两位，如果是11做第二种操作，这样就除去了最后一位，如果是01做第一种操作（不能做第二种操作，因为过程中不能出现偶数）。n的最大是1e9，最多30位，一定符合要求。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<iomanip>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const db pi=acos(-1.0);
const int N=40,M=2*N;
int a[N],b[N];
inline void solve()
{
	int n;
	cin>>n;
	if(n&1){
		int len=0,sz=0;
		while(n){
			a[++len]=n&1;
			n>>=1;
		}
		cout<<len-1<<endl;
		rep(i,1,len){
			if(a[i+1]) b[++sz]=2;
			else b[++sz]=1,a[i+1]=1; 
		}
		per(i,sz,0) cout<<b[i]<<" ";
		cout<<endl;
	}else cout<<-1<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

C. Make It Permutation

题意：

给定一个序列，可以进行两种操作，删除一个元素，花费为c，添加一个元素，花费为d，求使序列变为一个非空排列的最小花费。

思路：

因为排列不会存在重复元素，遇到重复元素一定要删除。将处理后的数组排序，考虑构造出1~a[i]的排列，删除后面的元素的花费，所有情况取最小值。注意将数组删除为空再补1的情况也要算。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<iomanip>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const db pi=acos(-1.0);
const int N=1e5+10,M=2*N;
int a[N],len;
inline void solve()
{
	len=0;
	set<int>st;
	int n,c,d,x;
	LL ans=0;
	cin>>n>>c>>d;
	rep(i,1,n+1){
		cin>>x;
		if(st.count(x)) ans+=c;
		else st.insert(x),a[++len]=x;
	}
	sort(a+1,a+1+len);
	LL mi=1e18,tot=0;
	rep(i,1,len+1){
		tot+=a[i]-a[i-1]-1;
		mi=min(mi,tot*d+(LL)(len-i)*c);
	}
	mi=min(mi,(LL)len*c+d);
	cout<<ans+mi<<endl;
}
int main()
{
//	#ifndef ONLINE_JUDGE
//		freopen("1.in","r",stdin);
//		freopen("1.out","w",stdout);
//	#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

D. Climbing the Tree

题意：

一个蜗牛爬树，树的高度为h，蜗牛每天爬a，下降b（a>b），从高度0花费n天爬上高度h。现在不知道h的值，有两种事件，事件1是给定a,b,n，需判断当前事件是否和前面的冲突；时间2是给定a,b，判断是否能根据当前信息求出确切的n。

思路：

先寻找a,b,h,n的关系，因为最后一次距离顶端小于等于a可以直接上去，考虑爬高度h-a的情况，显然需要\left \lceil \frac{h-a}{a-b} \right \rceil天，最后再花一天爬上h，总天数为\left \lceil \frac{h-a}{a-b} \right \rceil+1

对于事件1，有：

 \left \lceil \frac{h-a}{a-b} \right \rceil+1=n

于是可以根据a,b,n的值算出h的下界和上界，分别用lh和rh表示：

lh=(n-2)(a-b)+a+1

rh=(n-1)(a+b)+a

将lh和rh和前面的取交集，如果为空说明不合法，否则合法。

 对于事件2，根据当前lh和rh可以根据上式计算出n，n唯一则说明有解，否则无解。

注意h<=a,n=1的边界情况。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<iomanip>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const db pi=acos(-1.0);
const int N=1e5+10,M=2*N;
int n;
void cal(int a,int b,LL &lh,LL &rh)
{
	if(n==1){
		lh=1,rh=a;
		return;
	}
	LL t=1ll*(n-2)*(a-b)+a;
	lh=t+1,rh=t+a-b;
}
LL calc(int a,int b,LL h)
{
	if(h<=a) return 1;
	LL res=(h-a)/(a-b);
	if((h-a)%(a-b)) res+=2;
	else res+=1;
	return res;
}
inline void solve()
{
	LL lh=-1,rh=1e18;
	int q;
	cin>>q;
	rep(_,0,q){
		int op,a,b;
		cin>>op>>a>>b;
		if(op==1){
			cin>>n;
			if(_){
				LL l,r;
				cal(a,b,l,r);
				if(l>rh||r<lh) cout<<0<<" ";
				else cout<<1<<" ",lh=max(lh,l),rh=min(rh,r);
			}else{
				cout<<1<<" ";
				cal(a,b,lh,rh);
			}
			//cout<<lh<<" "<<rh<<endl;
		}else{
			if(lh==-1){
				cout<<-1<<" ";
				continue; 
			}
			LL n1=calc(a,b,lh),n2=calc(a,b,rh);
			if(n1==n2) cout<<n1<<" ";
			else cout<<-1<<" ";
		}
	}
	cout<<endl;
}
int main()
{
//	#ifndef ONLINE_JUDGE
//		freopen("1.in","r",stdin);
//		freopen("1.out","w",stdout);
//	#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

E. Monsters

题意：

给定一个n个点，m条边的无向无环图，每个点都有一个怪物对应一个危险值，能打败某个点的怪物当且仅当打败的怪物数大于等于危险值。开始选择一个点出发，可以通过一个点需要能打败该点的怪物，判断能否打败所有怪物。

n, m (1≤n,m≤2e5)

思路：

本题官方给出了最暴力的做法：找到每一个ai=0的点做扩散，每一次扩散判断是否能扩展到所有点。虽然直觉上会超时，但是可以证明这样做复杂度为O(n*log(n)*log(n))。

相比官方做法更容易想到用并查集维护连续可走的块。先将危险值从小到大排序，需要一个数组来记录一个集合是否被选择（是否走过），每一次扩散都将危险值大的点并到危险值小的点，维护集合大小，最后合法的结果是一定只有一个根节点。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include<bitset>
#include<iomanip>
#include<list> 
#include <algorithm>
#define pii pair<int,int>
#define pll pair<LL,LL>
#define pil pair<int,LL>
#define pli pair<LL,int>
#define pdd pair<db,db>
#define se second 
#define fi first
#define endl '\n'
#define rep(i,a,b) for (register int i=a;i<b;++i)
#define per(i,a,b) for (register int i=a;i>b;--i)
#define MEM(a,x) memset(a,x,sizeof(a))
#define all(x) (x).begin(),(x).end()
#define M(x) ((x)%MOD)
#define db double
#define eps 1e-9
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
const int MOD=1e9+7;
const db pi=acos(-1.0);
const int N=2e5+10,M=2*N;
pii p[N];
int h[N],e[M],ne[M],idx,s[N],d[N],ok[N],vis[N],sz[N];
void add(int a,int b)
{
	e[++idx]=b,ne[idx]=h[a],h[a]=idx;
}
int find(int x)
{
	if(x==s[x]) return s[x];
	return s[x]=find(s[x]);
}
inline void solve()
{
	idx=0;
	MEM(h,0);
	int n,m;
	cin>>n>>m;
	rep(i,1,n+1) cin>>p[i].fi,p[i].se=i,s[i]=i,ok[i]=0,vis[i]=0,sz[i]=1;
	sort(p+1,p+1+n);
	rep(i,0,m){
		int a,b;
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	rep(_,1,n+1){
		int u=p[_].se;
		if(p[_].fi==0) ok[u]=1;
		vis[u]=1;
		for(int i=h[u];i;i=ne[i]){
			int v=e[i];
			if(!vis[v]) continue;
			u=find(u),v=find(v);
			if(sz[v]>=p[_].fi&&ok[v]) ok[u]=1;
			if(u!=v){
				sz[u]+=sz[v];
				s[v]=u;
			}
		}
	}
	if(!ok[find(1)]){
		cout<<"NO"<<endl;
		return;
	}
	rep(i,2,n+1) if(find(i)!=find(1)){
		cout<<"NO"<<endl;
		return;
	}
	cout<<"YES"<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _=1;
	cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

GPT-3：大语言模型小样本学习

GPT-3：大语言模型小样本学习

论文标题&#xff1a;Language Models are Few-Shot Learners论文链接&#xff1a;https://arxiv.org/abs/2005.14165论文来源&#xff1a;OpenAI一、概述自然语言处理已经从学习特定任务的表示和设计特定任务的架构转变为使用任务无关的预训练和任务无关的架构。这种转变导致了…
阅读更多...
Python - Huffman Tree 霍夫曼树实现与应用

Python - Huffman Tree 霍夫曼树实现与应用

目录 一.引言 二.Huffman Tree 理论 1.定义 2.结构 3.构造 三.Huffman Tree 实现 1.生成霍夫曼树 2.编码霍夫曼编码 3.解码霍夫曼编码 4.霍夫曼树编码解码实践 四.总结 一.引言 上篇 Word2vec 的文章中指出每次计算词库 N 个单词的 Softmax 计算量很大&#xff0c;…
阅读更多...
办公工具-latex

办公工具-latex

一、排版总论 1.1 缺省权力 ​ 首先&#xff0c;最重要最需要强调的是&#xff0c;排版是一个信息量极大的工程。字体&#xff0c;格式&#xff0c;对齐方式&#xff0c;页眉页脚&#xff0c;都只是排版的冰山一角&#xff0c;可以说&#xff0c;一个人是没有办法完全控制一个…
阅读更多...
JVM 运行时数据区概述及线程

JVM 运行时数据区概述及线程

当我们通过前面的&#xff1a;类的加载 --> 验证 --> 准备 --> 解析 --> 初始化&#xff0c;这几个阶段完成后&#xff0c;就会用到执行引擎对我们的类进行使用&#xff0c;同时执行引擎将会使用到我们运行时数据区。 运行时数据区结构 内存概念&#xff1a; 内存…
阅读更多...
leetcode：只出现一次的数字 Ⅲ（详解）

leetcode：只出现一次的数字 Ⅲ（详解）

前言&#xff1a;内容包括&#xff1a;题目&#xff0c;代码实现&#xff0c;大致思路&#xff0c;代码解读 题目&#xff1a; 给你一个整数数组 nums&#xff0c;其中恰好有两个元素只出现一次&#xff0c;其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任…
阅读更多...
Qt界面编程（三）—— 父子关系、对象树、信号和槽（自定义信号和槽、Qt5与Qt4的写法）

Qt界面编程（三）—— 父子关系、对象树、信号和槽（自定义信号和槽、Qt5与Qt4的写法）

一、Qt按钮小程序 1. 按钮的创建和父子关系 在Qt程序中&#xff0c;最常用的控件之一就是按钮了&#xff0c;首先我们来看下如何创建一个按钮&#xff1a; #include <QPushButton>QPushButton * btn new QPushButton; //设置父亲btn->setParent(this);//设置文字b…
阅读更多...
接口测试-postman使用总结

接口测试-postman使用总结

一、为何使用postman postman是一款简单高效的接口测试工具&#xff0c;能够很方便发送接口请求&#xff0c;易于保存接口请求脚本&#xff0c;postman提供接口响应数据比对功能&#xff0c;可以设置预期结果作断言&#xff0c;还能把测试用例放在一个集合中批量执行&#xff…
阅读更多...
【JavaWeb】9—监听器

【JavaWeb】9—监听器

⭐⭐⭐⭐⭐⭐ Github主页&#x1f449;https://github.com/A-BigTree 笔记链接&#x1f449;https://github.com/A-BigTree/Code_Learning ⭐⭐⭐⭐⭐⭐ 如果可以&#xff0c;麻烦各位看官顺手点个star~&#x1f60a; 如果文章对你有所帮助&#xff0c;可以点赞&#x1f44d;…
阅读更多...
torchvision.transforms 常用方法解析（含图例代码以及参数解释）

torchvision.transforms 常用方法解析（含图例代码以及参数解释）

本文代码和图片完全源于 官方文档: TRANSFORMING AND AUGMENTING IMAGES 中的 Illustration of transforms&#xff0c;参数介绍源自函数对应的官方文档。 代码中的变换仅仅使用了最简单的参数&#xff1a;pad&#xff0c;size 等&#xff0c;这里展现的只是简单的变换&#xf…
阅读更多...
C/C++每日一练(20230408)

C/C++每日一练(20230408)

目录 1. 删除无效的括号 &#x1f31f;&#x1f31f;&#x1f31f; 2. 合并K个升序链表 &#x1f31f;&#x1f31f;&#x1f31f; 3. 四数之和 &#x1f31f;&#x1f31f; &#x1f31f; 每日一练刷题专栏 &#x1f31f; Golang每日一练 专栏 Python每日一练 专栏 …
阅读更多...
SQL Server用户定义的函数（UDF）使用详解

SQL Server用户定义的函数（UDF）使用详解

SQL Server用户定义的函数一、背景知识1.1、用户定义函数的优点1.2、函数类型1.3、指引1.4、函数中的有效语句1.5、架构绑定函数1.6、指定参数二、创建用户定义函数2.1、限制和权限2.2、标量函数示例&#xff08;标量 UDF&#xff09;2.3、表值函数示例2.3.1、内联表值函数 &am…
阅读更多...
项目管理软件调度的优势有哪些？

项目管理软件调度的优势有哪些？

如果没有项目时间表&#xff0c;要跟踪在何时以及必须使用哪些资源之前需要完成什么是非常困难和耗时的。时间表是一个时间表&#xff0c;它概述了所有项目任务和需要完成的里程碑的开始和结束日期。 项目进度中的任务将具有依赖性&#xff0c;这意味着如果完成数据在一项活动上…
阅读更多...
Redis7高级之Redlock算法和Redisson的使用（十）

Redis7高级之Redlock算法和Redisson的使用（十）

10.1 Redlock 红锁算法 1.解决手写分布式锁的单点故障问题 Redis 提供了 Redlock 算法&#xff0c;用来实现基于多个实例的分布式锁锁变量由多个实例维护&#xff0c;即使有实例发生了故障&#xff0c;锁变量仍然是存在的&#xff0c;客户端还是可以完成锁操作Redlock算法是实…
阅读更多...
计算机网络考试复习——第一章 1.5 1.6

计算机网络考试复习——第一章 1.5 1.6

1.5 计算机网络的类别 1.5.1计算机网络的定义&#xff1a; 系统集合&#xff0c;连接起来&#xff0c;协议工作&#xff0c;资源共享 计算机网络主要是由一些通用的、可编程的硬件互连而成的&#xff0c;而这些硬件并非专门用来实现某一特定目的&#xff08;例如&#xff0…
阅读更多...
Java源码（一）ThreadLocal、SpringBoot Jar 启动原理

Java源码（一）ThreadLocal、SpringBoot Jar 启动原理

思维导图 一、ThreadLocal 1.场景 项目采用SSMShiro登录认证&#xff0c;改造需求如下&#xff1a; 后台管理员登录需要限制&#xff0c;同一个用户的不同IP需要通过过自定义验证后才能登录。 2.问题 在完成需求后发现有管理员用户&#xff08;这里就用A&#xff09;通过验…
阅读更多...
Android build.gradle配置详解

Android build.gradle配置详解

Android Studio是采用gradle来构建项目的&#xff0c;gradle是基于groovy语言的&#xff0c;如果只是用它构建普通Android项目的话&#xff0c;是可以不去学groovy的。当我们创建一个Android项目时会包含两个Android build.gradle配置详解文件&#xff0c;如下图&#xff1a; 一…
阅读更多...
区块链3链（TRC ERC BSC）授权持币生息源码

区块链3链（TRC ERC BSC）授权持币生息源码

分享一款3链&#xff08;TRC ERC BSC&#xff09;授权持币生息源码、来自群友投稿的资源、据说是运营级的。简单的看了下没有问题什么大问题、有能力的可以拿来二开其他的模板。 搭建非常简单&#xff0c;教程就不写了、环境NGINX1.2PHP7.2MYSQL5.6TP默认伪静态 此类源码需要…
阅读更多...
【Python】数学 - 用 Python 自动化求解函数 f(x) 的值

【Python】数学 - 用 Python 自动化求解函数 f(x) 的值

目录 1、缘起 2、求以下函数的值 3、代码清单 3.1、求解 f(0)、f(1)、 f(​编辑)、f(​编辑) 3.2、求解 g(0)、g(1)、g(​编辑)、g(​编辑) 3.3、求解 h(0)、h(1)、h(​编辑)、h(​编辑) 4、总结 1、缘起 Python 是一种强大的编程语言&#xff0c;它具有广泛的应用领域。…
阅读更多...
Python模拟星空

Python模拟星空

文章目录前言Turtle基础1.1 Turtle画板1.2 Turtle画笔1.3 Turtle画图1.4 Turtle填色1.5 Turtle写字模拟星空模拟星球浪漫星空尾声前言 Python模拟星空&#xff0c;你值得拥有&#xff01;uu们一周不见啦&#xff0c;本周博主参考网上大佬们的星空&#xff0c;给大家带来了属于…
阅读更多...
C语言操作符优先级

C语言操作符优先级

在平时写代码时&#xff0c;经常会用到操作符&#xff0c;但是如果不了解这些操作符的优先级&#xff0c;可能会让程序的执行效果和我们预期的不一样。 例如&#xff1a; int a 2;int b 3;int c 4;//int ret a b * c;//我们想要执行的顺序是ab的值再乘c//如果了解操作符优…
阅读更多...
最新文章

Copyright @ 2022~2023