Articles in the category of 2018年多校

[WC2011]最大XOR和路径线性基

题解考虑到如果图中存在一些环，那么我们就可以在不影响其它值的情况下获得这些环上的值。具体证明：考虑到我们从1点出发经过一些点以后我们可以到达环到链条的起点v，然后我们经过环又回到v，这样我们的取值就是从1-v路径上的值异或上环上的值，然后我们回到1，根据异或的性质，相当于我们取得了环上的值，所以我们把所有环上的值加入到一个线性基上，然后把任意一条1-n路上上的值异或线性基上的值取最大值，任意...

285484026 October 3, 2019 No comments

「POI2011」Tree Rotations-线段树合并

现在有一棵二叉树，所有非叶子节点都有两个孩子。在每个叶子节点上有一个权值(有n个叶子节点，满足这些权值为1-n的一个排列)。可以任意交换每个非叶子节点的左右孩子。要求进行一系列交换，使得最终所有叶子节点的权值按照前序遍历序写出来，逆序对个数最少。输入解释：第一行一个数n，表示该二叉树的叶节点的个数；下面若干行，每行一个数 x如果x = 0，表示这个节点不是叶节点，递归地向下读入其左孩子和右孩...

285484026 October 3, 2019 No comments

[2019南昌网络赛] tsy's number 莫比乌斯反演整除分块积性函数递推

问题为： \begin{align*} 若k != 1\ g(p) &= p^k-p^{k-1}-(p^{k-1}-p^{k-2})\\ g(p) &= p^k-2p^{k-1}+p^{k-2}\\ g(p) &= (p-1)^2p^{k-2}\\ \end{align*}这样的话就可以用线性筛递推求得g(n)#include <bits/stdc++.h> const int...

285484026 April 23, 2019 1 comments

CCPC-Wannafly Winter Camp Day3 Div2

二十四点夏威夷手算答案，然后让我从890开始交，然后到891就过了,嘿嘿嘿，我觉得我还挺欧的，夏威夷真的牛逼,讲题的时候jls对他竖起了大拇指说了句牛逼#include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d",&n); if(n ...

285484026 January 28, 2019 No comments

HDU-6363 bookshelf 莫比乌斯反演

bookshelfProblem DescriptionPatrick Star bought a bookshelf, he named it ZYG !! Patrick Star has N book .The ZYG has K layers (count from 1 to K) and there is no limit on the capacity of each layer...

285484026 October 1, 2018 No comments