songhn's blog
CF1262D2 Optimal Subsequences (Hard Version) CF1262D2 Optimal Subsequences (Hard Version)
题意简述:给定一个长度为$n$的序列 给定$m$次询问$k$和$pos$表示:长度为$k$的总值和最大的子序列里的第$pos$位的值是几(假如有多个子序列满足要求字典序最小的一个) 题解:这道题的hard其实就和dp没啥关系 因为我们发现
2019-11-25
CF1262C Messy CF1262C Messy
题意简述:给定一个长度为$n$的括号序列 保证一半左括号一半右括号 每次可以指定一个区间反转 假设进过若干次反转以后 对于括号序列的每一个前缀 一共用$k$个合法(包含序列本身)那么符合题意 求一个长度任意的操作序列(长度小于等于$n$)在
2019-11-25
AtCoder Beginner Contest 145 AtCoder Beginner Contest 145
第一次AtCoder体验 A.Circle开场送温暖 int main() { int r;cin>>r; cout<<r*r<<endl; return 0; } B.Echo直接判断前
2019-11-17
P2312 解方程 P2312 解方程
题意简述:已知方程:$a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$求该方程在$[1,m]$内的正整数解 $(0<n\leq100,m\leq10^6,|a_i|\leq10^{10000})$ 题解:首先看到那么
2019-11-16
CF1239A Ivan the Fool and the Probability Theory CF1239A Ivan the Fool and the Probability Theory
题意简述:给定一个 $n\cdot m$ 的方格图,每个格子可以被染成黑色或白色,且与其相邻的四个格子中至多只有一个与其颜色相同,求方案数。 题解:我们可以一行一行的考虑 首先假如第一行存在连续的两个1 那么后面的状态就全部可以推出 因为
2019-11-15
CF1257C Dominated Subarray CF1257C Dominated Subarray
题意简述:给定一个序列 找出其中最短的连续子段使得子段中只有一个众数(子段长度大于等于2) 题解:首先考虑一下假如有一段连续相同的数字 那么答案就一定是2 即从连续的一段中随便挑连续的两个 那么众数就是这个数 那么接下来只剩下没有连续相同
2019-11-14
tyvj1340 送礼物 tyvj1340 送礼物
题意简述:有$n$个物品和一个容量为$w$的背包 求出背包最多能装多大体积的物品($w\leq 2^{31}-1$,$n\leq 45$) 题解:该题是经典的超大背包问题 对于这样这样$n$很小$v$很大的背包问题我们可以考虑搜索 假如直
2019-11-12
hdu4388 Stone Game II hdu4388 Stone Game II
1.题意简述:一开始有$n$堆石子和两个人 两个人轮流操作 每次可以一堆有$k$个石子的堆拆分成i和i^k两堆(i<k,i^k<k)每个人在一局中还有一次必杀技可以让i^k变成(2*i)^k假如最后不能操作那么那个人就输 问先手
2019-11-01
P1156 垃圾陷阱 P1156 垃圾陷阱
1.题解首先该题是一个线性dp问题 由于贪心的考虑我们每次到当前时间有可以取的垃圾都会直接捡起而不会再过一会儿 所以我们可以把每一个出现时间作为策略点 这样从头开始dp 所以我们首先需要对a数组进行排序 排序以后就可以从第一个垃圾到最后一
2019-10-18
POJ3666 Making the Grade POJ3666 Making the Grade
题意简述:已知一个序列$A$ 找到一个单调不增或者单调不减的序列$B$ 使得$\sum_{i=1}^{n}|A_i-B_i|$最小 题解:这题首先有一个引理 每一个$B_i$都在$A$中出现过 考虑一下简单的证明 设$A’$为$A$
2019-10-05
CF1228C Primes and Multiplication CF1228C Primes and Multiplication
这场CF我网炸了 然后赛后补题 这道题应该算是魔改一下阶乘质因数分解 题意翻译直接搬洛谷的了懒得打 1.题意简述: 2.题解:首先我们可以把$x$质因数分解 然后考虑$x$的因子$p$ 对于每一个$p$ 我们都要求出$g(1,p)\cd
2019-10-01
Comet OJ Contest 8C 符文能量 Comet OJ Contest 8C 符文能量
题目大意:给定一个长度为$n$的二元组序列$(a_i,b_i)$ 对相邻的$i-1$和$i$合并两个二元组的代价为$b_{i-1}\cdot a_i$ 你还可以选择一个区间 使得这个区间的所有二元组变为$(k\cdot a_i,k\cdot
2019-08-27
2 / 8