zqy1018_

分类

题解(31)

/ 注册

全部文章（共31篇）

NC15034

题意一个的方格，有的地方能放人，有的不能。人不能上下左右相邻放置。问放置方案总数。题解看到这么小就知道是状压 DP。以表示行的状态为例，设为前行处理完并且第行的状态为时的方案数目。那么只需要以行编号为阶段，内部枚举本行状态和上一行状态进行转移即可。时间复杂度为。 ...

2020-06-07

0 605

NC21228 货币系统

题目大意给定长为的序列，设。现在希望找到一个尽可能短的，设长为的序列使得。求。题解大概可以猜到是的子集。那么我们考虑一开始令为空，然后不断往中加入的元素，且维持尽量小。那么加入的顺序必然是从小到大。当中已有元素可以拼出时就不加入，否则加入...

2020-06-02

0 443

NC19913 [CQOI2009]中位数图

题目大意给定一个排列和，在该排列中。求该排列的长为奇数且以为中位数的子段个数。题解考虑将排列映射成另一个序列，某一位置上的数为那么映射后这一位置上的数变为。那么必然映射后的序列会有一个。问题转化为求新生成的序列中，包含这个在内且子段和为的子段个数。这个可以用前缀和比较...

2020-05-28

0 615

NC53683 「火」皇家烈焰

题目大意略。题解由于每一个位置上的描述会涉及当前状态及相邻状态，用表示**满足前个字符的要求**，且当前位置状态为，后一个位置状态为时的方案数目。则转移方程不难写出。初始状态为，答案为。理论上只刻画当前状态和此前状态似乎也可以，但是讨论就很麻烦。 #include <...

2020-05-14

0 472

牛客练习赛 63 C

题意有个数。时刻开始时第个数自增，时刻结束时可以选中一个数让其自增或者自减，也可以什么都不做。求可能的最小时刻，使得时刻结束后所有数相等。题解可以转化为对每一个位置求其为结束位置时可能的最小时刻。则。到位置之前会跑若干轮，设轮数最小为。则。设数列为。...

2020-05-08

0 609

NC20273 [SCOI2009]粉刷匠

题意个长为的 01 序列，可以涂色次。一次涂色涂一个序列的某一段（连续），获得的分数为这一段中 0 或者 1 的个数。一个位置不能重复涂。求最大分数。题解对每一序列暴力 DP 即可，可以算出每一序列涂次的答案。于是可以转化为一个背包问题。时间复杂度为。 #include <...

2020-05-07

0 646

NC14301 K-th Number

题目大意给定长为的序列，求其所有长度的子区间的第大数，所构成多重集的第大数。题解二分。现判定。问题转化为求第大数的子区间个数，若其则判定失败，否则判定成功。如果将原始序列转化为一个 01 序列，某位置上为表示原始序列上这个位置的数，否则为，那么区间个数...

2020-04-28

0 537

NC14583 糖糖别胡说

题目大意略。题解容易想到按秒处理。发现前个能力值加一可以转化为后面个能力值减一。于是维护到当前时间为止，当前位置及后面位置能力值被削减的量。之后就是简单的用两个堆处理一下即可。 #include <bits/stdc++.h> #define INF 2000000000...

2020-04-27

0 672

NC23049 华华给月月准备礼物

题目描述略。题解二分长度即可。 #include <bits/stdc++.h> #define INF 2000000000 using namespace std; typedef long long ll; int read(){ int f = 1, x = 0; ...

2020-04-22

0 484

NC14731 逆序对

题目大意求所有长的 01 序列的逆序对数之和。题解一种方法是考虑所有对，其中。这必然产生一个逆序对。对于其他位置则没有要求，因此这个对的贡献为。总共有种这样的对，因此答案为。另一种方式是 DP。取为长为时的答案，则。这似乎是一个可以求解的递归式，取，那么可以解出...

2020-04-22

0 528