Pinely Round 3 (Div. 1 + Div. 2)（A~D）（有意思的题）

2023-12-24 14:18:00

A - Distinct Buttons?

??????? 题意：

思路：模拟从（0,0）到每个位置需要哪些操作，如果总共需要4种操作就输出NO。

// Problem: A. Distinct Buttons
// Contest: Codeforces - Pinely Round 3 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1909/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 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;
	int flag[4] = {0 , 0 , 0 , 0};
	for(int i = 0 ; i < n ; i ++){
		int x , y;
		cin >> x >> y;
		if(x < 0){
			flag[0] = 1;
		}
		else if(x > 0){
			flag[1] = 1;
		}
		if(y < 0){
			flag[2] = 1;
		}
		else if(y > 0){
			flag[3] = 1;
		}
	}	
	int cnt = 0;
	for(int i = 0 ; i < 4 ; i ++){
		cnt += flag[i];
	}
	if(cnt <= 3){
		cout <<"Yes\n";
	}
	else{
		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 - Make Almost Equal With Mod?

思路：比较有意思的题目，可以发现k取2的倍数即可。证明如下：将所有数变为二进制表示，那么某个数模2的结果即二进制最后一位，模4的结果即二进制的后两位...如此类推。

?? ????????由于题目必然存在解，也就是说数组不可能全相等。既然不可能全相等，那一定存在整个数组某一位存在1和0。因此k取2的倍数必然能够满足题意。

????????

// Problem: B. Make Almost Equal With Mod
// Contest: Codeforces - Pinely Round 3 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1909/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 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 = 1e18;
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;
	int cnt1 = 0 , cnt0 = 0;
	for(int i = 0 ; i < n ; i++){
		cin >> a[i];
	}
	for(int j = 2 ; j <= llinf ; j *= 2){
		set<int>st;
		for(int i = 0 ;i < n ; i ++){
			st.insert(a[i] % j);
		}
		if(st.size() == 2){
			cout << j << endl;
			return;;
		}
	}
	
}            
signed 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;
}

C - Heavy Intervals?

??????? 题意：

思路：首先想到对l,r,c数组进行排序。可以发现，无论如何排序，所有区间长度之和是不会改变的。因此要让权值之和最小，需要让小的区间尽可能小。即对于任意 $r_{i}$ 而言， $l_{i}$ 为最靠近它的元素。而从小到大的处理 $r_{i}$ 可以保证不会影响到后面的数。

????????

// Problem: C. Heavy Intervals
// Contest: Codeforces - Pinely Round 3 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1909/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 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;
	}
}
void solve() 
{
	cin >> n;
	int l[n] , r[n] , c[n];
	for(int i = 0 ; i < n ; i ++)
		cin >> l[i];
	for(int i = 0 ; i < n ; i ++)
		cin >> r[i];
	for(int i = 0 ; i < n ; i ++)
		cin >> c[i];
	sort(c , c + n);
	sort(l , l + n);
	sort(r , r + n);
	int pre[n];
	stack<int>st;
	int ll = 0;
	int ans = 0;
	for(int i = 0 ; i < n ;i ++){
		while(ll < n && r[i] > l[ll]){
			
			st.push(l[ll]);
			ll++;
		}
		int x = st.top();
		st.pop();
		pre[i] = r[i] - x;
	} 	
	sort(pre , pre + n);
	for(int i = 0 ; i < n ; i ++){
		ans += pre[i] * c[n - i - 1];
	}
	cout << ans << endl;
}            
signed 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 - Split Plus K?

??????? 题意：

思路：假设最终所有数为 $ans$ ，对于 $a_{i}$ 而言，需要操作 $t$ 次以后能变成ans，需要满足 $a_{i} + t*k = (t + 1) * ans$ 。

????????转换一下后得到 $t = (a_{i} - ans)/(ans-k)$

????????即 $ans$ 成立的条件为： $\forall i((a_{i} - k)\%(ans - k)) = 0$

??????? 为了方便解释，假设所有数都大于 $k$ 。想要操作数最小，即 $ans-k$ 需要最大。可以发现，最终的 $ans-k$ 的最大值为 $gcd(a_{1} - k , a_{2} - k , a_{3} - k .... a_{n} - k)$ 。求出gcd之后再带回原式子求出操作数 $t$ 即可。相反所有数都小于 $k$ 也是一样的操作。需要注意存在数等于 $k$ 时，需要所有数都等于 $k$ ，否则输出-1。

????????

// Problem: D. Split Plus K
// Contest: Codeforces - Pinely Round 3 (Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/1909/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 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;
	}
}
void solve() 
{

// x + tk = (t + 1) * ans
// x - ans = t(ans - k)
// ans - k < 0 ??
// (x - ans / ans - k ) = t // ans 越大越好
	cin >> n >> m;
	for(int i = 0 ; i < n ; i++)
		cin >> a[i];
	sort(a.begin() , a.begin() + n);
	for(int i = 0 ; i < n ; i ++){
		if(a[0] < m && a[i] >= m){
			cout << -1 << endl;
			return;
		}
	}
	for(int i = 0 ; i < n ; i ++){
		a[i] -= m;
	}
	int ans = 0;
	for(int i = 0 ; i < n ; i ++){
		ans = gcd(ans , abs(a[i]));
	}
	int out = 0;
	if(a[0] == 0 && a[n - 1] != 0 || a[0] != 0 && a[n - 1] == 0){
		cout << -1 << endl;
		return;
	}
	else if(ans == 0){
		cout << 0 << endl;
		return;
	}
	for(int i = 0 ; i < n ; i ++){
		if(a[i] >= 0){
			out += (a[i] - ans) / ans ;
		}
		else{
			out += (a[i] + ans) / -ans;
		}
	}
	cout << out << endl;
}            
signed 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;
}

???? ??

????????

文章来源:https://blog.csdn.net/weixin_61825750/article/details/135177444
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！