Codeforces Round #313 (Div. 2)

题目描述，有n种纸币，每种有无数张，问最小不能组成的和是多少？

解题思路：

　　只需要在[1,max(纸币面额)]区间内找就好了，大于max(纸币面额)的和都可以通过[1,max(纸币面额)]内的数经过运算得到，两重循环一下就好了，简单的完全背包问题。

当然啦，这是最实在的做法，做codeforces脑洞开的一定要大，贴两个代码：

 1 #include <cstdio>//完全背包
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const int maxn = 1002;
 9 int dp[maxn*maxn], a[maxn];
10 int main ()
11 {
12     int n, i, j;
13     while (scanf ("%d", &n) != EOF)
14     {
15         for (i=0; i<n; i++)
16             scanf ("%d", &a[i]);
17         sort (a, a+n);
18         memset (dp, 0, sizeof(dp));
19         dp[0] = 1;
20         for (i=0; i<n-1; i++)
21             for (j=a[i]; j<a[n-1]; j++)
22                 dp[j] = max (dp[j], dp[j-a[i]]);
23         for (i=1; i<a[n-1]; i++)
24             if (!dp[i])
25             break;
26         if (i < a[n-1])
27             printf ("%d
", i);
28         else
29             printf ("-1
");
30     }
31     return 0;
32 }

 1 /*有1的话，任何数都可以组合到，没有1的话，任何数都组合不出1*/
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 int main ()
 5 {
 6     int n, m, num;
 7     while (scanf("%d", &n) != EOF)
 8     {
 9         m = 10;
10         while (n --)
11         {
12             scanf ("%d", &num);
13             m = min (m, num);
14         }
15         printf ("%d
", m==1?-1:1);
16     }
17     return 0;
18 }

B. Gerald is into Art

题目描述：

　　有一个x*y的矩形，是否可以装的下a1*b1,a2*b2两个矩形，两个矩形不可以重合，不可以折叠，但是可以接触。

解题思路：

　　暴力判定一下就ok了，在这里函数提高代码的利用率真的表现的很明显~~

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 typedef long long LL;
 8 const int maxn = 1002;
 9 int x, y, a1, b1, a2, b2;
10 int solve ()
11 {
12     int a, b;
13     a = a1 + a2;
14     b = max (b1, b2);
15     if (a<=x && b<=y || a<=y && b<=x)
16         return 1;
17     b = b1 + b2;
18     a = max (a1, a2);
19     if (a<=x && b<=y || a<=y && b<=x)
20         return 1;
21     return 0;
22 }
23 int main ()
24 {
25     while (scanf ("%d %d", &x, &y) != EOF)
26     {
27         scanf ("%d %d", &a1, &b1);
28         scanf ("%d %d", &a2, &b2);
29         if (solve())
30         {
31             printf ("YES
");
32             continue;
33         }
34         swap (a1, b1);
35         if (solve())
36         {
37             printf ("YES
");
38             continue;
39         }
40         swap (a2, b2);
41         if (solve())
42         {
43             printf ("YES
");
44             continue;
45         }
46         printf ("NO
");
47     }
48     return 0;
49 }

C. Gerald's Hexagon

题目描述：

　　给出一个六边形，六边形的6个内角都是120°，给出6个边的长度，问这个六边形可以分成几个边长为1的等边三角形？

解题思路：

　　直接求出面积就好咯，因为分成的是边长为1的的等边三角形，所以求面积的时候就更加简单了一点呢，具体看代码实现。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 using namespace std;
 6 const int maxn = 10;
 7 int main ()
 8 {
 9     int a[maxn], sum;
10     for (int i=0; i<6; i++)
11         scanf ("%d", &a[i]);
12     sum = (a[0]+a[1]+a[2]);
13     sum = sum *sum - a[0]*a[0] - a[2]*a[2] - a[4]*a[4];
14     printf ("%d
", sum);
15     return 0;
16 }

D. Equivalent Strings

题目描述：

　　判断字符串a,b是否相等，相等的条件(满足其一)是:

　　1:a == b

　　2:strlen(a)，strlen(b)同时为偶数并且相等的时候分别把a,b等分为a1,a2,b1,b2。当子串满足下面任意一个条件的时候，a == b

　　　　(1):a1 == b1 && a2 == b2

　　　　(2):a2 == b1 && a1 == b2

 1 //codeforcesD
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn =  200005;
 8 char a[maxn], b[maxn];
 9 bool dfs (int la, int ra, int lb, int rb)
10 {
11     int i, j;
12     for (i=la, j=lb; i<ra; i++, j++)
13         if (a[i] != b[j])
14         break;
15     if (i == ra)
16         return 1;
17     if ((ra - la) % 2)
18         return 0;
19     i = (ra - la) / 2;
20     if ((dfs(la,la+i,lb+i,rb)&&dfs(la+i,ra,lb,lb+i)) || (dfs(la,la+i,lb,lb+i)&&dfs(la+i,ra,lb+i,rb)))
21         return 1;
22 }
23 int main ()
24 {
25     while (scanf ("%s %s", a, b) != EOF)
26     {
27         int len = strlen (a);
28         if (dfs (0, len, 0, len))
29             printf ("YES
");
30         else
31             printf ("NO
");
32     }
33     return 0;
34 }

本文为博主原创文章，未经博主允许不得转载。