Articles in the category of 2018年多校

  1. Home
  2. 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