Problem A. 多国语言 做法 设 ，这两个数组可以扫描一遍 数组得到。 记 ，如果 ，输出 ">-<";否则如果 ，输出 "^v^";否则只存在唯一的 ，满足 ，如果此时 ，则输出 ，否则输出 "^v^"。 时间复杂度 。 代码 #include <bits/stdc++.h> using namespace std; const int maxn = 100100; int cnt[maxn], cntb[maxn], a[maxn]; int main(void) { // freopen(&quo...

写在前面 之前给牛客的提高组验过几次题，作为出题人还是第一次，中间有一些小锅，包括B题的样例不满足y<=n等等（实际上原来的第一组数据就是样例，后面修改重判了），但是最终还算比较完美 的结束了。 由于个人比较喜欢思维题，因此四道题的实现难度都不是很大，除了C题稍微有点套路（是数学题套数据结构）。 简单提要：A题比较简单，读懂题意基本就能AC了；B题其实是双向链 表，但是没有卡平衡树做法，因此不想动脑筋直接敲平衡树也是能AC的；C题是线段树维护矩阵 / 多项式等，由于不想卡常时限给了std的10倍，因此不管维护什么都是能AC的（除非常数真的巨大）；D题是一道难度较高的思维题，会KMP就能得...

题意 给出整数数组，求q次，每次给，求 。答案对1,000,000,007取模 题解 做法一 每次询问暴力求解。复杂度，不可接受。预计通过0%。 做法二 考虑对做法一进行优化，如果每次询问只枚举i，剩下的。这部分可以预处理出a的前缀和sum(即sum[i]=a[1]+...+a[n])，内查询。复杂度。预计通过30%。 做法三 观察到，所以。那么可以预处理的前缀和和的前缀和，每次询问内查询。复杂度。预计通过100%。 代码 #include <bits/stdc++.h> #define ll long long const int maxn = 100100; const int...

题意 螺旋状棋盘(如下)，棋子一开始在格子1，q次询问，每次询问x，表示棋子往前走x步(循环，n*n->1)，且分数加上行号和当前行号距离<x或列号和当前列号距离<x的格子的编号之和，输出每次走完的分数。 题解 关键词 预处理，二维前缀和 做法一 首先处理出编号i与行和列的关系，即求出a[x][y]为x行y列的编号，b[i]为编号i的行，c[i]为编号i的列。接下来模拟游戏过程，每次暴力把合法的格子的编号加上即可。复杂度 ，预计通过30%。其中k=6，是骰子的最高点数。 做法二 可以发现每次加上的格子由一些行和一些列组成，那么我们可以预处理出每行和每列的和，然后模拟时加上这些...

题意 有n个任务，m个处理任务的队列。任务处理时间为a[1],...,a[n]。按顺序从1-n处理任务。问有多少对满足第i个任务完成时间严格大于第j个任务完成的时间。 题解 关键词 优先队列树状数组 做法一 分为两步，第一步模拟求出结束的顺序，即得到一个数组b，b[i]表示第i号是第b[i]个办理完成的。这部分可模拟完成。然后遍历，得到b[i]>b[j]的数量。这部分也是。总复杂度，预计通过30%。 做法二 考虑加速做法一的两个部分。模拟部分可以使用优先队列进行加速。的复杂度得到数组b。求解，b[i]>b[j]的数量可以通过树状数组（或归并排序求逆序对的方法）加速。复杂度也是。总复...