なんとかのところ

E. Colorings and Dominoes 题意： 给定一个n∗mn*mn∗m个格子的黑白图，白色可染成红色或蓝色，共有2w2^w2w种染色方案(w为图中白色块数)。多米诺规格为1∗21 *21∗2，水平放置的多米诺只有放置的两个格子都是红色时才能染色，垂直放置的多米诺只有两个格子都是蓝色时才能染色，问每种染色方案最大放置多米诺数的和。 解析： 这道题可以考虑概率做法。首先对于水平或垂直放置两种，可以将连续的白色块看做一个竖条或横条，多米诺只能放置在这个横条或竖条上。其次对于全部方案我们设EEE为染色方案的期望，则答案为2w∗E2^w*E2w∗E。EEE的值为∑pd\sum p_d∑pd​，其中pdp_dpd​为可以在ddd和d+1d+1d+1间放置一块多米诺的概率。可以找几个简单的例子找规律。 当前放置格子前无白色块时，当且仅且当当前格子和下一个格子全部染成相同颜色时可放置，概率为14\frac{1}{4}41​。 当前放置格子前有一个白色块时，只有前一个白色块的颜色和后两个格子颜色不同时可以放置，概率为18\frac{1}{8}81​ 当前放置格子前有两个白色块时，用二进制 ...

P4926 [1007]倍杀测量者 题意： 找到一个最大的T，使得类型1的flag只需要达成SA≥(k−T)∗SBS_A\ge(k-T)*S_BSA​≥(k−T)∗SB​，类型2的flag只需达成SB≥(k+T)∗SAS_B\ge(k+T)*S_ASB​≥(k+T)∗SA​即可不用女装的情况下，仍然有人需要女装。 分析： 使用二分 + 差分约束 首先从题意可知，如果有一个T使得不等式有解，则此时无人女装。同样，如果有一个T使得不等式无解，则此时至少有一个人需要女装。故我们只需要用二分进行枚举并用spfa判负环判断不等式有解还是无解即可。 其次对差分约束系统进行分析： 由于精度问题，我们需要把原式转化为log(SA)≥log(k−T)+log(SB)log(S_A)\ge log(k-T)+log(S_B)log(SA​)≥log(k−T)+log(SB​)进行建边即可（另一种类型同理） 所以对于类型1，我们需要从A->B建一条长度为−log(k−T)-log(k-T)−log(k−T)的边。对于类型2，需要从A->B建一条长度为log(k+T)log(k+T)log(k+T ...

负环 负环是指图中出现了一个边权和为负的环。出现负环意味着该图不存在最短路，即S -> T的路径上一定可以通过一直经过负环无限缩小路径长度。 负环的判断可以使用SPFA算法。SPFA算法的特点是当一个点的最短路径发生更新时才会将点放入队列，故如果图中存在负环，则使用SPFA算法会一直进行更新，此时只需判断一个阈值，当超过阈值即可判断存在负环。 设置阈值有两种方法。第一种比较稳定但较慢，第二种不稳定但从经验角度来看一般可行。此外还存在一种优化。 第一种阈值为判断每个点最短路所包含的边数。如果某一点最短路包含边数大于等于n，则说明存在负环。 第二种阈值为判断入队次数是否大于某一值，如大于四倍点数时，可以判断存在负环。 优化则是可以将队列替换为栈，则如存在负环时，每次都会取最新更新的点判断，可以拥有更快的效率。 AcWing 904. 虫洞 题意： 给定一个无向图，以及一些有向负权边，问是否存在负环。 解析： spfa找负环模板题，直接求解即可 代码： 1234567891011121314151617181920212223242526272829303132333435363738 ...

C - Boss 题意：给出一个有向无环图，每条边x->y表示x是y的直属上司。两种操作，一种T x y表示将x和y的岗位互换，一种P x表示查询x的所有上司（直接或非直接领导）中的最小年龄 题解：用两个数组id1 id2。id1[i]表示在原关系图中i位置上的人现在的编号，id2[i]表示编号为i的人现在的位置。通过这两个数组可以在交换位置的时候O(1)更换位置并更新数组，具体细节看代码吧。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include <bits/stdc++.h>using namespace std;#define fast \ ios_base::sync_with_stdio(false); \ cin.tie(NULL);const int N = 1e3 + 1 ...

A - Arcade Game 题意：给一个小于9位且每一位各不相同的数字，一次可以让这个数字的所有位重新排列，如果获得的排列是所有排列的最大情况则获胜，否则如果大于当前数字则可继续游戏，直到获胜或失败。 题解：直接用组合数做肯定会超时，可以通过推式子的方式推出所有情况 首先求出当前位数一共有多少种排列情况n，并求出在所有排列情况中大于给出数字的数量sum。则一次到达最大值的概率为n!(n−0)!∗0!∗1n\frac{n!}{(n-0)!*0!}*\frac{1}{n}(n−0)!∗0!n!​∗n1​，第二次到达最大值的概率为n!(n−1)!∗1!∗1n∗n\frac{n!}{(n-1)!*1!}*\frac{1}{n*n}(n−1)!∗1!n!​∗n∗n1​可以看到两项之间仅差n−11∗n\frac{n-1}{1*n}1∗nn−1​，故可以通过递推式找到每一种情况，相加求和即为索求答案 代码： 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152 ...

题意 给定一棵树，树上每条边及每个点都有权值。定义Pu=∑vd(u,v)(tu+tv)P_u=\sum_{v}d(u,v)(t_u+t_v)Pu​=∑v​d(u,v)(tu​+tv​)其中d(u,v)d(u,v)d(u,v)为树上u到v的距离，tut_utu​和tvt_vtv​分别是两点权值，求每个点的P值。 分析 首先我们可以看到PuP_uPu​可以分成 tu∑vd(u,v)+∑vtvd(u,v)t_u\sum_{v}d(u,v)+\sum_vt_vd(u,v)tu​∑v​d(u,v)+∑v​tv​d(u,v) ，则我们只需要知道对于每一个节点∑vd(u,v)\sum_{v}d(u,v)∑v​d(u,v)和∑vtvd(u,v)\sum_vt_vd(u,v)∑v​tv​d(u,v)的值即可。直接计算复杂度太高，我们可以考虑通过一个已经计算出值的节点计算当前节点值。 当我们已经计算得到uuu的值，并想要得到与uuu相邻u′u'u′的值时，可以将除了u′u'u′的其他节点分为两部分，一部分不经过uuu，另一部分经过uuu。 计算∑vd(u,v)\sum_{v}d(u ...

A - Carryless Square Root 题目大意 给定一个数n，让你找出最小的a使得 a*a 在无进位乘法下等于n 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657//dfs 但是有一些细节问题需要注意#include <bits/stdc++.h>using namespace std;const int N = 2e2 + 10;const int INF = 0x3f3f3f3f;const long long LINF = 0x3f3f3f3f3f3f3f3f;const unsigned long long P = 1e9 + 7;const double eps = 1e-6;string s;int a[N],b[N],c[N];int Max = 0;//判断到当前位数下是否符合条件bool check(int pos){ memset(c,0,sizeof c); ...

I - Mason’s Mark 题目大意 给出一张仅有黑白两种颜色的照片，让你分析照片中有几个ABC 解析 题目很长…要求很多…但是读明白题后没有一点思路的难度。其他要求不再赘述，这里只说最关键的一点，就是黑色像素仅有三种可能，即噪点，相框，和标记。也就是说，只要排除了相框和标记的黑色像素，剩余的黑色像素一定是一个字母上的。剩下的工作就仅剩下判断这个黑色像素所属字母是什么字母了。我用了一种非常简单粗暴的方法…具体看代码吧 代码 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const long long LINF = 0x3f3f3f3f3f3 ...

manacher算法是一种可以在O(N)时间复杂度下求字符串所有回文子串的算法，也是求最大回文子串最高效的算法。这种算法在进行遍历的时候，充分利用了回文串的特性，减少了许多不必要的计算，使得时间复杂度降低到了线性水平。该算法的难度在于理解，一旦理解后，代码是非常简单的。 manacher算法有如下几个要点： 如何计算回文串长度（O(N2N^2N2)算法） 如何将奇回文串与偶回文串统一判断 如何优化O(N2N^2N2)时间复杂度的中心拓展算法 下面我们来一一讲解 一、如何计算回文串长度 如果没有时间上的限制，我们可以使用暴力的做法：中心拓展法 我们知道，如果一个字符串是回文串，那么该字符串必是中心对称的。故我们可以选择一个中心，从它开始，向两边逐一判断字符是否相同，拓展回文串长度。由于回文串可以是奇回文串也可以是偶回文串，我们需要选择一个字符或者选择两个字符中间作为中心进行逐一判断，故一共有 N + N - 1个中心。 二、奇回文串与偶回文串的统一判断 回文串既可以有aba的形式，也可以有abba的形式，在实际写代码的时候如果不进行处理，会使得代码变得比较复杂。 因此我们可以在每两个 ...

参考博客 前言 如果完全掌握了主席树的前置知识，主席树其实也是一种并不算很难的数据结构（虽然蒟蒻还是花了好久）。主席树主要的前置知识就是权值线段树，一旦理解了权值线段树的相关知识，那么主席树的学习应该也会变得较为简单。 权值线段树 权值线段树是线段树的一种，但是它与普通线段树不同的地方在于，普通线段树节点的区间代表的是序列中的区间，而权值线段树节点的区间则代表了序列中值的区间。 如这样一个序列：1 4 2 3 3 普通线段树中我们通常以序列下标为范围来进行线段树的区间划分，而在权值线段树中这个数组是这样保存的： 其中每个节点的值是这个序列在这个值域范围内一共有多少个数。 权值线段树的可加减性 让我们想象这样两颗权值线段树：一颗以序列[1,x]为序列建树，另一颗以[1,n]为基础序列建树，同时都用相同的范围建树，这样的两棵树每个节点所代表的值域是完全相同的。这也就是说，如果我们用第二棵树的某个节点的权值去减去第一棵树对应节点的权值，所得到的值便应该是[x+1,n]序列中该节点值域范围内数的数量，这也就是权值线段树的可加减性。 静态主席树 通过权值线段树及其性质，我们不难想到如何查找区间 ...