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

又是rng_58的神題。。SRM478

250pt:

創(chuàng)新互聯(lián)企業(yè)建站,十多年網(wǎng)站建設(shè)經(jīng)驗，專注于網(wǎng)站建設(shè)技術(shù)，精于網(wǎng)頁設(shè)計，有多年建站和網(wǎng)站代運(yùn)營經(jīng)驗，設(shè)計師為客戶打造網(wǎng)絡(luò)企業(yè)風(fēng)格，提供周到的建站售前咨詢和貼心的售后服務(wù)。對于網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計中不同領(lǐng)域進(jìn)行深入了解和探索，創(chuàng)新互聯(lián)在網(wǎng)站建設(shè)中充分了解客戶行業(yè)的需求，以靈動的思維在網(wǎng)頁中充分展現(xiàn)，通過對客戶行業(yè)精準(zhǔn)市場調(diào)研，為客戶提供的解決方案。

題意：給定一個初始數(shù)x，對于這個數(shù)可以進(jìn)行x*4+3，或者x*8+7的操作。最多進(jìn)行100000次操作

    問最少經(jīng)過幾次出現(xiàn)%1000000007 == 0的情況。。

思路：

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

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

   所以我們發(fā)現(xiàn)兩個操作都可以合并成x * 2 + 1的操作。所以直接模擬30w次*2+1操作。

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

code：

 1 #line 7 "CarrotJumping.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 
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<int> VI;
35 typedef vector<string> VS;
36 typedef vector<double> VD;
37 typedef long long LL;
38 typedef pair<int,int> 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。現(xiàn)在已知每個杯子當(dāng)前的水量，數(shù)量為x的杯子可以賣p[i]的錢。不過在賣之前可以做任意次操作：選兩個杯子a和b，把a(bǔ)的水往b倒，知道a空了或者b滿了為止。問這些杯子經(jīng)過操作后，最多一共能賣多少錢。

思路： 如果選中若干個杯子，那么這些杯子的狀態(tài)便是固定的，因為必須倒到滿或者空。

     那么集合dp的感覺就很明顯了

     dp[mask]表示選中mask狀態(tài)個的被子最多賣多少錢。然后枚舉子狀態(tài)即可。。

code：

 1 #line 7 "KiwiJuice.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 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<int> VI;
35 typedef vector<string> VS;
36 typedef vector<double> VD;
37 typedef long long LL;
38 typedef pair<int,int> PII;
39 int dp[1 << 16], cost[1 << 16];
40 class KiwiJuice
41 {
42 public:
43 int c, n;
44         vector<int> 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 <int> bottles, vector <int> 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

網(wǎng)站標(biāo)題：SRM478-創(chuàng)新互聯(lián)
網(wǎng)頁網(wǎng)址：http://bm7419.com/article14/igpge.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站改版、手機(jī)網(wǎng)站建設(shè)、小程序開發(fā)、企業(yè)建站、網(wǎng)站建設(shè)、關(guān)鍵詞優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)頁設(shè)計公司