Arn01d's planet

队名：智力不太好 过题数：5/13 排名：151/279，Bronze Medal 最后一个赛季的第一舞。开了个智力不太好的头。 一直觉得CCPC正式赛站比ICPC难，毕竟CCPC的队伍更少一点，选拔力度更大，何况正式赛前几次vp往年CCPC正式赛和电子科大出的题结果都不理想，所以这次是奔着铜牌去的，然而没想到居然离银牌只有一步之遥，， 热身赛感觉还行，熟悉了一下环境，做了做水题，有幸目睹右前方队伍坐踏椅子。 第二天开始意外就接连不断了。从酒店出来打车去学校·，虽然只有1.7公里但是太冷了。但是这司机好像不太会用智能设备，跟着导航的路要走到学校里面，但是保安不让进。然后那司机说只有乘客能改路线。ok。。。纠结（默默在心里骂司机）了一会后还是选择下车走路到现场。走了600米导致错过了早饭并且还拖着一个行李箱。这才叫热身赛好吧。 开始比赛之后，热身赛配置的pycharm环境被删了，因为有自动补全，但是没人告知选手。然后我们拖了一个志愿者过来问能用vscode吗（热身赛被告知没有配置cpp环境），然后那憨憨的志愿者回答说没有配置环境。然后我们就开始尝试别的编译器，但是没人用过codebloc ...

队名：智力不太好 过题数：5/12 排名：448/2156，校排第四 比赛地址：Dashboard - The 2024 CCPC Online Contest - Codeforces 第一次打CCPC网络赛，着实没想到网络赛第一步筛的是网络好的。比赛开始20分钟后刷出了题目，但是没人过题，结果挑了一个A来看（全场最难的题之一），还跟队友推得有理有据的，似乎是一个水题，，，30分钟后队友的电脑刷出题目了，发现L已经过了一车人，天都塌了，索性马上签L，然后想了想放弃了A（太明智了），开始签其他题。 除了L签到，还有一个博弈签到，也被速速推出然后一发，跟榜看B，队友一眼发现性质，然后又过了，开始1小时把签到题都签上了，甚至排在了学校第一。 然后就是慢慢啃中档题，两个都是dp，放心交给队友，推了推也推出了式子，虽然很丑（丑就对了）但是过了，另一个dp题交了几次wa了，后来我搓了几个样例试了试，查出问题后也很快过了。 然后就开始坐牢了，，， 另外一个J题，同校的很多都已经过了，然而我们一直干瞪眼，最后还剩一个半小时的时候（延长了一个小时）我想到了一个转化，似乎很有道理，然后就不会了。后来看题 ...

线性基：线性基是一个数的集合，并且每个序列都拥有至少一个线性基，取线性基中若干个数异或起来可以得到原序列中的任何一个数。类似于基底的概念，只不过运算方式是异或。 性质： 1. 原序列里面的任意一个数都可以由线性基里面的一些数异或得到。 1. 线性基里面的任意一些数异或起来都不能得到 0。 1. 线性基里面的数的个数唯一，并且在保持性质一的前提下，数的个数是最少的。 12345678910111213141516171819202122232425262728293031323334void add(ll x){ for(int i=60;i>=0;i--) { if(x&(1ll<<i))//注意，如果i大于31，前面的1的后面一定要加ll { if(d[i])x^=d[i]; else { d[i]=x; break;//插入成功就退出 ...

Operators 在C++中可以重载运算符，实现自定义的运算。当原有运算符被重载后，只有当输入参数满足条件才会执行。 全局模板函数中重载运算符 12345template<typename T>T operator+(const T& lhs,const T& rhs){ return a+b;} 类模板中重载运算符 12345678910111213141516171819202122232425262728293031template<typename T>class MyClass{public: MyClass(T v,T u):x(v),y(u){} MyClass operator+(const MyClass& other) const { return MyClass(x+other.x,y+other.y); } //重载输出 friend std::ostream& ope ...

跟着Stanford的cs系列补了一下C++。虽然打ACM一直在用C++，但是也只是用的C with cin cout，看课的同时练练听力磨磨耳朵，也有很多收获。 Stream $Stream$（流），分为输入流（$istream$），输出流（$ostream$）和双向流（$iostream$），其中 $istream$ 又分为 $ifstream$ 与 $istringstream$ ，分别用于文件与字符串的输入，$ostream$ 与 $iostream$ 同理。其中 $cin$ ，$cout$ 分别是输入流与输出流的一个实例，专用于向控制台或命令行输入输出。 以字符串相关的流为例，对于输出流有： 123456789ostringstream s("cat is cute ");cout<<s.str()<<endl;//cat is cutes<<"car";cout<<s.str()<<endl;//car is cuteostringstream p("cat is ...

暴力美学的集大成体现。 通常是对同一个问题有两种暴力的方法分别适用不同的数据范围，那么可以以某一个值为分界点，当小于这个阈值用一种暴力 $O(b)$，大于就用另一种暴力 $O(\frac{n}{b})$； 这个值通常为 $\sqrt{N}$ ； 这类题目会有明显或隐藏的限制条件，比如某个值的数量一定。 例1 给一个长为 $5\times 10^5$ 的序列，初值为0，完成 $q$ 次操作，要么是将 $a[x]$ 加上 $y$ ，要么是询问所有下标模 $x$ 等于 $y$ 的位置之和。 设置阈值 $b$ ，对于小于 $b$ 的模数，预处理数组 $dp[i][j]$ 表示模 $i$ 余 $j$ 的所有下标的数之和。 若模数大于 $b$ ，直接暴力枚举，$O(\frac{n}{b})$。 若模数小于 $b$ ，使用预处理的数组 $O(1)$ 查询。 对于更改，只修改模值小于 $b$ 的 $dp[i][j]$ ，$O(b)$。 故总时间复杂度为 $O(q(b+\frac{n}{b}))$ ，使阈值 $b=\sqrt{n}$ 时复杂度最低。 例2 $n$ 位用户组成了一个双向的网络。如 ...

第二场感觉好多了，没那么唐了，三个签到题出的没那么快但是都是一发过，在三题队中排名非常靠前；后期想出了一个有点复杂的 $I$ ，做出四个题，排名还不错。这次智力还可以。 A 题意：给定两个大小为 $1\times 1$ 的瓷砖花纹 $A,B$，现在要排一个 $n\times m$ 的瓷砖矩阵，使连续的条纹数量为 $K$ 。 一个找规律题，并不是很难，但似乎榜歪了，都没怎么考虑这个题。 将整个图案分成很多个 $2\times 2$ 的小区域，当每个区域排列都为 $ABBA$ 时会构成很多个圆，这样子的条纹数是最多的，而且每换掉一块瓷砖，花纹数量减少1。简单模拟即可，注意一下处理特殊情况，比如有些边界的瓷砖调换后不会影响数量。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959 ...

队名：智力不太好 瞎取个名字早早埋下了伏笔，，好久没打这么正式的比赛了，这一次真和队名呼应上了，两个签到都不是很顺利，第一签差点抬上树状数组，第二签wa了3发60min才通过 :(((((( 。然后150min推出了$A$ 的式子，写一手代码发现这玩意儿居然卡常（也有可能是我们的式子取模太多），最后全部预处理后一发wa，查了查发现没特判，第二发才过。后两人猛猛写 $I$ ，我在一边推 $B$，但是最后还是四题结束了，，有点可惜，赛后不久 $I$ 就出来了，$B$ 也推了出来。 A 题意：给出 $n,m,mod$ ，求符合以下要求的序列有多少个：一共有 $n$ 个数，每个数不超过 $2^m$ ，存在一个子序列所有数 $and$ 为1。 排除法。一共的序列种数为 $2^{nm}$ ，考虑不符合要求的排列： 若每个数的最后一位都是0，那么一定是不满足的。若存在某些数最后一位为1，那么： 这些数都不止一个1，否则本身就是1了； 这些数在相同的位上均含有1，否则全部 $and$ 起来前面的位就是0。 因此两重循环枚举：第一重枚举有 $i$ 个数结尾为1，第二重枚举这些数除了最后一位有 $ ...

同余最短路通常用于处理这类问题：已知 $a_1,a_2,…,a_n$ ，求 $x_1,x_2,…,x_n$ 使得 $sum=\sum a_ix_i$ 属于某个区间或者在某个区间的最小值。 若这个区间很小，那么可以直接用完全背包解决。 若区间达到 $10^{18}$ 级别，那么就不能用背包，考虑问题转化。 易得 $sum=\sum_{i=2}^{n}a_ix_i+a_1x_1=sum_1+a_1x_1$ ，即把 $a_1$ 单独提出来， 最后的答案可由 $sum_1$ 加上很多个 $a_1$ 得到。因此只需考虑在模 $a_1$ 意义下能得到的最小的数，即 $d[(x+y)%a_i]=d[x]+y$ 。可转化为建边 $add(x,(x+a_i)%a_1,a_i)$ 然后跑最短路。 例1 跳楼机 给出 $h,x,y,z$ ，求 $0-h$ 中有多少数可由多个 $x,y,z$ 组合得到。 同余最短路的模板。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515 ...

树的直径 求树的直径有两种方法，一种是树形dp，一种是两次dfs/bfs 性质 树的直径有一重要性质，在无负权边的图中，所有直径的中点相同。 树形dp 设 $d[x]$ 表示从 $x$ 开始到 $x$ 的子树中的最大距离，设 $f[x]$ 表示通过 $x$ 的最长链长度，那么有 $f[x]=max(d[y_i]+d[y_j]+w(x,y_i)+w(x,y_j))$ 。$f[x]$ 可以在dfs时直接维护。 123456789101112void dp(int x){ v[x]=1; for(int i=hed[x];i;i=nxt[i]) { int y=to[i]; if(v[y])continue; dfs(y); ans=max(ans,d[x]+d[y]+w[i]); d[x]=max(d[x],d[y]+w[i]); }} 两次dfs 从根开始dfs找到最远点，然后从最远点dfs找到的最长路径就是直径。 12345678910111213141516171819202122232425262728293031323334353 ...