难度分布    Easy: C,K,L,M,N   Easy-Medium：J,F,I,G   Medium：D,E,H   Medium-Hard：A,B    A. Convolution    2^(ab)=sqrt(2)^((a+b)^2-a^2-b^2)   对每个 a+b，求出 sqrt(2)^(-a^2-b^2) 的和   NTT   时间复杂度：O(nlogn)    B. 双圈覆盖    先将每个点度数变成3：拆点   之后⼀定有偶数个点，且去掉环后点两两配对了   第⼀类圈：最外层的环   第⼆类圈：配对边 和 {(2i,2i+1)} 构成的⼀系列欧拉回路   第三类圈：配...

Note: Some problems have been weakened. A、 Alternative Accounts There are at most contest. We consider the hardest case that . For each account, wecompute the set of contests it participated in.Let be the number of accounts whose participated contest is set .It is easy to see for an account that par...

A、黑色气球  签到题 ？  B、小吨的点分治  假设我们已经对一棵树进行了点分治得到对应的点分树。如果我 们删去原树中的一条边，把得到的两个连通块中的点分别称为黑点和白点。对于点分树中的每个白点（黑点），我们找到它的祖先中最近的一个白点（黑点）作为它新的父亲，这样就能得到两棵全由白点组成的树和全由黑点组成的树（因为有且仅有一个白点和黑点找不到同色的祖先），它们分别为原树切分得到的两棵树的点分树。 反过来再考虑，如果我们把两棵树通过一条边 连接起来，我们怎样把原有的两棵点分树合并起来，并且保持原本点分树中的祖先后代关系呢？可以发现，我们只要把 到所在点分树根节点的路径以及 到所在点分树根节点的...

难度预期 预期A,C < E < D,K,I,H < J < F,B < G 实际：A,C < E < H,K < F < B,J < D,I < G A 托米的字符串 题意：统计所有子串元音字母占比的平均值 题解：令表示前个字母中元音字母个数令长度为的子串中元音字母出现的个数之和为， 最后答案是. C 纳新一百的石子游戏 题意：对于每个前缀的所有石子堆，询问先手必胜方案数。 题解：设当前异或和为，则要找到的就是有多少堆石头满足，这样就能将变为来使得异或和为。考虑异或和的最高的为的二进制位，所有这一位是的显然都满足条件，这一位是...

A、期望逆序对 medium假设最终序列是 ，它作为最优解的一个必要条件是交换两个相邻的位置 不能让答案变得更优。交换两个相邻的数的时候，只有它们之间的相对顺序发生了改变，所有这个条件也可以被写成所有 是逆序对的概率不超过 。对于两个随机变量，考虑（x，y）是逆序对的概率不超过。的条件：1.，这时 的区间整体在 的左侧，因此形成逆序对的概率不超过号。2.，即 的区间包含 的区间时，如果 的区间在 的区间的正中央时，根据对称性，形成逆序对的概率是恰好。因此当 在 中间偏右的时候，逆序对的概率就小于了；中间偏左的时候，逆序对的概率大于。综上，条件可以被总结为。因此最开始把所有区间按照中点从小到大排...

你是不是也有这个常态？   当信心十足想刷个题的时候。。。     怎么这么多题？？算了，还是下次再做吧。      作为竞赛选手，我们需要做题，更需要科学做题——有规划！有路线！     牛油A：“有没有最短路的练习题集呀？”   牛油B：“想做蓝书的题，一道一道地找好麻烦。”   牛油C：“想把之前做过的题目整理在一起。”   牛油D：“我刚入门，该做哪些题目？”   牛油E：“我汇总了这几场比赛中数论的题目：链接 链接 链接 链接 链接...”           现在，牛客题单功能上线啦！~   Step1：搜索题目    位置：牛客竞赛>题库>搜索，你可以输入 题目关键词...

https://vjudge.net/problem/UVA-514 解题思路：.A的铁轨从1到n依次判断 如果和当前轮到的铁轨相同 则从A驶入B，如果不相同，则入栈等候。每次判断之前先判断栈顶的元素是否和当前轮到的铁轨相同 直到不相同为止。 #include<iostream> #include<stack> using namespace std; int main() { int N; while(cin >> N&&N) { int target[1010]; while(cin >> target[1]&&amp...

https://vjudge.net/problem/HDU-6152  我也是绝望啊 怎么写怎么超时 居然是人数大于6就直接是bad team了。 证明：先从6个人中选出一个人，他与另外5人要么认识，要么不认识。 所以至少有3个人对于他是一样的（至少有三个人他都认识或都不认识）。 假设这3个人他都认识。 再看这三个人，若是他们三个中有两个人认识，则这两个人已经与第一个人组成3个人，互相都认识；若是他们三个中两两都不认识，则他们三个人两两都不认识。  用图形来表达也许会更好：  假设6个人是6个点，其中两个人认识就用红色线段连线；若不认识就用黄色线段连线。只需证“其中必有一个同色三角形”那么从...

https://vjudge.net/problem/UVA-122  学习的第一个关于树的题目，按着紫书上的思路来的。再整理一下 #include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; struct Node{//结点的结构体 bool have_value; int v; Node *left,*right; Node():have_value(false),left(NULL),right(NULL){} }; ve...

https://vjudge.net/problem/HDU-1003  刚开始接触DP算法，细节上错了好多次。整理一下  dp数组存储以a[i]为结尾的和最大的子序列的值。  如果dp[i-1]是负的则dp[i]肯定等于a[i]，并更新起始位置。  最后判断一下dp[i]是不是目前最大的。 #include<iostream> #include<cstring> using namespace std; int a[100005]; int dp[100005]; int main() { int T; cin >> T; for(int j = 1 ; ...

https://vjudge.net/problem/HDU-1205   恩….不算太难…但是脑子诡异的短路了一发   思路差不多是数目最多的糖果先摆着，然后如果剩下的可以插空插满，就是成立的 不可以插满的话就是不成立，对于测试数据是4 2 1 3个糖果先摆上 然后剩下的三个插在4个的中间就可以了 。所以是剩下的大于等于最大值减一……就在这个地方诡异的短路了、一开始以为是大于最大值加一才成立  #include<iostream> using namespace std; int a[1000010]; int main() { int T; cin >> T; wh...

http://acm.hdu.edu.cn/showproblem.php?pid=6186  一开始自己做的时候一脸懵逼 然后在网上看了一下别人写的 又费了一番周折才A了这个题 意思是说 输入n个数 然后p次查询 每一次都输出除了第p个数以外 其他所有数的且运算，或运算，还有异或运算。思路也比较简单吧就是在一个数组里存前缀和 一个数组里存后缀和（前缀和也就是l[i]表示l[1]&l[2]&…l[i] 中间的符号也可以是|和^这里用&表示了 后缀和就是r[i]表示r[i]&r[i+1]&…r[n]）这样预处理完了以后 算答案的时候直接l[p-1]&amp...

http://acm.hdu.edu.cn/showproblem.php?pid=1285 一个拓扑排序的题 这个题的输入数据保证正确 所以不用判断有没有解 一开始按书上的用栈还有邻接表的数据结构 写了半天没写出来 后来在网上看的这种用  1.G数组赋值：ij有边给ij赋值为1  2.D数组赋值：D[i]表示i点的入度  3.找N-1次,每次找到第一个入度为0的点 输出 并且把和这个点发出的边删掉（对应点的入度减一） #include<iostream> #include<cstring> using namespace std; const int maxn = 5...

一个记忆化搜索的题目，参考了网上的代码才写出来的。  dfs（x，y）表示从x，y开始走的话最大的结果是多少。每一次搜索上下左右k步中 最大的那一个 还有一点dp的思想。dp数组用来记录结果，并且防止重复判断。 #include<iostream> #include<cstring> using namespace std; const int maxn = 110; int G[maxn][maxn]; int dp[maxn][maxn]; int dir[4][2]={0,1,0,-1,1,0,-1,0};//一个表示方向的数组 int n,k; int dfs(...