題干：

一個長度為N的數(shù)組A，從A中選出若干個數(shù)，使得這些數(shù)的和是N的倍數(shù)。

例如：N = 8，數(shù)組A包括：2 5 6 3 18 7 11 19，可以選2 6，因為2 + 6 = 8，是8的倍數(shù)。

Input

第1行：1個數(shù)N，N為數(shù)組的長度，同時也是要求的倍數(shù)。(2 <= N <= 50000)?
第2 - N + 1行：數(shù)組A的元素。(0 < Aii?<= 10^9)

Output

如果沒有符合條件的組合，輸出No Solution。?
第1行：1個數(shù)S表示你所選擇的數(shù)的數(shù)量。?
第2 - S + 1行：每行1個數(shù)，對應你所選擇的數(shù)。

Sample Input

8 2 5 6 3 18 7 11 19

Sample Output

2 2 6

解題報告：

? ?跟藍橋的那道K倍區(qū)間很像，只是這題不是連續(xù)區(qū)間了，，，所以有點傷。。想了半天沒想出來。

? 其實是可以轉(zhuǎn)化成那一題的，反正是個SPJ問題嘛，我們可以根據(jù)抽屜定理構造出一組解，就是一定存在連續(xù)區(qū)間，使得、、、于是就轉(zhuǎn)化成那道K倍區(qū)間了。。。預處理取模，求前綴，遍歷求解。。。思路就一樣了。

普及知識：

桌上有十個蘋果，要把這十個蘋果放到九個抽屜里，無論怎樣放，我們會發(fā)現(xiàn)至少會有一個抽屜里面至少放兩個蘋果。這一現(xiàn)象就是我們所說的“抽屜原理”。 抽屜原理的一般含義為：“如果每個抽屜代表一個集合，每一個蘋果就可以代表一個元素，假如有n+1個元素放到n個集合中去，其中必定有一個集合里至少有兩個元素。” 抽屜原理有時也被稱為鴿巢原理。它是組合數(shù)學中一個重要的原理。又叫狄利克雷抽屜原理

AC代碼：

#include<bits/stdc++.h> #define pm make_pair #define fi first #define se second using namespace std; int a[500005]; pair<int,int> sum[500005]; int main() {int n,ans;cin>>n;sum[0] = pm(0,0);for(int i = 1; i<=n; i++) {scanf("%d",a+i);sum[i] = pm((sum[i-1].first + a[i]) % n,i);}sort(sum+1,sum+n+1);for(int i = 1; i<n; i++) {if(sum[i].first == sum[i+1].first) {ans = i;break;}}printf("%d\n",sum[ans+1].second - sum[ans].second);for(int i = sum[ans].second+1;i<=sum[ans+1].second; i++) {printf("%d\n",a[i]);} return 0 ;}

?

總結

以上是生活随笔為你收集整理的【51Nod - 1103】N的倍数 （思维，鸽巢原理也叫抽屉定理，求倍数问题取模）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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