思维专题(不定期更新)

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,i,t;
 8     while (cin >> n, n != 0)
 9     {
10         for (i = 0; i < n; i++) cin >> dm[i];
11         sort(dm, dm + n);
12         int maxt = 1;
13         for ( 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 }

View Code

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 }

View Code

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
", ++Case, ans);
31     }
32     return 0;
33 }

View Code

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:
", 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 }

View Code

5、HihoCoder 1671 反转子串

　　题意：给定一个只包含括号和小写字母的字符串S，例如S="a(bc(de)fg)hijk"。其中括号表示将里面的字符串翻转。(注意括号可能嵌套) 请你输出翻转之后的字符串。

　　思路：对括号进行匹配，之后进行dfs.

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 char s[5000010];
 6 int L[5000010], R[5000010];
 7 int Cnt[5000010];
 8 int totlen;
 9 void Cal(int l,int r,int cnt)
10 {
11     if (cnt%2==1)
12     {
13         for (int i = r; i >= l; i--)
14         {
15             if (s[i] == ')')
16             {
17                 Cal(L[i] + 1, i - 1,0);
18                 i = L[i];
19             }
20             else printf("%c", s[i]);
21         }
22     }
23     else
24     {
25         for (int i = l; i <= r; i++)
26         {
27             if (s[i] == '(')
28             {
29                 Cal(i + 1, R[i] - 1,1);
30                 i = R[i];
31             }
32             else printf("%c", s[i]);
33         }
34     }
35 }
36 int main()
37 {
38     while (~scanf("%s",s))
39     {
40         totlen = strlen(s);
41         int top = -1;
42         for (int i = 0; i < totlen; i++)
43         {
44             if (s[i] == '(')
45             {
46                 Cnt[++top] = i;
47             }
48             else if (s[i] == ')')
49             {
50                 R[Cnt[top]] = i;
51                 L[i]=Cnt[top--];
52             }
53         }
54         Cal(0,totlen-1,0);
55         printf("
");
56     }
57     return 0;
58 }
59 //a(e(x(y(z)y)x(n(m)n)p(q)r)e)a
60 // 1 2 3 4 4 3 5 6 6 5 7 7 2 1

View Code