首页 > 其他分享 >CF1799B Equalize by Divide题解

CF1799B Equalize by Divide题解

时间:2023-05-14 14:34:54浏览次数:52  
标签:cnt Equalize int 题解 pos 数组 CF1799B 数字

本蒟蒻学习了jiangly大佬的思想,来发一个题解。

大致题意:

给定一个 \(n\) 个元素的数组 \(a\),每次可以选择 \(a[i]\) 和 \(a[j]\),然后使 \(a[i] = \lceil \frac{a_i}{a_j} \rceil\),如果最后可以使数组中的所有元素都相等,那么输出Yes,并输出每一个操作\(i, j\);否则输出No

本人不擅长使用Markdown,详细思路写在代码里面了。

// 思路:
// 1. 如果所有数字都相等,那么什么也不用干。
// 接下来的所有判断都假定所有数字不相等
// 2. 如果数组中有1,一定不可行,因为任何数字除以它还是它自己,用1除以任何数字却还是1,所以数组中有了1,就妄图改变数组中的任何一个数字。
// 3. 固定a[1], 不断地用别的数字a[i]和a[1]如以下方式操作,直到整个数组变为a[1]或者出现了2。
//	3. 1. 如果a[1] < a[i],那么a[1] = a[1] / a[i] 上取整。
//	3. 2. 否则,a[i] = a[i] / a[1] 上取整。
// 4. 如果,整个数组变为a[1],直接输出当前处理的步骤。
// 5. 否则,就将数组中不是2的元素,一个一个与2进行操作,再输出所有步骤。

// C++新语法:
// count(a, b, c) (a, b)的区间内c的个数
// find(a, b, c) 在(a, b)区间内找c并返回其指针

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using PII = pair<int, int>;

const int N = 110;

int n;
int a[N];
PII ans[N * 35];
int cnt;

void solve() {
	cnt = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	if (count(a + 1, a + n + 1, a[1]) == n) {
		cout << 0 << '\n';
		return;
	}
	
	if (count(a + 1, a + n + 1, 1) >= 1) {
		cout << -1 << '\n';
		return;
	}
	
	while (count(a + 1, a + n + 1, a[1]) < n && count(a + 1, a + n + 1, 2) == 0) {
		int pos = 2;
		while (a[pos] == a[1]) {
			pos++;
		}
		
		if (a[pos] > a[1]) {
			if (a[pos] % a[1]) a[pos] = a[pos] / a[1] + 1;
			else a[pos] = a[pos] / a[1];
			ans[++cnt] = {pos, 1};
		}
		else {
			if (a[1] % a[pos]) a[1] = a[1] / a[pos] + 1;
			else a[1] = a[1] / a[pos];
			ans[++cnt] = {1, pos};
		}
	}
	
	if (count(a + 1, a + n + 1, a[1]) < n) {
		int pos2 = find(a + 1, a + n + 1, 2) - a;
		for (int i = 1; i <= n; i++) {
			while (a[i] != 2) {
				if (a[i] & 1) a[i] = a[i] / 2 + 1;
				else a[i] = a[i] / 2;
				ans[++cnt] = {i, pos2};
			}
		}
	}
	
	cout << cnt << '\n';
	for (int i = 1; i <= cnt; i++) cout << ans[i].first << ' ' << ans[i].second << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

标签:cnt,Equalize,int,题解,pos,数组,CF1799B,数字
From: https://www.cnblogs.com/PlayWithCPP/p/17399263.html

相关文章

  • CF1728A Colored Balls: Revisited题解
    去我的Blog观看修改时间:2022/9/11修改了格式与标点修改时间:2022/9/13修改了个别不严谨的语句题目大意有\(n\)种颜色的球,颜色为\(i\)的球为\(cnt_i\)个(\(cnt_1+cnt_2+\dots+cnt_n\)为奇数)。每次从球堆中取出\(2\)个颜色不相同的球,问最后可能剩下哪种颜色的球(输出任意......
  • 常见问题解决 --- python必备技能 换源
    源是什么源是编程开发或则是操作系统要使用的第三方依赖软件应用市场,源又从何而来,其实源来自其他的源的克隆,或者是源提供者自己收集,编译,又或者作者的上传为什么要换源这些源往往都在国外,国内以为你懂的原因无法直接访问或者特别慢怎么换Windows下python永久换源方式有两种:修......
  • 常见问题解决 --- pip报错【WARNING: Retrying (Retry(total=4, connect=None, read=N
    问题现象【WARNING:Retrying(Retry(total=4,connect=None,read=None,redirect=None,st】解决方法:出现该错误信息是因为pip源连接证书验证失败,增加参数 --trusted-host例如pipinstallmatplotlib-ihttp://mirrors.aliyun.com/pypi/simple--trusted-hostmirrors.al......
  • 【题解】ars[A001]相控阵
    Link→模拟赛T1一道简单好想小可爱题。首先我们很容易得到一个结论,就是若想使总作用力最大,那么五个核弹中一定会有四个反应关系去对总作用力产生贡献。证明的话:五个核弹相当于一个五元环,不同模式相当于对点进行染色,我们不妨规定两种模式分别染色为红和蓝。因为边数\(n\)......
  • P8430 题解
    前言题目传送门!更好的阅读体验?比较妙的交互题。思路题意就是每次可以询问\([l,r]\)的括号子序列是否为合法,\((n-1)\)次询问后,需要求出整个括号序列。括号序列,自然想到栈。考虑每次进行一个\([\text{top},i]\)的询问。如果是合法,那么\(a_{\text{top}}=\text{LEFT},a......
  • CF543D 题解
    前言题目传送门!更好的阅读体验?比较有趣的换根DP。思路FirstDFS按照换根DP套路,先钦定\(1\)为首都(即根节点),并计算。显然是树形DP。设\(dp_{u}\)表示以\(u\)为根的子树全部满足的方案数。对于一条树边\((u,v)\):如果\((u,v)\)修,就意味着\(v\)对应子树的所......
  • ABC254F 题解
    前言题目传送门!更好的阅读体验?这题trick就是更相减损术:\(\gcd\{a_1,a_2,a_3,\cdots,a_n\}=\gcd\{a_1,a_2-a_1,a_3-a_2,\cdots,a_n-a_{n-1}\}\)。思路有了这个trick之后这题就好做了。并不需要其他题解一样画表格,化简式子就行,过程并没有难点。\[\begin{a......
  • UVA12096 题解
    这道题虽然被评黄,但个人感觉不止普及组难度,而且是一道很有价值的题目。题解区里全是\(O(n^2logn)\)的STL大法,我来发一篇\(O(n^2)\)哈希做法。目前0ms喜提最优解。这道题是codeforcesgym的题目,本质上就是模拟栈中集合插入,复制,相加,取交集,取并集的过程。注意,这些集合都是......
  • [AGC001E] BBQ Hard题解
    Problem[AGC001E]BBQHard计算:\[\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+b_i+a_j+b_j}{a_i+a_j}\]其中\(n\leq2\times10^5\),\(a_i,b_i\leq2000\)Solution以\(a_i\)代\(a_i+b_i\)则等价于求\[\sum_{i=1}^{n}\sum_{j=i+1}^n\binom{a_i+a_j}{b_i+b_j}......
  • 【题解】Luogu[P3750] [六省联考 2017] 分手是祝愿
    Link→小清新dp题,纪念自己的700ac(一个点只有两个状态开和不开,且按两下相当于没按,我们可以从大到小有亮的就按一下,如果我们按到了不需要按的键,就需要再按一下使他变回来。设\(f_i\)表示\(i\)个正确选择变为\(i-1\)个的期望操作次数。则有\(\dfrac{i}{n}\)概率按到......