Cruiying

分类

2-sat(1) BSGS(2) dfs(2) dp(63) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) LCA(6) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 分数规划(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 后缀数组(15) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章（共51篇）

CF577B (抽屉原理+01背包)

给出 1个长度为 n 的序列，以及 1 个正整数 m。问这个原序列中是否存在非空子序列，使其元素之和能被 m 整除。把多于n+1个的物体放到n个抽屉里，则至少有一个抽屉里的东西不少于两件。代入本题中我们可以发现，当得到这个序列的n个前缀和%m时，一定会出现两个相同的数，这两个前缀和相减得到的序列和...

dp

2019-07-30

0 702

CF 118D（dp计数好题）

题目大概说有n1个步兵和n2骑兵要排成一排，连续步兵数不能超过k1个，连续骑兵数不能超过k2个，问有几种排列方案。 dp[i][j][x][y]表示已经有i个步兵j个骑兵参与排列且末尾有x个连续步兵或y个连续骑兵的方案数. #include <bits/stdc++.h> using n...

dp

2019-07-29

0 918

CF180E(双指针)

假设你在玩下面这个简单的电脑游戏。屏幕显示了n个排列整齐的立方体。每个立方体被涂上m种颜色中的一种。您可以删除不超过k个数据集(这些数据集不必一个接一个地删除)。之后，其余的***数据集连接在一起(这样间隙就被关闭了)，系统计算分数。你得到的点数等于连续出现的相同颜色方块的最大序列的长度。编写一个程...

dp

2019-07-29

0 426

CF255C (dp求最长交替子序列)

找到一串序列a中的一段最长子序列，子序列满足x,y,x,y,x,y...交替的形式。 dp[i][j] 表示以a[i]为开始a[j]为结尾的最长交替子序列 dp[i][j] = dp[j][k] + 1 (a[i] == a[k] 形成交替) #include <bits/stdc++.h&...

dp

2019-07-28

0 789

CF 766C (dp)

给你一个小写字符串str和26个整数a[i]，是用来限制（字母i所在的字符串不能超过a[i]）输出分割字符串的方案数。输出所有方案中，最少的分割次数。输出所有方案中，最大的子串长度。 dp[i][0] 表示前i个字母正确分割的数量dp[i][1] 表示前i个字母正确分割且数量最少dp[i][1] ...

dp

2019-07-28

0 442

CF1061C Multiplicity (dp)

题意：给定一个数组{an}，问这个数组的所有子序列{bm}中，有多少子序列满足:对于所有的i(1<=i<=m)满足bi是i的倍数，答案对10^9+7取模题解：首先想到二维DP，从i长中找到j长的子序列的方法=dp[i][j] 如果a[i]可以除以j，原式=dp[i-1][j-1]+d...

dp

2019-07-28

0 561

AtCoder D - Digits Parade(dp)

Given is a string SS. Each character in SS is either a digit (0, ..., 9) or ?. Among the integers obtained by replacing each occurrence of ? with a di...

dp

2019-07-28

0 672

CF741B （01背包+并查集）

题目描述：有n个人(1<=n<=1000)。每个人有一个重量wi(1<=wi<=1000)和一个魅力值bi(1<=bi<=10^6)。 n个人之间有m(1<=m<=min(n*(n-1)/2, 10^5))个关系。第i个关系由两个数字xi和yi组成，...

dp

2019-07-27

0 389

CF1051D Bicolorings(状压dp)

给定一个2×n的棋盘，可以对上面的格子黑白染色，求染色后棋盘上的联通块的个数正好为k的染色方案数。用0：表示001：表示112：表示103：表示01dp[i][j][k] 表示第i个位置用j状态是有k个联通块的数量然后枚举当前位置的状态与前一个的状态形成的联通块的数量 #include <bi...

dp

2019-07-27

0 491

CF 279C (区间单峰)

给出个整数，个查询，对于一个查询，对应于子段，需要你判断这个子段是不是单峰的。 b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk 此处的单峰，指的是，开始时是一段单调不减的，然后以一段单调不增结束；同时这两段的长度为零也是可以的。 L[i] 表示...

dp

2019-07-26

0 537