青烟绕指柔

分类

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 数论(12) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

全部文章（共382篇）

[CQOI2015]任务查询系统

题目链接：[CQOI2015]任务查询系统因为对于任务来说，对一段区间是有用的，于是我们可以用差分来表示区间，然后主席树维护前缀区间和即可。然后因为我们是求和，我们同时主席树也要维护区间的数字个数，因为求K小和。但是有可能当前区间的有a个相同的数字，我们求b个和，然后b<a，然...

2019-12-27

0 435

解方程

因为a比较大，使用高精度去计算必然会TLE。于是我们可以利用hash的思想，相当于对等式，两边同时取模。这里我使用了孪生素数来双hash，增加可靠性。计算多项式直接秦九韶就行（初中知识应该都会） AC代码： #pragma GCC optimize(2) #include<...

2019-12-27

0 581

51Nod 树的距离之和

给定一棵无根树，假设它有n个节点，节点编号从1到n, 求1-n这n个节点，到其他n-1个节点的距离之和。输入第一行包含一个正整数n (n <= 100000)，表示节点个数。后面(n - 1)行，每行两个整数表示树的边。输出每行一个整数，第i(i = 1,2,…n)行表示所有节点到...

2019-12-27

0 327

51Nod 1711 平均数

LYK有一个长度为n的序列a。他最近在研究平均数。他甚至想知道所有区间的平均数，但是区间数目实在太多了。为了方便起见，你只要告诉他所有区间(n*(n+1)/2个区间)中第k大的平均数就行了。输入第一行两个数n,k(1<=n<=100000,1<=k<=n*(n+...

2019-12-27

0 473

华华和奕奕学物理

题目描述众所周知，9406计算机大佬众多，他们不仅代码能力强，而且都精通物理。物理无处不在，甚至坐电梯的时候，zck和xxr都在讨论若电梯突然失重会怎样。身为文科生的华华和奕奕非常难过，他们决定学习物理，不能让小伙伴们看不起。奕奕现在正在研究一道物理题。有Q次操作：若op<mark>...

2019-12-27

0 447

抓捕盗窃犯

题目链接：抓捕盗窃犯仔细想一下图的构成就可以看出，一个点一个出度，所以对于每一个联通块比构成环，在环上随便一个点设置哨卡就能抓到联通块所有人。所以我们找到m个最大的联通块即可。更复杂的图可以用Tarjan，但是我们这道题直接并查集即可。 AC代码： #include<bit...

2019-12-27

0 378

小D的剑阵

题目链接：小D的剑阵对于每一把剑，我们都有选不选的问题，也就是非黑即白的问题。于是我们可以想到最小割建图。先加上所有可以增加的价值，然后减去最小割即可。然后列出方程，解出小学生都能解的方程就可以了。 AC代码： #include<bits/stdc++.h>...

2019-12-27

0 353

流星雨

题目链接：流星雨比较简单的概率dp，我们令dp[i]为第i天，下流星雨的概率，然后就不难递推了。最后乘以下流星雨的个数即可。 AC代码： #include<bits/stdc++.h> #define int long long using namespace std...

2019-12-27

0 571

选点

题目链接：选点看似像树形dp，而且还很麻烦。但是我们可以注意一下，这是二叉树，大小关系为：左儿子 > 右儿子 > 根所以如果我们先遍历根，然后往右儿子走，然后往左儿子走，的dfs序。然后就是求LIS就行了。比较思维。 AC代码： #include<...

2019-12-27

0 425

筱玛的迷阵探险

题目链接：筱玛的迷阵探险数据量比较小，于是可以想到爆搜，但是复杂度为 2^40，必然不行，于是对于二进制求max，我们可以想到用Trie去维护。怎么做呢？我们双向dfs，对每一个走到 n/2 步数的节点分别开一个Trie，然后下一次从终点走到这个节点时，然后从这个节点当中的Trie里面去找m...

2019-12-27

0 485