洛谷8.30

「EZEC-3」排列

题目描述

pigstd 有一堆数，他想在这么多数中选出若干个数排成一列，记为 $x_1,x_2,\cdots ,x_p$（$p$ 为数的个数）。

这一列数合法当且仅当满足以下条件：

• $p\ge 2$。
• 令 $y_i=x_{i+1}-x_i$（特别的，$y_p=x_1-x_p$），如果把 $y_1$ 到 $y_p$ 按 $y_1,y_2,\cdots ,y_p$ 的顺序排成一圈，那么每两个相邻的数互为相反数且绝对值都为 $k$。

pigstd 想知道，在所有合法的数列中，所有在这个数列中的数之和最大是多少。

输入格式

第一行两个整数 $n,k$。

接下来 $n$ 行，每行两个整数 $a_i,b_i$，表示 pigstd 有 $b_i$ 个 $a_i$。

不保证 $a_i$ 互不相同，若有 $a_i$ 相同则累加其个数计算。

输出格式

一行一个整数，表示在每一种排列中，所有在这个排列中的数的最大的和。

若没有合法的排列，则只输出 $\text{NO}$。

样例 #1

样例输入 #1

4 3 
1 5
2 4
3 3
0 2

样例输出 #1

6

提示

【样例 1 说明】

当 pigstd 的排列为：$0,3,0,3$ 或 $3,0,3,0$ 时，总和最大，为 $6$。

【数据规模与约定】

对于 $100\%$ 的数据，$1\le n\le 10^6$，$0\le k,a_i\le 10^6$，$1\le b_i\le 10^6$。

本题采用捆绑测试。

• Subtask 1（5 points）：保证无合法的数列；
• Subtask 2（15 points）：$k=0$；
• Subtask 3（5 points）：$n=1$；
• Subtask 4（5 points）：$n=2$；
• Subtask 5（30 points）：$n,k,a_i,b_i\le 10^3$；
• 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=-y_2$，可以发现需要$x1==x3$,即每相隔一个元素x的值相同，因此若p为奇数的话，在第一个例子中$p==3$，则需要$x_1==x_3==x_2$，即所有元素都相等，，此时对于$k==0$的情况，因此现在我们可以发现这题$k==0$很可能需要特判，简单分析一下可以知道$res=max(a\times cnt[a])(其中a为选出来的数)$；若p为偶数，则只需要$x_1==x_3==...x_{n-1}、x_2==x_4==...==x_n$，即选出来的x序列实际只包含两个数，此时$res=max((a+b)\times (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$，工厂的生产力等于 $1$。在每个时刻，你可以提高生产力或者生产商品。如果选择提高生产力，在下一个时刻时工厂的生产力加 $1$；如果选择生产商品，则下一个时刻你所拥有的商品数量增加 $p$，其中 $p$ 是本时刻工厂的生产力。

有 $n$ 个订单，可以选择接受或者不接受。第 $i$ 个订单 $(t_i,g_i,m_i)$ 要求在时刻 $t_i$ 给买家提供 $g_i$ 个商品，事成之后商品数量减少 $g_i$，而收入增加 $m_i$ 元。如果接受订单 $i$，则必须恰好在时刻 $t_i$ 交易，不能早也不能晚。同一时刻可以接受多个订单，但每个订单只能被接受一次。要求最后的总收入最大。

例如，如果一共有两个订单 $(5,1,8)$ 和 $(7,15,3)$，用如下策略是最优的：时刻 $0$, $1$, $2$ 提高生产力（时刻 $3$ 的生产力为 $4$），然后在时刻 $3$，$4$ 生产商品，则在时刻 $5$ 时将拥有 $8$ 个商品。此时接受第 $1$ 个订单（还会剩下 $7$ 个商品），并且在时刻 $5$，$6$ 继续生产商品，则在时刻 $7$ 时拥有 $7+4+4=15$ 个商品，正好满足订单 $2$。

输入格式

输入第一行包含一个整数 $n$，即订单数目。以下 $n$ 行每行三个整数 $t_i,g_i,m_i$。

输出格式

输出仅一行，为最大总收入。输出保证在 $32$ 位带符号整数范围内。

样例 #1

样例输入 #1

2
5 1 8
7 15 3

样例输出 #1

11

提示

【数据范围】

分析

状压+模拟，首先将订单按时间排序，然后用二进制串st表示订单的状态，假设当前拥有have个商品，生产力为make，需要生产need个商品，则在有效时间t内，实际是在求解方程$(make+x)\times (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;
}