光 100pts
赛时打的错解A了，就很神奇；
其实可以发现答案有可二分性，考虑二分答案，每次check时枚举左上角和右下角的耗电量，然后对左下角的耗电量再进行二分，最后判定以下即可；
赛时就这么打的，然后赛后拍出来了；
其实这个思路是对的，只是 $ \lfloor \frac n4 \rfloor $ 这个条件有误差，所以暴力在这个范围内判断一下即可；
时间复杂度：$ O(n^2 \log^2 n) $，常数极大，但是跑不满，可以过；
爬 10pts
直接暴搜10pts；
考虑正解，我们发现，能在某一个节点产生贡献的只有它自己和其直接儿子，所以只考虑这一部分即可；
因为是异或，考虑对值进行二进制拆分，依次考虑每一位的贡献；
假设现在考虑到第 $ k $ 位，设当前节点 + 其直接儿子为 $ tot $，其中这一位为 $ 1 $ 的数的个数有 $ sum $ 个；
先考虑当前节点不是根的情况：
那么只有当有奇数个这一位为 $ 1 $ 的数在这个节点时，这一位才能产生贡献，其它数咋跳都没有影响，这个方案数为：
\[(C_{sum}^{1} + C_{sum}^{3} + C_{sum}^{5} + ...) \times 2^{n - sum - 1} \]其中：
\[C_{sum}^{1} + C_{sum}^{3} + C_{sum}^{5} + ... = 2^{sum - 1} \]注意上面两项并不能合并（因为前一项是有值的，合并以后可能就没值了）；
然后减去只有一个数的情况，考虑 $ sum $ 个数，每个数只上去一次，剩下的 $ tot - 1 $ 个数不动，其余的 $ n - tot - 1 $ 个数随便，方案数为：
\[sum \times 2^{n - tot - 1} \]总方案数为：
\[2^{sum - 1} \times 2^{n - sum - 1} - sum \times 2^{n - tot - 1} \]最后乘一个 $ 2^k $ 即可；
对于是根的情况，分奇偶讨论一下即可（因为根不能往上跳）；
时间复杂度 $ \Theta(n \log 1000000000) $；
点击查看代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long mod = 1e9 + 7;
int n;
long long a[500005];
long long ans;
struct sss{
int t, ne;
}e[200005];
int h[200005], cnt;
void add(int u, int v) {
e[++cnt].t = v;
e[cnt].ne = h[u];
h[u] = cnt;
}
long long fac[100005], fav[100005], p[100005];
long long ksm(long long a, long long b) {
long long ans = 1;
while(b) {
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
long long C(long long n, long long m) {
if (n == m) return 1;
if (m == 0) return 1;
if (n < m) return 0;
return fac[n] * fav[m] % mod * fav[n - m] % mod;
}
int main() {
freopen("climb.in", "r", stdin);
freopen("climb.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int xx;
for (int i = 2; i <= n; i++) {
cin >> xx;
add(xx, i);
}
fac[0] = 1;
fav[0] = 1;
p[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = fac[i - 1] * i % mod;
fav[i] = ksm(fac[i], mod - 2);
p[i] = p[i - 1] * 2 % mod;
}
for (int k = 30; k >= 0; k--) {
for (int i = 1; i <= n; i++) {
int sum = 0;
int tot = 1;
for (int j = h[i]; j; j = e[j].ne) {
int u = e[j].t;
tot++;
if ((1 << k) & a[u]) sum++;
}
if (tot == 1) continue;
if ((1 << k) & a[i]) sum++;
if (sum == 0) continue;
if (i == 1) {
bool vis = ((1 << k) & a[i]);
if (vis) {
long long o = 0;
o = ((p[max(0, sum - 2)] * p[max(0, n - sum)] % mod - p[max(0, n - tot)]) % mod + mod) % mod;
ans = (ans + (1 << k) * o % mod) % mod;
} else {
long long o = 0;
o = (p[max(0, sum - 1)] * p[max(0, n - sum - 1)]) % mod;
ans = (ans + (1 << k) * o % mod) % mod;
}
} else {
long long o = 0;
o = ((p[max(0, sum - 1)] * p[max(0, n - sum - 1)] % mod - sum * p[max(0, n - tot - 1)] % mod) % mod + mod) % mod;
ans = (ans + (1 << k) * o % mod) % mod;
}
}
}
cout << ans;
return 0;
}
字符串 50pts；
赛时 $ \Theta(Tn^4) $ 暴力DP 50pts也是没谁了；
正解是贪心；
因为对于 $ B $ 有 $ c $ 的限制，所以我们构造出一种形如以 $ c $ 个 $ B $ 和 $ 1 $ 个 $ A $ 为循环节，循环 $ i $ 次的字符串；
如：当 $ c = 3 $ ，$ i = 2 $ 时，我们构造出的字符串为 $ BBBABBBA $，特别的，当 $ i = 1 $ 时，字符串是形如 $ BBBAAA $ （$ m $ 个 $ B $ 和 $ n $ 个 $ A $）的；
然后我们考虑枚举 $ i $，每次加入剩下的 $ A $ 和 $ B $；
先加 $ A $，从头加一个可以获得 $ 1 $ 的贡献，然后每剩下 $ a $ 个 $ A $ 就有 $ 1 $ 的贡献；
再加 $ B $，从末尾加一个可以获得 $ 1 $ 的贡献，然后先把循环节里的 $ B $ 补充成 $ b + 1 $ 的倍数并依据给的公式计算其贡献，然后每剩下 $ b $ 个 $ B $ 就有 $ 1 $ 的贡献；
有点细节需要注意；
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
int t;
int n, m, a, b, c;
int ans, sum;
int main() {
freopen("string.in", "r", stdin);
freopen("string.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> t;
while(t--) {
cin >> n >> m >> a >> b >> c;
ans = 0;
for (int i = 0; i <= min(n, m / c); i++) {
sum = 0;
if (i == 0) {
sum++;
sum += (n - 1) / a;
sum += (m - 1) / b;
sum++;
ans = max(ans, sum);
continue;
}
sum++;
sum += (2 * i - 1);
int suma = n - i;
if (suma > 0) {
sum++;
suma--;
}
if (suma > 0) sum += (suma / a);
int sumb = m - c * i;
if (sumb > 0) {
sumb--;
sum++;
}
if (sumb > 0) {
int o = c % b;
int res = 0;
if (o == 0) res = 1;
else res = b + 1 - o;
if (i * res >= sumb) {
int ss = sumb / res;
sum += ss * ((c + res - 1) / b);
sum += (i - ss) * ((c - 1) / b);
} else {
sum += i * ((c + res - 1) / b);
sumb -= res * i;
sum += (sumb / b);
}
} else {
sum += i * ((c - 1) / b);
}
ans = max(ans, sum);
}
cout << ans << '\n';
}
return 0;
}
奇怪的函数 30pts
赛时 $ \Theta(nq) $ 暴力能有30pts更是没谁了；
To be continued...
标签：赛记,int,res,sum,long,sumb,ans,csp,模拟 From： https://www.cnblogs.com/PeppaEvenPig/p/18438789