思路 设圆心为,点坐标为.因为点到圆心的距离的平方为.这样有个式子.这些式子两两相减可以得到个元一次方程组,这样直接跑高斯消元解出圆心坐标即可.复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define Re register #define MAXN 15 #define LD long double int N; LD a[MAXN][MAXN], b[MAXN][MAXN]; int main(){ scanf( "%d", &N ); for ( int i = 1; i <= N + 1; ++...

思路 很明显的区间DP.环形处理可以使用枚举断哪条边(复杂度为,比较危险)或者复制一遍接在后面(复杂度为).这里采用后者.转移时乘法需要注意负数,因为负负得正可能反而比两个最大值相乘更大,因此需要同时记录区间能得到的最大值和最小值.加法转移:乘法转移:然后在取最大值即可. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ...

思路 比较难的贪心题.首先,对于权值最大的节点(不算根节点),染了它的父亲之后的第一步肯定是先染它.因此可以将这两个点缩起来(反正染的步骤是连续的).下一步该怎么办呢?仍然是找权值最大的点,不过要稍加变换.假设缩起来的点的权值为,与第三者的权值比较,先染的话代价为,先染$的话代价为,作差后为,那么只要比较与即可.这样推下去可以发现将缩起来的点的权值看做即可.然后就可以得出整棵树染色的顺序,求出答案即可.暴力一点复杂度为,可以过.下面代码就是的.如果用或堆之类的东西优化一下复杂度应该可以到. 代码 #include<bits/stdc++.h> using namespace std...

思路 这题可以使用倍增解决.预处理出表示从的第个字符开始匹配,匹配个需要的个数与个最后一位匹配到的哪个位置.然后就可以求出最大的使能由生成.然后即为答案.复杂度为,表示字符集大小.具体实现细节参考代码. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i ) ...

思路 我们可以分情况讨论.  第N个小时正在休息这种情况就是一个DP题.设表示当前处理到第个小时,已经休息了个小时,最后一维为表示第个小时正在休息,否则不在休息.转移也不难: ,这个时刻不休息的话前面休不休息无所谓. ,这个时刻休息的话要考虑前一个小时休不休息.如果前一个小时休息的话这个小时休息是有体力恢复的,否则没有.初值的话,答案为. 第N个小时不在休息其实只要改变一下初值与答案就OK了.初值的话,答案为.表示第一个小时休息有体力恢复的话,最后一个小时必须处于休息状态.转移过程是一模一样的.  时空复杂度为,空间有点大了,需要滚动数组. 代码 #include<bits/stdc++...

思路 显而易见,答案具有单调性,时间越长,越容易控制疫情.所以很容易想到二分时间.首先,占据一个点肯定不如占据这个点的父亲,因此时间内到达不了号节点的尽力往上跳就可以了(暴力跳可不行,需要使用倍增).还有一些军队可能会经过号节点到达其他号节点的儿子节点.先来证明一个结论:若些军队的集合不经过号节点能到达号节点的儿子节点,并且其不能到达号节点又回到,还有其他不经过号节点的军队还未占据,中的某一支军队(当然是还能走的路程最小的那支)来占据号节点不会更劣.这个其实不难证明,若来自的另一个儿子节点的军队来占据,而的军队都穿过去占据其他节点,说明在节点时还能走的路程大于等于,而中的军队还能走的路程都小于...

思路 因为对于一个环,给其中任何一点支援都是等效的,因此先对原图进行缩点.对于缩点后的图,入度为0的点不能被其他学校支援,其他入读不为0的都能被其他学校支援,因此第一问答案就是入度为0的点.而要满足第二问的条件,必须使都在一个强连通分量才行.这样答案就是max(入度为0的点个数,出度为0的点个数).特别地,所有点都在一个强连通分量时答案为0. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <=...

思路 设计状态表示最后一个数为,长度为的严格递增子序列个数.我们可以轻松地推出转移方程: 注意到这两个限制是二维的,第一维直接按顺序枚举不断加入状态即可解决,第二维套一个树状数组即可解决.因为可能很大需要离散化.复杂度为看起来有点大,但是因为树状数组常数小,还是可以过的.实现中为了减小内存使用了滚动数组.注意一下边界与初始化. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ...

思路 都这么小可以考虑考虑状态压缩.表示填了前行,只有第行还有一些位置没有填过(满足). 可以从上一种状态转移过来需要满足以下条件:   每段连续的都是偶数个.  因为数据范围比较小,并且你也不知道询问有多少,可以预处理出所有可能输入的答案(当然也可以打表,虽然好像不太厚道),然后每次询问直接输出答案即可.注意要开. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #de...

思路 ,这么小的数据范围当然要想到状态压缩.我们把放置炮兵的位置变成,不放炮兵为.这题比较猥琐的一点就是会影响到能否放炮兵的有前两行.这样至少需要三维,记录当前到哪行以及前两行的状态.这样不能承受.由于这特殊的"十字",每行两个炮兵之间至少要两个格子.打个表可以发现满足条件的状态大概只有六十几个,这样就大大减少了状态,复杂度变得可以接受,直接暴力跑动态规划即可,注意判断不合法的情况.复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for...

思路 假设源点已经确定为1,那么直接跑树形DP即可.表示到叶子节点的最大流量(不考虑父亲节点的限制,也就是说看成父亲流到的流量为无穷),但是现在源点不一定为1,考虑怎么快速地"换根".设为为根时真正的答案.首先,它流到以为根时就是其儿子节点的流量是(注意是叶子节点时要赋为0).流到以为根时为父亲,而以为根时是其儿子节点的最大流量为.如果不减去就会导致多出计算流到的流量.然后就可以转移了.总复杂度为. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) ...

思路 将数组复制一倍衔接在最后,那么答案就是用单调队列维护一下的最大值即可.注意及时排除已经不满足的状态.复杂度为,常数也比较优秀. 代码 using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i ) #define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]...

思路 设为字符串中从到部分为一整棵树时的方案数.我们可以枚举第一棵子树,也就是为一棵子树,其它子树在为剩余的子树(与为根节点,同时也是的根节点,也就是说这两个点是同一个点).然后乘法原理与加法原理计算出答案即可.可以发现,一般情况下,很多状态是无用的.所以用记忆化搜索效率更高. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i ) #define fd( i, b, e ) f...

思路 先将所有左边界-1,也就是将所有"块"变成"点",从"第l块到第r块"到"坐标之间的块",方便离散化.先对所有区间按右边界排序,枚举每个区间,更新答案大家可能发现我的转移方程与算法竞赛进阶指南上不太一样,因为我的表示方式不同,书上表示覆盖第1块到第i块都被覆盖过的最优答案,而我是坐标从到之间所有的块都被覆盖过的最有答案.前面也说过,这样主要是方便离散化.对于前面那个转移方程,复杂度是的,肯定过不去.用线段树优化一下复杂度就是. 代码 #include<bits/stdc++.h> using namespace std; #define i64 long long #defi...