板刷计划:ARC073

前言：ATCODER的题是真的硬阿。思维量大…虐杀我这种无智商选手。

A.模拟，略.

---

B.暴力枚举

题目大意:

给你一个容量为w($w\le 1e9$)的背包.现在有n($n\le 100$)个物品，每个物品有体积 $w_i$ 和 价值 $v_i(w_i,v_i\le 1e9)$.现在要让你最大化背包价值. 体积$w_i\in [w_1,w_1+3]$

题目思路:

一个NPC问题。但是给定了体积的值域范围。不难想到对物品按体积大小分成4类再按价值从大到小排序.之后直接枚举每种体积的物品选多少个.跑个dfs即可。这样就包含了所有可能情况.

复杂度: $O((\frac{n}{4}{)}^4)$

---

C.究极思维,贪心.

题目大意:

给你n($n\le 1e5$)个二元组$(x_i,y_i)$。现在有两个集合A,B.你需要将所有二元组的其中一个放入集合A或B里。那么另外一个就会放入到另外一个集合里去。现在让你最小化下式: $$(ma{x}_A-mi{n}_A)\ast (ma{x}_B-mi{n}_B)$$

题目思路:

方法一 ：正解

不难发现,二元组的最小值MI以及最大值MX一定存在于A,B集合中的一个。即一定会在上式中出现.

那么根据他们出现的情况讨论一下:

1.当 MI,MX 一个属于A，一个属于B.(具体是哪个不重要，因为对称)。假设:$MI\in A，MX\in B$

很显然,现在我们的策略就是：将每一个二元组中 较小的给A集合。 较大的给B集合.这样一定是最优的。

注：当时到这里我就卡住了，无法继续往下推了。。

2.当 MI,MX 同时属于A/B(具体是哪个不重要，因为对称)。假设:$MI,MX\in A$

由于 $(ma{x}_A-mi{n}_A)$已经确定，现在我们要做的事情就是最小化$(ma{x}_B-mi{n}_B)$.

这里的思路是:枚举$mi{n}_B$. 假设最优解时$mi{n}_B=x_i$,那么那些 【二元组较小值 小于 $x_i$】的二元组的较大值y要给B集合.

显然对x（$x<y$）从小到大排序,然后从小到大枚举x以及其后缀x就可以。为什么后缀全要选，因为我们人为规定了$x<y$.所以后缀二元组中我们一定要选x.至于x的前缀二元组一定要选y，是因为必须要选才能满足$mi{n}_B=x_i$

这里有个很简单的实现方式，用multiset,然后算完情况1后对二元组排序。直接模拟交换二元组即可。

AC代码:

#include<bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define mp make_pair const int maxn = 2e5 + 5; const int mod = 1e9 + 7; pii a[maxn]; multiset<ll> A , B; int main() { ios::sync_with_stdio(false); int n; cin >> n; for (int i = 1 ; i <= n ; i++){ cin >> a[i].first >> a[i].second; if (a[i].first > a[i].second) swap(a[i].first , a[i].second); A.insert(max(a[i].first,a[i].second)); B.insert(min(a[i].first,a[i].second)); } ll ans = (*(--A.end()) - *(A.begin())) * (*(--B.end()) - *(B.begin())); sort(a + 1 , a + 1 + n); for (int i = 1 ; i <= n ; i++){ A.erase(A.find(a[i].second)); B.erase(B.find(a[i].first)); A.insert(a[i].first); B.insert(a[i].second); ans = min (ans , (*(--A.end()) - *(A.begin())) * (*(--B.end()) - *(B.begin()))); } cout << ans << endl; return 0; }

方法二 ：随机化 + 贪心

离谱

---

D.dp + 线段树

待补.

题目大意:

题目思路: