有1...10k的砝码，在天枰上，左右轮流放置砝码，要求之后左右轮流比另一侧重量要大，要求相邻两次砝码不能相同。
解题报告给出(i,j,k)表示balance,j表示最后一次的砝码重量,k表示第几步，然后表示从点(0,0,0)->(x,y,m)的图论问题，跟动态规划是等价的，复杂度是O(w^3*m)。
我给出了一个比上述算法更优的一个算法，做法是用dp[i][j]表示第i步balance达到j时的所有可能的砝码情况的二进制mask，复杂度是O(w^2*m)，但要求w<32。
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std; int dp[][];
char w[]; int main() {
int m;
scanf("%s%d", w, &m); memset(dp, , sizeof(dp));
dp[][] = ; for (int i = ; i <= m; i++) {
for (int j = ; j <= ; j++) {
if (dp[i - ][j] > ) {
for (int k = ; k <= ; k++) if (w[k - ] == '') {
if (dp[i - ][j] ^ ( << k)) {
if (j >= && j - k < ) {
dp[i][j - k] |= ( << k);
} else if (j < && j + k > ) {
dp[i][j + k] |= ( << k);
}
}
}
}
}
} int ans_j = -;
for (int j = ; j <= ; j++) if (dp[m][j] > )
ans_j = j; if (ans_j == -) {
printf("NO\n");
} else {
printf("YES\n");
int i = m;
vector<int> ans;
int last = ;
while (i > ) {
for (int j = ; j <= ; j++) {
if (dp[i][ans_j] & ( << j)) {
if (j == last) continue; ans.push_back(j); if (ans_j >= ) ans_j -= j;
else ans_j += j; last = j; break;
}
}
i--;
}
for (i = ans.size() - ; i >= ; i--) {
printf("%d ", ans[i]);
}
printf("\n");
}
}
很裸的一个线段树了。
#include <cstdio>
#include <iostream>
using namespace std; const int MAXN = << ; int num[MAXN]; class SegNode {
public:
int L, R;
int level, sum;
} node[MAXN * ]; class SegTree {
public:
void build(int r, int L, int R) {
node[r].L = L;
node[r].R = R; if (L == R) {
// leaf
node[r].level = ;
node[r].sum = num[L];
} else {
// non leaf
int M = (L + R) / ;
build( * r, L, M);
build( * r + , M + , R);
node[r].level = node[ * r].level + ;
if (node[r].level & ) {
node[r].sum = node[ * r].sum | node[ * r + ].sum;
} else {
node[r].sum = node[ * r].sum ^ node[ * r + ].sum;
}
}
}
void update(int r, int p, int b) {
if (node[r].L == node[r].R) {
node[r].sum = b;
} else {
if (p <= node[ * r].R) {
// left
update( * r, p, b);
} else if (p >= node[ * r + ].L) {
// right
update( * r + , p, b);
}
if (node[r].level & ) {
node[r].sum = node[ * r].sum | node[ * r + ].sum;
} else {
node[r].sum = node[ * r].sum ^ node[ * r + ].sum;
}
}
}
} tree; int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = ; i <= ( << n); i++) {
scanf("%d", &num[i]);
}
tree.build(, , << n);
for (int i = ; i < m; i++) {
int p, b;
scanf("%d%d", &p, &b);
tree.update(, p, b);
printf("%d\n", node[].sum);
}
}