[NOI2016]优秀的拆分 题解
题目地址:洛谷:【P1117】[NOI2016]优秀的拆分 – 洛谷、BZOJ …
May all the beauty be blessed.
题目地址:洛谷:【P2564】[SCOI2009]生日礼物 – 洛谷、BZOJ:Problem 1293. — [SCOI2009]生日礼物
小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。
小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。
有K种颜色的珠子共N个,分别在一长段彩带的不同位置,可能存在多个珠子在同一位置的情况,求最短的子彩带使得彩带上具有所有K种颜色的珠子,长度定义为终止坐标-起始坐标。
输入格式:
第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的位置。
输出格式:
输出应包含一行,为最短彩带长度。
输入样例#1:
6 3 1 5 2 1 7 3 1 3 8
输出样例#1:
3
【样例说明】
有多种方案可选,其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据, N≤10000;
对于80%的数据, N≤800000;
对于100%的数据,1≤N≤1000000,1≤K≤60,0≤Ti<231。
本题可以用一个叫做“双指针”的算法解决。我们将珠子按照它们的坐标排序后,固定这个序列的左端(左指针),寻找一个最近的右端位置(右指针)使得左端到右端之间包含了所有颜色的珠子。由于有左右两个指针,我们把这种算法叫做双指针。具体而言,我们可以用一个cnt数组维护指针之间的区间内每种颜色珠子的数量,如果归0就对种类数-1,如果从0变为非0就对种类数+1。那么我们只需要让左指针左移时减去上一个位置的珠子,然后再寻找右指针的位置,这样维护一通,并且对每一对左右指针求长度更新答案即可。
排序采用STL排序,复杂度O(n \log n),根据上面的描述,双指针算法是O(n)的,因此总复杂度O(n \log n),可以通过本题。
双指针是常用的基础算法,常常能在CF题中见到它。
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
typedef long long LL;
typedef std::pair<int, int> PII;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 1000005;
int n, k, cnt[MAXN];
std::vector<PII> vec;
int main() {
n = readint(); k = readint();
for(int i = 1, ti, pos; i <= k; i++) {
ti = readint();
while(ti--) {
pos = readint();
vec.push_back(PII(pos, i));
}
}
std::sort(vec.begin(), vec.end());
int ans = 1e9, sum = 0;
int r = 0;
for(int l = 0; l < vec.size(); l++) {
while(r < vec.size() && sum < k) {
if(!cnt[vec[r].second]) sum++;
cnt[vec[r].second]++;
r++;
}
if(r >= vec.size() && sum < k) break;
ans = std::min(ans, vec[r - 1].first - vec[l].first);
cnt[vec[l].second]--;
if(!cnt[vec[l].second]) sum--;
}
printf("%d", ans);
return 0;
}
题目地址:洛谷:【P3265】[JLOI2015]装备购买 – 洛谷、BZOJ:Problem 4004. — [JLOI2015]装备购买
脸哥最近在玩一款神奇的游戏,这个游戏里有 n 件装备,每件装备有 m 个属性,用向量zi(aj ,…..,am) 表示 (1 <= i <= n; 1 <= j <= m),每个装备需要花费 ci,现在脸哥想买一些装备,但是脸哥很穷,所以总是盘算着怎样才能花尽量少的钱买尽量多的装备。对于脸哥来说,如果一件装备的属性能用购买的其他装备组合出(也就是说脸哥可以利用手上的这些装备组合出这件装备的效果),那么这件装备就没有买的必要了。
严格的定义是,如果脸哥买了 zi1,…..zip这 p 件装备,那么对于任意待决定的 zh,不存在 b1,….,bp 使得 b1zi1 + … + bpzip = zh(b 是实数),那么脸哥就会买 zh,否则 zh 对脸哥就是无用的了,自然不必购买。
举个例子,z1 =(1, 2, 3);z2 =(3, 4, 5);zh =(2, 3, 4),b1 =1/2,b2 =1/2,就有 b1z1 + b2z2 = zh,那么如果脸哥买了 z1 和 z2 就不会再买 zh 了。
脸哥想要在买下最多数量的装备的情况下花最少的钱,你能帮他算一下吗?
输入格式:
第一行两个数 n, m。接下来 n 行,每行 m 个数,其中第 i 行描述装备 i 的各项属性值。接下来一行 n 个数,其中 ci 表示购买第 i 件装备的花费。
输出格式:
一行两个数,第一个数表示能够购买的最多装备数量,第二个数表示在购买最多数量的装备的情况下的最小花费
输入样例#1:
3 3 1 2 3 3 4 5 2 3 4 1 1 2
输出样例#1:
2 2
如题目中描述,选择装备 1 装备 2,装备 1 装备 3,装备 2 装备 3 均可,但选择装备 1 和装备 2 的花费最小,为 2。
对于 100% 的数据, 1 <= n;m <= 500; 0 <= aj <= 1000。
在异或向量空间中的线性基维护算法的实质是一个高斯消元。对于常规的m维向量,同样也可以用类似的思路来维护。因此这个题对于线性基类问题来说应该算是裸题了。
似乎EPS有点卡精度,因此使用了long double。
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <algorithm>
typedef long long LL;
typedef long double LD;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 505;
const LD EPS = 1e-8;
int n, m;
struct Node {
LD vec[MAXN];
int cost;
inline bool operator<(const Node &rhs) const {
return cost < rhs.cost;
}
} equip[MAXN];
LD mat[MAXN][MAXN];
int main() {
n = readint(); m = readint();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
equip[i].vec[j] = readint();
}
}
for(int i = 1; i <= n; i++) {
equip[i].cost = readint();
}
std::sort(equip + 1, equip + n + 1);
int cnt = 0, sum = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(fabs(equip[i].vec[j]) > EPS) {
if(!mat[j][j]) {
memcpy(mat[j], equip[i].vec, sizeof(LD) * MAXN);
sum += equip[i].cost; cnt++;
break;
} else {
LD t = equip[i].vec[j] / mat[j][j];
for(int k = j; k <= m; k++) {
equip[i].vec[k] -= mat[j][k] * t;
}
}
}
}
}
printf("%d %d", cnt, sum);
return 0;
}
题目地址:洛谷:【P2048】[NOI2010]超级钢琴 – 洛谷、BZOJ:Problem 2006. — [NOI2010]超级钢琴
小Z是一个小有名气的钢琴家,最近C博士送给了小Z一架超级钢琴,小Z希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出n个音符,编号为1至n。第i个音符的美妙度为Ai,其中Ai可正可负。
一个“超级和弦”由若干个编号连续的音符组成,包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的,当且仅当这两个超级和弦所包含的音符集合是相同的。
小Z决定创作一首由k个超级和弦组成的乐曲,为了使得乐曲更加动听,小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。
输入格式:
输入第一行包含四个正整数n, k, L, R。其中n为音符的个数,k为乐曲所包含的超级和弦个数,L和R分别是超级和弦所包含音符个数的下限和上限。
接下来n行,每行包含一个整数Ai,表示按编号从小到大每个音符的美妙度。
输出格式:
输出只有一个整数,表示乐曲美妙度的最大值。
输入样例#1:
4 3 2 3 3 2 -6 8
输出样例#1:
11
共有5种不同的超级和弦:
最优方案为:乐曲由和弦1,和弦3,和弦5组成,美妙度为5 + 2 + 4 = 11。+
所有数据满足:-1000 ≤ Ai ≤ 1000,1 ≤ L ≤ R ≤ n且保证一定存在满足要求的乐曲。
暴力可过的点1~2,我们考虑枚举每个长度在[L, R]范围内的区间,将其和加入一个堆,并使堆的元素数量始终不超过k,以确保不爆空间即可。实测这个方法在开O2的情况下还能过4。复杂度O(n(R-L+1) \log n)。
点3有性质k=1,也就是说只用查最大值,考虑把所有元素开个ST表存起来,对于确定的区间左端点i,查询最大值的区间应当是[i+L-1, i+R-1],只需要在这个区间内做RMQ后,减去[1, i-1]的元素求和即可,这里可以预处理一个前缀和。枚举区间左端点即可,复杂度O(n \log n)。
如果将这个方法应用于求k大,我们考虑这样的一个信息(i, l, r, mx)表示选择区间左端点为i,且查询最大值的区间为[l, r],这个区间中取得最大值的位置是mx,我们先类似点3的做法将所有信息插入堆中,然后从堆顶拿最大值以后将该信息拆分成(i, l, mx-1, newmx1)和(i, mx+1, r, newmx2)两个子信息,RMQ出来newmx1和newmx2,插回堆里,就能达成我们想要的效果。这个算法的复杂度是O(n \log n)。
模拟考的时候只想到了点3的做法,并没想到可以用堆来推广做,感觉到好亏啊QAQ,明明离AC那么近。
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <queue>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF
: *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 500005;
LL n, k, L, R, a[MAXN];
LL mx[MAXN][20], mxd[MAXN][20], pow2[MAXN];
struct Node {
LL val;
int beg, l, r, mx;
inline bool operator<(const Node &rhs) const {
return val < rhs.val;
}
};
std::priority_queue<Node> pq;
inline int querymx(int l, int r) {
int k = floor(log(r - l + 1) / log(2));
if(mx[l][k] > mx[r - pow2[k] + 1][k]) {
return mxd[l][k];
} else {
return mxd[r - pow2[k] + 1][k];
}
}
int main() {
n = readint(); k = readint(); L = readint(); R = readint();
for(int i = 1; i <= n; i++) {
a[i] = readint() + a[i - 1];
}
for(int i = 1; i <= n; i++) {
mx[i][0] = a[i];
mxd[i][0] = i;
}
pow2[0] = 1;
for(int i = 1; i <= 20; i++) {
pow2[i] = pow2[i - 1] << 1;
}
for(int i = 1; i <= 20; i++) {
for(int j = 1; j + pow2[i] - 1 <= n; j++) {
if(mx[j][i - 1] > mx[j + pow2[i - 1]][i - 1]) {
mx[j][i] = mx[j][i - 1];
mxd[j][i] = mxd[j][i - 1];
} else {
mx[j][i] = mx[j + pow2[i - 1]][i - 1];
mxd[j][i] = mxd[j + pow2[i - 1]][i - 1];
}
}
}
for(int i = 1; i + L - 1 <= n; i++) {
int l = i + L - 1, r = std::min(i + R - 1, n);
pq.push(Node {a[querymx(l, r)] - a[i - 1], i, l, r, querymx(l, r)});
}
LL ans = 0;
while(k--) {
Node t = pq.top(); pq.pop();
ans += t.val;
if(t.l == t.r) continue;
if(t.l != t.mx) pq.push(Node {a[querymx(t.l, t.mx - 1)] - a[t.beg - 1],
t.beg, t.l, t.mx - 1, querymx(t.l, t.mx - 1)});
if(t.r != t.mx) pq.push(Node {a[querymx(t.mx + 1, t.r)] - a[t.beg - 1],
t.beg, t.mx + 1, t.r, querymx(t.mx + 1, t.r)});
}
printf("%lld", ans);
return 0;
}