工大最菜

题解

01规划(3) ACM比赛总结(3) ACM训练日记(11) bfs(7) dfs(5) Dilworth定理(1) dp(80) exgcd(1) gcd(2) java(1) KM(1) kmp(4) map(4) MOD运算(1) os(3) rmq(1) set(2) STL的操作(1) __int128(1) 一般图带花树的最大匹配(2) 三分(2) 中位数(1) 主席树(6) 二分(8) 二分图匹配(9) 二分图最大匹配(1) 二分图的多重匹配(1) 二维偏序(2) 二进制(2) 优先队列(2) 倍增DP(2) 其他(1) 分块(11) 分层图最短路(1) 分治(5) 分组背包(3) 前缀和(6) 动态最短路(1) 区间dp(18) 单调队列(2) 单调队列dp(2) 博弈论(11) 双连通(5) 同余最短路(1) 后缀和(1) 后缀数组(2) 因数(1) 大整数(1) 大模拟(2) 字典树(1) 字符串哈希(16) 完全背包(1) 容斥(1) 尺取(4) 并查集(3) 序列自动机(2) 康托展开(1) 异或(4) 强连通(1) 思维(6) 扩展KMP(3) 扫描线(2) 技巧(11) 拉格朗日插值法(1) 拓扑排序(3) 数位dp(8) 数学推导(2) 数论(18) 整体二分(2) 暴力(6) 最大权闭合子图(1) 最小生成树(5) 最小表示法(1) 最短路(15) 未归档(2) 构造(2) 构造树(1) 染色问题(1) 树(9) 树dfs序(2) 树上分块(2) 树上启发式合并(6) 树上差分(2) 树形dp(16) 树状数组(3) 树的BFS序(1) 树链剖分(6) 概率(24) 模拟退火(6) 欧拉函数(3) 欧拉回路(4) 点分治(5) 状压dp(11) 珂朵莉树(2) 生成函数(4) 矩阵快速幂(3) 矩阵计数(1) 离散数学(1) 离线(1) 线性基(1) 线性规划(1) 线段树(18) 线段树合并(2) 组合数学(1) 组合计数(1) 网络流(14) 莫比乌斯反演(1) 莫队(6) 表达式求值(1) 计数(5) 计算几何(4) 调度问题(1) 贪心(8) 费用流(6) 费用背包(1) 递归(2) 长链剖分(1)

/ 注册

全部文章 / 题解（共14篇）

每日一题 4月14日 Xorto 异或枚举区间端点

思路：我们知道[i, j]和区间[x, y]异或为0.那么我们枚举右区间端点。那么每次新增加的贡献为左区间异或值为Xor[x, j]的个数。我们在扫描的时候，可以维护所有的左区间的值和个数。 #include <bits/stdc++.h> #define LL long long us...

2020-04-14

0 584

每日一题 4月13日树学和 Accumulation Degree 换根DP

思路：看到这个题要求所有点，肯定要换根，我们肯定要把f[1]求出来。 #include<bits/stdc++.h> #define LL long long using namespace std; vector<vector<int> > v(100000...

2020-04-13

0 512

每日一题 4月9日 Running Median 动态中位数

思路：用两个优先队列，一个维护大的一半，一个维护小的一半。然后就可以了。 #include <bits/stdc++.h> #define LL long long using namespace std; int main(){ int t; scanf("%d", &am...

2020-04-08

1 628

牛客算法周周练1 ABCDE题解

A:思路：直接枚举这个交换点就可以了。 #include<bits/stdc++.h> #define LL long long using namespace std; LL a[100005]; LL s[100005]; int main(){ int t; scanf...

2020-04-07

0 595

每日一题 4月8日黑白树树形DP

#include<bits/stdc++.h> #define LL long long using namespace std; int k[100005], f[100005]; int ans=0; vector<vector<int> > v(10000...

2020-04-07

0 678

每日一题 4月7日树 dfs序+DP

#include <bits/stdc++.h> #define LL long long using namespace std; const int mod=1e9+7; LL f[305][305]; int main(){ int n, m; scanf("%d%d"...

2020-04-07

0 540

牛客OI周赛15-提高组 - 恢复数列

思路：可以证明n=X+m(X-1)+1 (m>=0),如果除去a[1].那么就是X+m(X-1)个数。因为每X个X^t的和=X^(t+1)，然后再从m(X-1)个中拿出X-1个数和X^(t+1)合成X^(t+2)一直到合成只有一个数X^(t+m+1)。t可以任意取。 #include <...

2020-04-04

1 655

每日一题 4月3日 Shortest Path 树上贪心

题意：有一棵树，有n个节点。让你分成n/2对。所有对之间的距离和最小。思路：我们尽量让每条边不重复经过。那么对于一棵子树v。和他的父亲节点u。还有之间的边权w。如果siz[u]%2==1那么v就和u连。ans+=w。如果siz[u]%2==0那么v和自己的子树连过了。不加w的贡献。 #include...

2020-04-02

0 513

每日一题 4月1日 Rinne Loves Edges 树形DP

#include<bits/stdc++.h> #define LL long long using namespace std; struct node{ LL to, w; }; vector<vector<node> > v(100005); LL...

2020-04-01

0 519

每日一题 3月31日城市网络树上倍增 or DFS+线段树 or DFS+单调栈

思路一：树上倍增 //我们讲一讲这个是怎么逼近 //可以证明f[u][0]一定是f[father[u]][i]购买路径上的节点 //把一个查询作为一个节点。那么最后就是看从查询的u节点开始能最多跳多少次，并且不超过v节点。 //往上倍增寻找第一个比a[u]大的节点下面那个节点(他的父亲就是第一个比...

2020-03-30

2 1053