BZOJ1026: [SCOI2009]windy数[数位DP]
1026: [SCOI2009]windy数 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 6346 Solved: 2831[Submit][Status][Discuss] Description windy定义了一种windy数。不...
[Bzoj1026][SCOI2009]windy数(数位dp)
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1026 比较明显的数位dp，dp[pos][num]表示pos位和上一位数差为num的个数。 初始将num设为-2，然后记忆化开始搜 1 #include<bits/stdc++...
[BZOJ1026][SCOI2009]windy数（数位dp）
题目描述 传送门 题解 状态：f(i,j)表示i位数，第i位是j，每位相差至少为2的数的个数 转移： if (Abs(j,k)>=2) f[i][j]+=f[i-1][k]; 注意：这道题处理前导0的情况比较吃屎，这里的转移方程是不包括前导0的情况，我的处理方法是在求解的时候单独...
[BZOJ1026]SCOI2009 windy数|数位DP
第一次见数位DP，看完题解才会做，f[i][j]表示最高有i位，第i位是j的个数，然后枚举0-9转移状态就行了。。计数的时候要考虑全面。。 #include<iostream>#include<cstdio>#include<cstdlib>#include&l...
【BZOJ1026】【SCOI2009】windy数 数位DP
链接： #include <stdio.h>int main(){ puts("转载请注明出处[辗转山河弋流歌 by 空灰冰魂]谢谢"); puts("网址：blog.csdn.net/vmurder/article/details/46446473");} 题解： ...
[bzoj1026][SCOI2009]windy数_数位dp
windy数 bzoj-1026 题目大意：求一段区间中的windy数个数。 注释：如果一个数任意相邻两位的差的绝对值都不小于2，这个数就是windy数，没有前导0。$区间边界<=2\cdot 10^9$。 想法：数位dp裸题，何为数位dp? 数位dp的意思就是我们交换一种dp的方式。通过数位...
BZOJ3323: [Scoi2013]多项式的运算
3323: [Scoi2013]多项式的运算Time Limit: 12 Sec Memory Limit: 64 MBSubmit: 128 Solved: 33[Submit][Status]Description某天，mzry1992 一边思考着一个项目问题一边在高速公路上骑着摩托车。一个...
BZOJ 1083: [SCOI2005]繁忙的都市 kruskal
1083: [SCOI2005]繁忙的都市题目连接：http://www.lydsy.com/JudgeOnline/problem.php?id=1083Description城市C是一个非常繁忙的大都市，城市中的道路十分的拥挤，于是市长决定对其中的道路进行改造。城市C的道路是这样分布的：城市中有...
BZOJ4570: [Scoi2016]妖怪
题目传送门4570: [Scoi2016]妖怪Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 491 Solved: 125[Submit][Status][Discuss]Description邱老师是妖怪爱好者，他有n只妖怪，每只妖怪有攻击力atk...
BZOJ1082: [SCOI2005]栅栏 题解
题目大意：有一些木材，可以没有浪费地将一根木材分成几块木板（比如长度为10的木板可以切成长度为8和2的两块木板）。现在你希望得到一些长度的木板，问通过分割木材最多能得到几块想要的木板。思路：首先，长度短的木板一定比长度长的木板容易得到，因此若要得到最多的木板，它们必定是所有木板中最短的——可以对木板...
bzoj 1070 [SCOI2007]修车（最小费用最大流）
1070: [SCOI2007]修车Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 3515 Solved: 1411[Submit][Status][Discuss]Description同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共...
BZOJ_2754__[SCOI2012]_喵星球上的点名_(暴力+后缀数组)
描述http://www.lydsy.com/JudgeOnline/problem.php?id=2754给出n个姓名串和m个点名串.求每个点名串在多少人的姓名中出现过(在名中出现或在姓中出现,不能跨越),以及最后每个人被点到多少次.分析这种解法是用后缀数组优化一下暴力,(优化了吗?)复杂度并不能...
BZOJ3325 : [Scoi2013]密码
从以每一位为中心的回文串长度可以用Manacher倒推出$O(n)$对相等和不等关系。将相等的用并查集维护，不等的连边。然后输出方案时若还没被染过色，则求一个mex。#include<cstdio>#define N 200010int n,m,i,x,r,p,f[N],g[N],fa[...
SCOI2014 方伯伯的OJ onlinejudge
终于用自己的方法水过去了。本地测慢的一组要三四秒，一共要十几秒，BZOJ貌似一共只让跑6s，于是就还T着的。一开始没看n<=1e8，想的直接splay+map（splay维护名次，map维护对应标号的节点所在位置）然后写完看到n的范围 就傻了= =百度了一下 splay里面的点要包含一段区间想...
P1896 [SCOI2005]互不侵犯King
题目描述在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。输入输出格式输入格式：只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）输出格式：...
【BZOJ4443】[Scoi2015]小凸玩矩阵 二分+二分图最大匹配
【BZOJ4443】[Scoi2015]小凸玩矩阵Description小凸和小方是好朋友，小方给小凸一个N*M（N<=M)的矩阵A,要求小秃从其中选出N个数，其中任意两个数字不能在同一行或同一列，现小凸想知道选出来的N个数中第K大的数字的最小值是多少。Input第一行给出三个整数N,M,K接...
POJ 2711 Leapin' Lizards / HDU 2732 Leapin' Lizards / BZOJ 1066 [SCOI2007]蜥蜴（网络流，最大流）
POJ 2711 Leapin' Lizards / HDU 2732 Leapin' Lizards / BZOJ 1066 [SCOI2007]蜥蜴（网络流，最大流）DescriptionYour platoon of wandering lizards has entered a strang...
BZOJ 1066 [SCOI2007]蜥蜴（最大流）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1066【题目大意】在一个r行c列的网格地图中有一些高度不同的石柱，一些石柱上站着一些蜥蜴， 你的任务是让尽量多的蜥蜴逃到边界外。 每行每列中相邻石柱的距离为1， 蜥蜴的跳跃距离...
bzoj 1066: [SCOI2007] 蜥蜴
这道题还是挺好想的，但我一开始还是想错了……把每个石柱拆成两个点，一个入度，一个出度，两个点连一条容量为高度的边，这样就可以限制从此石柱上经过的蜥蜴的数量。关于蜥蜴是否单独成点，我是单独当成了一个点，貌似做麻烦了，可以直接源点连石柱，但那样我想会不会造成一些问题，貌似也没有。虽然很水，但还是调了很久...
bzoj 1066 : [SCOI2007]蜥蜴 网络流
题目链接给一个n*m的图， 里面每一个点代表一个石柱， 石柱有一个高度。 初始时有些石柱上面有蜥蜴， 蜥蜴可以跳到距离他曼哈顿距离小于等于d的任意一个石柱上，跳完后， 他原来所在的石柱高度会减一， 如果高度变为0， 那么石柱消失， 无法在跳到这个位置上， 跳到的那个石柱高度不会发生改变， 同一时刻一...