资讯

精准传达 • 有效沟通

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

网站建设 >

查看其它板块

SRM478-创新互联

又是rng_58的神题。。SRM478

250pt:

创新互联企业建站,十多年网站建设经验，专注于网站建设技术，精于网页设计，有多年建站和网站代运营经验，设计师为客户打造网络企业风格，提供周到的建站售前咨询和贴心的售后服务。对于网站建设、成都网站设计中不同领域进行深入了解和探索，创新互联在网站建设中充分了解客户行业的需求，以灵动的思维在网页中充分展现，通过对客户行业精准市场调研，为客户提供的解决方案。

题意：给定一个初始数x，对于这个数可以进行x*4+3，或者x*8+7的操作。最多进行100000次操作

    问最少经过几次出现%1000000007 == 0的情况。。

思路：

   x*4+3 = (x * 2 + 1) * 2 + 1

   x * 8 + 7 = (x * 4 + 3) * 2 + 1

   所以我们发现两个操作都可以合并成x * 2 + 1的操作。所以直接模拟30w次*2+1操作。

  如果操作y次*2+1那么答案便是(y + 2) / 3,注意y == 1时无解需特判

code：

 1 #line 7 "CarrotJumping.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 1000000007
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 CarrotJumping
42 {
43 public:
44 int theJump(int x)
45         { 
46   for (int i = 1; i <= 300000; ++i){
47                   x = (x * 2 + 1) % M;
48  if (x == 0 && i >= 2) return (i + 2) / 3;   
49              }    
50   return -1;
51         }
52 };
View Code

500pt

题意：有N<=15个杯子，所有杯子的容量都是一样的，为C<50。现在已知每个杯子当前的水量，数量为x的杯子可以卖p[i]的钱。不过在卖之前可以做任意次操作：选两个杯子a和b，把a的水往b倒，知道a空了或者b满了为止。问这些杯子经过操作后，最多一共能卖多少钱。

思路： 如果选中若干个杯子，那么这些杯子的状态便是固定的，因为必须倒到满或者空。

     那么集合dp的感觉就很明显了

     dp[mask]表示选中mask状态个的被子最多卖多少钱。然后枚举子状态即可。。

code：

 1 #line 7 "KiwiJuice.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 #define two(i) (1 << i)
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 
34 typedef vector VI;
35 typedef vector VS;
36 typedef vector VD;
37 typedef long long LL;
38 typedef pair PII;
39 int dp[1 << 16], cost[1 << 16];
40 class KiwiJuice
41 {
42 public:
43 int c, n;
44         vector b, p;
45 void calculateCost(int mask){
46   int v = 0, bn = 0;
47   for (int i = 0; i < n; ++i)
48 if (two(i) & mask){
49                        v += b[i];
50                        ++bn;
51                  }
52              cost[mask] = p[v % c] + (v / c) * p[c] + p[0] * (bn - v / c - 1);
53         }
54 int dfs(int mask){
55 if (dp[mask] != -1) return dp[mask];
56               dp[mask] = 0;
57 for (int i = mask; i; i = (i-1) & mask)
58                   dp[mask] = max(cost[i] + dfs(mask ^ i), dp[mask]);
59 return dp[mask];
60         }
61 int theProfit(int C, vector  bottles, vector  prices)
62         {
63                b = bottles, p = prices;
64                n = b.size(), c = C;
65  for (int i = 1; i < two(n); ++i)
66                    calculateCost(i);
67                memset(dp, -1, sizeof(dp));
68  return dfs(two(n) - 1);
69         }
70 };
View Code
网站名称：SRM478-创新互联
URL分享：http://cdkjz.cn/article/igpge.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

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

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

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

在线咨询 提交需求
友情链接 交换友情链接
水泥基自流平成都宣传画册设计电商网站建设普格博源建站网站建设公司网站推广公司攀枝花网站建设虚拟主机购买成都定制网站开发定制网站设计

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

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

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