Codeforces Round #553 (Div. 2) ABCD题解 A. Maxim and Biology 思路：暴力即可 #include<bits/stdc++.h> using namespace std; const int inf=0x3f3f3f3f; const int MAXN=1e5+10; int MAX=1e5+1; char cc[]="ACTG"; int getans(char c,char tc) { return min((tc-c+26)%26,(c-tc+26)%26); } char s[1000]; int ma...

J - Vasya and a Tree （树状数组+离线处理） CodeForces - 1076E  题意： ​ 给定有n个点的一棵树，顶点1为根。m次操作，每次都把以v为根，深度dep以内的子树中所有的顶点（包括v本身）加x。求出最后每个点的值为多少 思路： ​ 离线处理+树状数组。其中树状数组维护当前深度区间信息。 （终于知道什么是离线查询）  ​ 我们可以     D   F   S    DFS   DFS序遍历以     1    1   1为根的树，每到一个节点，就根据当前节点的修改信息向下修改，离开该节点就修改回来，这样每到一个节点，影响他状态的只有他的祖宗节点。而当前节点的...

关于c++迭代器的一些讨论。 具体结论已经经过实验。 c++STL库封装了一些非常常用的数据结构，但是想要熟悉掌握这些就不能不熟悉迭代器。 主要说三个问题以及结论  正向迭代器与反向迭代器的相互转化以及转化的效率问题: 转化是O(1)还是O(log)的不太清楚。 .删除迭代器指向的元素后，it++ 还有效吗？ 删除迭代器指向的元素后，it会自动移动到下一个位置吗？ 正向迭代器和反向迭代器同样能够      −   −   ​    --​   −−​吗？  1 . 正向迭代器与反向迭代器的相互转化以及转化的效率问题 这里以     s   e   t   <   i   n   ...

I - 80-th Level Archeology（前缀和，区间交集） CodeForces - 731D  题意： ​ 给出n个串，一共有c种字母编号为1-c。然后描述每一个串。每一次可以使得所有串的所有字母编号+1（编号为c的变成1）.问最少多少次吼能够使得所有的串按照字典序递增 思路： ​ 我们只要保证相邻的两个串都递增即可。对于每两个串，我们求出假设我们旋转k次就可以使得着两个串递增。其中k的区间可以线性求出来。最后我们只要找出被区间覆盖n-1次的点即可。这个k就是答案。 ​ 至于怎么线性求k的区间，因为两个串不管旋转多少次他们的大小都取决于最前面的不同的数。那么我们只要找到第一个不...

H - Babaei and Birthday Cake CodeForces - 629D https://vjudge.net/contest/301590#problem/H 题意： ​ 有n个蛋糕，从1编号到n，现在用这些蛋糕制作一个大蛋糕，要求编号大的蛋糕必须放在编号小的蛋糕上面，且上面的蛋糕的体积必须严格大于下面蛋糕的体积，问能制作出的大蛋糕的最大体积 思路： ​ 每次找出面积比他小的堆起来的最大蛋糕面积即可。找的过程可以将所有面积离散化，然后用树状数组查找（线段树，map都可以实现）。 ​ 且面积之间的累加和比较可以用     h   ∗   r   ∗   r    h*r*r...

Codeforces Round #552 (Div. 3) E Two Teams 题意： ​ n个人排成一排，每个人都有一个iq，且iq不重复。现在给你一个k，且有两个教练编号为分别为1，2轮流进行以下操作 ​ 该教练从排成的一行中找出iq最大的人加入自己的团队，且让iq最大的人左边的k个人和右边的k个人都加入自己的团队（如果人数不够k个，则只把剩余的加入即可）。 ​ 现在问所有的人都被选出之后所处的团队编号。 思路： ​ 我们需要维护两个信息  一行人的编号的顺序，以及对应的iq. 此时所有人的iq最大的人的编号。  ​ 我们第一个可以采用set容器实现；第二个使用map容器实现（也可以...

KiKi’s K-Number  (树状数组) HDU - 2852  题意： 题意：题目给定三种操作: 0 x 表示把x插入容器 ; 1 x 表示删除一个x如果没有x则输出 No Elment! ; 2 a k 表示比a大的数中的第k大的数 如果没有输出No Find! 思路： ​ 树状数组维护元素出现次数前缀和即可。操作0即修改；操作1先查询x是否存在，如果存在删除一个即可。操作2可以用二分逐渐逼近答案。 #include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; ty...

F - Disharmony Trees HDU - 3015  题意： ​ 对于n棵树，给出所在位置和高度，根据给出的规则算出每棵树的位置等级     x   l   e   v    xlev   xlev和高度等级     h   l   e   v    hlev   hlev 然后，定义f=两树之间的位置的那估计的绝对值，s=两树中最小的高度等级，求所有树之间f*s和。 思路： ​ 预处理把所有的树重新构造距离和高度熟属性，我们让所有树按照树的高度从高到低排序，那么每次求当前这个树与前面每个树的 Disharmony Value 即可，因为高度是从高到低，所以与前面每颗数计算的min...

E - Apple Tree POJ - 3321  题意： ​ 一颗苹果树，刚开始所有节点都有苹果，有以下两种操作，一种是改变一个节点的状态（有苹果就取走，没苹果就产生一个），一种是询问一个点的子树（包括节点自己）一共有多少个苹果，对于每次询问输出结果 分析： 重新DFS序给节点标号，那么没个节点的子孙就对应一个连续的区间。那么修改点的状态相当于单点修改，查询操作相当于区间求和，树状数组和线段树都可以写。  注：POJ存树图用vector超时 #include<cstdio> #include<iostream> #include<vector> #inc...

C - Mobile phones（二维树状数组） POJ - 1195  题意：对一个     n   ∗   n    n*n   n∗n的矩阵进行一些操作和查询，操作：单点修改。查询：求子矩阵元素和 思路： ​ 真没想到二维的树状数组是这样的。（真不知道二维线段树应该怎么维护，期待(☆▽☆)！ ） 构建二维树状数组之后我们可以求     i   ,   j    i,j   i,j左上角矩阵的和 。求子矩阵可以转化为多个左上角矩阵元素和的加减。  二维树状数组的第二维(也就是行向量代表的节点吧)之间的关系，跟一维向量的 节点之间关系相同。 看博文：https://blog.csdn.ne...

树状数组基础总结 入门博文：http://www.cnblogs.com/acgoto/p/8583952.html 树状数组与线段树的思想的一些相同与不同。 共同点：同时一个节点维护多个叶子节点的信息 不同点：线段树节点采用二分的规则，而树状数组节点利用了bit位的性质来锁定管理的叶子节点，且树状数组只能直接查询1~i区间的信息，而线段树可以直接查询     [   l   ,   r   ]    [l,r]   [l,r] 区间信息， 树状数组可以解决问题的思路推广到线段树都可以用线段树解决。不过树状数组代码量是真的小！ 树状数组核心函数： 这样的代码要求其叶子节点必须从1开始（因为此处...

H - Matrix Multiplication ZOJ - 2316 首先我先说明一下，如果我英语不是太渣的话那么题中说的矩阵是     n   ∗   m    n*m   n∗m的矩阵。（我知道是     n   ∗   n    n*n   n∗n的邻接矩阵）。但是我看题解矩阵     A    A   A都是     n   ∗   n    n*n   n∗n的邻接矩阵 题意： ​      n   ​    n​   n​个顶点，     m   ​    m​   m​个双向边，下面输入     m   ​    m​   m​个边，从而生成一个矩阵     A   ​   ...

D - 度度熊与邪恶大魔王 ​ HDU - 6082  思路： ​ 数据很水，     1000   ∗   1000   ∗   10    1000*1000*10   1000∗1000∗10的复杂度，多组输入都能过。 ​      d   p   [   f   ]   [   h   ]    dp[f][h]   dp[f][h] 表示防御力为      f    f   f 血量为     h    h   h被消灭所需的最小晶石数量。那么假设第     i    i   i个技能造成的伤害为     K   [   i   ]    K[i]   K[i],晶石数量为     ...

B - Minimum HihoCoder - 1586  题意： 一段序列支持两种操作：  1.Output      M   i    n    x   ,   y   ∈   [   l   ,   r   ]     (   a   x   ,   a   y   )    Min _{x,y∈[l,r]} (ax,ay)   Minx,y∈[l,r]​(ax,ay). 2.Let       a   x    =   y    a_x=y   ax​=y.  思路： ​ 维护区间最大值，最小值即可。假设区间     [   l   ,   r   ]    [l,r]   [l,r]...