梦熊 NOIP第一场题解

P11267 【MX-S5-T1】王国边缘

原题链接

这道题做的时候看出来了是基环树，但没想到倍增，用特殊性质过了$20pts$，该说不说，梦熊的题确实很难。

老样子，简化题意：

给定一个长度为 n 的 $01$字符串 $T=S\infty 。$
一个人在 $T$ 上移动。他的一次移动为：设当前下标为 $x$，则跳
到 $[x+1,x+m]$ 中最后一个为 $1$ 的位置，如果区间中不存在 $1$则移动至 $x+1$。有 q 次询问，每次询问给定 $x,y$，求从 $x$ 开始移动 $y$ 次后的下标对 $10^9+7$ 取模的值。

分析思路

先考虑对于
$1\sim n$中的每个点往后跳一次会跳多少距离。

那么我们来想一下，为什么我们只需要考虑$1\sim n$的点，而不需要找别的距离。

我们能发现，由于字符串是无限循环的，所以1对于位置模上$n$的结果相同时，那么往后跳的距离也是相同的。

我们可以先将字符串断成环成链倍长后做前缀和来处理$l\sim r$中的$1$的数量。

然后很容易想出二分得出往后跳的距离。

然后我们就可以求出对于每个点$i$往后可以跳跃的距离。

然后问题询问的是往后跳$k$次的最终位置。

经典的倍增，但我就是没看出来，寄了。

$code$

T2 P11268 【MX-S5-T2】买东西题

原题链接

这道题本来想打特殊性质的，感觉生活应用题都还好想一点，但还是打寄了，哎。(っ °Д °;)っ

简化题意：

你要买$n$个物品，第 $i$个物品原价 $a_i$，折扣价 $b_i$。
你还有 $m$ 个优惠券，第 $i$ 个优惠券形如原原原价价价满 $w_i$ 减 $v_i$。
对于第 $i$ 个物品，你可以选择以下三种购买方式之一：

1. 使用原价 $a_i$ 购买。
2. 使用折扣价 $b_i$ 购买。
3. 选择一个优惠券 $j$，要求满足 $a_i\ge w_i$，使用优惠券 $j$，以 $a_i-v_j$ 的价格购买。

注意每个优惠券 $j$只能被最多一个 $i$使用。
求购买所有物品最少用钱。

解题思路：

可以这样理解：$a$元的物品有$b$元的折扣，就相当于$a$元的物品有一张$a-b$的优惠券。
因为一张优惠券是满 $w$元才可以用，所以可以用的物品在价格$a$上是一段区间$[a,\inf ]$。

有一个很朴素的想法是，将每一个物品最多能省多少钱先弄出来，然后用优惠券想办法把省的最小的钱换成优惠券。

先将物品和优惠券按满多少可以有优惠排序，再枚举优惠券，最后就是按照上面说的逐步加进去就好了。

想要快速求出最小值可以用优先队列，如果到最后还用不到优惠券的记得把打得折加进去。

时间复杂度还是很优的，仅要$O(nlogn)$

$code$

#include<bits/stdc++.h>
#define int long long
#define maxn 1000050
#define gll greater<int>
#define vll vector<int>
using namespace std;
inline int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
int n, m;
struct node {
int x, y;
} a[maxn], b[maxn];
bool cmp(node a, node b) {
//不能写成下面的形式，会爆范围
//if(a.x==a.y) return a.y>b.y;
//else return a.x>b.x;
return a.x == b.x ? a.y > b.y : a.x > b.x;
}
int res = 0;
priority_queue<int, vll, gll > q;
signed main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
int x, y;
x = read();
y = read();
a[i].x = x, a[i].y = x - y;
res += a[i].x;
}
for (int i = 1; i <= m; i++) {
b[i].x = read(), b[i].y = read();
}
int i = 1;
sort(a + 1, a + n + 1, cmp);
sort(b + 1, b + m + 1, cmp);
for (int j = 1; j <= m; j++) {
while (i <= n && a[i].x >= b[j].x) {
q.push(a[i].y);
i++;
}
if (q.size() && q.top() < b[j].y) {
q.pop();
q.push(b[j].y);
}
}
while (i <= n) {
q.push(a[i].y);
i++;
}
while (q.size()){
res -= q.top();
q.pop();
}
cout << res;
return 0;
}

T3 P11269 【MX-S5-T3】IMAWANOKIWA (Construction ver.)

原题链接

题目太复杂，表示读懂稍许困难。

简化题意：

给你一个初始长度为 $n$，只包含 $0,1,2$ 的序列 $a_1\sim n$，你每次可以选择两个相邻的数 $p,q$，删去它们，并在原位置插入
$popc(p+q)。$其中，$popc(x)$ 表示 $x$在二进制表示下 $1$ 的个数。

显然每次操作后序列长度都会减少 $1$，所以执行 $n-1$ 次操作
后，这个序列会恰好剩下一个数。请你最小化剩下的这个数，并
给出字典序最小的操作位置序列。

题目思路：

T4

简化题意：

有 $n+m$ 个括号序列，分别是 $S1,S2,S3,...,Sn$ 和
$T1,T2,T3,...,Tm。$

对一个括号序列 $A，f(A)$为满足以下条件的 $(i,j)$ 对数：
$1.i\in [1,n]，j\in [1,m];$
$2.Si$ 是 $A$ 的前缀且 $Tj$ 是 $A$ 的后缀。

求所有长度为 $k$ 的合法括号序列 $S，f(S)$ 的和。答案对
$10^9+7$ 取模。
保证 k 为偶数。
$$$$$$$$$$$$$$$$$$$$$$$$$$$$

原文地址：https://blog.csdn.net/xiebohang/article/details/143650362

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！