scoi2009专题

【BZOJ】1026: [SCOI2009]windy数数位DP

传送门：【BZOJ】1026: [SCOI2009]windy数题目分析：数位DP水题。代码如下： #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

BZOJ 1293 [SCOI2009] 生日礼物题解与分析

1293: [SCOI2009]生日礼物 Time Limit: 10 Sec Memory Limit:162 MB Submit: 630 Solved: 326 Description 小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩

1026: [SCOI2009]windy数（数位dp)

1026: [SCOI2009]windy数 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 12141 Solved: 5770 [Submit][Status][Discuss] Description 　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和

P4159 [SCOI2009] 迷路（矩阵快速幂，两点路径为k的方案数）

思路：具体参考https://www.luogu.com.cn/blog/qq-2056188203/mi-lu-scoi2009-ti-xie 简而言之，就是如果权值为1，要求两点之间经过 k k k条边的路径方案数，只要将邻接矩阵进行 k k k次方就好了。本题权重为1~9，我们将每个点拆成10个点，两个点边权就通过拆成的点建边来表示，这样就成了权值为1的邻接矩阵形式了。 #inc

【bzoj1025】【SCOI2009】【游戏】【dp】

Description windy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。如： 1 2 3 4 5 6 对应的关系为 1->2 2->3 3->1 4->5 5->4 6

【SCOI2009】windy数

Description windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ Input 两个整数，A B。 Output 一个整数，表示A~B中有多少个windy数。 Sample Input 1 10 Sample Output 9 Data Constr

【SCOI2009】迷路

Description windy在有向图中迷路了。该有向图有 N 个节点，windy从节点 0 出发，他必须恰好在 T 时刻到达节点 N-1。现在给出该有向图，你能告诉windy总共有多少种不同的路径吗？注意：windy不能在某个节点逗留，且通过某有向边的时间严格为给定的时间。 Input 第一行包含两个整数，N T。接下来有 N 行，每行一个长度为 N 的字符串。第i行第j列为

[SCOI2009]粉刷匠牛客DP入门

0x00 题目来源 [SCOI2009]粉刷匠 0x10 Tag 线性DP、区间DP 0x20 题目描述 windy有 N 条木板需要被粉刷。每条木板被分为 M 个格子。每个格子要被刷成红色’0‘或蓝色’1‘。 windy每次粉刷，只能选择一条木板上一段连续的格子，然后涂上一种颜色。每个格子最多只能被粉刷一次。如果windy只能粉刷 T 次，他最多能正确粉刷多少格子？

[SCOI2009]迷路题解

[SCOI2009]迷路 [SCOI2009]迷路文章目录思考过程题解思考过程这个东西发现距离只有 9 9 9，记得 L c m ( 1 … 9 ) = 2520 \tt Lcm(1 \dots 9) = 2520 Lcm(1…9)=2520 那么直接考虑暴力处理出来，之后对于每个 T T T 进行分开计算即可。显然这个很难写，但是同样是因为距

P4158 [SCOI2009]粉刷匠

Portal. DP。设 f ( i , j ) f(i,j) f(i,j) 表示前 i i i 条木板粉刷 j j j 次能正确粉刷的最大格子数， g ( i , j , k ) g(i,j,k) g(i,j,k) 表示第 i i i 条木板上粉刷 j j j 次涂了前 k k k 个格子能正确粉刷的最大格子数，用前缀和数组记录蓝色格子数（ s u m i , j sum_{i

【SCOI2009】bzoj1026 windy数

Description 　　windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道，在A和B之间，包括A和B，总共有多少个windy数？ Input 　　包含两个整数，A B。 Output 　　一个整数先统计出来f[i][j]表示i位数，首位为j，合法的数的个数。逐位统计的时候，每一位累加与上一位差满足要求的数。

【SCOI2009】bzoj1294 围豆豆

暴力bfs显然不可行，需要判重。虽然状态有无穷多个，但是我们只关心哪些豆子被包围以及目前的步数。为了方便从每个豆子向上偏右引一条射线，记下多边形穿过射线次数的奇偶性，就可以表示豆子被包围的情况。这样，记状态 (x,y,s) (x,y,s)表示当前在点 (x,y) (x,y)，被奇数次穿过的豆子为集合 s s，每走一步枚举豆子进行更新，复杂度O(m2n22dd)O(m^2n^22^dd

BZOJ 1294 [SCOI2009]围豆豆Bean

Description Input 第一行两个整数N和M，为矩阵的边长。第二行一个整数D，为豆子的总个数。第三行包含D个整数V1到VD，分别为每颗豆子的分值。接着N行有一个N×M的字符矩阵来描述游戏矩阵状态，0表示空格，#表示障碍物。而数字1到9分别表示对应编号的豆子。 Output 仅包含一个整数，为最高可能获得的分值。 Sample Input 3 8 3 30