SRM475-创新互联

250pt：

题意：有最长N=17的一条格子，每个格子是W、B和R三种颜色之一，当某个格子上有兔子时，下一个回合该兔子按照以下的规则移动：

成都创新互联成立于2013年，是专业互联网技术服务公司，拥有项目成都网站制作、做网站网站策划，项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命，1280元东区做网站,已为上家服务,为东区各地企业和个人服务,联系电话:028-86922220

如果兔子在第一个格子，则向右移动一格；

否则如果兔子在倒数两个格子，则向左移动一格；

否则如果兔子在W格上，则向左移动一格；

否则如果兔子在B格上，则向右移动一格；

否则兔子在R格上，如果是它第一次移动，则向左移动一格，否则回到上一步过来的地方。

每一轮每个兔子移动，然后最后一个格子消失，如果某个格子上有多于一只兔子，则这个格子上的兔子消失。整个过程一直持续到总格子数等于2为止。现在在N个格子里面初始随机放R只兔子，问最后期望剩下几只兔子。

思路：模拟几个你会发现因为每回奇数位置的要跳到偶数位置，反之也一样。所以答案必然跟奇偶性有关系

很明显，奇数上的会相互抵消，偶数也一样。所以统计就很简单了。再者枚举一下初始位置即可。

code：

 1 #line 7 "RabbitStepping.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 #define two(i) (1 << i)
34 typedef vector VI;
35 typedef vector VS;
36 typedef vector VD;
37 typedef long long LL;
38 typedef pair PII;
39 
40 
41 class RabbitStepping
42 {
43 public:
44 double getExpected(string field, int r)
45         {
46 int n = field.size();
47 int a, b;
48 double ret = 0;
49 for (int i = 0; i < two(n); ++i){
50                     a = b = 0;
51 for (int j = 0; j < n; ++j) if (two(j) & i){
52 if (j & 1) ++a;
53 else ++b;    
54                     }
55 if (a + b == r) ret += (a & 1) + (b & 1);
56               }
57 for (int i = 1; i <= r; ++i)
58                  ret = ret / (n - i + 1.0) * (i + .0);
59 return ret; 
60         }
61   };

View Code

500pt

题意：第一年7月天上掉下一对小兔子；之后:

每年3月，老兔子生一对小兔子，原来的小兔子升级为老兔子；

某些年的11月，消失一半兔子，消失的兔子总是年龄较大的那些。

现在给定最多50个兔子会消失一半的年份，问第K<=10^7年的12月一共有多少兔子。答案模MOD=1,000,000,009。

思路：如果没有消失这一说，那么答案就是一个斐波那契数列。那就难在如何处理消失的。

而且每次%MOD后，再处理消失便会出问题。所以我们必须要用另外一个来记录奇偶性。

由于最多消失50次，也就是说最多有50次的/2操作。那么我们直接记录下当前答案%2^50的结果便可直到奇偶性。。

接下来直接模拟就行了。注意奇偶分开操作就行

code:

 1 #line 7 "RabbitIncreasing.cpp"
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #include 
22 #include 
23 #include 
24 #include 
25 using namespace std;
26 
27 #define PB push_back
28 #define MP make_pair
29 
30 #define REP(i,n) for(i=0;i<(n);++i)
31 #define FOR(i,l,h) for(i=(l);i<=(h);++i)
32 #define FORD(i,h,l) for(i=(h);i>=(l);--i)
33 #define M 1000000009
34 #define P (1LL << 51)
35 typedef vector VI;
36 typedef vector VS;
37 typedef vector VD;
38 typedef long long LL;
39 typedef pair PII;
40 
41 
42 class RabbitIncreasing
43 {
44 public:
45 long long power(long long a, int b){
46   long long ret = 1;
47   for (;b > 0; b >>= 1){
48   if (b&1) ret = (ret * a) % M;
49                    a = (a * a) % M;
50              }
51   return ret;
52         }
53 int getNumber(vector  leave, int k)
54         {
55                 sort(leave.begin(), leave.end());
56   int T2 = power(2, M - 2);
57   long long cur = 1, pre = 0, next;
58   long long a = 1, b = 0, c;
59   long long dec, tmp;
60   if (leave[0] == 1) return 0;
61   int l = 0, n = leave.size();
62   for (int i = 2; i <= k; ++i){
63                      next = (cur + pre) % M;
64                      c = (a + b) % P;
65  if (l < n && leave[l] == i){
66  if (c & 1){
67                                 dec = (c + 1) / 2;
68                                 c /= 2;
69                                 a = (a - dec + P) % P;
70                                 tmp = ((next + 1) * T2) % M;
71                                 cur = (cur - tmp + M) % M;
72                                 next = (next - tmp + M) % M;
73                            }else {
74                                 dec = c / 2;
75                                 c /= 2;
76                                 a = (a - dec + P) % P;
77                                 tmp = (next * T2) % M;
78                                 cur = (cur - tmp + M) % M;
79                                 next = (next - tmp + M) % M;
80                            }
81                            ++l;
82                      }
83                      pre = cur, cur = next;
84                      b = a, a = c;
85                 }
86   return cur;
87         }
88 };

View Code
当前文章：SRM475-创新互联
文章来源：http://scyanting.com/article/hcesi.html

SRM475-创新互联

其他资讯