Mathematics

jzoj 1747

題目大意

有n堆石子，總和為$2^k$，現(xiàn)在對(duì)于兩堆石子，你可以從a中取b的分量到b（a要大于b），問(wèn)合成一堆大小為$2^k$的石子要怎么做（輸出a,b）

輸入樣例

2 2 3 1

輸出樣例

2 1 1 2

數(shù)據(jù)范圍

對(duì)于30%的數(shù)據(jù)，n=2；
對(duì)于100%的數(shù)據(jù)，$n?100000，k?31。$

解題思路

既然總和就是最后一堆的大小那就是把所有合在一起啦
我們從小到大枚舉二進(jìn)制下的每一位，如果有1的那就找另一個(gè)有1的和他調(diào)一下，這樣就可以清掉一位，我們不停清，最后就只剩$2^k$了

代碼

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; ll n, k, p, s, a[100500]; int main() {scanf("%lld %lld", &n, &k);for (ll i = 1; i <= n; ++i)scanf("%lld", &a[i]);for (ll sum = 1, i = 0; i < k; ++i, sum <<= 1)//每一位for (ll j = 1; j <= n; ++j)if (a[j]&sum){if (!p)//沒(méi)有前面一個(gè)先記錄下來(lái)s = j, p = 1;else{if (a[j] > a[s])//有前面一個(gè)就要判斷誰(shuí)給誰(shuí){a[j] -= a[s];//給他那么多就減掉那么多a[s] <<= 1;//乘上2printf("%lld %lld\n", s, j);}else{a[s] -=a[j];a[j] <<= 1;printf("%lld %lld\n", j, s);}p = 0;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的Mathematics（jzoj 1747）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。