四糸智乃

题解

算法(12)

/ 注册

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

2019牛客多校第四场 C sequence

同南昌网络赛，贴过来改改直接过了。因为不单调，所以不能直接尺取，分治的话可以拿脚写。放宽了时限所以可以接受nlogn的复杂度。本来直接for是不单调的，但是如果规定分治中点mid，那么过mid往两侧延伸的最小值单调递减，过mid往两侧延伸的前缀和的前缀最大值与前缀最小值也是单调的。 ...

分治

2019-07-27

0 1017

HDUBeauty Of Unimodal Sequence

同NOIP2004合唱队形，原题DP部分可以直接贴。题意：求一个最长严格先上升后下降子序列，有两问，输出字典序最小解和字典序最大解。从后往前DP，使用线段树维护，过程中使用后继数组记录转移过程。然后顺着模拟一遍取出来就行了。思路很简单。 #include<bits/stdc+...

线段树序列型DP 动态规划最长上升子序列

2019-07-24

0 781

2019HDU1008多校Harmonious Army

题意：有n个人两种职业可供选择，有m对选择的关系，当两个人同时选择第一种职业时，将会获得a的权值,都选择第二种职业时将会获得c的权值，两人职业不同时将会获得的权值。让你为每个人分配职业，使得全职总和最大。既然有两种职业，当然不难想到二分图。一个人可选择两种职业，考虑拆点，拆成战士...

二分图最大流网络流最小割

2019-07-24

0 942

CodeForces1019E Raining season

半平面交对偶转凸包树分治归并排序求闵可夫斯基和用李超线段树维护答案。题意：给一颗树，每条边的边权是一个关于t的一次函数，问你在每个t下树的直径是多少。如果t是定值，那么就是求直径。求直径的方法除了dfs两遍，还有一个方法是树分治，类似分治法求最大子段和。考虑树分治，找到重...

单调栈凸包树分治半平面交闵可夫斯基和李超树

2019-07-23

2 1501