首页 > 代码库 > 思维专题(不定期更新)
思维专题(不定期更新)
1、UVa 11100 - The Trip, 2007
题意:给出若干大小不同的包裹，小的能够装在大的包裹里面。求最小的大包裹数，并且保证在所有的大包裹中，所含有的小包裹数目最小。
思路：显然，相同大小的包只能放在不同的大包里，那么最小的大包数目就是相同大小的包的最大数目，记为k。之后，根据从小到大排序后,对于每个大包i可选取从i开始，间隔k个包的那些包裹作为该大包从里到外的各个包裹。
1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 int dm[10005]; 5 int main() 6 { 7 int k = 1,n; 8 while (cin >> n, n != 0) 9 { 10 for (int i = 0; i < n; i++) cin >> dm[i]; 11 sort(dm, dm + n); 12 int maxt = 1; 13 for (int i = 1, t = 1; i < n; i++) 14 { 15 if (dm[i] == dm[i - 1]) t++; 16 else 17 { 18 if (t > maxt) maxt = t; 19 t = 1; 20 } 21 } 22 if (t > maxt) maxt = t; 23 if (k > 1) cout << endl; 24 cout << maxt << endl; 25 for (int i = 0; i < maxt; i++) 26 { 27 for (int j = i; j < n; j += maxt) 28 { 29 if (j == i) cout << dm[j]; 30 else cout << ‘ ‘ << dm[j]; 31 } 32 cout << endl; 33 } 34 k++; 35 } 36 return 0; 37 }
2、Uva 11384 - Help is needed for Dexter
题意：给出N，即有1~N个数，每个数的大小为1~N，每次选取剩下的若干个数，然后对于所有所选数字，减去选取数字中的某个数字。求最小的操作数，使得最后每个数为0.
思路：每次二分操作，对于右侧的数字减去中间的那个数，结果为1~m,0~m(m+1)；不断重复，最小的操作数即为log2(N)+1
1 #include <cmath> 2 #include<iostream> 3 using namespace std; 4 int main() 5 { 6 int n; 7 while (cin>>n) 8 { 9 cout << (int)log2(n) + 1 << endl; 10 } 11 return 0; 12 }
3、UVA 10795 A Different Task(汉诺塔递归)
题意：给出汉诺塔的一个初始局面（对于n个盘子（编号大的盘子大），给出其所在柱子编号1或2或3），再给出一个目标局面，求移动次数。
思路：从编号大的开始考虑，如果其初始位置a和目标位置c相同，则不移动；否则,设此时盘子编号为k,中间局面为k号盘子在a位置，1~k-1号盘子在6-a-c位置。则操作数为f(start,k-1,6-a-c)+f(final,k-1,6-a-c)+1,即从初始局面到中间局面的移动次数+目标局面到中间局面的移动次数+1(移动第k个盘子)(start和final分别为存储初始和目标位置的数组)。对于f(P,i,fnl),如果P[i]==fnl,则f(P,i,fnl)=f(P,i-1,fnl);否则，需要把前i-1个盘子移到6-P[i]-fnl号柱子上做中转(次数为f(P,i-1,6-P[i]-fnl))，然后把i号盘子移到fnl号柱子(次数为1)，最后把前i-1号盘子移到fnl上（次数为2^(i-1)-1）,即f(P,i,fnl)=f(P,i-1,6-P[i]-fnl)+2^(i-1).
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 long long f(int* P, int i, int final) 5 { 6 if (i == 0) return 0; 7 if (P[i] == final) return f(P, i - 1, final); 8 return f(P, i - 1, 6 - P[i] - final) + (1LL << (i - 1)); 9 } 10 11 const int maxn = 60 + 10; 12 int n, start[maxn], finish[maxn]; 13 14 int main() 15 { 16 int Case = 0; 17 while (cin>>n,n!=0) 18 { 19 for (int i = 1; i <= n; i++) cin>>start[i]; 20 for (int i = 1; i <= n; i++) cin>>finish[i]; 21 int k = n; 22 while (k >= 1 && start[k] == finish[k]) k--; 23 24 long long ans = 0; 25 if (k >= 1) 26 { 27 int other = 6 - start[k] - finish[k]; 28 ans = f(start, k - 1, other) + f(finish, k - 1, other) + 1; 29 } 30 printf("Case %d: %lld\n", ++Case, ans); 31 } 32 return 0; 33 }
4、UVa 11520 Fill the Square
题意：给出一个n*n的图，初始时图里存放若干大写字母，其他为空(记为‘.‘),之后往里面空的地方存放大写字母，要求有公共边的两个字母不相同，同时最后存放结束时从上到下，从左到右的字典序最小。
思路：对于每个‘.‘,判断应填入的大写字母即可。
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 char m[15][15]; 5 int n; 6 void Fill(int r, int c) 7 { 8 for (char C = ‘A‘; C <= ‘Z‘; C++) 9 { 10 if (r - 1 >= 0 && m[r - 1][c] == C) continue; 11 else if (c - 1 >= 0 && m[r][c - 1] == C) continue; 12 else if (c + 1 < n&&m[r][c + 1] == C) continue; 13 else if (r + 1 < n&&m[r + 1][c] == C) continue; 14 m[r][c] = C; 15 return; 16 } 17 } 18 int main() 19 { 20 int Case=1,N; 21 cin >> N; 22 while (N--) 23 { 24 cin >> n; 25 for (int i = 0; i < n; i++) 26 { 27 for (int j = 0; j < n; j++) cin >> m[i][j]; 28 } 29 for (int i = 0; i < n; i++) 30 { 31 for (int j = 0; j < n; j++) 32 { 33 if (m[i][j] == ‘.‘) Fill(i, j); 34 } 35 } 36 printf("Case %d:\n", Case++); 37 for (int i = 0; i < n; i++) 38 { 39 for (int j = 0; j < n; j++) cout << m[i][j]; 40 cout << endl; 41 } 42 } 43 return 0; 44 }
思维专题(不定期更新)