http://tioj.ck.tp.edu.tw/problems/1265
有點小煩的題目，排列組合和爆搜得結合吧。
問一個東西的可能性的問題。
這套保加利亞題好像都是爆搜題啊~~爆搜全餐。
題目給我們一張桌子，分成3*4共12格格子，然後給我們12個相異正整數，問我們，讓直排(三格)數字和是三的倍數、橫排(四格)數字和是二的倍數的排法共有幾種，並且一種排法中，因為任意交換行和列也都是成立的，所以當作一種排法。
問題轉化成，把12個數字分成相同的三堆，每堆和都是偶數，然後每堆在分成相同的四堆(美一堆貢獻一個數字組成新的一堆)，每堆和是三的倍數。
因為這樣子的排列組合數量不大，可以枚舉。
先DFS暴力找出第一種分堆法，注意因為我們只要分成相同的三堆數字，所以不需要讓三堆有排列，要達到這個條件，只要固定第一個數字就好(因為要是第一個數字換人，那他將會在別堆形成重複的一堆)，所以在暴力枚舉的時候每堆第一個數字一選下去就不用是其他數字了。
然後第二種分堆法比較簡單，只接讓每堆都跑出4階排列就可以了，不過因為我們一樣不希望堆重複出現，所以第一個4階可以不用做(當成兩個分一堆，再分配給第一排的四個人)。
最後記得檢查每堆是否符合規定，然後加總答案即可。
題目說正整數最大會到50位數，可能有人會覺得要寫大數，其實完全不用。
二的倍數好解決，只要判斷最後一位是奇數偶數就可以，加起來也只要看奇數跟偶數的個數，就可以判斷數字和是奇數偶數。而三的倍數，只要套用國中有教過的，每一個位數的數字和是三的倍數的話，這個整數就是三的倍數這個性質，而這個性質也可以推到多個數字和，每個位數和是三的倍數的話數字和就是三的倍數。
所以對於一個整數，我們只要記錄每一位的數字和和還有是否是奇數，一個Pair搞定。
輸入的過程如果有寫過輸入優化的話就會覺得很簡單。
PS. std::next_permutation()是求排列的好幫手。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
typedef pair<int,bool> PIB;
PIB D[13];
bool wed[13];
int ans, DP[3][5];
int solve_column(){
do{
do{
bool flag = true;
F(4){
int tmp = 0;
Fi(j,3)tmp+=D[DP[j][i]].first;
if(tmp%3){
flag = false;
break;
}
}
if(flag)ans += 1;
}while(next_permutation(DP[2],DP[2]+4));
}while(next_permutation(DP[1],DP[1]+4));
}
int DFS(int x,int y,int p){
DP[x][y] = p;
if(y==3){
int tmp = 0;
F(4)tmp+=D[DP[x][i]].second;
if(tmp&1)return 0;
if(x==2)return solve_column();
F(12)if(!wed[i]){
wed[i] = true;
DFS(x+1,0,i);
wed[i] = false;
return 0;
}
}
Fl(i,p+1,12)if(!wed[i]){
wed[i] = true;
DFS(x,y+1,i);
wed[i] = false;
}
}
bool input(PIB&x){
char c;
while(c = cin.get(), c<'0'||c>'9')if(c==EOF)return false;
x.first = c-'0';
x.second = (c-'0')&1;
while(c = cin.get(), c>='0'&&c<='9')x.first += c-'0',x.second = (c-'0')&1;
return true;
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
while(input(D[0])){
F(11)input(D[i+1]);
ans = 0;
wed[0] = true;
DFS(0,0,0);
wed[0] = false;
cout<<ans<<endl;
}
}
|
