[AtCoder] ARC77 D: Decrease (Contestant ver.)

題目連結:http://arc079.contest.atcoder.jp/tasks/arc079_b
構造題,我的構造方法是假定有$n$個數且要湊出$k$次,讓最後的結果為$n-2, n-2, n-2, \cdots , n-2, n-1$,則稍微算一下後就會發現原始的數字必為$n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-2, \cdots , n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-2,n \lfloor \frac{k}{n} \rfloor - (k - \lfloor \frac{k}{n} \rfloor) + n-1 $,因為其實對於每個數他其實就只會扣掉$n$ $\lfloor \frac{k}{n} \rfloor$次,並且加上總次數減掉$\lfloor \frac{k}{n} \rfloor$的$1$,所以全部家負號後就變成這樣了,不過餘數的地方要好好處理一下(平均分給別人),以免有地方不小心太大。
為了怕有數字超過$10^{16}+1000$這裡$N$直接取50即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	lld k;cin>>k;
	int n=50;
	cout<<n<<'\n';
	for(int i=0;i<n-1;i++){
		lld kn = k/n;
		if(i<k%n) kn++;
		cout<<n*kn-(k-kn)+n-2<<' ';
	}
	lld kn = k/n;
	cout<<n*kn-(k-kn)+n-1<<'\n';
	return 0;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology