【Vijos P1007】绕钉子的长绳子 c++题解
</pre><h1><strong>背景</strong></h1>平面上有N个圆柱形的大钉子，半径都为R,所有钉子组成一个凸多边形。<p>现在你要用一条绳子把这些钉子围起来，绳子直径忽略不计。</p><p&g...
vijos1053 用spfa判断是否存在负环
MARK 用spfa判断是否存在负环判断是否存在负环的方法有很多，其中用spfa判断的方法是：如果存在一个点入栈两次，那么就存在负环。细节想想确实是这样，按理来说是不存在入栈两次的如果边权值为正的话这个算法是O(N*M)还有一种方法是直接用bellman-ford，虽说spfa也就是bellman-...
[vijos1892]树上的最大匹配（树形DP）
题目：https://vijos.org/p/1892分析：（100分其实用到各种c++优化，没什么实际意义，所以弄70就可以了）题目很简单，很容易想出用树形DP，但是求方案数的时候，满满都是细节……，本渣考试时候就跪了……只能膜拜神犇代码……#include<cstdio>#inclu...
Vijos1605 NOIP2008 提高组T4 双栈排序 BFS
欢迎访问~原文出处——博客园-zhouzhendong去博客园看该题解题目传送门-Vijos1605题意概括有1个1~n的排列，有2个栈，现在通过以下操作，使得出栈序列有序。操作a当前元素入栈<S1>操作b弹出S1栈顶元素操作c当前元素入栈<S2>操作d弹出S2栈顶元素如果无...
Vijos1386 IOI2007 矿工配餐 动态规划
感觉早些年IOI的题都不难啊，也就NOIp难度……现在貌似变难了状态用dp[n][a1][b1][a2][b2]表示n表示处理到前n个餐车第一组矿工得到的最近一种食物用a1表示，a1的上一种食物用b1表示，第二组矿工的用a2和b2表示a和b的取值范围为[0,3]，0表示没有食物，1~3分别表示三种食...
Vijos 1404 遭遇战 - 动态规划 - 线段树 - 最短路 - 堆
背景你知道吗，SQClass的人都很喜欢打CS。（不知道CS是什么的人不用参加这次比赛）。描述今天，他们在打一张叫DUSTII的地图，万恶的*要炸掉藏在A区的SQC论坛服务器！我们SQC的人誓死不屈，即将于*展开激战，准备让一个人守着A区，这样*就不能炸掉服务器了。（一个人就能守住...
Vijos1523 NOI2002 贪吃的九头龙 树形dp
思路不算很难，但细节处理很麻烦前面建图、多叉转二叉，以及确定dp处理序列的过程都是套路，dp的状态转移过程以注释的形式阐述#include<cstdio>#include<cstring>#include<algorithm>#include<queue&g...
Vijos P1196吃糖果游戏[组合游戏]
描述Matrix67和Shadow正在做一个小游戏。桌子上放着两堆糖果，Matrix67和Shadow轮流对这些糖果进行操作。在每一次操作中，操作者需要吃掉其中一堆糖果，并且把另一堆糖果分成两堆（可以不相等）留给对方操作。游戏如此进行下去，糖果数会越来越少，最后必将出现这样一种情况：某人吃掉一堆糖果...
NOIP 车站分级 (luogu 1983 & codevs 3294 & vijos 1851) - 拓扑排序 - bitset
描述一条单向的铁路线上,依次有编号为1,2,...,n的n个火车站。每个火车站都有一个级别,最低为1级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站x,则始发站、终点站之间所有级别大于等于火车站x的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)...
Vijos P1459 车展 treap求任意区间中位数
描述遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：L1R1L2R2…LmRm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri...
Vijos P1448 校门外的树【多解，线段树，树状数组，括号序列法+暴力优化】
校门外的树描述校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：K=1，K=1，读入l、r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同K=2，读入l,r表示询问l~r之...
vijos & codevs 能量项链 - 动态规划
描述在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能...
【动态规划】Vijos P1218 数字游戏（NOIP2003普及组）
题目链接：https://vijos.org/p/1218题目大意：一个N个数的环，分成M块，块内的数求和%10，最后每块地值累乘，求最大和最小。n（1≤n≤50）和m（1≤m≤9）太小了可以随便搞。题目思路：【动态规划】区间DP。环形DP。断环为链，在后面补一段N，当链做。f[i][j]表示前I个...
【vijos】1750 建房子（线段树套线段树+前缀和）
https://vijos.org/p/1750是不是我想复杂了。。。。自己yy了个二维线段树，然后愉快的敲打。但是wa了两法。。。。。。。sad原因是在处理第二维的更新出现了个小问题，sad。voidpushup1(intx){for1(i,1,mm<<2)mn[x][i]=min(m...
Vijos 1120 花生采摘
和“过河”一样，在很久以前我也曾经尝试过做这道题，可无奈当时没有看清题目。题目上说要先找最大的，然后次之。当时纠结了好久，可惜没做出来。但是现在就很好做了，只需要用结构体把每一个花生植株记录下来，sort从大到小排序。然后枚举花生，每次枚举判断一次就好了。但是！！如果我们把题目改一下。不是先找最大的...
Vijos1006P1006晴天小猪历险记之Hill[最短路]
P1006晴天小猪历险记之HillAccepted标签：晴天小猪历险记[显示标签] 背景在很久很久以前，有一个动物村庄，那里是猪的乐园（^_^），村民们勤劳、勇敢、善良、团结……不过有一天，最小的小小猪生病了，而这种病是极其罕见的，因此大家都没有储存这种药物。所以晴天小猪自告奋勇，要去采取这种药草...
vijos1059题解
题目：XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。小XC想把自己垒的城堡送给幼儿园里漂亮的...
Vijos 1011 清帝之惑之顺治 记忆录式的动态规划（记忆化搜索）
背景顺治帝福临，是清朝入关后的第一位皇帝。他是皇太极的第九子，生于崇德三年（1638）崇德八年八月二ten+six日在沈阳即位，改元顺治，在位18年。卒于顺治十八年（1661），终24岁。顺治即位后，由叔父多尔衮辅政。顺治七年，多尔衮出塞射猎，死于塞外。14岁的福临提前亲政。顺治帝天资聪颖，读书勤奋...
Vijos1459 车展 (数学）
描述遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：L1R1L2R2…LmRm单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri...
2016vijos 1-1 兔子的字符串（后缀数组 + 二分 + 哈希）
题意：给出一个字符串，至多将其划分为n部分，每一部分取出字典序最大的子串ci，最小化最大的ci先看一个简化版的问题：给一个串s，再给一个s的子串t，问能否通过将串划分为k个部分，使t成为划分后的s的字典序最大子串 对于这个问题，从串s的最后面开始，一个字符一个字符的向前推如果当前[l,r]字典序比t...