E. Are You Fired?(贪心&分类） 传送门 思路：首先要知道，因为假设满足条件，那么也显然满足。 接下来对正负进行讨论， ，只需对进行判断。如果则输出，反之不成立。 ,  因为要满足 因为，所以区间右端肯定包含。 因此 将含的项移到一边： 因为 所以最终等式为 只需让即可。 因为最大为，所以可以递推得到左边所有的最值。 时间复杂度： AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e5+5; #define mst(a) memset(a...

P2863 [USACO06JAN]The Cow Prom S(Tarjan) 传送门 思路：模板题。 ==注意==：不能根据的来判断连通块的大小。 举个例子个结点，一条边即 显然遍历到2时，此时栈中有两个数，但是.会进入到涂色。但是只会涂一个点，因为它是孤立点。事实上可以有另外一种判断方法，因为某一个结点要么属于连通块，要么是一个孤立点，所以在判断时可以标记一下此时的是否大于1，然后看是否变为0了，如果变为0了说明属于一个大于1的连通块，否则是一个孤立结点，这种方法就不需要用到数组。 AC代码: #include<bits/stdc++.h> using namespace s...

I - Swordfish(最小生成树） 题意：给定个点的坐标，求最小生成树。 思路：因为最大只有100，用或者都可以。 这里重新温习一下两个算法： 对所有边排序，每次取最小边，取条边，同时用并查集维护当前图点的集合，如果不在集合里则加入该边。 时间复杂度:为边数。  用一个数组维护当前子图与所有结点的最短距离。任取一结点开始，每次取与其相连的最短边的结点并加入，然后用该结点进行松弛当前子图到所有结点的最短距离.每次找到一条边，一共需要次。 朴素复杂度： 与类似用优先队列实现的时间复杂度: 代码： #include<cstdio> #include<iostream> ...

数列分块1(学习） 题目传送门 适用范围：区间修改，单点查询。 思想：分块操作，将个数作为一组(一块)。 每次操作会涉及最多个块和包括左右区间不完整最多个 元素。 即每次操作的复杂度大约在： 根据均值不等式最合适。 总复杂度：  树状数组做法待补 AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) int a[N],bk,n,tag[N],bl[N]; void add(int l...

E - ∙ (Bullet)(组合数学） 传送门 思路：显然对于一组只有两种情况，同号或者异号, 存在0。  且要使。显然是同号与异号进行组合。  且我们只需考虑除去最大公因数的组合. 因为。 所以我们考虑储存同号的个数及对应异号的个数。(这里用实现即可） 对于当前组，假设同号个数为,异号个数为，由于不能同时选同号和异号的， 显然我们可以只选同号或者只选异号的，这样有种情况。 和同时包含了当前组一个数不选的情况，所以要减去1. 即对于当前组的贡献为. 所以根据乘法原理有:   1.显然当中只有一个时，等价于与进行组合，可以归为. 2.当时，因为它们不能与其他数共存，只能单独存在。所以对于这样的...

k-size字符串(组合数学） 传送门 思路：因为要分成段，显然字符与字符的段数绝对值值差 设分成段，即： . 显然当为偶数时，只有这种情况。 即或 在个位置放置相应的一个字符或。 接下来就等价于将个数放入个格子的方式. 也等价于 整数分成个非负整数的方式。 令为整数x分成个非负整数的方式。 有(这里是保证第一个格子有数,不是第一个格子只放一个1) 即对应第一个数为0和第一个数不为0之和或者说是第一个格子不放东西和第一个格子放东西的方式之和。 根据观察这是一个组合数的递推： 根据,  所以可得 最后奇，偶数讨论一下即可得出答案。 需要注意的可能存在组合数的分母或分子的情况要舍去。 AC代码: ...

C. Count Triangles(组合数学) 传送门 思路：考虑所有的组成的可行解。 显然组成三角形, 因为，所以. 又因为.所以具有可行解的最小值为. 最大值即. 所以 接下来考虑每种对答案的贡献,首先考虑对于当前,的取值。 显然只能取.又因为.所以 可选的个数为. 接下来考虑可选的个数. 根据乘法原理可得当前的贡献为： 综上可以通过遍历得到答案。 时间复杂度: AC代码： #include<iostream> #include<algorithm> typedef long long ll; using namespace std; signed main(){...

G - Crossing River(贪心） 题意：每次两个人坐船过河，每次过河的时间取速度较慢的那个人，问所有人过河所需最短时间。 思路：经典贪心题目，我们将时间进行从小到大排序，根据贪心思想，我们肯定需要人过了河带船回来，显然肯定要速度快的带船回来所用时间更少，所以每次我们需要运速度较慢的人过去然后他们就不用管了。接下来对特殊情况进行讨论。 当时显然 当 当时,显然船要回一次,所以肯定时速度最快的人回， 即 当时，我们可以通过每次运两个(最慢和次慢）将情况变为前面三种情况，此时要分两种情况 类比的方法， ：通过让最慢和次慢的一起过河，从而减少一次次慢的时间，但要增加一倍次快的时间，方法是先...

P2532 [AHOI2012]树屋阶梯（数&高精度） 题目传送门 思路：卡特兰数的变形，可根据包含直角点的矩形覆盖的阶梯点的位置进行加法原理，然后对每个情况进行乘法原理，可以得到卡特兰数的递推式的形式。 根据左上角阶梯的方案数右下角阶梯形的方案数该情况方案数由上图可知：图1为，图2为,图3为后面的图依次类推。 得到： 为递推式。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=1e4+5; struct num{ int a[N],l; }ans; int n; void multi(num &...

G - Eva's Balance (3进制&数论） 题意：给个的幂次方数：和一个数，要求用这个数中若干个使左右两个秤盘数之和相等.（开始被放在左盘） 思路：因为都是的幂次方,题目等价于构造两个的幂次方之和相减等于,所以考虑进制下来表示. 所以被转化为的数字串。当该位为时,显然可以不会用到或者直接抵消掉。 当时,因为。所以等价于然后。 当时,显然，所以等价于.然后再根据的正负情况，将负的给左盘，正的给右盘，此题就解决了。 时间复杂度： AC代码: #include<cstdio> #include<algorithm> #include<iostream&...

牛牛的揠苗助长（二分&贪心） 题目传送门 假设水稻先不长，显然是数组中某一个数相等是最优的。依次类推 因此若不进行任何操作，数组变成数组 有： 然后将数组排序，显然当为奇数时，肯定是选取 当为偶数时也是选取，而不是选取 这里做个证明： 因为花费的公式为：  对于前者：将代入: ​ 对于后者：将代入： ​  显然前者花费小。所以无论为奇数还是偶数,都是最优解。 因为当时能使所有数相等,那么都可以通过使那个要增加的数减1来保持相等。所以接下来用对答案不断二分就可以了。时间复杂度： AC代码： #include<cstdio> #include<algorithm> ...

D. Monopole Magnets（DFS&构造） 题目传送门 思路： 当一行全为白时,显然这一行极到不了,因为每一行都必须有一个极。假设这个极对应的列存在黑色,显然极要向该极靠近,但极又到不了白色,所以显然这样是无解的,所以存在全白行必须对应全白列. 当一行存在黑色时，黑色必须是连续的一部分,否则该行的极会吸引极越过白色部分到黑色的一端去.对列同理. 其他情况都可以通过在黑色连通块放一个极然后每格都放一个极构造出来。最后答案就是的次数了。 时间复杂度： AC代码: #include<bits/stdc++.h> using namespace std; const i...

A - Fire Net（DFS） 题意：给地图，问最多能放多少炮台，炮台不能互相攻击（有墙或者不在同一行或同一列） 思路：从左到右，从上到下将每个点做为起点开始搜，如果从某一个点开始搜，它之前的点是不用搜的，因为若 它之前有点可以作为炮台，说明这个点已经被搜过了。所以这种搜法是正确的。这里有个简化的技巧，用一维编号表示二维坐标 以作为起点，记它的编号为,依次类推的编号为 当前编号的坐标为.用两个数组分别标记行列，来维护整个地图即可。 AC代码: #include<cstdio> #include<cstring> using namespace std; const ...

E - Fox and Card Game 题意：给堆牌，两人一个人只能从某一个牌堆的牌顶取，一个只能从牌底取，问各自在最优策略下各自取到牌的总和最大。 思路：对每堆牌的奇偶性进行讨论，如果是偶数，那么显然在双方都选最优策略的情况，这堆牌肯定是所有堆中最好的。那么对手为了不让对方不取完这堆最优的牌，对手肯定也会取这堆牌，那么一直取下去，肯定先手取完上半堆，后手取完下半堆牌，再对奇数讨论，与偶数牌堆类似，除了取最中间的那个牌外，两人还是会取一样的牌数，当取到中间牌时，先手会考虑所有奇数牌堆的中间牌谁最大，如果此时的中间牌堆不是最大的，那么先手会选择让对方取这个牌，转而取另一个奇数牌堆的中间牌，后...