A – 异或粽子
“傻逼题。”——XG_Zepto
这道题还是挺好做的，先把所有前缀异或和放入 Trie 树中，然后\(O(n)\)枚举右端点\(r\)，在 Trie 树中查找与前缀异或和\([1-r]\)异或的最大值并放入堆中（放入堆时标记好排名为\(1\)）。之后在堆中取出，并不停的放入排名逐渐变大的异或和查询值，收集前\(k\)个即可。
“傻逼题。”——XG_Zepto
这道题还是挺好做的，先把所有前缀异或和放入 Trie 树中，然后\(O(n)\)枚举右端点\(r\)，在 Trie 树中查找与前缀异或和\([1-r]\)异或的最大值并放入堆中（放入堆时标记好排名为\(1\)）。之后在堆中取出，并不停的放入排名逐渐变大的异或和查询值，收集前\(k\)个即可。
给定一个平面\((n,m)\)，处理如下操作：
给一个排列\(p[1-n]\)和取值范围在\([1,n]\)内的数组\(a[]\)，处理\(q\)个询问：在数组的字段\([l,r]\)内是否存在排列的环形偏移。
考虑正向扫描，处理出每一个位置上的数到左边「最近的上一个环形偏移数」的位置，并同时更新自己所在的位置供下一次循环进行使用：
这道题的主要做法就是贪心了。我们枚举\(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]];