资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

SRM475-创新互联

250pt：SRM475

题意：有最长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://www.cdkjz.cn/article/hcesi.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
成都app开发公司成都装饰装修雅安机房托管德阳电信机房成都免费建站云服务器app网站建设免备案空间温江电信机房香港主机

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图