又是一个坐牢局，最近几天就不适合写代码。
D. Sternhalma
题意
跳棋。给一个如题中图所示的棋盘，每个格子都带有一个分值，棋盘上某些格子里有一个棋子。可以执行两种操作：1.随便移去一个棋子，不得分；2.设有相邻且共线三个格子u,v,w（v在中间），如果u,v中都有棋子而w没有，可以把u中棋子越过v跳到w位置，然后移去v中棋子，获得v处的分值。现在有n次询问，每次询问告诉你每个格子有无棋子，问能得到的最大分值。
解法
由于只有19个格子，考虑状压，可以用一个数来表示棋盘上的一个棋子摆放状态。手动打出可行的每种状态转移方式，然后类似暴力模拟，求出当前状态的最大分值即可。如果写法不够好而导致TLE，可以在所有询问开始之前，从0开始反向转移状态，求出每个初始状态的最大分值，每次询问后直接输出对应结果即可。
听说有傻子看完题之后整个思路都对，就没想到用状压，真离谱吧，反正不是我。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 25;
const int M = 1e6 + 5;
int scr[N], n, cnt[M];
char ch[N];
queue<int> q;
int tp;
bool inq[M];
struct node{
int u, v, w;
node(int u1 = 0, int v1 = 0, int w1 = 0){
u = u1;
v = v1;
w = w1;
}
};
vector<node> ve;
void d(int uu, int vv, int ww){
ve.push_back(node(uu, vv, ww));
ve.push_back(node(ww, vv, uu));
}
void init(){
d(0,1,2); d(2,6,11); d(11,15,18); d(16,17,18); d(7,12,16); d(0,3,7);
d(0,4,9); d(1,4,8); d(3,4,5); d(1,5,10); d(2,5,9); d(4,5,6);
d(3,8,13); d(4,8,12); d(7,8,9); d(4,9,14); d(5,9,13); d(8,9,10); d(5,10,15); d(6,10,14); d(9,10,11);
d(8,13,17); d(9,13,16); d(12,13,14); d(9,14,18); d(10,14,17); d(13,14,15);
}
int main(){
init();
int sz = ve.size();
cin.tie(0);
for(int i = 0; i < 19; i++){
cin >> scr[i];
}
cnt[0] = 0;
inq[0] = 1;
q.push(0);
int tp, to;
while(!q.empty()){
tp = q.front();
q.pop();
for(int i = 0; i < 19; i++){
if(!(tp & (1 << i))){
to = tp | (1 << i);
if(!inq[to]){
inq[to] = 1;
q.push(to);
}
cnt[to] = max(cnt[to], cnt[tp]);
}
}
for(int i = 0; i < sz; i++){
if((!(tp & (1 << ve[i].u))) && (!(tp & (1 << ve[i].v))) && (tp & (1 << ve[i].w))){
to = tp - (1 << ve[i].w) + (1 << ve[i].u) + (1 << ve[i].v);
if(!inq[to]){
inq[to] = 1;
q.push(to);
}
cnt[to] = max(cnt[to], cnt[tp] + scr[ve[i].v]);
}
}
}
cin >> n;
while(n--){
int st = 0;
for(int i = 0; i < 19; i++){
cin >> ch[i];
if(ch[i] == '#') st += (1 << i);
}
cout << cnt[st] << endl;
}
return 0;
}
I. Dragon Bloodline
题意
用一些元素合成龙蛋。合成每个龙蛋需要n种元素，第i种元素需要a[i]个；有k种工具龙可以用来收集元素，第i种工具龙有b[i]个，它们中每个可以任选一种元素，收集2i-1个该种元素。问最多能合成多少个龙蛋。
解法
读完题就在纠结，如何判断一个工具龙是收集需求量大的元素好，还是收集很多需求量少的元素好？很难判断。但是如果先假定一个要合成的龙蛋的个数，再判断能否合成这么多龙蛋，就比较简单：
建立一个优先队列，里面存储每一种元素的总需求量。尽量用收集量大的工具龙，去收集需求量大的元素。这样，浪费掉的收集量一定是最小的。因为收集一定量的元素之后，考虑剩下的工具龙，它们的收集量越“零散”，在后续过程中越不容易造成浪费。
所以，上述过程套上二分答案就行了。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
const int N = 5e4 + 5;
int ti, n, k;
ll a[N], b[25], c[25], num[25];
priority_queue<ll> q;
bool check(ll x){
while(!q.empty()) q.pop();
for(int i = 1; i <= n; i++){
q.push(a[i] * x);
}
ll tp, db;
int p = k;
while(!q.empty()){
if(!p) return 0;
tp = q.top();
q.pop();
if(tp > num[p]){
db = min(tp / num[p], b[p]);
b[p] -= db;
tp -= db * num[p];
if(!b[p]) p--;
if(tp) q.push(tp);
}
else{
b[p]--;
if(!b[p]) p--;
}
}
return 1;
}
int main(){
scanf("%d", &ti);
while(ti--){
scanf("%d%d", &n, &k);
ll totnd = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
totnd += a[i];
}
for(int i = 1; i <= k; i++){
scanf("%d", &b[i]);
c[i] = b[i];
}
num[1] = 1;
for(int i = 2; i <= k; i++){
num[i] = num[i - 1] * 2;
}
ll totnum = 0;
for(int i = 1; i <= k; i++){
totnum += num[i] * b[i];
}
ll l = 1, r = totnum / totnd, mid, ans = 0;
bool rst;
while(l <= r){
mid =(l + r) / 2;
for(int i = 1; i <= k; i++){
b[i] = c[i];
}
rst = check(mid);
if(!rst){
r = mid - 1;
}
else{
ans = max(ans, mid);
l = mid + 1;
}
}
printf("%lld\n", ans);
}
return 0;
}