D - Ki
题意：给一棵有根树，节点1为根，有$Q$次操作，每次操作将一个节点及其子树的所有节点的权值加上一个值，问最后每个节点的权值。
思路：dfs序再差分一下就行了。
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 7; vector<int> G[N]; int dfn[N], id, n, q, last[N], pos[N]; long long val[N], ans[N]; void dfs(int u, int fa) { dfn[u] = ++id; pos[id] = u; for (auto v: G[u]) { if (v == fa) continue; dfs(v, u); } last[u] = id; } int main() { scanf("%d%d", &n, &q); for (int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); while (q--) { long long x; int u; scanf("%d%lld", &u, &x); val[dfn[u]] += x; val[last[u] + 1] -= x; } for (int i = 1; i <= n; i++) { val[i] += val[i - 1]; ans[pos[i]] = val[i]; } for (int i = 1; i <= n; i++) printf("%lld%c", ans[i], " \n"[i == n]); return 0; }
E - Strings of Impurity
题意：给两个字符串$s$, $t$，把$s$复制$10^{100}$次成$s‘$，即‘abc‘变成‘abcabc...abcabc‘，问$t$作为$s‘$的子序列出现，最早结束位置的下标，不存在则输出-1。
如样例一
$s‘$: conteStcONtest
$t$: son
大写表示匹配上的位置，答案为10。
思路：子序列问题都可以用一个$ne[i][j]$表示$s$串中到了$i$位置，下一个$j$字符的位置，从后往前扫可以预处理出来，然后统计答案就用$t$来贪心地匹配$s$，能匹配多前就多前，当前位置之后没有$t_{j}$这个字符了，就必须进入下一个$s$串中，然后答案只需要看跳了多少个$s$串和最后的位置在哪。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; char s[N], t[N]; int ne[N][26]; int fir[26]; int main() { scanf("%s%s", s + 1, t + 1); int len1 = strlen(s + 1), len2 = strlen(t + 1); for (int i = len1; i >= 0; i--) { for (int j = 0; j < 26; j++) ne[i][j] = fir[j]; if (i) fir[s[i] - ‘a‘] = i; } int id = 0, ans = 1; for (int i = 1; i <= len2; i++) { if (ne[id][t[i] - ‘a‘]) { id = ne[id][t[i] - ‘a‘]; } else { if (!fir[t[i] - ‘a‘]) { puts("-1"); return 0; } id = fir[t[i] - ‘a‘]; ans++; } } printf("%lld\n", 1LL * (ans - 1) * len1 + id); return 0; }
F - Coincidence
题意：给定 $L$ 和 $R$，问有多少对 $x, y\left(L \leq x \leq y \leq R\right)$ 满足$y$ Mod $x = y$ XOR $x$
思路：
$\because y$ Mod $x < x$
$\therefore y$ XOR $x < x$
所以说明$y$和$x$最高位的1必须在同一个位置
$\therefore \dfrac {y}{x} < 2$
$\therefore y - x = y$ XOR $x$
举几个例子就会发现其实满足这个条件的$y$和$x$在二进制下是可以不用借位直接相减的，比如
$y$: 10110(22)
$x$: 10010(18)
此时$y$ XOR $x = y - x = 4$
就可以得到$y$ And $x = x$且$x$和$y$最高位的1的位置相同
然后就可以数位DP做。
数位DP同时枚举两个数二进制的情况，其中$y$不超过$R$，$x$不小于$L$，当前还有前导零的情况下，这一位$y$和$x$必须相同，之后保证一下$x$的每一位不能大于$y$(即出现$y$当前位是0，$x$当前位是1)就行了。
#include <bits/stdc++.h> #define ll long long using namespace std; const int MOD = 1e9 + 7; ll dp[70][2][2][2]; ll solve(ll l, ll r, int pos, bool limit1, bool limit2, bool lead) { if (pos < 0) return 1; ll &ans = dp[pos][limit1][limit2][lead]; if (ans != -1) return ans; ans = 0; int up2 = limit2 ? (r >> pos & 1) : 1; int up1 = limit1 ? (l >> pos & 1) : 0; for (int i = up1; i <= 1; i++) for (int j = 0; j <= up2; j++) { if (i > j) continue; if (lead && i != j) continue; (ans += solve(l, r, pos - 1, limit1 && i == up1, limit2 && j == up2, lead && j == 0)) %= MOD; } return ans; } int main() { memset(dp, -1, sizeof(dp)); ll l, r; scanf("%lld%lld", &l, &r); printf("%lld", solve(l, r, 60, 1, 1, 1)); return 0; }
Atcoder Beginner Contest 138 简要题解
原文：https://www.cnblogs.com/Mrzdtz220/p/11671345.html
