https://codeforces.com/contest/1841
https://codeforces.com/contest/1841/problems
D. Pairs of Segments
https://codeforces.com/contest/1841/problem/D
因为 \(n\) 只有 \(2000\)，所以考虑枚举每一对 \((i, j)\) 满足区间有交集并且 \(i \neq j\)。
如果有交集，就合并。
然后就是从这些合并好的区间内选出尽可能多的不交的区间。
然后 DP，设 \(f_i\) 按下标顺序选，表示最后一个区间的右端点为 \(i\) 的，最多用了多少个区间（原来的）。
设合并好的区间分别为 \([l_1', r_1'], [l_2', r_2'], \dots, [l_m', r_m']\)，那么我们按右端点从大到小 DP：
\[f_{r} = \max(f_{r}, 2 + \max_{i = 0}^{l - 1} f_{i}) \]其中 \(f_0 = 0\)。
最后答案就是所有的 \(f\) 取个 max 再用 \(n\) 减去。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
int n, l[2005], r[2005], a[4005], f[4005], pre[4005];
map < int, int > mp;
set < int > st[4005];
signed main () {
int _;
read (_);
while (_ --) {
read (n);
for (int i = 1;i <= n; ++ i) {
read (l[i]), read (r[i]);
a[i] = l[i], a[i + n] = r[i];
}
sort (a + 1, a + 1 + 2 * n);
int m = unique (a + 1, a + 1 + 2 * n) - a - 1;
mp.clear ();
for (int i = 1;i <= m; ++ i) mp[a[i]] = i;
for (int i = 1;i <= n; ++ i) l[i] = mp[l[i]], r[i] = mp[r[i]];
for (int i = 1;i <= m; ++ i) st[i].clear ();
for (int i = 1;i <= n; ++ i) {
for (int j = i + 1;j <= n; ++ j) {
if (r[i] < l[j] || r[j] < l[i]) ;
else st[max (r[i], r[j])].insert (min (l[i], l[j]));
}
}
for (int i = 0;i <= m; ++ i) f[i] = 0;
int ans = 0;
pre[0] = 0;
for (int i = 1;i <= m; ++ i) {
int now = 0;
int siz = 0;
for (int las : st[i]) {
siz = 1;
now = max (now, las - 1);
}
if (siz) f[i] = pre[now] + 2;
ans = max (ans, f[i]);
pre[i] = max (pre[i - 1], f[i]);
}
printf ("%d\n", n - ans);
}
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/
E. Fill the Matrix
https://codeforces.com/contest/1841/problem/E
我们把每一行的每一个极大的空白的区间取出来，排成一个序列，那么就是要取尽可能少的区间使得长度和 \(\geq m\)，设取了 \(k\) 个，那么答案就是 \(m - k\)。
发现这样的区间（不考虑行号）只有 \(n\) 个，直接暴力分解然后加就行了。
然后就贪心取。
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
bool Memory_Begins;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
template < class Z >
inline void read (Z &tmp) {
Z x = 0, f = 0;
char c = getchar ();
for ( ; c < '0' || c > '9' ; c = getchar ()) f |= (c == '-');
for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
tmp = !f ? x : -x;
}
int n, a[200005], st[200005][19], lg[200005];
ll f[200005];
ll m;
inline int query (int l, int r) {
int k = lg[r - l + 1];
int L = st[l][k], R = st[r - (1 << k) + 1][k];
if (a[L] < a[R]) return L;
else return R;
}
bool Memory_Ends;
signed main () {
fprintf (stderr, "%.3lf MB\n", (&Memory_Begins - &Memory_Ends) / 1048576.0);
int _; read (_);
while (_ --) {
int sz = 0;
read (n);
for (int i = 1;i <= n; ++ i) read (a[i]), a[i] = n - a[i];
for (int i = 1;i <= n; ++ i) st[i][0] = i;
for (int j = 1;j < 19; ++ j) {
for (int i = 1;i + (1 << j) - 1 <= n; ++ i) {
int L = st[i][j - 1], R = st[i + (1 << (j - 1))][j - 1];
if (a[L] < a[R]) st[i][j] = L;
else st[i][j] = R;
}
}
lg[0] = -1;
for (int i = 1;i <= n; ++ i) {
lg[i] = lg[i >> 1] + 1;
}
read (m);
for (int i = 1;i <= n; ++ i) f[i] = 0;
queue < tuple < int, int, int > > q;
q.push (make_tuple (1, n, 0));
while (!q.empty ()) {
tuple < int, int, int > tmp = q.front ();
q.pop ();
int L = get < 0 > (tmp), R = get < 1 > (tmp), w = get < 2 > (tmp);
int u = query (L, R);
f[R - L + 1] += a[u] - w;
if (L < u) q.push (make_tuple (L, u - 1, a[u]));
if (u < R) q.push (make_tuple (u + 1, R, a[u]));
}
ll ans = m;
for (int i = n;i >= 1; -- i) {
if (m >= f[i] * i) m -= f[i] * i, ans -= f[i];
else {
ans -= m / i;
if (m % i) -- ans;
break;
}
}
printf ("%lld\n", ans);
}
fprintf (stderr, "%.3lf ms\n", 1e3 * clock () / CLOCKS_PER_SEC);
return 0;
}
/*
Things to check:
1. int ? long long ? unsigned int ? unsigned long long ?
2. array size ? is it enough ?
*/