又是rng_58的神题。。
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：
#line 7 "CarrotJumping.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair #define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i)
#define M 1000000007
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII; class CarrotJumping
{
public:
int theJump(int x)
{
for (int i = ; i <= ; ++i){
x = (x * + ) % M;
if (x == && i >= ) return (i + ) / ;
}
return -;
}
};
500pt
题意：有N<=15个杯子，所有杯子的容量都是一样的，为C<50。现在已知每个杯子当前的水量，数量为x的杯子可以卖p[i]的钱。不过在卖之前可以做任意次操作：选两个杯子a和b，把a的水往b倒，知道a空了或者b满了为止。问这些杯子经过操作后，最多一共能卖多少钱。
思路： 如果选中若干个杯子，那么这些杯子的状态便是固定的，因为必须倒到满或者空。
那么集合dp的感觉就很明显了
dp[mask]表示选中mask状态个的被子最多卖多少钱。然后枚举子状态即可。。
code：
#line 7 "KiwiJuice.cpp"
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std; #define PB push_back
#define MP make_pair
#define two(i) (1 << i)
#define REP(i,n) for(i=0;i<(n);++i)
#define FOR(i,l,h) for(i=(l);i<=(h);++i)
#define FORD(i,h,l) for(i=(h);i>=(l);--i) typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<double> VD;
typedef long long LL;
typedef pair<int,int> PII;
int dp[ << ], cost[ << ];
class KiwiJuice
{
public:
int c, n;
vector<int> b, p;
void calculateCost(int mask){
int v = , bn = ;
for (int i = ; i < n; ++i)
if (two(i) & mask){
v += b[i];
++bn;
}
cost[mask] = p[v % c] + (v / c) * p[c] + p[] * (bn - v / c - );
}
int dfs(int mask){
if (dp[mask] != -) return dp[mask];
dp[mask] = ;
for (int i = mask; i; i = (i-) & mask)
dp[mask] = max(cost[i] + dfs(mask ^ i), dp[mask]);
return dp[mask];
}
int theProfit(int C, vector <int> bottles, vector <int> prices)
{
b = bottles, p = prices;
n = b.size(), c = C;
for (int i = ; i < two(n); ++i)
calculateCost(i);
memset(dp, -, sizeof(dp));
return dfs(two(n) - );
}
};