Hi_archer

自己选择的路,跪着也要走完

【NOI2010】 超级钢琴 线段树+堆

[2006: [NOI2010]超级钢琴][1]一句话题意：计算出所有区间和中前K大题解：显然根据题目要求我们需要在$O(NlogN)$的时间复杂度内解决这个问题。首先我们枚举左端点L，然后设区间右端点处在[qL,qR]这个区间。我们需要在$O(logN)$的时间复杂度内计算出从左端点到右端点区间和的最大值。如何快速的计算出这个最大值以及最大值所在的位置呢？预处理出前缀和，这样的话我们上述问...

  • 285484026
  • April 12, 2019
  • No comments
    •

    「SDOI2017」数字表格 莫比乌斯反演

    题目链接：https://loj.ac/problem/2000到这里为止时间复杂度显然是$O(TN^{2})$可以获得30分。那要AC我们就得继续对上式进行变形。设$i=dk$并带入下式并变形得显然这个表达式可以O(NlogN)的求出前缀积。然后我们根据这个表达式的性质再使用整数分块，然后就可以在$O(T\sqrt{N}logN)$内求出答案。代码：#include <bits/st...

  • 285484026
  • April 2, 2019
  • No comments
    •

    整除分块

    整除分块在数论中经常会出现如下表达式：显然我们直接计算的时间复杂度为$O(N)$，于是我们需要一种拥有更优时间复杂度的算法。通过打表我们可以发现。改表达式具有一些特殊的性质。1.$\lfloor \frac{N}{i} \rfloor$最多只有$2\sqrt{N}$种取值证明:对于$i\leq\sqrt{N}$,只有$\sqrt{N}$种取值，对于$\sqrt{N}$,同样也只有$\sqrt...

  • 285484026
  • April 2, 2019
  • No comments
    •

    Codeforces Round＃536（Div.2）

    A. Lunar New Year and Cross Counting题意：计算给定的数据中满足以下图形的X.X .X. X.X题解：模拟#include <bits/stdc++.h> using namespace std; int n,sum; char s[1000][1000]; inline bool check(int x,int y){ if(s[...

  • 285484026
  • February 3, 2019
  • No comments
    •

    CCPC-Wannafly Winter Camp Day8 Div2

    Aqours时间复杂度O(N)的题解：根据题目规定的条件，显然从每个叶子节点暴力往上面跳，并且在一路上记录从叶子节点到当前点的距离，直到找到一个已经被记录过的点，答案就是那个点上记录的值加上当前点到这个点的距离，并且在从那个点饭回来的路上要尝试用从那个点到这条路径的距离更新每个点记录的最近的叶子结点的距离。#include <bits/stdc++.h> const int M...

  • 285484026
  • January 29, 2019
  • No comments