SRM475-創(chuàng)新互聯(lián)

250pt：

題意：有最長N=17的一條格子，每個格子是W、B和R三種顏色之一，當某個格子上有兔子時，下一個回合該兔子按照以下的規(guī)則移動：

成都創(chuàng)新互聯(lián)成立于2013年，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目成都網(wǎng)站制作、做網(wǎng)站網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元東區(qū)做網(wǎng)站,已為上家服務(wù),為東區(qū)各地企業(yè)和個人服務(wù),聯(lián)系電話:028-86922220

如果兔子在第一個格子，則向右移動一格；

否則如果兔子在倒數(shù)兩個格子，則向左移動一格；

否則如果兔子在W格上，則向左移動一格；

否則如果兔子在B格上，則向右移動一格；

否則兔子在R格上，如果是它第一次移動，則向左移動一格，否則回到上一步過來的地方。

每一輪每個兔子移動，然后最后一個格子消失，如果某個格子上有多于一只兔子，則這個格子上的兔子消失。整個過程一直持續(xù)到總格子數(shù)等于2為止?，F(xiàn)在在N個格子里面初始隨機放R只兔子，問最后期望剩下幾只兔子。

思路：模擬幾個你會發(fā)現(xiàn)因為每回奇數(shù)位置的要跳到偶數(shù)位置，反之也一樣。所以答案必然跟奇偶性有關(guān)系

很明顯，奇數(shù)上的會相互抵消，偶數(shù)也一樣。所以統(tǒng)計就很簡單了。再者枚舉一下初始位置即可。

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月，消失一半兔子，消失的兔子總是年齡較大的那些。

現(xiàn)在給定最多50個兔子會消失一半的年份，問第K<=10^7年的12月一共有多少兔子。答案模MOD=1,000,000,009。

思路：如果沒有消失這一說，那么答案就是一個斐波那契數(shù)列。那就難在如何處理消失的。

而且每次%MOD后，再處理消失便會出問題。所以我們必須要用另外一個來記錄奇偶性。

由于最多消失50次，也就是說最多有50次的/2操作。那么我們直接記錄下當前答案%2^50的結(jié)果便可直到奇偶性。。

接下來直接模擬就行了。注意奇偶分開操作就行

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
網(wǎng)頁名稱：SRM475-創(chuàng)新互聯(lián)
當前鏈接：http://weahome.cn/article/hcesi.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

SRM475-創(chuàng)新互聯(lián)

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管