problem1 link
$f[i][j]$表示经过前$i$个怪物之后，花费$j$个硬币可以得到的最大值。
problem2 link
设$nim[i]$表示数字$i$的nim值。那么题目就是求有多少个区间$[L,R]$满足这个区间内所有数字的nim值的抑或不是０．通过记录前缀和的个数，可以$O(n)$计算得到。现在问题是计算每个值的nim值。
可以用数学归纳法证明$i$的nim值等于$i$中的质因子的个数，比如$nim[6]=2,nim[12]=3$等。所以对于给出的的区间$[L,R]$,只需要枚举$sqrt{R}$之内的质数，判断$[L,R]$内哪些数字的质因子有该质数。
假设需要考虑的所有质数为$p_{1},p_{2},...,p_{m},n=R-L+1$，那么复杂度为$sum_{i=1}^{m}frac{n}{p_{i}}$
problem3 link
(1)首先考虑只有一个特殊点$A$，假设$A$为树根，那么只需要为每个点找到一个父节点即可，对于节点$i$来说，如果$j$满足$dist[i]<dist[j]$，那么$j$可以作为$i$的父节点。所以如果令$f[i]$表示可以作为$i$的父节点的节点数，那么答案为$prod_{i=1}^{n}(1+f(i))$
(2)考虑有两个特殊点$A,B$，假设$B$为树根，令$i$为$AB$之间距离$B$最近的节点($i$有可能就是Ａ),那么将从$i$开始以及Ａ的子节点这些都叫做$A$分支，其他的除了$B$以外的节点都叫做其他分支。令$AB$之间的长度为$p$.那么一个节点$j$满足$dist[A]-dist[B]=p$时，它就在其他分支上，否则就在A分支上。那么其他分支其实就是一个特殊点的问题，而Ａ分支可以看做$i$节点是新的$B$的两个特殊点的问题。
(3)现在考虑三个特殊点$ABC$。分两种情况：第一，存在一个节点$i$使得ABC在以$i$为根的三个分支上。现在所有除了$i$以外的点，要么在A,B,C中的一个分支上，要么在之外的分支上。比如，如果一个点$j$满足$A[j]-A[i]=B[j]-B[i]=C[j]-C[i]$，那么它就在其他分支上，如果$A[j]-A[i]=B[j]-B[i] eq C[j]-C[i]$，那么它就在C分支上。这样其他分支上就是一个特殊点的问题，而A分支，Ｂ分支，Ｃ分支就是三个两个特殊点的问题（$i$是两个特殊点问题中的$B$）; 第二，如果ABC是一条链上的三个点，假设Ｂ在中间，那么现在B作为树根，每个节点要么在Ａ分支，要么在Ｃ分支，要么在其他分支。这里需要首先确定AB和BC的长度，这里可以枚举节点$i$在其他分支，AB中间，BC之间，A分支上但是不是AB之间等情况来确定AB和BC的长度，这样就又转化成一个特殊点和两个特殊点的问题。
code for problem1
#include <vector>
class MonstersValley {
public:
int minimumPrice(std::vector<long long> dread, std::vector<int> price) {
const int n = static_cast<int>(dread.size());
std::vector<std::vector<long long>> f(
n + 1, std::vector<long long>(n * 2 + 1, -1));
f[0][0] = 0;
for (int i = 1; i <= n; ++i) {
long long t = dread[i - 1];
int c = price[i - 1];
for (int j = 0; j <= 2 * i; ++j) {
if (f[i - 1][j] != -1) {
f[i][j + c] = std::max(f[i][j + c], f[i - 1][j] + t);
if (f[i - 1][j] >= t) {
f[i][j] = std::max(f[i][j], f[i - 1][j]);
}
}
}
}
for (int i = 0; i <= n * 2; ++i) {
if (f[n][i] != -1) {
return i;
}
}
return 0;
}
};
code for problem2
#include <chrono>
#include <cmath>
#include <iostream>
#include <vector>
class TheDivisionGame {
public:
long long countWinningIntervals(int L, int R) {
std::vector<int> prime = ComputePrime(static_cast<int>(std::sqrt(R)) + 1);
int n = R - L + 1;
std::vector<int> value(n);
std::vector<int> nim(n, 0);
for (int i = 0; i < n; ++i) {
value[i] = i + L;
}
for (size_t i = 0; i < prime.size() && prime[i] * prime[i] <= R; ++i) {
int s = L;
if (L % prime[i] != 0) {
s += prime[i] - L % prime[i];
}
while (s <= R) {
while (value[s - L] % prime[i] == 0) {
value[s - L] /= prime[i];
nim[s - L] += 1;
}
s += prime[i];
}
}
for (int i = 0; i < n; ++i) {
if (value[i] != 1) {
++nim[i];
}
}
std::vector<int> num(32, 0);
num[0] = 1;
long long result = 0;
for (int i = 0, prefix = 0; i < n; ++i) {
prefix ^= nim[i];
result += i + 1 - num[prefix];
num[prefix] += 1;
}
return result;
}
private:
std::vector<int> ComputePrime(int M) {
std::vector<int> prime;
std::vector<bool> tag(M + 1, false);
for (int i = 2; i <= M; ++i) {
if (!tag[i]) {
prime.push_back(i);
}
for (size_t j = 0; j < prime.size() && prime[j] * i <= M; ++j) {
tag[prime[j] * i] = true;
if (i % prime[j] == 0) {
break;
}
}
}
return prime;
}
};
code for problem3
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
class UnknownTree {
static constexpr int mod = 1000000009;
public:
int getCount(std::vector<int> distancesA, std::vector<int> distancesB,
std::vector<int> distancesC) {
int result = 0;
for (int i = 0; i < static_cast<int>(distancesA.size()); ++i) {
Add(result, Compute(i, distancesA, distancesB, distancesC));
}
Add(result, ComputeLine(distancesA, distancesB, distancesC));
Add(result, ComputeLine(distancesB, distancesA, distancesC));
Add(result, ComputeLine(distancesA, distancesC, distancesB));
return result;
}
private:
void Add(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
int Compute(int root, const std::vector<int> &A, const std::vector<int> &B,
const std::vector<int> &C) {
std::vector<int> other, set_a, set_b, set_c;
std::vector<int> set_a_root, set_b_root, set_c_root;
int n = static_cast<int>(A.size());
for (int i = 0; i < n; ++i) {
if (i != root) {
int da = A[i] - A[root];
int db = B[i] - B[root];
int dc = C[i] - C[root];
if (da > 0 && da == db && da == dc) {
other.push_back(da);
} else if (da > 0 && da == db) {
set_c.push_back(C[i]);
set_c_root.push_back(da);
} else if (da > 0 && da == dc) {
set_b.push_back(B[i]);
set_b_root.push_back(da);
} else if (db > 0 && db == dc) {
set_a.push_back(A[i]);
set_a_root.push_back(db);
} else {
return 0;
}
}
}
long long result = SolveCase1(other);
result = result * SolveCase2(A[root], set_a_root, set_a) % mod;
result = result * SolveCase2(B[root], set_b_root, set_b) % mod;
result = result * SolveCase2(C[root], set_c_root, set_c) % mod;
return static_cast<int>(result);
}
int ComputeLine(const std::vector<int> &A, const std::vector<int> &B,
const std::vector<int> &C) {
std::set<std::pair<int, int>> all;
auto Insert = [&](int ab, int bc) {
if (ab > 0 && bc > 0) {
all.insert({ab, bc});
}
};
int n = static_cast<int>(A.size());
for (int i = 0; i < n; ++i) {
Insert(A[i] - B[i], C[i] - B[i]);
Insert(A[i] + B[i], C[i] - B[i]);
Insert(B[i] - A[i], C[i] - B[i]);
Insert(A[i] - B[i], B[i] + C[i]);
Insert(A[i] - B[i], B[i] - C[i]);
}
int result = 0;
for (auto &e : all) {
Add(result, ComputeLine(e.first, e.second, A, B, C));
}
return result;
}
int ComputeLine(int ab, int bc, const std::vector<int> &A,
const std::vector<int> &B, const std::vector<int> &C) {
int n = static_cast<int>(A.size());
std::vector<int> other, set_a, set_c;
std::vector<int> set_a_b, set_c_b;
for (int i = 0; i < n; ++i) {
if (A[i] - B[i] == ab && C[i] - B[i] == bc) {
other.push_back(B[i]);
} else if (A[i] - B[i] == ab && OnLater(bc, B[i], C[i])) {
set_c.push_back(C[i]);
set_c_b.push_back(B[i]);
} else if (C[i] - B[i] == bc && OnLater(ab, B[i], A[i])) {
set_a.push_back(A[i]);
set_a_b.push_back(B[i]);
} else {
return 0;
}
}
long long result = SolveCase1(other);
result = result * SolveCase2(ab, set_a_b, set_a) % mod;
result = result * SolveCase2(bc, set_c_b, set_c) % mod;
return static_cast<int>(result);
}
bool OnLater(int d, int da, int db) {
return (da + db == d) || (da - db == d) || (d > 1 && da + db > d);
}
int SolveCase1(const std::vector<int> &d) {
int n = static_cast<int>(d.size());
long long result = 1;
for (int i = 0; i < n; ++i) {
int t = 1;
for (int j = 0; j < n; ++j) {
if (j != i && d[j] < d[i]) {
++t;
}
}
result = result * t % mod;
}
return static_cast<int>(result);
}
int SolveCase2(int ab, const std::vector<int> &B, std::vector<int> &A) {
int n = static_cast<int>(B.size());
if (n == 0) {
return 1;
}
std::vector<int> set_b, set_a_middle, set_a_other;
int middle_branch = 0;
for (int i = 0; i < n; ++i) {
if (B[i] + ab == A[i]) {
set_b.push_back(B[i]);
} else {
if (B[i] + A[i] < ab) {
return 0;
} else if (B[i] + A[i] == ab) {
set_a_middle.push_back(B[i]);
} else if (B[i] - A[i] == ab) {
set_a_other.push_back(A[i]);
} else if (B[i] + A[i] > ab) {
++middle_branch;
} else {
return 0;
}
}
}
long long result = SolveCase1(set_b);
if (set_a_middle.size() == 0) {
if (middle_branch != 0) {
return 0;
}
result = result * SolveCase1(set_a_other) % mod;
return static_cast<int>(result);
}
std::sort(set_a_middle.begin(), set_a_middle.end());
int m = static_cast<int>(set_a_middle.size());
for (int i = 0; i + 1 < m; ++i) {
if (set_a_middle[i] == set_a_middle[i + 1]) {
return 0;
}
}
int delta = set_a_middle[0];
if (delta >= ab) {
return 0;
}
std::vector<int> d_set_a, d_set_b;
for (int i = 0; i < n; ++i) {
if (B[i] + ab != A[i]) {
if (B[i] + A[i] == ab) {
if (B[i] != delta) {
d_set_b.push_back(B[i] - delta);
d_set_a.push_back(A[i]);
}
} else {
if (B[i] <= delta) {
return 0;
}
d_set_b.push_back(B[i] - delta);
d_set_a.push_back(A[i]);
}
}
}
result = result * SolveCase2(ab - delta, d_set_b, d_set_a) % mod;
return static_cast<int>(result);
}
};