赛后总结就是菜死了。 本场比赛个人难度分级：  A CDGM BFH IJL K  听说E有问题，我看了大概15min也没看懂，就不评价难度了 缩短博客长度，只发核心代码。 水题 A 牛客输出字符串的题目一律用PHP /\*I like "algorithmic competitions" and I want to be stronger*/\ C int main(){ ll T=read(); while(T--){ ll a=read(),b=read(),c=read(); ll aa=read(),bb=read(),cc=read(); ll ans=min(c,aa)+min(...

太丢人了

这个学期一直在遭受苦难，好久都没有这么开心过了。感谢我的队友，以及一路上所有帮助我们的人。

E 弦 显然我们需要给出所有弦不交的概率P。 先对分子（两两相连且不相交的情况总数）进行推导：其实这和经典题目凸多边形的三角形划分很相似（但我也没有做过）。易知 时有1种情况, 有2种情况。  时有五种情况，如图：  其实这里已经可以大概猜到是卡特兰数了，但是这里我们做一些更严谨的推导，网上的推导要么就是没有，要么就复杂而且不讲人话。下面给出一种简洁的证法来证明连不相交弦的情况总数为卡特兰数。 众所周知，卡特兰数本身和栈/递归联系非常紧密。所以无论是理解还是证明卡特兰数，引入递归的思想十分重要。   比如对于n=4的情况，我们轻轻地连一条线。此时圆被我们切割成了两个部分：线的左边和右边。左边和...

并查集简介 0. 并查集的引入 并查集主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作：合并（Union）：把两个不相交的集合合并为一个集合。查询（Find）：查询两个元素是否在同一个集合中。 它是一种非常精巧且使用的数据结构，它主要用于处理一些不相交集合的合并问题。经典的例子有连通子图、最小生成树的Kruskal算法和最近公共祖先（LCA）等。  并查集的时间复杂度（不包括初始化）为  1. 并查集的初始化2. 合并3. 查找4. 优化为了解决搜索树退化问题，需要完成优化： 本段落转自Pecco，水印是因为牛客强制水印（差评）。  查找的优化：路径压缩 int fin...

循环控制 # 指定起始点 for i in range(1, 10) # 指定步长 for i in range(1, 10，2) # 使用range()函数来创建一个列表： list(range(5)) # [0,1,2,3,4] # pass语句 while True: pass # 占位符 为了弥补没有空分号的缺陷 py可以对循环语句使用else count = 0 while count < 5: print (count, " 小于 5") count = count + 1 else: print (count, " 大于或等于 5")...

十六进制转八进制 #include<bits/stdc++.h> using namespace std; int deal(char x) { if(x>='A') return x-'A'+10; else return x-'0'; } int main() { string hex; while(cin>>hex) { int len=hex.size(),i=0; if(len%3==1) printf("%o",deal(hex[0])),i=1; else if(len%3==2) printf("%o",de...

奇偶半排序  设计算法将顺序线性表中的所有奇数集中到数组的左边，所有的偶数集中到数组的右边，要求算法的时间复杂度为O(n)。  #include<iostream> #include<algorithm> using namespace std; int main() { int n; while(cin>>n) { int a[n]; for(int i=0; i<n; i++) cin>>a[i]; for(int L=0,R=n-1;L<R;){ while(a[L]&1) ++L; while((L<R)&amp...

这次比赛我不应该贪B题的，看到钟涛做出来了我就觉得我应该也可以（但是我没搜洛谷，如果主攻D题可能就做出来了。  D题 https://ac.nowcoder.com/acm/contest/3007/D 思路 其实我的思路是对的，就是对每个Bi，找有多少个比相应位置Ai后面的Ai可以换到这个位置来。然后有多少个，在这个位置上，就有多少种方案，就能乘多少次。真正麻烦的是不要做重复做的事情，内层循环继承j的值容易超时。最后long long。 实现 TLE #include<bits/stdc++.h> using namespace std; typedef long long ll...

总结 是收获颇丰的一场，明天醒来补题，现在记下来，免得忘记了。  圆周率的表示方法const double PI=acos(-1);，我之前记过，但是忘记了，这次还是写的 const double PI=3.14159264354;(这个也是我背下来的 【J题】https://ac.nowcoder.com/acm/contest/view-submission?submissionId=42948838&returnHomeType=1&uid=538133338 sin函数的使用方法 2*r*sin(PI/n) 表示圆内接多边形的边长，因为sin里面是弧度制，所以要特别注意...

本次训练赛大量涉及STL。 D题 题意 https://ac.nowcoder.com/acm/contest/3005/D长度为n数组，求子段异或值为0的个数。这道题据说是滴滴还是字节跳动面试题改编，原题是不可分割求最大，用DP，这一题是可分割，应该是简单了不少。 思路 与其说思路不如说是教训。  数组开太大（2e5*2e5）即使是在全局变量里面开出来也不允许，而且这种情况是段错误而不是MLE。 wa了也不能证明不会TLE。 N=2e5就不要幻想n2的复杂度能过了。  我的错误代码 #include<bits/stdc++.h> using namespace std; type...

H题 题意 统计1~n“k合因子数”数量。一个数的k合因子数是指这个数所有是合数的因子的数量。 思路 使用埃氏筛标记出来[1,n]所有的合数，因为埃氏筛的模板是标记质数，要特别注意1和0既不是质数又不是合数，所以记得要改一下标记。完成了这一步以后，我们得到一个[1,n]是否是合数的bool数组chk，要鉴别一个数x是否是合数，只需要查chk[x]即可。然后逐个检索每个合数，得到它们的因数个数，再减去其中非因数的即可。  其实我前一个小时一直在想这题，确切的说是一直在胡思乱想，我总觉得有更好的更优美的写法，可以直接一步到位。就是模仿欧拉筛：简单说一下，埃氏筛是筛掉所有质数的倍数，欧拉筛加了一个“...

https://ac.nowcoder.com/discuss/364961?tdsourcetag=s_pctim_aiomsg题解传送门 本次比赛C题DP挺经典的，值得回顾。 G题 判正误 判断  最早觉得是大数，一开始想直接用python糊过去。pythonTLE了以后还搞了很久的大数快速幂/大数加法，最后还是ZT大佬提醒我数据范围1e9……如果不取模直接快速幂也过不了。这次比赛一个深刻的教训就是大数取模，浮点数eps，不管题目给没给，都要考虑。 cpp代码 多次取模快速幂 #include <bits/stdc++.h> #define sscc ios::sync_wit...

中间一度怀疑是牛客的测评机出问题了……才发现是自己的数组越界。太艰难了。https://ac.nowcoder.com/acm/contest/2340/C题目是比较简单的，思路大概就是求解第一天到第t-1天的最佳策略，所以大概也可以说是一道贪心的题目。那么怎么确定最佳策略呢——填表。每个纪念品都会覆盖到某个值下的最优解，并且可以使得后续可以直接调用其生成的最优解，最后推出m对应的生成价值。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e4+5; int main(...