Water Balance 题意: n个数 可进行以下操作任意次：选择区间【l，r】其中的A【i】都变成这个区间的平均数，要求最小字典序 思路： 由于最后答案使单调不减的 那假设前i个元素答案以求出，看当前位置的元素能否对当前答案优化，即前面元素的个区间答案 加 上当前元素能否使区间均值变小，一直维护一个答案序列就可以了 教训 换个角度想问题会好很多 ← 每次遇到类似题目的时候总是会想的很麻烦 导致失去耐心 要时刻保持清醒的头脑 低头太久会导致思维混乱 #include<bits/stdc++.h> #define LL long long #define pdi pair...

B - Three Religions DP Question： 现有一个主串S 和 三个空串 A,B,C(只含小写字母)。问每次操作后 S 是否能包含 A B C (在保证 A B C 串内字母顺序不变的情况下组成S的一个子序列) 操作是在某个串后面添加或删除字母 一共q次操作 |A| ,|B| ,|C| <= 250 。|S| <= 100000 。 q<1000 我们要及时发现题目特点来确定解法 去主动猜测这题该怎么去做 要大胆假设，细心实现 Solution： 发现串a,b,c <= 250 那么可以建立一个dp数组 DP[i] [j] [k] 表示 A串匹...

E. Nanosoft Question: 定义一个logo 形状颜色如下类推 ，现在有一个关于logo的颜色矩阵 长n宽m 并有q次询问：r1,c1 r2,c2 直接最大的logo有多大 n,m<=500 q<=1000; Solution: 记录每种颜色数量的二维前缀和 ，那么对于一个区域 是否为logo只需分别判断其中颜色数量即可，并且以某个点为起点的logo最多只有一个 ，所以我们可以暴力直接枚举答案长度 和起点一直更新答案即可 时间复杂度为O（min(n，m)/2nm）此题是可以解决的 但当n，m<1000时我们怎么解决呢？ 通过观察发现每一个大的logo都包含...

Andrew and Taxi Question： 给一n个节点m条边的有向有权图 现可以改变其中一些边的方向 总代价是这些边的最大值，问使该图无环的最小花费 n,m<1e5 Solution： 由于代价为所有边的最大值，想到二分 然后对所有大于mid的边进行拓扑排序后，如果没有环那mid这个值就是可行的。 并且把不在图中的边（即权值小于mid）并且top【u】>top【v】的边翻转即可 #include<bits/stdc++.h> #define rep(i,a,b) for(LL i=(a);i<=(b);i++) #define per(i,a,b...

例题 POJ 3237（） BZOJ 3083 BZOJ 3531 BZOJ 3589 BZOJ 3626 将树上问题通过dfs序的性质转换为区间问题，从而对树上修改时就可转化为相应的区间修改。再通过引入重儿子，重链一系列概念将时间复杂度也变成了可以接受的层次 通过两次dfs求出树上一系列的信息 void dfs1(int u){ sz[u]=1; dep[u]=dep[fa[u]]+1; for(int i=head[u];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa[u...

总结 二分图的最大匹配：匈牙利算法 二分图的最小点覆盖数 = 二分图最大匹配数 二分图最大独立集 = 总点数 - 二分图最大匹配数 （有向无环图）不可重叠最少路径覆盖数=原图点数 - 二分图的最大匹配 二分图多重匹配就是 在匈牙利算法上加上一维 limit 的维度（可以引入源点和汇点 进而转化成最大流问题） 二分图最大权匹配 是 条件 好像是 在完备匹配的基础上？ KM算法 （也可通过网络流解决） 01染色；转换为 行和列 将一件事情拆成两种属性 并对对应属性间构造关系求最大匹配 将连接两种事务的条件看成边，即求最大匹配 前置知识： 增广路：由未匹配点开始未匹配点结束，中间交错出现匹配边...

l链接 Answer ：本题突破口在于 gcd ⁡ ( a , b ) = gcd ...

链接 Answer ： 可以把怪兽看成二维坐标上的一些点，每个点有一些权值。 然后对于所有的x=ai（攻击）的轴上都有m个bi（防御）那么对于每一个bi它所能打死的所有怪兽就是当前的轴的左面所有y小于bi的怪兽 所以问题就转化为一个区间求和+区间最大值的问题 用线段树维护就好了 坑点:把握好题目给的条件，以及输入顺序（怪兽是先给的防御力 …好坑） Code： #include<bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long LL; const in...

8/13 Permutation A Simple Stone Game Geometry Problem K-th Number Palindrome Color a Tree X-Men Server Interview 链接 Permutation 根据题意构造一个A[i]-A[i-2]=1的数列即可 easy A Simple Stone Game 很容易想到求出N堆石子的总数量后，枚举每种因子得到一个解（将每堆石子模mid后贪心的凑出k堆）然后取最小值。但是因子的数量可能会很多会超时，那么我们在仔...

6/13 Little Boxes Rabbits Heron and His Triangle Infinite Fraction Path Tree Wandering Robots 链接 就这几个题目来说感觉都偏技巧性，考验思维能力。 Little Boxes 输出a+b+c+d JAVA就行 Rabbits 分析题目得到 答案最多就是a[n]-a[1]-n+1 即最大值和最小值之间的空隙，那么由于每次移动一个点时，会有k个间隙被浪费掉（k为与它最近的点之间的间隙）。那我们每次移动的时候都贪心的选择k较小的，然后考虑把...

文章目录 Justifying the Conjecture Fixing Banners Keeping Rabbits Interesting Permutation Exchanging Gifts Binary Numbers Artful Paintings补 LRU Algorithm补 Justifying the Conjecture 显然，构造一个偶数和一个质数是最方便的，那么直接判断奇偶性选择输出2,n-2还是3,n-3就行，n<6特判 #include<bits/stdc++.h&g...

第一次AK写篇题解庆祝一下~~ 文章目录 A.Divisibility Problem B. K-th Beautiful String C. Ternary XOR D. Carousel E. Tree Queries F. Make k Equal A.Divisibility Problem 看代码吧 #include<bits/stdc++.h> #define pb push_back #define fi first #define se second using namespace std; ...

文章目录 B. Balanced Diet C. Line-line Intersection E. Minimum Spanning Tree D. Master of Data Structure F. Mini-game Before Contest 坑 G. Radar Scanner H. Skyscraper J. Time Limit 链接 B. Balanced Diet 贪心，假设最大天数为k，那么所有物品最大得k项都拿（再满足题意的情况下） #include <bits/stdc++.h&...

链接 操作1可以将所有的高度变成0 or 1（像俄罗斯方块一样）并且这其中的0和1可以全局互换 操作2和操作1可以移动这些1，并且将相邻的0 0 -> 1 1 那么问题就转换成，放置偶数个位置0，或偶数个位置1 所以当n*m%2==1时 0和1总会有一个是偶数 否则，也可以简单的构造出一个组合数公式，并化简为(a+b)^c的组合形式 思考问题的方向是个很重要的东西，一道题能不能快速的解出来很大一部分是取决于你努力的方向。 题目的难易程度也与解题方法是否好想有关 要想在赛场上快速解决一个问题，就要锻炼迅速判断这道题的方向的能力，这对我们很重要 #include<iost...