spnooyseed

分类

2019 icpc Nanchang(1) 2019 icpc yinchuan(3) 2019icpc Nanjing(3) 2019暑假8月份(13) 2019暑假牛客补题(2) 2019牛客多校训练--第一场补题(1) 2019牛客多校训练-第一场补题(1) Atcoder(4) CF(2) dp(1) hash(1) Loj(1) python(1) upc补题(7) 分层最短路(1) 搜索(1) 数学一本通-数论(7) 数学一本通组合数学(2) 数据结构(6) 数论(2) 数论 -- 类扩展欧几里得(1) 最小生成树(1) 最短路(4) 未归档(5) 板子(5) 树状数组(1) 模板(7) 每日一题(1) 牛客(1) 规律题(1) 题解(1)

/ 注册

全部文章（共88篇）

E - Sum of gcd of Tuples (Hard)

莫比乌斯反演过程：最后就是 #include <bits/stdc++.h> using namespace std ; const int mod = 1e9 + 7 ; const int N = 1e5 + 5 ; int phi[N] , tot , prime[N] , ...

2020-04-13

0 984

「一本通 4.4 例 4」次小生成树

题目描述原题来自：BeiJing 2010 组队赛给定一张个点条边的无向图，求无向图的严格次小生成树。设最小生成树的边权之和为，严格次小生成树就是指边权之和大于的生成树中最小的一个。输入格式第一行包含两个整数和，表示无向图的点数与边数；接下来行，每行三个数，表示点 ...

2020-04-09

0 928

次长上升子序列

题目描述最长上升子序列是一道经典的题目,liu_runda很想在模拟赛中考考这个题目,但是他又不想被选手骂出原题,于是就把原题魔改一下再出出来.对于一个数列a[1],a[2]…a[n], 我们定义子序列是一系列下标的集合: {x1,x2…xm}其中, 1<=x1<x2<x3…<...

2020-04-06

0 748

Shortest Path【每日一题】

1、题意给一颗偶数个节点的有边权树，节点数为n ，要求划分成n / 2 个集合，两个点在一个集合中，代价为两点之间的最短路径，然后要求求最小代价 2、策略 1)、贪心的讲，我们两点之间尽量连一到两条边，不然多条边肯定会造成更大的代价， 2)、树上的算法一般都是由dfs 为主体...

2020-04-03

0 665

树形dp初探

此题目的意思就是现在有以s节点为根节点的一棵树，要求断掉一些边，使得叶子节点无法到达根节点（在一个树中，只有一个度的节点只有叶子节点，或者单链式的树(如样例2)）单链式的树根节点和叶子节点都有且只有一个度，所以要特殊考虑一下下面直接考虑树形dp做法考虑一下研究总问题：以s为节点的子树断掉一些...

2020-04-01

0 590

取最值

参照题解，但他这个是凸的题目描述今有一两行n列的长矩阵，其中的数有正有负，均不超出整数的范围。小明想从这个长矩阵中圈出一个“凹”字形（可正可倒），使得这个“凹”字形中的所有数之和尽可能大，请问能达到的最大值是多少？输入输入第一行包含一个整数n，即矩阵的列数，n小于1000000...

2020-03-20

0 641

马拉车算法模板

大佬博客马拉车用于解决最长回文子串问题，重点是子串，而不是子序列，想了解最长回文子序列的可以看下这篇博客传送门。对于这种问题，当然最简单粗暴的方法就是暴力求解，但太暴力也不好，毕竟会TLE。所以对于求最长回文子串的问题有一种神奇的算法——马拉车算法，神奇就神奇在时间复杂度为O(n)。我先说一下...

2020-03-20

0 790

凸包模板

凸包算法（Graham扫描法）详解先说下基础知识，不然不好理解后面的东西两向量的X乘p1(x1,y1),p2(x2,y2) p1Xp2如果小于零则说明 p1在p2的逆时针方向如果大于零则说明 p1在p2的顺时针方向 struct node{ double x,y; ...

2020-03-17

0 789

F - Perils in Parallel

类似于差分异或前缀和，将区间操作连成图，跑一便 #include <bits/stdc++.h> using namespace std ; const int N = 2e5 + 10 ; int a[N] , b[N] , c[N] , d[N] ; int n , m ; i...

2020-03-13

0 695

F. Maximum White Subtree 树形dp*换根

大佬博客 #include <bits/stdc++.h> using namespace std ; const int N = 2e5 + 10 ; int ans[N] , a[N] , dp[N] ; vector<int> v[N] ; int dfs(int u...

2020-03-13

0 624