Educational Codeforces Round 161 (Rated for Div. 2)(A~E)

被教育咯

A - Tricky Template 

        题意：

        思路：读题读了半天..可以发现，若对于第i位而言，c_{i} == a_{i} || b_{i} == c_{i}，那么c就一定与模板匹配。否则模板只需要取大写的c_{i}即可。因此若所有的 i，都有c_{i} == a_{i} || b_{i} == c_{i}，那么就不能构造，否则一定可以构造出模板。

        

// Problem: A. Tricky Template
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/0
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	cin >>n;
	string s[3];
	for(int i = 0 ; i < 3; i ++)
		cin >>s[i];
	int cnt1 = 0 , cnt0 = 0;
	for(int i = 0 ; i < n ; i ++){
		if(s[0][i] != s[2][i] && s[1][i] != s[2][i]){//不匹配
			cout <<"YES\n";
			return;
		}
	}	
	cout <<"NO\n";
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

B - Forming Triangles 

        题意：

        思路：显然，需要确定拿的策略：一定要拿两根一样长的木棍和一根比他们短的木棍。因此对a数组进行排序，然后模拟一下就行了。

// Problem: B. Forming Triangles
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/B
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
#define int long long
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
int pre[N];
int sum[N];
void solve() 
{
	cin >> n;
	int a[n + 5];
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}	
	sort(a + 1, a + 1 + n);
	int cnt = 0;
	int ans = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(i == 1 || a[i] == a[i - 1]){
			cnt ++;
		}
		else{
			cnt = 1;
		}
		ans += sum[i - 1] - sum[i - cnt]; 
	}
	cout << ans << endl;
}            
signed main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    for(int i = 0 ; i < N ; i ++){
    	pre[i] = i - 1;
    }
    for(int i = 1 ; i < N ; i ++){
    	sum[i] = sum[i - 1] + pre[i];
    }
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

 C - Closest Cities 

        题意：

        思路：可以发现：若要从a走到b，不可能先往远离 b的地方走，然后再跳到b。因此从a走到b的花费其实就是a直接朝着b走的花费，分别预处理一下向右走和向左走的花费即可。

// Problem: C. Closest Cities
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	cin >> n;
	LL a[n + 5];
	a[0] = -llinf;
	a[n + 1] = llinf;
	for	(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	LL suml[n + 5];
	suml[0] = suml[1] = 0;
	for(int i = 1 ; i <= n ; i ++){
		if(a[i] - a[i - 1] > a[i + 1] - a[i]){
			suml[i + 1] = suml[i] + 1;
		}
		else{
			suml[i + 1] = suml[i] + a[i + 1] - a[i];
		}
	}
	LL sumr[n + 5];
	sumr[n] = 0;
	for(int i = n ; i > 1; i --){
		if(a[i] - a[i - 1] < a[i + 1] - a[i]){
			sumr[i - 1] = sumr[i] + 1;
		}
		else{
			sumr[i - 1] = sumr[i] + a[i] - a[i - 1];
		}		
	}

	int m;
	cin >> m;
	for(int i = 0 ; i < m ; i ++){
		int x , y;
		cin >> x >>y;
		if(x >y){
			cout <<sumr[y] - sumr[x] << endl;
		}
		else{
			cout << suml[y] - suml[x]<<endl;
		}
	}
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

D - Berserk Monsters  

        题意：

        思路:可以发现：在一轮游戏过后，只有死去的怪物的两边的怪物可能会在下一轮死去。因此每一轮游戏，只需要处理可能会死去的那些怪物即可。（第一轮所有都有可能死去）由于涉及到某只怪兽的左右两只怪兽和删除某只怪兽的操作，因此可以用链表来模拟所有怪兽的情况，这样每次删除的花费都是O（1）的。 每只怪兽最多只会形成两只可能死亡的怪兽，因此整体模拟的复杂度应该是O（N）的。

// Problem: D. Berserk Monsters
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}
void solve() 
{
	cin >> n;
	LL a[n + 5] , b[n + 5] , l[n + 5] , r[n + 5];//链表存储
	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 ++){
		l[i] = i - 1;
		r[i] = i + 1;
	}
	l[1] = -1 , r[n] = -1;
	vector<int>v;//当前有效的怪兽
	for(int i = 1 ; i <= n ; i ++)
		v.pb(i);
	vector<int>vis(n + 5 , -1);
	for(int i = 0 ; i < n ; i ++){
		vector<int>die;
		for(auto it : v){
			int sum = 0;
			if(l[it] != -1){
				sum += a[l[it]];
			}
			if(r[it] != -1){
				sum += a[r[it]];
			}
			if(sum > b[it]){
				die.pb(it);
			}
		}
		cout << die.size()<<" ";
		v.clear();
		for(auto it : die){
			vis[it] = i;//第几轮死亡的
		}
		for(auto it : die){
			if(l[it] != -1){
				r[l[it]] = r[it];
				if(vis[l[it]] < i){//未死亡且不在v中
					v.pb(l[it]);
					vis[l[it]] = i;//标记在v中
				}
			}
			if(r[it] != -1){
				l[r[it]] = l[it];
				if(vis[r[it]] < i){
					v.pb(r[it]);
					vis[r[it]] = i;
				}
			}
		}
	}
	cout << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

E - Increasing Subsequences 

        题意：

        思路：可以发现，在考虑空集的情况下，若在当前已有数组的最后加一个最大值，那么整体的方案数就是原来的两倍，而在已有数组的最后加一个最小值，那么方案数就比原来多1。因此本题变成了从原本的1，通过*2 或者 +1 操作来变成X。同样按照二进制模拟就行。

// Problem: E. Increasing Subsequences
// Contest: Codeforces - Educational Codeforces Round 161 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1922/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define pb push_back
#define x first
#define y second 
#define endl '\n'
const LL maxn = 4e05+7;
const LL N = 5e05+10;
const LL mod = 1e09+7;
const int inf = 0x3f3f3f3f;
const LL llinf = 5e18;
typedef pair<int,int>pl;
priority_queue<LL , vector<LL>, greater<LL> >mi;//小根堆
priority_queue<LL> ma;//大根堆
LL gcd(LL a, LL b){
	return b > 0 ? gcd(b , a % b) : a;
}

LL lcm(LL a , LL b){
	return a / gcd(a , b) * b;
}
int n , m;
vector<int>a(N , 0);
void init(int n){
	for(int i = 0 ; i <= n ; i ++){
		a[i] = 0;
	}
}

LL k;
void solve() 
{
	cin >> k;
	vector<int>ans;
	int l = 0 , r = 0;
	//末尾添加最大数 -> 方案数 * 2 
	//末尾添加最小数 -> 方案数 + 1
	vector<int>t;
	while(k){
		if(k & 1){
			t.pb(1);
		}
		else{
			t.pb(0);
		}
		k /= 2;
	}
	for(int i = t.size() - 2 ; i >= 0 ; i --){
		if(t[i] == 1){
			ans.pb(++r);
			ans.pb(--l);
		}
		else{
			ans.pb(++r);
		}
	}
	cout << ans.size() << endl;
	for(auto it :ans){
		cout << it <<" ";
	}	
	cout << endl;
}            
int main() 
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    int t=1;
	cin>>t;
    while(t--)
    {
    	solve();
    }
    return 0;
}

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

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

相关文章

gitgud.io+Sapphire注册账号教程

gitgud.io+Sapphire注册账号教程

gitgud.io是一个仓库&#xff0c;地址 https://gitgud.io/&#xff0c;点进去之后会看到注册页面。 意思是需要通过注册这个Sapphire账户来登录。点击右边的Sapphire&#xff0c;就跳转到Sapphire的登陆页面&#xff0c;点击创建新账号&#xff0c;就进入注册页面。&#xff0…
阅读更多...
中仕公考：国考进面后资格复审需要准备什么?

中仕公考：国考进面后资格复审需要准备什么?

参加国考面试的考生在资格审核阶段需要准备以下材料&#xff1a; 1、本人身份证、学生证或工作证复印件。 2、公共科目笔试准考证复印件。 3、考试报名登记表。 4、本(专)科、研究生各阶段学历、学位证书(应届毕业生没有可以暂时不提供)。 5、报名资料上填写的各类证书材料…
阅读更多...
【webrtc】GCC 7： call模块创建的ReceiveSideCongestionController

【webrtc】GCC 7： call模块创建的ReceiveSideCongestionController

webrtc 代码学习&#xff08;三十二&#xff09; video RTT 作用笔记 从call模块说起 call模块创建的时候&#xff0c;会创建 src\call\call.h 线程&#xff1a; 统计 const std::unique_ptr<CallStats> call_stats_;SendDelayStats &#xff1a; 发送延迟统计 const…
阅读更多...
统计学-R语言-6.1

统计学-R语言-6.1

文章目录 前言参数估计的原理总体、样本和统计量点估计区间估计评价估计量的标准有效性 总体均值的区间估计一个总体均值的估计&#xff08;大样本&#xff09;一个总体均值的估计&#xff08;小样本估计&#xff09; 练习 前言 本篇文章将开始介绍参数估计的相关知识。 参数估…
阅读更多...
本地安装配置禅道BUG管理系统并结合内网穿透实现公网访问管理界面

本地安装配置禅道BUG管理系统并结合内网穿透实现公网访问管理界面

文章目录 前言1. 本地安装配置BUG管理系统2. 内网穿透2.1 安装cpolar内网穿透2.2 创建隧道映射本地服务3. 测试公网远程访问4. 配置固定二级子域名4.1 保留一个二级子域名5.1 配置二级子域名6. 使用固定二级子域名远程 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个…
阅读更多...
《30天自制操作系统》学习笔记（七）

《30天自制操作系统》学习笔记（七）

先体验一下编译仿真方法&#xff1a; 30天自制操作系统光盘代码在下面链接&#xff0c;但是没有编译仿真工具&#xff1a; https://gitee.com/zhanfei3000/30dayMakeOS 仿真工具在下面链接&#xff1a; https://gitee.com/909854136/nask-code-ide 这是一个集成的编译仿真工…
阅读更多...
Docker五部曲之五：通过Docker和GitHub Action搭建个人CICD项目

Docker五部曲之五：通过Docker和GitHub Action搭建个人CICD项目

文章目录 项目介绍Dockerfile解析compose.yml解析MySQL的准备工作Spring和环境变量的交互 GitHub Action解析项目测试结语 项目介绍 该项目是一个入门CICD-Demo&#xff0c;它由以下几部分组成&#xff1a; Dockerfile&#xff1a;用于构建自定义镜像compose.yml&#xff1a;…
阅读更多...
开源免费的可私有化部署的白板excalidraw 详细部署教程

开源免费的可私有化部署的白板excalidraw 详细部署教程

简介 excalidraw 是一款开源免费的虚拟白板&#xff0c;提供一个在线的实时协作白板工具&#xff0c;使用户能够创建简单的图形和图示。 excalidraw 的设计目标是提供一个易于使用的绘图工具&#xff0c;支持团队协作&#xff0c;同时具有跨平台和实时协作的功能。 简单易用&…
阅读更多...
DAY04_Spring—Aop案例引入代理机制

DAY04_Spring—Aop案例引入代理机制

目录 1 AOP1.1 AOP案例引入1.1.1 数据库事务说明 1.2 Spring实现事务控制1.2.1 代码结构如下1.2.2 编辑User1.2.3 编辑UserMapper/UserMapperImpl1.2.4 编辑UserService/UserServiceImpl1.2.5 编辑配置类1.2.6 编辑测试类 1.3 代码问题分析1.4 代理模式1.4.1 生活中代理案例1.4…
阅读更多...
Gitlab添加ssh-key报500错误处理

Gitlab添加ssh-key报500错误处理

Gitlab添加ssh-key报500错误 一、查看日志 发现Errno::Enoent(No such file or derectory -ssh): rootasu1:/home/caixin# tail -f /var/log/gitlab/gitlab-rails/production.log二、分析 根据日志提示&#xff0c;好像是缺少文件或目录&#xff0c;后面有个ssh,难首是依赖s…
阅读更多...
【python】—— 字典

【python】—— 字典

目录 &#xff08;一&#xff09;什么是字典 &#xff08;二&#xff09;字典的基本操作 2.1 创建字典 2.2 查找 key 2.3 新增/修改元素 2.4 删除元素 2.5 遍历字典元素 2.6 取出所有 key 和 value &#xff08;三&#xff09;合法的 key 类型 &#xff08;四&#xff09…
阅读更多...
VUE组件--动态组件、组件保持存活、异步组件

VUE组件--动态组件、组件保持存活、异步组件

动态组件 有些场景可能会需要在多个组件之间进行来回切换&#xff0c;在vue中则使用<component :is"..."> 来实现组件间的来回切换 // App.vue <template><component :is"tabComponent"></component><button click"change…
阅读更多...
登陆提示：不支持你所在的地区，“Openai’s services are not available in your country…”

登陆提示：不支持你所在的地区，“Openai’s services are not available in your country…”

错误 登陆时提示“openai’s services are not available in your country”&#xff0c; 说明&#xff1a;Openai的服务在你的地区不可用解决&#xff1a;先清理下浏览器缓存&#xff0c;然后更换代理节点&#xff0c;开启全局模式&#xff0c;最好用欧美节点&#xff0c;或…
阅读更多...
hyperf 二十一 数据库 模型关系

hyperf 二十一 数据库 模型关系

教程&#xff1a;Hyperf 一 定义关联 根据文档 一对一&#xff1a;Model::hasOne(被关联模型&#xff0c;被关联模型外键&#xff0c;本模型被关联的字段)一对多&#xff1a;Model::hasMany(被关联模型&#xff0c;被关联模型外键&#xff0c;本模型被关联的字段)反向一对多…
阅读更多...
Docker 安装 PHP

Docker 安装 PHP

Docker 安装 PHP 安装 PHP 镜像 方法一、docker pull php 查找 Docker Hub 上的 php 镜像: 可以通过 Sort by 查看其他版本的 php&#xff0c;默认是最新版本 php:latest。 此外&#xff0c;我们还可以用 docker search php 命令来查看可用版本&#xff1a; runoobrunoob:…
阅读更多...
【51单片机】数码管的静态与动态显示（含消影）

【51单片机】数码管的静态与动态显示（含消影）

数码管在现实生活里是非常常见的设备&#xff0c;例如 这些数字的显示都是数码管的应用。 目录 静态数码管&#xff1a;器件介绍&#xff1a;数码管的使用&#xff1a;译码器的使用&#xff1a;缓冲器&#xff1a; 实现原理&#xff1a;完整代码&#xff1a; 动态数码管&#…
阅读更多...
python222网站实战(SpringBoot+SpringSecurity+MybatisPlus+thymeleaf+layui)-热门帖子推荐显示实现

python222网站实战(SpringBoot+SpringSecurity+MybatisPlus+thymeleaf+layui)-热门帖子推荐显示实现

锋哥原创的SpringbootLayui python222网站实战&#xff1a; python222网站实战课程视频教程&#xff08;SpringBootPython爬虫实战&#xff09; ( 火爆连载更新中... )_哔哩哔哩_bilibilipython222网站实战课程视频教程&#xff08;SpringBootPython爬虫实战&#xff09; ( 火…
阅读更多...
WAF攻防相关知识点总结1--信息收集中的WAF触发及解决方案

WAF攻防相关知识点总结1--信息收集中的WAF触发及解决方案

什么是WAF WAF可以通过对Web应用程序的流量进行过滤和监控&#xff0c;识别并阻止潜在的安全威胁。WAF可以检测Web应用程序中的各种攻击&#xff0c;例如SQL注入、跨站点脚本攻击&#xff08;XSS&#xff09;、跨站请求伪造&#xff08;CSRF&#xff09;等&#xff0c;并采取相…
阅读更多...
web前端项目-中国象棋【附源码】

web前端项目-中国象棋【附源码】

中国象棋 【中国象棋】是一款历史悠久、深受人们喜爱的策略类游戏。在Web前端技术中&#xff0c;我们可以使用HTML、CSS和JavaScript等语言来制作一款中国象棋游戏。玩家使用棋子&#xff08;帅/相/士/炮/马/车/炮/卒&#xff09;在棋盘上相互对弈&#xff0c;将对手的“帅”棋…
阅读更多...
python入门，函数的进阶

python入门，函数的进阶

1.函数的多返回值 加上逗号&#xff0c;一个函数每次就能返回多个值 2.函数的多种参数使用形式 1.位置参数 调用函数时根据参数位置来传递参数 就是我们平时写函数时所使用的形式 注意&#xff1a; 传递的参数和定义的参数的顺序以及个数必须一致 2.关键字参数 通过键值…
阅读更多...
最新文章

Copyright @ 2022~2023