洛谷8.30
「EZEC-3」排列
题目描述
pigstd 有一堆数，他想在这么多数中选出若干个数排成一列，记为 x 1 , x 2 , ⋯ , x p x_{1},x_{2},\cdots,x_{p} x1,x2,⋯,xp（ p p p 为数的个数）。
这一列数合法当且仅当满足以下条件：
- p ≥ 2 p \ge 2 p≥2。
- 令 y i = x i + 1 − x i y_{i} = x_{i + 1} - x_{i} yi=xi+1−xi（特别的， y p = x 1 − x p y_{p}=x_{1}-x_{p} yp=x1−xp），如果把 y 1 y_{1} y1 到 y p y_{p} yp 按 y 1 , y 2 , ⋯ , y p y_1,y_2,\cdots,y_p y1,y2,⋯,yp 的顺序排成一圈，那么每两个相邻的数互为相反数且绝对值都为 k k k。
pigstd 想知道，在所有合法的数列中，所有在这个数列中的数之和最大是多少。
输入格式
第一行两个整数 n , k n,k n,k。
接下来 n n n 行，每行两个整数 a i , b i a_{i},b_{i} ai,bi，表示 pigstd 有 b i b_{i} bi 个 a i a_{i} ai。
不保证 a i a_{i} ai 互不相同，若有 a i a_{i} ai 相同则累加其个数计算。
输出格式
一行一个整数，表示在每一种排列中，所有在这个排列中的数的最大的和。
若没有合法的排列，则只输出 NO \texttt{NO} NO。
样例 #1
样例输入 #1
4 3
1 5
2 4
3 3
0 2
样例输出 #1
6
提示
【样例 1 说明】
当 pigstd 的排列为： 0 , 3 , 0 , 3 0,3,0,3 0,3,0,3 或 3 , 0 , 3 , 0 3,0,3,0 3,0,3,0 时，总和最大，为 6 6 6。
【数据规模与约定】
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 1 0 6 1 \le n \le 10^6 1≤n≤106， 0 ≤ k , a i ≤ 1 0 6 0 \le k,a_{i} \le 10^6 0≤k,ai≤106， 1 ≤ b i ≤ 1 0 6 1 \le b_{i} \le 10^6 1≤bi≤106。
本题采用捆绑测试。
- Subtask 1（5 points）：保证无合法的数列；
- Subtask 2（15 points）： k = 0 k = 0 k=0；
- Subtask 3（5 points）： n = 1 n = 1 n=1；
- Subtask 4（5 points）： n = 2 n = 2 n=2；
- Subtask 5（30 points）： n , k , a i , b i ≤ 1 0 3 n,k,a_i,b_i \le 10^3 n,k,ai,bi≤103；
- Subtask 6（40 points）：无特殊限制。
分析
从一个简单的例子开始分析，对于x1、x2、x3，则
y
1
=
x
2
−
x
1
,
y
2
=
x
3
−
x
2
,
y
3
=
x
1
−
x
3
y_1=x_2-x_1,y_2=x_3-x_2,y_3=x_1-x_3
y1=x2−x1,y2=x3−x2,y3=x1−x3，要使得
y
1
=
−
y
2
y_1=-y_2
y1=−y2，可以发现需要
x
1
=
=
x
3
x1==x3
x1==x3,即每相隔一个元素x的值相同，因此若p为奇数的话，在第一个例子中
p
=
=
3
p==3
p==3，则需要
x
1
=
=
x
3
=
=
x
2
x_1==x_3==x_2
x1==x3==x2，即所有元素都相等，，此时对于
k
=
=
0
k==0
k==0的情况，因此现在我们可以发现这题
k
=
=
0
k==0
k==0很可能需要特判，简单分析一下可以知道
r
e
s
=
m
a
x
(
a
×
c
n
t
[
a
]
)
(
其中
a
为选出来的数
)
res=max(a\times cnt[a])(其中a为选出来的数)
res=max(a×cnt[a])(其中a为选出来的数)；若p为偶数，则只需要
x
1
=
=
x
3
=
=
.
.
.
x
n
−
1
、
x
2
=
=
x
4
=
=
.
.
.
=
=
x
n
x_1==x_3==...x_{n-1}、x_2==x_4==...==x_{n}
x1==x3==...xn−1、x2==x4==...==xn，即选出来的x序列实际只包含两个数，此时
r
e
s
=
m
a
x
(
(
a
+
b
)
×
(
m
i
n
(
c
n
t
[
a
]
,
c
n
t
[
b
]
)
)
(
其中
a
、
b
为选出来的两个数
)
res=max((a+b)\times(min(cnt[a],cnt[b]))(其中a、b为选出来的两个数)
res=max((a+b)×(min(cnt[a],cnt[b]))(其中a、b为选出来的两个数)
代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e6 + 6;
ll cnt[N];
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, k, maxn = 0;
cin >> n >> k;
for(int i = 1; i <= n; i ++ ) {
int a, b;
cin >> a >> b;
maxn = max(maxn, a);
cnt[a] += b;
}
ll res = -1;
if(k == 0) {
for(int i = 0;i <= maxn; i ++ ) {
if(cnt[i] >= 2) {
res = max(res, (ll)i * cnt[i]);
}
}
} else {
for(int i = 0; i <= maxn; i ++ ) {
int j = i + k;
if(j > maxn) break;
if(cnt[i] && cnt[j])
res = max(res, (ll)(i + j) * min(cnt[i], cnt[j]));
}
}
if(res == -1) cout << "NO" << endl;
else cout << res << endl;
return 0;
}
[CQOI2012] 模拟工厂
题目描述
有一个称为“模拟工厂”的游戏是这样的：在时刻 0 0 0，工厂的生产力等于 1 1 1。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加 1 1 1；如果选择生产商品，则下一个时刻你所拥有的商品数量增加 p p p，其中 p p p 是本时刻工厂的生产力。
有 n n n 个订单，可以选择接受或者不接受。第 i i i 个订单 ( t i , g i , m i ) (t_i, g_i, m_i) (ti,gi,mi) 要求在时刻 t i t_i ti 给买家提供 g i g_i gi 个商品，事成之后商品数量减少 g i g_i gi，而收入增加 m i m_i mi 元。如果接受订单 i i i，则必须恰好在时刻 t i t_i ti 交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。
例如，如果一共有两个订单 ( 5 , 1 , 8 ) (5,1,8) (5,1,8) 和 ( 7 , 15 , 3 ) (7,15,3) (7,15,3)，用如下策略是最优的：时刻 0 0 0, 1 1 1, 2 2 2 提高生产力（时刻 3 3 3 的生产力为 4 4 4），然后在时刻 3 3 3， 4 4 4 生产商品，则在时刻 5 5 5 时将拥有 8 8 8 个商品。此时接受第 1 1 1 个订单（还会剩下 7 7 7 个商品），并且在时刻 5 5 5， 6 6 6 继续生产商品，则在时刻 7 7 7 时拥有 7 + 4 + 4 = 15 7+4+4=15 7+4+4=15 个商品，正好满足订单 2 2 2。
输入格式
输入第一行包含一个整数 n n n，即订单数目。以下 n n n 行每行三个整数 t i , g i , m i t_i, g_i, m_i ti,gi,mi。
输出格式
输出仅一行，为最大总收入。输出保证在 32 32 32 位带符号整数范围内。
样例 #1
样例输入 #1
2
5 1 8
7 15 3
样例输出 #1
11
提示
【数据范围】
| 编号 | n ≤ n \le n≤ | t i ≤ t_i \le ti≤ | g i ≤ g_i \le gi≤ | m i ≤ m_i \le mi≤ |
|---|---|---|---|---|
| 1 ∼ 3 1 \sim 3 1∼3 | 5 5 5 | 100 100 100 | 10000 10000 10000 | 10000 10000 10000 |
| 4 ∼ 6 4 \sim 6 4∼6 | 10 10 10 | 100 100 100 | 10000 10000 10000 | 10000 10000 10000 |
| 7 ∼ 10 7 \sim 10 7∼10 | 15 15 15 | 100000 100000 100000 | 1 0 9 10^9 109 | 1 0 9 10^9 109 |
分析
状压+模拟，首先将订单按时间排序，然后用二进制串st表示订单的状态，假设当前拥有have个商品，生产力为make，需要生产need个商品，则在有效时间t内，实际是在求解方程
(
m
a
k
e
+
x
)
×
(
t
−
x
)
=
n
e
e
d
(make+x)\times (t-x)=need
(make+x)×(t−x)=need，化简一下使用求根公式判断是否有解，若无解，则说明不可能满足下一个商品的要求，继续枚举下一种状态，否则更新make、have的值。
代码
#include<iostream>
#include<cmath>
#include<algorithm>
typedef long long ll;
using namespace std;
const int N = 20;
int n;
struct node_ {
ll t, g, m;
friend bool operator < (const node_ a, const node_ b) {
return a.t < b.t;
}
}node[N];
ll res = 0;
ll f(ll make, ll time, ll need) {
ll a = 1;
ll b = make - time;
ll c = need - make * time;
ll delta = b * b - 4 * a * c;
if(delta < 0) return -1;
return floor((-b+sqrt(delta)) / 2 / a);
}
void check(ll st) {
node_ tNode[N];
ll cnt = 0;
ll num = 0;
for(int i = 1; i <= n; i ++ ) {
// cout << i << " ";
if(st & (1 << i - 1)) {
tNode[++ cnt] = node[i];
num += node[i].m;
}
}
// cout << " ";
ll have = 0;
ll make = 1;
for(int i = 1; i <= cnt; i ++ ) {
ll t = tNode[i].t - tNode[i - 1].t;
// cout << "t == " << t << " " << "have == " << have << " " << "make == " << make << " ";
ll sum = 0;
for(int j = i; j <= cnt; j ++ ) {
sum += tNode[j].g;
if(sum > have) {
t = min(t, f(make, tNode[j].t - tNode[i - 1].t, sum - have));
// cout << "t == " << t << endl;
}
}
if(t < 0) return ;
make += t;
have += make * (tNode[i].t - tNode[i - 1].t - t) - tNode[i].g;
}
res = max(res, num);
return ;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> node[i].t >> node[i].g >> node[i].m;
sort(node + 1, node + n + 1);
for(int i = 0; i < (1 << n); i ++ ) {
check(i);
}
cout << res << endl;
return 0;
}