SRM484

又Orz了一发rng_58。。

250pt:

题意:给定一种兔子数:当S(x*x) = S(x)*S(x)时,x为兔子数,其中S(x)表示各个数位之和。

思路:本来想了一个复杂度很高的想法。。然后想看一下是否正确时,才知道是是找规律。。原来规律就是x的每一位只可能是0-3.所以直接枚举即可。。

code:

 1 #line 7 "RabbitNumber.cpp"
 2 #include <cstdlib>
 3 #include <cctype>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <vector>
 9 #include <string>
10 #include <iostream>
11 #include <sstream>
12 #include <map>
13 #include <set>
14 #include <queue>
15 #include <stack>
16 #include <fstream>
17 #include <numeric>
18 #include <iomanip>
19 #include <bitset>
20 #include <list>
21 #include <stdexcept>
22 #include <functional>
23 #include <utility>
24 #include <ctime>
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 #define rep(i,n) for(int i=0;i<(n);++i)
30 typedef vector<int> VI;
31 typedef vector<string> VS;
32 typedef vector<double> VD;
33 typedef long long LL;
34 typedef pair<int,int> PII;
35 
36 
37 class RabbitNumber
38 {
39         public:
40         int L, R;
41         set<int> S1;
42         int S(long long x){
43             int res = 0;
44             for (;x;) res += x % 10, x /= 10;
45             return res;
46         }
47         void dfs(int number, int k){
48             if (k == 9){
49                 if (number < L || number > R) return;
50                 if (number && S(number) * S(number) == S((long long)(number) * number)) S1.insert(number);
51                 return;
52             }
53             for (int i = 0; i <= 3; ++i) dfs(number * 10 + i, k + 1);
54         }
55         int theCount(int low, int high)
56         {
57              L = low;
58              R = high;
59              S1.clear();
60              if (high == 1000000000) S1.insert(R);
61              dfs(0, 0);
62              return (int)S1.size();
63         }
64 
65 };
View Code

500pt

题意:一个堆栈,每次往里面扔一个气球(气球有四种颜色,可任意选一个放进去),每次当栈顶有L<=10个气球的时候,这L个将会破掉。问往里面扔N<=1000后并且最后栈为空的方案数

思路:想了好久还是不会做。。不过思路确实不难。

        dp[i][j]表示放了i个气球,并且还需要j个气球可使栈为空的方案数。

        那么,如果当前j为0,不管放什么颜色都还需要L-1个球来消掉。

                如果j不为0,有两种情况,一种放跟栈顶颜色一样,则j-1,否者j+L-1

 code:

 1 // BEGIN CUT HERE
 2 /*
 3 
 4 */
 5 // END CUT HERE
 6 #line 7 "PuyoPuyo.cpp"
 7 #include <cstdlib>
 8 #include <cctype>
 9 #include <cstring>
10 #include <cstdio>
11 #include <cmath>
12 #include <algorithm>
13 #include <vector>
14 #include <string>
15 #include <iostream>
16 #include <sstream>
17 #include <map>
18 #include <set>
19 #include <queue>
20 #include <stack>
21 #include <fstream>
22 #include <numeric>
23 #include <iomanip>
24 #include <bitset>
25 #include <list>
26 #include <stdexcept>
27 #include <functional>
28 #include <utility>
29 #include <ctime>
30 using namespace std;
31 
32 #define PB push_back
33 #define MP make_pair
34 #define rep(i,n) for(int i=0;i<(n);++i)
35 #define fep(i,n) for(int i=0;i<=(n);++i)
36 #define M 1000000007
37 typedef vector<int> VI;
38 typedef vector<string> VS;
39 typedef vector<double> VD;
40 typedef long long LL;
41 typedef pair<int,int> PII;
42 int dp[1200][1200];
43 
44 class PuyoPuyo
45 {
46         public:
47         int theCount(int L, int N)
48         {
49              memset(dp, 0, sizeof(dp));
50              dp[0][0] = 1;
51              rep(i, N) fep(j, N) if (dp[i][j]){
52                   if (j) dp[i+1][j-1] = (dp[i+1][j-1] + dp[i][j]) % M;
53                   else  dp[i+1][L-1] = (dp[i+1][L-1] + ((long long)dp[i][j] * 4) % M) % M; 
54                   if (j && j + L - 1<= N)
55                        dp[i+1][j + L - 1] = (dp[i+1][j + L - 1] + ((long long)dp[i][j] * 3) % M) % M;       
56              }
57              return dp[N][0];   
58         }
59 };
View Code
原文地址:https://www.cnblogs.com/yzcstc/p/3628615.html