题目 思路：先进行一遍全部过程的模拟储存下来，为了方便模拟尽量先将相同的方向走完，而对于多少步step，将连续的相同方向当作一步，如DDDDDULLL->5D1U3L，只需判别存储好的全部模拟字符串前后不同步数+1即可，细节见代码。 #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #include<vector> #define pii ...

题目 思路：可以知道每一个点要想造成一个不能通过的结果，需要它的正对面 左对面 右对面 ，1岩浆0空地 故我们将其贡献算为，如果当前为x,y为1->0，则贡献减少lst[3-x][y]+lst[3-x][y-1]+lst[3-x][y+1]，如果为0->1则减少，另y=1或n时特殊判断。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath>...

题目 思路：看数据大小1e5可以知道我们需用O(n)或O(nlogn)的算法。故开两个队列，q0,q1，一个表示存储以0结尾一个存储以1结尾，当队列空时另增加一个新的子序列，不为空时将转变一个序列从q0->q1（当遇到1且q0中还剩下xxxx0的字序列时，不剩则再增加一个子序列），细节见代码。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath>...

题目 思路：看N为2e5可知复杂度为O(n)或O(nlogn)，在这我用两个map分别记录每个男和女各自可以和多少匹配，首先选好一组匹配，那么还可以找出多少组匹配与之组成两组呢？答案为：k - 此组匹配中男生可以匹配女生数 - 此组匹配中女生可以匹配男生数+1（他们自身匹配那条线多匹配了一次）。 Code: #include<iostream> #include<string> #include<map> #include<algorithm> #include<memory.h> #include<cmath> #...

题目 思路：选出K个博主，要使得总共关注者最大， 先看一个简单例子如1 2 2 3 4 4 4 4 5 6 7 7 k=6最大为4+4+5+6+7+7=33.可以知道我们一定要选最大的后面6个博主 4 4 5 6 7 7 假设换了前面一个必然导致和不为最大值，而这六个博主其实5 6 7 7也已经定死了，能选择的只有4（第n-k+1个博主的值）我们只需从总共的4个拥有4个关注者的博主选两个答案为C 4 2=4*3/2=6。再推广到普遍情况设第K大博主关注者数量为t，答案为：所有关注者数量为t的博主中选出前k大博主中关注者数量为t的博主的数量个，即总共值为t的个数中选出最大k个中值为t的个数个。...

题目 思路：对于一个结点有四种情况00 11 10 01，其中00 11我们不需要重新交换。然后因为每个子树都可用其父亲及往上的结点的值交换。故我们从上到下更新每一个结点的交换值，其值为min(自己，父亲)。然后从1开始dfs，先深入到最底下结点,让下面的结点先进行交换（因为越往下的结点花费越少），还剩下的没交换的给其父节点，一层层往上，如果最终都还剩下没交换好的，则不可能全交换。 Code: #include<iostream> #include<vector> #define FAST ios::sync_with_stdio(false),cin.tie(0...

题目 思路：当我们选定了一个怪物作为开始先杀掉后，对于余下的怪物我们一定要按顺序一个个杀掉，因为对于一开始被杀的后一个怪物（如果没炸死的话）我们最终一定要杀掉的，如果他是在他后面一个怪物被杀之后被杀那么它的爆炸不会产生贡献，我们在贪心的决断下，一定要先杀他让它的爆炸伤害物尽其用。那么其实我们只需枚举一下各个怪物第一个杀，取最小即可。但暴力的话复杂度O(n^2)，但可以发现其实对于每一个结果只是改动了一个小地方。我们先求出一个假设每个怪物的爆炸伤害都做出了贡献的sum=min（i-1的爆炸伤害-i的生命值，0)i=1,2,3…n 。然后枚举每一个i，ans=min(ans,sum+i怪物的生命...

题目 思路：其实构造起来还是不难的，要使形成一条字典序最小的欧拉回路。 如下: n=5 12131415 232425 3435 45 1 从这不难发现规律，我们只需找到它的起始位置，然后开始模拟，假设是第i行，i i+1 i i+2 i i+3…n每次到了n时到下一行i+1开始，正好模拟r-l+1步即可，细节见代码。 Code: #include<iostream> #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long...

题目 思路：首先来看一下这个距离是怎么计算的 -4 -3 -2 -1 0 1 2 3 4 不难发现4到3和-3的距离和=2 * 4 到-2 2到-1 1的距离和也都为2 * 4，在此可以发现规律一个较大的数到两个较小的数的距离和等于其自身二倍。观察0 1 2 -1 -2…到4 -4的距离和为都为2*4，又发现了一个规律一个绝对值较小的数和两个绝对值比它大的正负数的距离和=二倍大数的绝对值。 那么给出了d的序列，不难得出最大的那个di必然是最大的那个数和其他数的距离和，其对应的ai值为(di/2)/n,现在我们得到了最大的那个ai，那么我们现在要推出第二大的ai，其值=((第二大di)/2-...

题目 思路：一开始觉得像个dp,但一看范围太大了。然后发现每种刀剑的质量固定的特点，那么很容易想到贪心肯定先把质量小的搞完，而数量范围最多2e5。所以暴力遍历主人拿质量小的货物（刀或间）从0–最大可拿的数量个，然后剩下的容量去拿另一种。到了仆人尽可能先拿质量小的货物，剩余容量去拿质量大的。注意边界即可。 Code: #include<iostream> #include<cmath> #define pii pair<int,int> using namespace std; int main() { int t;cin >> ...

D. Guess The Number Time limit 2 seconds Memory limit 512Mb Input standard input Output standard output This is an interactive problem. Somebody has secretly set the number x (1 ≤ x ≤ n). Your program has to guess this number interacting with the testing system. There are two kinds of queries: ? ...

题目 思路：首先给所有的区间排个序，使L（左边界）小的排在前面,然后开始枚举，每枚举完一个区间把该区间的R(右边界)加入到multiset中，如果遇到当前区间的L大于multiset中的R值则抛出该R,因为L是递增的该R也不会对之后的区间产生贡献，对于每个枚举的区间ans+=cal(multiset.size(),k-1)表示已经选定了该区间再从multiset之前出现过的区间中选出k-1个区间（不符合条件的R>该L的已经被erase了），这种方法是不重不漏的。 现在解释一下，为何这是不重不漏的。首先每一个区间的贡献产生于两个阶段，第一个是它刚遍历到时会加上一个和已经遍历过的区间选出...

#define lowbit(x) (x&(-x)) int c[Max], n;//n为元素个数 void add(int x, int v)//单点给元素+v {for (int i = x;i <= n;i += lowbit(i))c[i] += v;} int que(int x)//询问前x元素的总和 { int ans = 0; for (int i = x;i != 0;i -= lowbit(i))ans += c[i]; return ans; }

题目 思路：首先贪心一下，我们想要使得移动次数最小那肯定用前面离得近的元素去移动，所以我们用一个que来记录各个元素的位置，每使用完这个前面的位置的就pop掉。其次对于每一次移动我们需要知道它之前还剩多少个元素在这我们用树状数组来维护，每移去一个元素我们就让这个元素-1，初始时都为0.然后每次操作只需+que(i)-1的贡献即可。 如：3 4 5 3 7 6 3 假设我把7移到了最前面（干脆直接当作7不存在了） 3 4 5 3 (7) 6 3，那么对于原本7后面的6 3，他们下一步想要移到队首需要交换的次数比原来的次数少了一次，而对于原本7前面的数3 4 5 3它们想移动到队首所需的次数...