D - Ki
题意：给一棵有根树，节点1为根，有$Q$次操作，每次操作将一个节点及其子树的所有节点的权值加上一个值，问最后每个节点的权值。
思路：dfs序再差分一下就行了。
#include <bits/stdc++.h>
using namespace std; const int N = 2e5 + ;
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 = , u, v; i < n; i++) {
scanf("%d%d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(, );
while (q--) {
long long x;
int u;
scanf("%d%lld", &u, &x);
val[dfn[u]] += x;
val[last[u] + ] -= x;
}
for (int i = ; i <= n; i++) {
val[i] += val[i - ];
ans[pos[i]] = val[i];
}
for (int i = ; i <= n; i++)
printf("%lld%c", ans[i], " \n"[i == n]);
return ;
}
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 + ; char s[N], t[N];
int ne[N][];
int fir[]; int main() {
scanf("%s%s", s + , t + );
int len1 = strlen(s + ), len2 = strlen(t + );
for (int i = len1; i >= ; i--) {
for (int j = ; j < ; j++)
ne[i][j] = fir[j];
if (i) fir[s[i] - 'a'] = i;
}
int id = , ans = ;
for (int i = ; i <= len2; i++) {
if (ne[id][t[i] - 'a']) {
id = ne[id][t[i] - 'a'];
} else {
if (!fir[t[i] - 'a']) {
puts("-1");
return ;
}
id = fir[t[i] - 'a'];
ans++;
}
}
printf("%lld\n", 1LL * (ans - ) * len1 + id);
return ;
}
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 + ;
ll dp[][][][]; ll solve(ll l, ll r, int pos, bool limit1, bool limit2, bool lead) {
if (pos < ) return ;
ll &ans = dp[pos][limit1][limit2][lead];
if (ans != -) return ans;
ans = ;
int up2 = limit2 ? (r >> pos & ) : ;
int up1 = limit1 ? (l >> pos & ) : ;
for (int i = up1; i <= ; i++)
for (int j = ; j <= up2; j++) {
if (i > j) continue;
if (lead && i != j) continue;
(ans += solve(l, r, pos - , limit1 && i == up1, limit2 && j == up2, lead && j == )) %= MOD;
}
return ans;
} int main() {
memset(dp, -, sizeof(dp));
ll l, r;
scanf("%lld%lld", &l, &r);
printf("%lld", solve(l, r, , , , ));
return ;
}