题解p4069 2016 sdoi
【题解】P3648 [APIO2014] 序列分割
# 【题解】P3648 [APIO2014] 序列分割 对于这道题,我们很容易想出一个暴力 `DP`: 设 $f_{i,j,k}$ 表示将区间 $[i,j]$ 切割 $k$ 次的最大得分,$s_i$ 表示 $a_i$ 的前缀和。 我们可以得到一个式子: $$ f_{i,j,k} = \max_{i\ ......
CF786c分块题解
## CF786c分块题解 ### 思路: 首先思考一下如果直接硬着头皮做会怎么样? 对于每一个k,我都要遍历一遍数组贪心求解ans,导致n方时间复杂度 要发现一下性质: 1. 答案最多为ceil(n/k)。 2. 随着k的增加,答案单调不增。 3. 随着k的增加,答案越不容易改变(连续相同的答案越 ......
【牛客周赛 Round 10】A-D题解
### A https://ac.nowcoder.com/acm/contest/64272/A **题意** 游游定义一个数组为“稳定的”,当且仅当数组相邻的两个元素之差的绝对值不超过1。例如[2,3,2,2,1]是稳定的,而[1,3,2]则不是稳定的。 游游拿到了一个数组,她想求出该数组的最长 ......
【动态规划】【SDOI2017】序列计数
# 【动态规划】【SDOI2017】序列计数 ### 题目描述 Alice 想要得到一个长度为 $n$ 的序列,序列中的数都是不超过 $m$ 的正整数,而且这 $n$ 个数的和是 $p$ 的倍数。 Alice 还希望,这 $n$ 个数中,至少有一个数是质数。 Alice 想知道,有多少个序列满足她的 ......
8.30 模拟赛 光和影(dream) 题解
概括:大分类讨论。 首先有个重要结论,无论是三种操作中的哪一种,他的左儿子仍然在他的左子树内,右儿子在右子树内。同时,旋转一个点一次,对他更上面的点的深度没有影响。 以此,我们预处理出一个 $up_{u,0/1}$ 表示将 $u$ splay 到根上,对左子树和右子树深度的影响,由于上面的结论,这个 ......
CF838D Airplane Arrangements 题解
## 题意 一架飞机有 $n$ 个座位排成一列,有 $m$ 名乘客($m \leq n$)依次上飞机。 乘客会选择一个目标座位(两人可以选同一个目标座位),然后选择从前门或者后门上飞机,上飞机后,他们会走到自己的目标座位,如果目标座位已经有人坐了,他们会继续往前走,在走到第一个空位后坐下。如果走到最 ......
【题解】P2900 [USACO08MAR] Land Acquisition G
题目链接:[P2900 [USACO08MAR] Land Acquisition G](https://www.luogu.com.cn/problem/P2900) 我们通过题目可以得出一个较为清晰的结论: - 我们将所有的矩形排列起来,可以发现最后被完全包含在另一个矩形内的矩形是没有意义的。 ......
[ABC318G] Typical Path Problem 题解
## 题意 给定一个 $N$ 个节点和 $M$ 条边组成的简单无向联通图,给定三个节点 $A,B,C$,求是否存在一条简单路径满足 $A \rightarrow B \rightarrow C$。 ($3 \le N, M \le 2 \times 10^5$)。 ## 题解 因为简单路径要求每个节 ......
【题解】AtCoder Regular Contest 163 A-D
E 太过于 adhoc,F 太过于神仙,就不做了。 ## A.Divide String ### 题目描述: 多组数据。 给出一个长为 $N$ 的字符串,问能否将其划分为多段,使字典序**严格**上升,保证 **$\sum{N}\le2000$**。 $ 2\ \le\ N\ \le\ 2000 $ ......
题解:【ABC318G】 Typical Path Problem
[题目链接](https://www.luogu.com.cn/problem/AT_abc318_g) 无脑圆方树。建广义圆方树,对于路径 $u \to v$ 上的圆点为必须经过的割点,经过的方点连出去的任意一个点 $z$,记路径上和方点相连的两个圆点为 $x,y$,原图必定存在一条简单路径 $x ......
【动态规划】“新手动态规划合集”题解
## 动态规划三要素 阶段,状态,决策 ## 动态规划经典模型 ### LIS(最长上升子序列) 给定长度为 $N$ 的序列 $A[i]$,求出其最长上升子序列的长度。(以不严格上升为例) - 阶段:已经处理的序列长度 $i$ - 状态:$f[i]$ 表示以 $A[i]$ 结尾的 LIS 长度 - ......
win2016搭建frp内网穿透的FTP服务器可用phpstorm
操作系统:Windows Server 2016 Standard FTP服务器:ser-U 7.0.0.1 之前用FileZilla Server,但phpstorm怎么连接不上FTP,最后安装Ser—U使用了SSH模式成功连通。 #### 下载安装Ser-U ![image](https://i ......
[ABC318D] General Weighted Max Matching 题解
# [ABC318D] General Weighted Max Matching 题解 ## 题意 给定无向有权完全图,求最大权匹配。 ## 思路分析 注意到 $n \le 16$,我考虑状压 DP。 设当前点集 $S$ 中最大权匹配的答案是 $f_S$,我们考虑 $S$ 中“最后”一个点 $p$ ......
[ABC318E] Sandwiches 题解
## 题意 给定一个长度为 $N$ 的正整数列 $A = \left(A_1, A_2, \cdots,A_N\right)$,求满足以下条件的正整数三元组 $\left(i, j, k\right)$ 的数量: - $1 \le i typedef long long valueType; typ ......
CF1848B Vika and the Bridge 题解
# CF1848B Vika and the Bridge 题解 ## 题目大意 ~~给个题目传送门吧,感觉题意已经很清楚了~~ [题目传送门](https://www.luogu.com.cn/problem/CF1848B) ## 分析 (~~我不会告诉你我第一眼看过去是二分~~) 因为我们只能 ......
[ABC318E] Sandwiches 题解
一开始考虑枚举 $i$ 或 $k$ 来统计,发现需要 $O(n^2)$ 的时间复杂度。 因此考虑枚举 $j$,我们可以用 $l_x$ 表示满足 $i const int N=3e5+5; int n; int a[N]; int l[N],r[N]; long long ans,sum; int m ......
[ABC318D] General Weighted Max Matching 题解
因为 $n$ 很小,所以考虑状压 dp。 令 $sta$ 为一个二进制整数,表示当前第 $i$ 个点有没有被匹配。 那么显然对于每一个 $sta$ 第 $i,j$ 两点未被匹配的都可以用边 $(i,j)$ 来转移到 $sta|(1 #include typedef long long ll; con ......
P3604 美好的每一天题解
[传送门](https://www.luogu.com.cn/problem/P3604) # 好题! 首先说这道题的时间复杂度:$O(26n\sqrt n)$。因为转移是的常数是 $O(26)$ 并非 $O(1)$,这启示我们,**看数据范围,不要被O(1)给限制了,O(1)是一般情况,有些题不一 ......
【题解】AtCoder Beginner Contest 318(D - Ex)
赛时过了 A-G,Ex 仿佛猜到了结论但是完全不懂多项式科技,就炸了。 大家好像都秒了 A,B,C 就不写了。 ## D.General Weighted Max Matching ### 题目描述: 给你一个加权无向完全图,图中有 $N$ 个顶点,编号从 $1$ 到 $N$。连接顶点 $i$ 和 ......
P4198 楼房重建题解
[传送门](https://www.luogu.com.cn/problem/P4198) 一眼数据结构。 考虑线段树,记录该区间能看到最多的建筑数量 $ans_{wz}$ 以及看到区间中最大的斜率(或者说,该区间内最后看到的建筑)$xl_{wz}$。 很明显,假如我现在的修改操作是 $(x,y)$ ......
AT_abc318_e 题解
# AT_abc318_e Sandwiches 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc318_e) [AtCoder](https://atcoder.jp/contests/abc318/tasks/abc318_e) # ......
P3872 [TJOI2010] 电影迷题解
[传送门](https://www.luogu.com.cn/problem/P3872) 一眼网络流,考虑建图。 根据贪心思想,我们最好选完所有正权点,不选所有负权点。 **Trick:考虑 $S$ 向所有正权点连边,流量为权值,所有负权点向 $T$ 连边,流量为权值绝对值。** 但他还有一些限制 ......
[ABC318C] Blue Spring 题解
# [ABC318C] Blue Spring 题解 ## 题意简述 主人公出去旅游要买票,共有若干天,每天要花不同钱。现在有“通行证”出售,通过购买通行证,可以在某一天直接用通行证,以此来省去当天原本需要花费的票价。通行证只能一套一套买,每套中有 $D$ 个,买一套要花费 $P$ 元。可以购买任意 ......
AT_abc318_d 题解
# AT_abc318_d General Weighted Max Matching 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc318_d) [AtCoder](https://atcoder.jp/contests/abc31 ......
AT_abc318_c 题解
# AT_abc318_c Blue Spring 题解 ## Links [洛谷](https://www.luogu.com.cn/problem/AT_abc318_c) [AtCoder](https://atcoder.jp/contests/abc318/tasks/abc318_c) ......
Sushi 题解
[题目传送门](https://www.luogu.com.cn/problem/AT_dp_j) 一道 dp 题。 发现以前课上讲的题能水题解。 在 `dp` 之前,我们需要明确以下几个东西: **状态的表示**,**状态转移方程**,**边界条件**跟**答案的表示**。 ### 状态的表示 $ ......
[图论与代数结构 601] 最小费用最大流 题解
[题目传送门](https://www.luogu.com.cn/problem/B3608) 一道网络流题。 费用流板子题。费用流实际上是在给最大流套个最短路,而费用流一般边权会有负数,所以用 SPFA 算法,~~关于 SPFA,它复活了~~。 可以在最大流做 bfs 的时候将 SPFA 套上去。 ......
ABC317题解报告
我直接从第三题开始讲了。 [T3](https://atcoder.jp/contests/abc318/tasks/abc318_c) 把数组 $A$ 从大到小排序。 然后从前往后把前 $q$ 个数加起来,然后判断这 $q$ 个数的和与 $d$ 的大小关系,如果大了就变成 $d$。 然后有些细节就 ......
【题解】NOIP2021
咕咕咕的东西总是要补的。 ## A.报数 ### 题目描述: 报数游戏是一个广为流传的休闲小游戏。参加游戏的每个人要按一定顺序轮流报数,但如果下一个报的数是 $7$ 的倍数,或十进制表示中含有数字 $7$,就必须跳过这个数,否则就输掉了游戏。 在一个风和日丽的下午,刚刚结束 SPC20nn 比赛的小 ......