首页 > 其他分享 >Candy Party (Hard Version) 题解

Candy Party (Hard Version) 题解

时间:2023-12-19 12:24:40浏览次数:46  
标签:__ lg cnt int 题解 Hard del Party mean

原题链接:CF1868B2
简单版:CF1868B1

题意

有 \(n\) 个人,第 \(i\) 个人手上最初有 \(a_{i}\) 颗糖。现在每个人可以把自己手中的糖选一些给不多于一个人,同时每个人也只能接受不多于一个人的糖,选出的糖的数量必须是二的次幂。问能否能让每个人最终手上的糖的数量相等。

思路

首先,这道题与简单版的区别在于:这道题可以选择不给其它人糖。换句话说,如果你需要得到 \(2^{x}\) 颗糖,你除了可以选择得到 \(2^{x+1}\) 颗糖,给出 \(2^{x}\) 颗糖,还有了一种新的选择:直接得到 \(2^{x}\) 颗糖。而简单版则只能选择前者,因为题目要求你必须给出一次糖。

然后考虑如何解决。首先平均数不是整数或者 \(a_{i}-mean\) 的值在二进制表示下下 \(1\) 的个数不符合题目要求的话直接判断为无解。然后我们发现上述的这两种选择的本质区别其实就是 \(x\) 的个数和 \(x+1\) 的个数的变化,且变化只针对相邻的两个数值,所以可以考虑贪心。我们先假设每次都先选第二种情况,最后再来调整。记录三个数组 \(cnt,add,del\) 分别表示 \(x\) 得到的次数(如果是负数则为给出),\(x\) 最多可以再被多选几次,\(x\) 最多可以再被多给出几次。

得到这三个数组之后再来调整每一个 \(cnt\) 的值,判断每一个数,看 \(cnt_{i}\) 的正负,奇偶性。如果为奇数的话一定无解,因为每一次操作 \(x\) 的数量一定会增加或减少 \(2\) 的倍数个,因为从给出 \(2^{x}\) 颗糖变成了得到 \(2^{x}\) 颗糖。如果为偶数的话就用 \(add\) 或者 \(del\) 来调整即可。如果 \(add\) 或者 \(del\) 出现了不够的情况时说明了无解。注意:如果 \(cnt_{i}\) 加上了 \(k\),那么 \(cnt_{i+1}\) 就要减去 \(k \div 2\),反之亦然。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf 0x3f
#define inf_db 127
#define ls id << 1
#define rs id << 1 | 1
#define re register
#define endl '\n'
typedef pair <int,int> pii;
const int MAXN = 2e5 + 10;
const int MAXM = 30 + 10; 
int cnt[MAXN],T,n,a[MAXN],sum,mean,add[MAXM],del[MAXM];
inline int Lowbit(int x){return x & -x;} 
inline bool check()
{
	for(int i = 0;i <= 31;i++) add[i] = del[i] = cnt[i] = 0;
	for(int i = 1;i <= n;i++)
	{
		int now1 = Lowbit(abs(a[i] - mean));
		int now2 = abs(a[i] - mean) + now1;
		if(Lowbit(now2) != now2) return false;
		if(a[i] - mean > 0) cnt[__lg(now1)]--,cnt[__lg(now2)]++;
		if(a[i] - mean < 0) cnt[__lg(now1)]++,cnt[__lg(now2)]--;
		int tmp = __builtin_popcount(abs(a[i] - mean));
		if(a[i] - mean > 0 && tmp == 1) add[__lg(now1)]++;
		if(a[i] - mean < 0 && tmp == 1) del[__lg(now1)]++;
	}
	for(int i = 0;i <= 30;i++)
	{
		if(cnt[i] % 2 != 0) return false;
		if(cnt[i] < 0)
		{
			if(add[i] * 2 < -cnt[i]) return false;
			cnt[i + 1] -= -cnt[i] / 2;
		}
		if(cnt[i] > 0)
		{
			if(del[i] * 2 < cnt[i]) return false;
			cnt[i + 1] += cnt[i] / 2;
		}
	}
	return true;
}
signed main()
{
	cin >> T;
	while(T--)
	{
		cin >> n;sum = 0;
		for(int i = 1;i <= n;i++) cin >> a[i],sum += a[i];
		mean = sum / n;
		if(sum % n != 0){puts("No");continue;}
		if(check() == true) puts("Yes");
		else puts("No"); 
	}
	return 0;
}

标签:__,lg,cnt,int,题解,Hard,del,Party,mean
From: https://www.cnblogs.com/Creeperl/p/17913430.html

相关文章

  • 【0909 B组】切蛋糕 题解
    原题链接:切蛋糕。题意给定一个\(n\)行\(m\)列的蛋糕,问横着切\(i\)刀,竖着切\(j\)刀后美味度最小的蛋糕的美味度尽可能大。一块蛋糕的美味度为它所含有的小块的美味度之和。数据范围:\(1\len,m\le14\)。思路看到数据范围,我们可以考虑一种类似于状态压缩的思想,先枚举......
  • Cyclic Operations 题解
    前言看这道题有好多巨佬都是用Tarjan来做的,在这里讲一个自认为比较简单的做法,(不到\(30\)行)。题意题意比较难讲,建议自己去看一下翻译,在这里不多赘述。思路首先看到题目中间给的一个每一次操作的式子:\(a_{l_{i}}=l_{(i\modk)+1}\)。仔细观察这个式子后会发现,其实每一次......
  • P4630 [APIO2018] 铁人两项 题解
    今天学习了圆方树,并且做了一道和这道题很像的题,于是就又来做了一下这道题。题意给定一张不保证连通的无向图。求有多少个点对\((a,b,c)\)满足\(a\)到\(c\)的简单路径上经过了点\(b\)。思路显然圆方树。点双缩点过后构造一颗圆方树,然后考虑如何计算答案。圆方树有一个实......
  • [ABC315G] Ai + Bj + Ck = X (1 <= i, j, k <= N) 题解
    原题链接:ABC315G前置知识:扩展欧几里得算法。如果还不会扩欧的话,建议先去做这道题。题意给定\(n,a,b,c,k\)。求有多少个\(x,y,z(x,y,z\len)\)满足\(ax+by+cz=k\)。思路首先看到题目给出的方程式:\(ax+by+cz=k\)。我们会发现很像扩欧板子中的:\(ax+by=k\)。只不过又多了一......
  • [ABC318G] Typical Path Problem 题解
    原题链接:ABC318G显然是圆方树。点双缩点过后建立一颗以点\(c\)为根节点的圆方树,考虑什么情况是合法的。从点\(a\)开始往上跳直到跳到点\(c\),如果中间走过了某一个方点并且这个方点与\(b\)点有直接连边,那么就是合法的;否则不合法。证明:如果路径中所经过的方点和\(b\)点......
  • [ABC318F] Octopus 题解
    前言赛时只做到了E题,赛后才来补的F题,还没做出来,看来还是我太菜了。看了题解过后感觉这道题的思路特别巧妙,于是就来写了这篇题解。题意简述一下题意。有\(n\)个宝藏位置分别在\(a_{i}\),另外有一只章鱼有\(n\)条触手,每条触手的长度为\(b_{i}\)。求有多少个点\(k\)......
  • Two-Colored Dominoes 题解
    前言看了这道题的几篇题解,感觉讲的方法都比较麻烦,这里讲一个感觉比较简单的方法。思路首先判断是否有解。计算一下每一行和每一列的牌的数量,只要有一个是奇数就无解,否则有解。证明显然,偶数一定可以分成两组,在纸上模拟一下也可以得出。其次看如何构造。对于竖着的牌,显然只对每......
  • P3071 [USACO13JAN] Seating G 题解
    题意:维护两个操作,区间推平,求连续\(0\)的个数为\(x\)的最前位置。线段树。因为需要求连续\(0\)的个数,所以维护区间左边连续\(0\)的最大个数,区间右边连续\(0\)的最大个数以及区间连续\(0\)的最大个数。注意修改的时候要看是修改为\(1\)还是修改为\(0\)。查询的时......
  • P2664 树上游戏 题解
    原题链接:P2664。题意:给定一棵树,每个点都有一个颜色\(c_{i}\)。对于每一个点\(i\),求出\(\sum_{j=1}^{n}s(i,j)\)的值。其中\(s(i,j)\)表示点\(i\)到点\(j\)的颜色数量。路径相关,考虑点分治。假设当前的重心为\(u\),那么对\(u\)自己的贡献就是\(u\)到\(u\)的所有......
  • [ABC328F] Good Set Query 题解
    复习了一下边带权并查集板子。设\(d_{x}\)表示当前点到它所在连通块根节点的距离。合并点\(x\)和点\(y\)所在两个连通块时需要更新\(d\)。因为将\(x\)点所在连通块的根节点的父亲节点设为了\(y\)点所在连通块的根节点,所以有\(x\toy\toFind(y)=x\toFind(x)\to......