- 博客(20)
- 收藏
- 关注
RSS订阅原创 [ybtoj5.2.3/UVA10559] 方块消除 Blocks [区间DP]
题意给你 NNN 个数 (N⩽200)(N\leqslant 200)(N⩽200) ，每次可以通过消去其中连续且相同的 xxx 个数以获得 x2x^2x2 的分数求可以获得的最大的分数思路一个很naive的想法就是设为 fi,jf_{i,j}fi,j 这种标准形式的区间DP但想一下就会发现在里面的数会受到其他数的影响，所以这样是不可取的那可不可以增加状态来表示呢？设 fi,j,kf_{i,j,k}fi,j,k 表示区间 iii 到 jjj 且之后跟着 kkk 个与第 jjj 个数相同
2021-07-09 15:31:29
110
原创 [ybtoj 4.5.5/P2680] 运输计划 [LCA/二分]
题意一棵树，有 NNN 个点，有边权给你 MMM 条路径，每条路径的权值等于在这条路径上的所有边的边权之和求在将一条边的边权改成 000 的情况下，所有的路径的权值的最大值最小思路在看到这种“最大值最小的”题目时，有一个常见的思路就是二分考虑直接二分答案然后就可以得到一个很显然的结论一个答案是合法的，当且仅当所有权值比答案大的路径都经过同一条边且所有的路径，且这些路径减去这条边的权值都比答案小然后就可以把这道题的判断改为判定如上条件了在判定每一条边被路径经过的次数时候可以利用树上差分的方
2021-07-08 16:41:07
68
原创 [ybtoj 4.4.5/CF555E] A Simple Task [线段树]
题意给定一个长度不超过 10510^5105 的字符串（小写英文字母），和不超过 10510^5105 个操作。每个操作 l,r,kl,r,kl,r,k 表示给区间 [l,r][l,r][l,r] 的字符串排序，k=1k=1k=1 为升序，k=0k=0k=0 为降序。最后输出最终的字符串。题解考虑到只有 262626 个字母，尝试将每个字母暴力拆开做线段树。具体来说就是在每次要求排序的时候将区间内的所有字母的数量取出，设 a[i]a[i]a[i] 表示区间有 a[i]a[i]a[i] 个 ii
2021-06-13 10:49:57
62
原创 [ybtoj 4.4.3/洛谷P4513] 小白逛公园 [线段树]
题意单点修改，区间求最大子段和思路用线段树维护维护每个区间的最大前缀和 lmaxlmaxlmax，最大后缀和 rmaxrmaxrmax，最大子段和 maxmaxmax 以及区间和 sumsumsum，可得以下递推式：lmaxl,r=max( lmaxl,mid,suml,mid+lmaxmid+1,r )lmax_{l,r}=\max(\ lmax_{l,mid},sum_{l,mid}+lmax_{mid+1,r}\ )lmaxl,r=max( lmaxl
2021-06-13 08:28:50
92
原创 [ybtoj 4.2.3 /UVA12983] The Battle of Chibi
题意在一个长度为 nnn 的序列中找到长度为 mmm 的严格上升子序列的个数 ，答案对 109+710^9+7109+7 取模。1⩽n,m⩽1031\leqslant n,m \leqslant 10^31⩽n,m⩽103思路设 f[i][j]f[i][j]f[i][j] 表示长度为 iii，以 jjj 结尾的子序列的数量，可以列得方程f[i][j]=∑k<jf[i−1][k]f[i][j]=\sum_{k<j}{f[i-1][k]}f[i][j]=k<j∑f[i−1][k]
2021-06-11 19:57:25
65
原创 某OJ进阶题单原题大赏
以洛谷作为主要的OJ写问号的有待补充目录第一部分 基础算法1.1 递推算法1.2 贪心算法1.3 二分算法第一部分 基础算法1.1 递推算法例题1 -> P1595 信封问题例题2 -> ?例题3 -> P1025 数的划分例题4 -> P1057 传球游戏例题5 -> ?1.2 贪心算法例题1 -> P1843 奶牛晒衣服例题2 -> P1325 雷达安装例题3 -> P2859 [USACO06FEB]Stall Reservat
2020-12-24 16:33:28
634
17
原创 如何优雅地在CSP2020中爆炸
裂开初赛乱写一通压线过了/kk然而似乎考的还是跟去年差不多/kk上午进场后调试时不会开栈（暗示RP–）然后开始做题，刷T1。然后看T2，三分钟胡了一个暴力桶排。但怕因为人傻常数大，所以老老实实敲了个对顶堆。（允许STL好评，priority_queue真香）然后看T3一眼不可做，就去看T4（然后看一眼T4，发现是自己做过的题（（（20分钟做完后就去淦T3淦了一个半小时后终于敲完了对完拍后一看还有一个小时于是就去淦小恐龙（终于在最后20分钟时淦上万了（（（然后检查了N遍没有
2020-11-21 10:42:23
115
原创 2008GDSOI 鱼肉炸弹
自闭了。题目链接解法可以看出，对于每个节点，它能控制的点为比它小的所有点。所以我们可以找到在一个区间最大的那个点，坐标记为 maxmaxmax。然后分治，在 (l,max−1)(l,max-1)(l,max−1) 和 (max+1,r)(max+1,r)(max+1,r) 中找出最大的，他们分别为 maxmaxmax 的左子树和右子树。可以用线段树维护。然后进行类似选课的DP。没了。Code#include<iostream>#include<cstdio>
2020-08-14 21:58:22
108
原创 [洛谷P1983] 车站分级
上个月做完了旅行计划，本来想做这道题的，可最终拖了一个月才A掉原题链接理解题意这题请尽量看懂题目，否则直接GG。题上有一个条件被隐藏了，但它非常重要：途中停靠点等级>途中未停靠点等级那么解决题目的方法就出来了：1. 制造一个图2. 将每一次行驶途中停靠的点向未停靠点连一个边类似于这样（0,1,2,3,4表示停靠点，5,6,7,8,9表示未停靠点）全部弄完后直接上一次拓扑...
2020-01-17 21:31:38
156
原创 售货员的难题
精！神！污！染！洛谷学校OJ这题就是传说中的TSP问题。TSP问题也就是最小哈密顿回路问题在这题中，这里的图为完全图，所以我们不用邻接表，可以用邻接矩阵。先来一种暴力做法，复杂度为Θ(n∗n!)\Theta(n*n!)Θ(n∗n!)#include<iostream>using namespace std;int a[41][41],vis[41],ans=214...
2020-01-17 21:25:51
699
原创 [洛谷 P1546 最短网络 Agri-Net]&最小生成树学习笔记
最小生成树学习笔记最小生成树，图论中一种极其基础的算法。针对此算法，主要有两种解法：PrimΘ(n2)Prim\quad\Theta(n^2)PrimΘ(n2)KruskalΘ(mlogm)Kruskal\quad\Theta(mlogm)KruskalΘ(mlogm)Primprim非常简单，就是直接将离加入点最近的未加入点直接加入。代码：#include<iostrea...
2019-12-20 22:09:22
129
原创 [SSL 1776] 游乐场
毫无难度地水掉了这道题。链接其实这一道题非常水，只需输入后遍历所有的点然后输出就行了。代码#include<cstdio>#include<iostream>using namespace std;int a[500][500],v[500],d[500],n,m,o,q;void dfs(int i){ v[i]=1; o++;q+=d[i]; ...
2019-12-18 17:19:30
101
原创 [SSL 1759]求连通分量
最近要学图论，所以写了一大堆关于图论的博客题意：给出无向图G=(V,E)G=(V,E)G=(V,E)求最大联通分量。其实这道题很水，轻轻松松就A了。给出几种方法：DFS+邻接矩阵#include<cstdio>#include<cstring>#include<iostream>using namespace std;bool a[200...
2019-12-14 16:44:57
112
原创 [洛谷P1173] 旅行计划
老师说过要讲图论，于是我提前将这道题A了。是不是有点快而且闲题意给你一个拓扑图，让你判断从每一个点到其它任意一个点的最长路。N<=100000,M<=200000N<=100000,M<=200000N<=100000,M<=200000洛谷链接首先，这道题不能用邻接矩阵，因为N<=100000N<=100000N<=10000...
2019-12-14 14:13:54
199
原创 [CSP-J 2019]纪念品 题解
洛谷链接考场上想了两个钟没想出来，自闭了。相信是一位掌握DP的同学都看得出来这道题一定是DP，但估计没几个人可以一眼看出来。我绝望地看了眼T4，然后完全绝望……进入正题我们先从一个个点来说。10%这应该是最简单的了，直接输出即可……15%（1）这里，我们只需用到贪心来做。当一段连续上升的数出现后，直接在最高点套现，然后在第二天买入，即可得到最优解。附上代码段int i=1...
2019-12-11 17:31:28
1779
1
原创 洛谷P1457 城堡 The Castle /1104 USACO 2.1 城堡 (foodfill)
题目链接：洛谷学校OJ读题当初看到这道题时，我的内心是奔溃的：什么魔鬼输入？！什么恶心要求？！我 *(数据删除)算了，还是好好做题吧。输入处理通过观察，我们可以知道每一个数都可以这样分解假设某行有一个数111111,我们可以:把它拆成二进制:11= 1 0 1 11/表示南面有墙0/表示东面没有墙1/表示北面有墙1/表示西面有墙所以我们可以设一个布尔类型三维数组a...
2019-12-07 14:38:52
334
2
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人