Educational Codeforces Round 164 (Rated for Div. 2) A-E

A. Painting the Ribbon

在这里插入图片描述
暴力模拟即可

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
 
void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	vector<int> a(n+5);
	int f=0;
	for(int i=1;i<=n;i++){
		a[i]=f;
		f=(f+1)%m;
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=0) cnt++;
	}
	if(cnt>k) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
 
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// cout.tie(0);
	int t;
	t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

B. Make It Ugly

在这里插入图片描述
思路：显然，当一个数组的开头和结尾不同时，其一定是不好的，我们思考，是否存在其他方式让数组变得不好，自己造几组样例手玩一下就会发现，当数组中存在两个不同的数，并且这两个数相邻，且不等于数组开头/结尾时，这个数组是不好的，所以我们把数组变得不好的方式有三种：
其一是让数组的开头和结尾不同，其二便是让两个不同的数相邻。
按照上述策略进行贪心即可。

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
 
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+5);
	map<int,int> mp;
	for(int i=1;i<=n;i++) cin>>a[i],mp[a[i]]++;
	int cnt=n;
	if(mp.size()==1) {
		cout<<-1<<endl;
		return ;
	}
	int last=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=a[1]){
			cnt=min(cnt,i-last-1);
			last=i;
		}
	}
	cnt=min(cnt,n-last);
	cout<<cnt<<endl;
 
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// cout.tie(0);
	int t;
	t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

C. Long Multiplication

在这里插入图片描述
思路：这种题目一般是具有什么性质，对于给定的两个数，我们容易发现，无论两个数的数位如何交换，其和不会改变，那么令 x + y = c x+y=c x+y=c , x = c − y x=c-y x=c−y,对于给定的 x × y x\times y x×y,我们可以表示为 f = ( c − y ) × y f=(c-y)\times y f=(c−y)×y,容易得到，当 x = c / 2 x=c/2 x=c/2时，整个式子会得到最大值，那么此时的 x x x和 y y y 相等，所以我们想让 f ( x ) f(x) f(x)的值越大，那么 x x x和 y y y的差值就要越小，因此贪心的去构造交换即可。

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
 
void solve()
{
	string a,b;
	cin>>a>>b;
	for(int i=0;i<a.size();i++){
		if(a[i]==b[i]) continue;
		else if(a[i]<b[i]){
			for(int j=i+1;j<a.size();j++){
				if(a[j]<b[j]) swap(a[j],b[j]);
			}
			break;
		}
		else if(a[i]>b[i]){
			for(int j=i+1;j<a.size();j++) if(a[j]>b[j]) swap(a[j],b[j]);
			break;
		} 
	}
	cout<<a<<endl;
	cout<<b<<endl;

}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// cout.tie(0);
	int t;
	t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

D. Colored Balls

在这里插入图片描述
思路：考虑一组的贡献，容易得到，定义一组的总个数为 s u m sum sum，最大值为 m x mx mx, 那么这一组的贡献为 m i n ( m x , ( s u m + 1 ) / 2 ) min(mx,(sum+1)/2) min(mx,(sum+1)/2)，为什么呢，
当除最大值之外的所有值之和小于最大值时，我们为了保证一组内每种颜色的球不超过 1 个，那么至少得分出 m x mx mx组。
当其大于最大值时，贡献为 ( s u m + 1 ) / 2 (sum+1)/2 (sum+1)/2,这样保证是最小的，为什么呢，我们每次将数组中的最大值和次大值减一，最后只会剩下1个或0个，因此向上取整即可。
计算完一组的贡献，我们考虑如何进行 2 n 2^n 2n组，当我们放入 a i a_i ai​时，我们无法确定此时具体的贡献，所以我们很容易想到，对a数组进行从小到大的排序，然后使用 f [ k ] f[k] f[k]表示总和为 k k k时的方案数，因为知道了当前总和，所以我们枚举 a i a_i ai​即可。
具体的方案数则是可以用背包进行维护，有时候对于这种每个数选或是不选从而构成 2 n 2^n 2n级别的题目，则可以考虑背包，同时对于背包问题，当其数据范围过小时，我们是可以用状压去解决背包问题的，即用一个二进制数去枚举当前这一位选或是不选。

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
 
template<const int T>
struct ModInt {
    const static int mod = T;
    int x;
    ModInt(int x = 0) : x(x % mod) {}
    ModInt(long long x) : x(int(x % mod)) {} 
    int val() { return x; }
    ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); }
    ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
    bool operator == (const ModInt &a) const { return x == a.x; };
    bool operator != (const ModInt &a) const { return x != a.x; };
    void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; }
    void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; }
    void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; }
    void operator /= (const ModInt &a) { *this = *this / a; }
    friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); }
    friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); }
    friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod);}
    friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a;}
    friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x;}
    friend istream &operator>>(istream &is, ModInt &t){return is >> t.x;}
 
    ModInt pow(int64_t n) const {
        ModInt res(1), mul(x);
        while(n){
            if (n & 1) res *= mul;
            mul *= mul;
            n >>= 1;
        }
        return res;
    }
    
    ModInt inv() const {
        int a = x, b = mod, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        if (u < 0) u += mod;
        return u;
    }
    
};
using mint = ModInt<998244353>;
 
mint dp[N];
 
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+5);
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a.begin()+1,a.begin()+1+n);
	mint ans=0;
	dp[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=5000;j++){
			if(j<=a[i]) ans+=dp[j]*a[i];
			else ans+=dp[j]*((j+a[i]+1)/2);
		}
		for(int j=5000;j>=a[i];j--) dp[j]+=dp[j-a[i]];//对当前ai去跑背包即可
	}
	cout<<ans<<endl;
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

同时可以将d题改变一下，同样是计算 2 n 2^n 2n组，但每一组的贡献为该组的最大值，计算最后的答案。
这样就将a数组从大到小进行排序，考虑当前 a i a_i ai​对答案的贡献即可。

E. Chain Reaction

在这里插入图片描述
ok又是经典问题
思路：我们考虑 k = 1 k=1 k=1的情况，那么对于每个 a i a_i ai​而言，其只有在 a i > a i − 1 a_i>a_{i-1} ai​>ai−1​时，才会产生贡献，所以整个序列的贡献为： ∑ i = 1 i = n m a x ( 0 , a i − a i − 1 ) \sum_{i=1}^{i=n}max(0,a_i-a_{i-1}) i=1∑i=n​max(0,ai​−ai−1​)
那么我们考虑 k k k 等于任意值的情况，显然为 m a x ( ⌈ a i k ⌉ − ⌈ a i − 1 k ⌉ , 0 ) max(\lceil {a_i\over k} \rceil-\lceil {a_{i-1}\over k} \rceil,0) max(⌈kai​​⌉−⌈kai−1​​⌉,0)
因此对于上述的情况， a i a_i ai​的贡献为+1， a i − 1 a_{i-1} ai−1​的贡献为-1，我们统计每个位置对应的贡献即可。
最后应该如何进行计算呢，我们会发现当 a i a_i ai​处于某个区间时，其 a i k a_i\over k kai​​的值是一定的，所以我们可以枚举这个定值 x x x，从而得到当 a i a_i ai​处于 [ ( x − 1 ) ∗ k + 1 , x ∗ k ] [(x-1)*k+1,x*k] [(x−1)∗k+1,x∗k]，其值是一定的。最后便可以得到答案。

#include <bits/stdc++.h>
 
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
// int mod = 998244353;
const int maxv = 4e6 + 5;
// #define endl "\n"
 
void solve()
{
    int n;
    cin>>n;
    vector<int> a(n+5);
    for(int i=1;i<=n;i++) cin>>a[i];
    int mx=*max_element(a.begin()+1,a.begin()+1+n);
    vector<ll> c(N);
    for(int i=1;i<=n;i++) {
        if(a[i]>a[i-1]) c[a[i]]++,c[a[i-1]]--;//计算每个值对应的贡献
    }
    for(int i=1;i<=mx;i++) c[i]+=c[i-1];//因为我们需要进行区间计算，所以先得算出前缀和
    for(int i=1;i<=mx;i++){
        ll res=0;
        for(int j=1;j<=(mx+i-1)/i;j++){//即枚举上文所说的x，
            res+=j*(c[min(j*i,mx)]-c[(j-1)*i]);
        }
        cout<<res<<" ";
    }
    cout<<endl;
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
	system("pause");
	return 0;
}

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

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

相关文章

ICCV2023人脸识别TransFace论文及代码学习笔记

ICCV2023人脸识别TransFace论文及代码学习笔记

论文链接&#xff1a;https://arxiv.org/pdf/2308.10133.pdf 代码链接&#xff1a;GitHub - DanJun6737/TransFace: Code of TransFace 背景 尽管ViTs在多种视觉任务中展示了强大的表示能力&#xff0c;但作者发现&#xff0c;当应用于具有极大数据集的人脸识别场景时&#…
阅读更多...
Leaflet实现离线地图展示，同时显示地图上的坐标点和热力图

Leaflet实现离线地图展示，同时显示地图上的坐标点和热力图

在实际工作中，因为部署环境的要求，必须使用离线地图，而不是调用地图接口。我们应该怎么解决这种项目呢？ 下面介绍一种解决该问题的方案：Leaflet+瓦片地图 一、Leaflet Leaflet 是一个开源并且对移动端友好的交互式地图 JavaScript 库。 它大小仅仅只有 42 KB of JS, 并且拥…
阅读更多...
opencv图片绘制图形-------c++

opencv图片绘制图形-------c++

绘制图形 #include <opencv2/opencv.hpp> #include <opencv2/core.hpp> #include <filesystem>bool opencvTool::drawPolygon(std::string image_p, std::vector<cv::Point> points) {cv::Mat ima cv::imread(image_p.c_str()); // 读取图像&#xf…
阅读更多...
如何调节电脑屏幕亮度？让你的眼睛更舒适！

如何调节电脑屏幕亮度？让你的眼睛更舒适！

电脑屏幕亮度的调节对于我们的视力保护和使用舒适度至关重要。不同的环境和使用习惯可能需要不同的亮度设置。可是如何调节电脑屏幕亮度呢&#xff1f;本文将介绍三种不同的电脑屏幕亮度调节方法&#xff0c;帮助您轻松调节电脑屏幕亮度&#xff0c;以满足您的需求。 方法1&…
阅读更多...
C++必修：从C到C++的过渡(下）

C++必修：从C到C++的过渡(下）

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;C学习 贝蒂的主页&#xff1a;Betty’s blog 1. 缺省参数 1.1. 缺省参数的使用 缺省参数是声明或定义函数时为函数的参数指定…
阅读更多...
直接插入排序与希尔排序的详解及对比

直接插入排序与希尔排序的详解及对比

目录 1.直接插入排序&#xff08;至少有两个元素才可以使用&#xff09; 排序逻辑 B站动画演示&#xff1a;直接插入排序 逻辑转为代码&#xff1a; 稳定性&#xff1a;稳定 时间复杂度&#xff1a;O(N^2) 空间复杂度&#xff1a;O(1) 应用场景 2.希尔排序&#xff08;对…
阅读更多...
VUE父组件向子组件传递值

VUE父组件向子组件传递值

创作灵感 最近在写一个项目时&#xff0c;遇到了这样的一个需求。我封装了一个组件&#xff0c;这个组件需要被以下两个地方使用&#xff0c;一个是搜索用户时用到&#xff0c;一个是修改用户信息时需要用到。其中&#xff0c;在搜索用户时&#xff0c;可以根据姓名或者账号进…
阅读更多...
C++之STL-String

C++之STL-String

目录 一、STL简介 1.1 什么是STL 1.2 STL的版本 1.3 STL的六大组件 ​编辑 1.4 STL的重要性 二、String类 2.1 Sting类的简介 2.2 string之构造函数 2.3 string类对象的容量操作 2.3.1 size() 2.3.2 length() 2.3.3 capacity() 2.3.4 empty() 2.3.5 clear() 2.3.6…
阅读更多...
【Unity】苹果(IOS)开发证书保姆级申请教程

【Unity】苹果(IOS)开发证书保姆级申请教程

前言 我们在使用xcode出包的时候&#xff0c;需要用到iOS证书(.p12)和描述文件(.mobileprovision) 开发证书及对应的描述文件用于开发阶段使用&#xff0c;可以直接将 App 安装到手机上&#xff0c;一个描述文件最多绑定100台测试设备 1.证书管理 进入网站Apple Developer &…
阅读更多...
uni-appH5修改端口号

uni-appH5修改端口号

阅读更多...
从虚拟化走向云原生，红帽OpenShift“一手托两家”

从虚拟化走向云原生，红帽OpenShift“一手托两家”

汽车行业已经迈入“软件定义汽车”的新时代。吉利汽车很清醒地意识到&#xff0c;只有通过云原生技术和数字化转型&#xff0c;才能巩固其作为中国领先汽车制造商的地位。 和很多传统企业一样&#xff0c;吉利汽车在走向云原生的过程中也经历了稳态业务与敏态业务并存带来的前所…
阅读更多...
视频美颜SDK原理与实践：从算法到应用

视频美颜SDK原理与实践：从算法到应用

当下&#xff0c;从社交媒体到视频通话&#xff0c;人们越来越依赖于视频美颜功能来提升自己的形象。而视频美颜SDK作为支撑这一技术的重要工具&#xff0c;其原理和实践至关重要。 一、什么是视频美颜SDK&#xff1f; 视频美颜SDK是一种软件开发工具包&#xff0c;用于集成到…
阅读更多...
FloodFill算法---DFS

FloodFill算法---DFS

目录 floodfill算法概念&#xff1a; 算法模板套路&#xff1a; 例题1&#xff1a;图像渲染 例题2&#xff1a;岛屿数量 例题3&#xff1a;岛屿的最大面积 例题4&#xff1a;被围绕的区域 floodfill算法概念&#xff1a; floodfill算法是一种常用的图像处理算法&#xf…
阅读更多...
【IDEA】在IntelliJ IDEA中导入Eclipse项目：详细指南

【IDEA】在IntelliJ IDEA中导入Eclipse项目：详细指南

IntelliJ IDEA和Eclipse是两款常用的集成开发环境&#xff08;IDE&#xff09;&#xff0c;在软件开发中经常会遇到需要在它们之间迁移项目的情况。本文将重点介绍如何在IntelliJ IDEA中导入Eclipse项目&#xff0c;以帮助开发者顺利地迁移他们的项目&#xff0c;并在IntelliJ …
阅读更多...
云主机修复监控插件异常的方法

云主机修复监控插件异常的方法

首先&#xff0c;进入云监控服务--选择主机监控&#xff0c;勾选上网络配置异常的云主机&#xff0c;最上面的修复插件配置&#xff0c;然后等待大约半个小时多&#xff0c;再观察下主机的状态。 一般情况下问题都可以被解决&#xff0c;如果解决不了&#xff0c;可以尝试卸载…
阅读更多...
剑指 Offer 03.:数组中重复的数字

剑指 Offer 03.:数组中重复的数字

剑指 Offer 03. 数组中重复的数字 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0&#xff5e;n-1 的范围内。数组中某些数字是重复的&#xff0c;但不知道有几个数字重复了&#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。…
阅读更多...
Linux下的进程管理：创建、终止、切换与等待

Linux下的进程管理：创建、终止、切换与等待

文章目录 一、引言二、进程创建1、进程创建的概念与场景2、进程创建的方式a、fork() 系统调用b、fork() 后的执行流程 3、进程创建的过程a、进程创建过程b、子进程创建过程 4、父子进程关系与属性继承 三、进程终止1、进程终止的原因2、进程的错误码和退出码a、错误码b、退出码…
阅读更多...
Golang基础5-指针、结构体、方法、接口

Golang基础5-指针、结构体、方法、接口

指针 和c/c类似&#xff0c;但是go语言中指针不能进行偏移和运算&#xff0c;安全指针 &&#xff08;取地址) *(根据地址取值) nil(空指针&#xff09; make和new之前对比&#xff1a;make用于初始化slice&#xff0c;map&#xff0c;channel这样的引用类型 而new用于类…
阅读更多...
热知识：更多团队采用3个及以上内部开发者平台

热知识：更多团队采用3个及以上内部开发者平台

01 介绍 根据 Perforce Puppet 的一份新报告中&#xff0c;平台工程的采用已经在一些企业内看到了成效&#xff0c;78% 的受访者表示他们的组织拥有专门的平台团队至少三年了。 然而&#xff0c;这并不意味着这些组织只使用同一套工具。四分之三的调查参与者表示&#xff0c;他…
阅读更多...
如何使用SOLIDWORKS添加装饰螺纹线规格

如何使用SOLIDWORKS添加装饰螺纹线规格

在我们的设计过程中&#xff0c;有很多的时候螺纹规格在机械设计手册上没有&#xff0c;而我们的SOLIDWORKS软件里面录制的都是符合标准的的螺纹&#xff0c;至于其他的特种或者超出的规格需要我们设计人员去手工添加&#xff0c;以下介绍我们装饰螺纹线新规格的添加方法&#…
阅读更多...
最新文章

Copyright @ 2022~2023