codevs专题

codevs 1028 花店橱窗布置最小费用最大流

花与花瓶连边，容量为1，费用为对应费用，s向花连边，容量为1，费用为0，花瓶向t连边，容量为1，费用为0。这里要求最大费用，把费用设为相反数，结果也取相反数。 #include<iostream>#include<cstring>#include<cstdio>#include<queue>#define inf 1000000000using namespace std;int

codevs 1074食物链并查集

a和b之间有三种关系，a和b同类，a吃b，b吃a，用a+n表示a吃的，a+2*n表示吃a的。与关押犯人一样，但这里要影射出2种虚拟的才足以表示出关系。 #include<cstdio>#include<iostream>using namespace std;int n,k,d,x,y;int fa[200000];int find(int x){return x==fa[x]?

xth 砍树(codevs 1369)

题目描述 Description 在一个凉爽的夏夜，xth 和 rabbit 来到花园里砍树。为啥米要砍树呢？是这样滴，小菜儿的儿子窄森要出生了。Xth这个做伯伯的自然要做点什么。于是他决定带着rabbit 去收集一些木材，给窄森做一个婴儿车……（xth 早就梦想着要天天打菜儿他儿窄森的小 pp，到时候在婴儿车里安装一个电子遥控手臂，轻轻一按，啪啪啪……“乌卡卡——”xth 邪恶滴笑了，

Codevs P1036 商务旅行

Codevs P1036 商务旅行题目描述 Description 某首都城市的商人要经常到各城镇去做生意，他们按自己的路线去做，目的是为了更好的节约时间。假设有N个城镇，首都编号为1，商人从首都出发，其他各城镇之间都有道路连接，任意两个城镇之间如果有直连道路，在他们之间行驶需要花费单位时间。该国公路网络发达，从首都出发能到达任意一个城镇，并且公路网络不会存在环。你的任务是帮助该

数的划分 CODEVS - 1039

http://codevs.cn/problem/1039/ 参考博客https://blog.csdn.net/qq_37321281/article/details/74531143 #include <stdio.h>int main(){int e[201][7];int n,k,i,j;while(scanf("%d%d",&n,&k)!=EOF){for(i=0;i<=n;

SSL 1026 VIJOS 1126 洛谷 1034 CODEVS 1101 矩形覆盖#区间dp#

题目用 k 个矩形覆盖所有点，矩形的边平行于坐标轴。问题是当 n 个点坐标和 k 给出后，使得覆盖所有点的 k 个矩形的面积之和为最小。约定：覆盖一个点的矩形面积为 0；覆盖平行于坐标轴直线上点的矩形面积也为0。各个矩形必须完全分开（边线与顶点也都不能重合）。分析可以用dp，先离散。 f [ i ] [ j ] [ i 1 ] f[i][j][i1] f[i][j][i1]表示覆

#单调队列#洛谷 1090 SSL 1040 VIJOS 1097 CODEVS 1063 合并果子

题目及O（ n l o g 2 n nlog_2n nlog2n）做法分析其实我们也可以用O（n）来做，首先来个桶排。再用一个单调队列存下两个最小值，不断更新。代码 #include <cstdio>#include <cctype>using namespace std;short t[20001],l,r,min[2],n,head; int a[30001],

#离散# VIJOS 1237 CODEVS 2765 隐形的翅膀

题目选出两只最小的翅膀，使长度比接近黄金比例。分析我们可以把每一只翅膀都乘上黄金比例，然后快排找出最接近的。代码 #include <cstdio>#include <cctype>#include <algorithm>#define gs 0.6180339887498949using namespace std;double a[60001]; int n

#乘法逆元，组合计数#洛谷 1313 codevs 1137 jzoj 3027 计算系数

题目给定一个多项式$ (ax + by)^k$ ，请求出多项式展开后 $xnym $项的系数。分析根据二项式定理，有 ( a x + b y ) k = ∑ i = 0 k C k i a i b k − i x i y k − i (ax+by)^k=\sum_{i=0}^kC_k^ia^ib^{k-i}x^iy^{k-i} (ax+by)k=i=0∑kCkiaibk−ixi

#动态规划，多重背包#codevs 1068 洛谷 1541 jzoj 1863 乌龟棋

题目求通过走卡片的步数获得的最大得分（一开始在1，自动加上得分）分析长得挺像背包的，比较简单233 int now=1+i+j*2+k*3+p*4;if (i) f[i][j][k][p]=max(f[i][j][k][p],f[i-1][j][k][p]+a[now]);if (j) f[i][j][k][p]=max(f[i][j][k][p],f[i][j-1][k][

jzoj 1234 洛谷 1203 codevs 1542 坏掉的项链破碎的项链

题目求把圆环拆成链，从一端开始收集同颜色的珠子直到你遇到一个不同的颜色珠子，在另一端做同样的事，能得到的最大的珠子数。分析可以把链扩大3倍，然后纯模拟233 代码 #include <iostream>using namespace std;string a; int n,ans;int max(int a,int b){return (a>b)?a:b;}int

codevs 3943 数学奇才琪露诺

题目对于有趣的数x，x的数位和 k ∗ p ^k*p k∗p+(加号重点) q = x 。 q=x。 q=x。，求在一个区间里有趣的数的个数。分析枚举数位和，我的方法是用C++自带的堆升序排列。代码 #include <cstdio>#include <queue>using namespace std;typedef long long ll;ll k,p,q,

#单调队列，动态规划#洛谷 2627 jzoj 2202 2321（高中）codevs 4654 修剪草坪

题目在n头奶牛里选择若干头，使连续的奶牛不超过k头并让总价值最大。分析这道题正向选择比较难选，所以就想到了n头奶牛都选并去掉奶牛后使总价值最大。用单调队列维护，时间复杂度O（n）代码 #include <cstdio>#include <cctype>using namespace std;typedef long long ll;ll n,k,l,r,q[10

#动态规划#SP703 codevs 2182 1383 CH 5102 Mobile Service 移动服务

题目有三个移动服务员，最初分别在位置1，2，3处。如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。从 p p p到 q q q移动一个员工，需要花费 c ( p , q ) c(p,q) c(p,q)。求最小花费。分析用动态规划，但是普通的动态规划不仅时间超时，空间也无法满足，所以需要

#动态规划，线性动态规划#codevs 2185 CH 5101 LCIS 最长公共上升子序列

题目求两个序列的最长公共上升子序列分析首先，优化的方法 for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (a[i]==b[j])for (int k=0;k<j;k++)if (b[k]<a[i])f[i][j]=max(f[i][j],f[i-1][k]+1); 但是 O ( n 3 ) O(n^3) O(n3)的算法对于 n

#网络流，费用流，SLF优化，SPFA，zkw费用流#jzoj 1586 codevs 1362 洛谷 2604 网络扩容

题目有两个问题，首先求1到 n n n的最大流（不解释了），然后求1到n使最大流扩展 k k k的费用，每扩展一个最大流，扩展一次边的费用分析当然如何做第二个问题，可以重新建一个汇点流量是最大流 + k +k +k，费用为0，并且原来的边再建一次从 u u u到 v v v，费用为该边的费用，流量无限跑一次最大流，then就讲完了代码 #include <cstd

#堆优化dijkstra#洛谷 1828 jzoj 1287 codevs 2038 ssl 1693 香甜的黄油

题目有 n n n个点，求每个点的单源最短路径的最短和分析其实跑 n n n遍 s p f a spfa spfa或 d i j k s t r a dijkstra dijkstra堆优化就行了代码 #include <cstdio>#include <queue>struct node{int y,w,next;}e[2901];int n,m,dis[801]

#zkw费用流，最小费用最大流#洛谷 4012 codevs 1917 ssl 2620 深海机器人问题

题目大意在一个平面直角坐标系中，机器人只能往右和上采集标本，每个格点都有不同的价值，现在若干个机器人从某点出发目的地为某点，问采集到的最大价值分析其实这道题类比于K取方格数，容易建出这样一张图然后跑一遍最大费用最大流就可以了，但是我把费用取反，跑的是最小费用最大流代码 #include <cstdio>#include <deque>#include <cstri

#zkw费用流，最大费用最大流#codevs 1227 洛谷 2045 poj 3422 k取方格数方格取数加强版

题目跑 k k k遍方格取数,问能取到的最大价值分析按照算法竞赛进阶指南，建边应该是拆点后入点连接出点用两条边，一条容量为1,费用为 a i , j a_{i,j} ai,j，另一条容量为 k − 1 k-1 k−1，费用为0，向右向下的有向边容量为 k k k,费用为0，从（ 1 ， 1 ）（1，1）（1，1）入点开始跑到 ( n , n ） (n,n） (n,n）的出点

Codevs P1052 地鼠游戏

地鼠游戏大贪心此题可以用DP解但是贪心也是对的思路在地鼠缩回地里之前都是可以敲掉的可以考虑优先队列时间倒着流逝凡是在时间范围内的地鼠都压进堆里每秒敲的时候就可以取堆头元素保证敲得是价值最高的代码 #include <queue>#include <cstdio>#include <iostream>#i

Codevs 4768 跳石头 NOIP2015 DAY2 T1

4768 跳石头时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 传送门题目描述 Description 一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向

Codevs 1082 线段树练习 3(线段树分块)

1082 线段树练习 3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 大师 Maste 传送门题目描述 Description 给你N个数，有两种操作： 1：给区间[a,b]的所有数增加X 2：询问区间[a,b]的数的和。输入描述 Input Description 第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，每行表示操作的个数

Codevs 1080 线段树练习(线段树树状数组分块CDQ分治)

1080 线段树练习时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 传送门题目描述 Description 一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<

codevs 4511 信息传递(NOIP2015 day1 T2)

4511 信息传递 NOIP2015 day1 T2 时间限制: 1 s 空间限制: 128000 KB 传送门题目描述 Description 有个同学（编号为 1 到）正在玩一个信息传递的游戏。在游戏里每人都有一个固定的信息传递对象，其中，编号为的同学的信息传递对象是编号为的同学。游戏开始时，每人都只知道自己的生日。之后每一轮中，所有人会同时将自己当前所知的生日信息告诉各自的信息

Codevs 2597 团伙(并查集)

2597 团伙时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 传送门题目描述 Description 1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：我朋友的朋友是我的朋友；我敌人的敌人也是我的朋友。两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的

Codevs 1074 食物链 2001年NOI全国竞赛

1074 食物链 2001年NOI全国竞赛时间限制: 3 s 空间限制: 64000 KB 题目等级 : 钻石 Diamond 传送门题目描述 Description 动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。　　现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。　　有人用两