wordpress企业网站模板下载,wordpress生存,织梦源码网站建设好了后登录不了,徐州在线网d1的题意是有n个人每个人都有一定的糖果#xff0c;同时每个人必须给其他人一次糖果和接收其他人给他的一次糖果#xff0c;同时给出的糖果和接收的数目都是2^x#xff0c;最后确保每个人拥有的糖果数目一样
思路#xff1a;我们可以先由平均数算出每个人最终要拥有的糖果…d1的题意是有n个人每个人都有一定的糖果同时每个人必须给其他人一次糖果和接收其他人给他的一次糖果同时给出的糖果和接收的数目都是2^x最后确保每个人拥有的糖果数目一样
思路我们可以先由平均数算出每个人最终要拥有的糖果然后每个只能加上一个2^x减去一个2^y
所以可以看过程中的2^x和2^y是否能想抵消就行了
比如一个人要到达最后状态需要加上31颗糖果那么他就是 加上32再减去1
即 100000-1 11110 最终前面的一是连续的
如果需要加上29颗的话 29的二进制是 11101 他无论怎么加上减去二进制数都是无法实现的
假设需要p
也就是要满足
(p(p-p))p0就行了
-------------------------------------------------------------------------------------------------
d2的要求就是每个人至多给别人一次2^x个数的糖果和至多接收别人一次2^x个数的糖果
也就是可以不接受或者不给出
如果你需要加上31颗糖果时你必须给出和接收一次 因为11110仅仅一次操作无法得到
然后开一个数组存储需要的操作次数(这里面的东西是不可以改变的比如有一个2^x你就必须要用下面数组中的一个-2^x去消除)
如果你是2^x的话你可以选择操作一次或者两次
你可以重新开一个去存储有多少个需要2^x个糖果这里面的东西可以改变的可以与上面消去或者进行下面这个操作让他尽可能的变成0
然后假如要加上2^x的话操作是2^(x1)-2^x也就是两个2^x能相互抵消并合成一个2^(x1)
然后贪心的去给他们合并就行了
const int B 35;
signed main()
{ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);int T;cin T;while (T--){int n;cin n;vectorinta(n);int tot 0;for (int x : a) cin x, tot x;if (tot % n ! 0) {cout No\n;continue;}int avg tot / n;vectorintdeg(B), poscnt(B), negcnt(B);bool ok 1;for (int i 0; i n; i) {int diff a[i] - avg;if (diff 0) {continue;}bool neg 0;if (diff 0) {diff -diff;neg 1;}int z diff -diff;if (diff z){int u __lg(diff);//最高位1的位置if (neg) poscnt[u];else negcnt[u];continue;}diff z;if (diff (diff - 1)) {ok 0;break;}int u __lg(z);int v __lg(diff);if (neg){deg[v];deg[u]--;}else {deg[u];deg[v]--;}}if (!ok) {cout No\n;continue;}for (int i 0; i B; i) {if (i B - 1 max({ deg[i],-deg[i],poscnt[i],negcnt[i] }) 0) {ok 0;break;}while (deg[i] 0) {if (negcnt[i]) {negcnt[i]--;deg[i];deg[i 1]--;}else if (poscnt[i]) {poscnt[i]--;deg[i];}else {ok 0;break;}}while (deg[i] 0) {if (negcnt[i]) {negcnt[i]--;deg[i]--;}else if (poscnt[i]) {poscnt[i]--;deg[i]--;deg[i 1];}else {ok 0;break;}}int s poscnt[i] - negcnt[i];if (s 1) {ok 0;break;}deg[i 1] s / 2;}if (!ok) {cout No\n;continue;}cout Yes\n;}
}
