牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共16篇）

模拟100 题解

A. 组合将两个字符之间建边，问题转化为一笔画，也就是欧拉路问题。所以直接用dfs压栈的方法解决，注意正确使用当前弧优化。 void dfs1(int x){ for(int i=head[x];i;){ if(vis[i>>1]){ head[x]...

dp 线段树图论欧拉路状压

2019-11-05

0 369

模拟102 题解

A. 你相信引力吗显然是单调栈处理。然而优弧/劣弧两种情况，加上高度存在相同，就比较难处理。然而环是可以平移的，所以一个好的方法是将其中的最大值移到一个端点，于是跨环端点的情况只出现在右半部分形成一个单调不降的序列。顺便去重就可以了。 B. 停不下来的团长奥...

图论 dp 线段树单调栈拓扑排序并查集

2019-11-06

0 327

模拟110 题解

A. 最大或因为或运算特殊的性质，从高位到低位进行贪心。将$l$，$r$的二进制位分别取出，从高到低枚举每一位，当存在一个二进制位不同，即在此位$l$为$0$而$r$为$1$。那么$x$可以选择后面每个二进制位中的$1$，保证低位贡献的最大化，$y$只要保证高位的贡献就可以了。 ...

图论单调指针位运算二分答案折半搜索

2019-11-11

0 287

省选模拟6 题解

A. Yist 首先考虑怎样的情况答案是不收敛的。操作中涉及到对一个权值非$0$，并且不作除法的点的加法贡献。因为只要最终的答案，可以想到对每个点作为出边的贡献分别处理。部分分提示求出第一次迭代的贡献，发现对于每个点，贡献都是一个等比数列，所以只要代入求和公式就好了。然而暴力做的复...

分块图论后缀自动机 dp 树状数组

2020-01-13

0 393

省选模拟9 题解

A. Surprise me 直接将$\varphi(i*j)$展开为$\varphi(i)*\varphi(j)*\frac{gcd(i,j)}{\varphi(gcd(i,j))}$。于是可以套用莫比乌斯反演。最终的式子大概是$\sum \limits_{T=1}^{n}f(T)\su...

二分图虚树图论结论题莫比乌斯函数点分治提交答案

2020-01-17

0 654

省选模拟21 题解

A. 灯容易发现问题是连通块数，因为原图是树，可以用点数（为$1$的点）减边数（连接相邻的为$1$的点的边）表示。点数是易于维护的，所以问题是维护边数。考虑一个情况，每种颜色的出现次数都很少，那么可以直接在原序列上暴力。另一种情况，每种颜色的出现次数都很多，并且颜色总数不多。那么...

根号分治 dp 图论

2020-02-08

0 317