这道题的主要做法就是贪心了。我们枚举\(i\)从\(n-1\)到\(1\)，记\(vis[i]\)为编号为\(i\)的节点是否可以转移、\(arr[i]\)为\(i\)位置上的数，在转移关系集中寻找\((i,j), vis[j]=true\)的\(j\)。由于我们是从后向前转移，所以我们找到的这些\(j\)的位置都是在\(i\)之后的，符合转移要求。之后我们验证目前已转移的答案\(ans\)与满足条件的关系个数\(cnt\)与\(i\)的和是否为\(n\)，如果符合意味着转移符合条件，便直接进行转移；如果不符合，那么我们把该点的标记打上，意味着可以从此被转移。
很简单，扫描的时候如果所在数位为偶数位，向答案添加当前数位即可。
// A.cpp
#include <bits/stdc++.h>
using namespace std;
char str[66000];
int main()
{
int ans = 0, len;
scanf("%d", &len), scanf("%s", str + 1);
for (int i = 1; i <= len; i++)
if (((str[i] - '0') & 1) == 0)
ans += i;
printf("%d", ans);
return 0;
}
我们先来考虑无限制的版本，也就是不考虑询问的硬币数量限制。我们可以用一个完全背包搞一搞，复杂度为线性。
dp[0] = 1;
for (int i = 0; i < 4; i++)
for (int j = ci[i]; j < MAX_N; j++)
dp[j] += dp[j - ci[i]];
学习树上差分的前提是：
学习了这些之后，我们就可以开始学习树上差分了。树上差分的思想跟差分类似：都是在不得不求前缀和的情况下，将区间操作变为单点操作，降低复杂度。树上差分曾两次在 NOIp 系列比赛中出现过，所以学习树上差分很有必要（我怀疑是出题组不敢出树链剖分，但又要考察选手们对树上操作的熟悉程度，所以采用了这么个坑爹玩意）。我们先来学习一个基本的操作：点的链上区间加。
首先规定，\(N<M\)。之后写出统计答案的式子：
\[ \sum_{i=1}^N \sum_{j=1}^M lcm(i,j) \\ \sum_{i=1}^N \sum_{j=1}^M \frac{ij}{\gcd(i,j)} \]
然后我们可以试着去枚举最大公约数\(gcd(i,j)=d\)，然后让\(i,j\)成为唯一的两个互质因子。
这道题还是比较有意思的（啊呀看了好久的题解才会写，真菜），主要就是把\(d\)转换成了：
\[ d(xy) = \sum_{i|x}^x \sum_{j|y}^y [\gcd(i,j) = 1] \]
可以感性理解一下：每一次约数被枚举出来的时候，只有互质的情况下才会被计数，避免了重复计数。 Continue reading →