1. NOIP2010提高组 关押罪犯
来源：NOIP2003提高组 https://ac.nowcoder.com/acm/contest/258/C
(二分，染色法判断二分图) O((N+M)logC)
- 将罪犯当做点，罪犯之间的仇恨关系当做点与点之间的无向边，边的权重是罪犯之间的仇恨值。
那么原问题变成：将所有点分成两组，使得各组内边的权重的最大值尽可能小。
我们在 [0,109] 之间枚举最大边权 limist, 当 limist固定之后，剩下的问题就是：- 判断能否将所有点分成两组，使得所有权值大于 limit 的边都在组间，而不在组内。也就是判断由所有点以及所有权值大于 limit 的边构成的新图是否是二分图。
- 判断二分图可以用染色法，时间复杂度是 O(N+M), 其中 N 是点数，M 是边数，可以参考AcWing 860. 染色法判定二分图。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 20010,
M = 200010;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int color[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
bool dfs(int u, int c, int limit)
{
color[u] = c;
for (int i = h[u]; ~i; i = ne[i])
{
if (w[i] <= limit) continue;
int j = e[i];
if (color[j])
{
if (color[j] == c) return false;
}
else if (!dfs(j, 3 - c, limit)) return false;
}
return true;
}
bool check(int limit)
{
memset(color, 0, sizeof color);
for (int i = 1; i <= n; i++)
if (color[i] == 0)
if (!dfs(i, 1, limit))
return false;
return true;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, c);
}
int l = 0, r = 1e9;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
printf("%d\n", l);
return 0;
}
2. 聪明的质检员
来源：NOIP2011提高组 https://ac.nowcoder.com/acm/contest/259/B
算法知识点：二分，前缀和
复杂度： O(n^2)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; const int N = 200010;
int n, m;
LL S;
int w[N], v[N];
int l[N], r[N];
int cnt[N];
LL sum[N];
LL get(int W)
{
for (int i = 1; i <= n; i++)
if (w[i] >= W)
{
sum[i] = sum[i - 1] + v[i];
cnt[i] = cnt[i - 1] + 1;
}
else
{
sum[i] = sum[i - 1];
cnt[i] = cnt[i - 1];
}
LL res = 0;
for (int i = 0; i < m; i++) res += (cnt[r[i]] - cnt[l[i] - 1]) *(sum[r[i]] - sum[l[i] - 1]);
return res;
}
int main()
{
scanf("%d%d%lld", &n, &m, &S);
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &v[i]);
for (int i = 0; i < m; i++) scanf("%d%d", &l[i], &r[i]);
int l = 0, r = 1e6 + 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (get(mid) >= S) l = mid;
else r = mid - 1;
}
printf("%lld\n", min(abs(get(r) - S), abs(S - get(r + 1))));
return 0;
}
3.借教室
来源：NOIP2012提高组 https://ac.nowcoder.com/acm/contest/260/B
算法知识点：二分，差分
复杂度： O((n + m)logm
解题思路：
C++代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL; const int N = 1000010;
int n, m;
int r[N], d[N], s[N], t[N];
LL b[N];
bool check(int k)
{
for (int i = 1; i <= n; i++) b[i] = r[i];
for (int i = 1; i <= k; i++)
{
b[s[i]] -= d[i];
b[t[i] + 1] += d[i];
}
LL res = 0;
for (int i = 1; i <= n; i++)
{
res += b[i];
if (res < 0) return true;
}
return false;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
for (int i = n; i; i--) r[i] -= r[i - 1];
for (int i = 1; i <= m; i++) scanf("%d%d%d", &d[i], &s[i], &t[i]);
int l = 1, r = m;
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
if (check(r))
{
puts("-1");
printf("%d\n", r);
}
else puts("0");
return 0;
}
4. 跳石头
来源：NOIP2015提高组 https://ac.nowcoder.com/acm/contest/263/A
算法知识点：二分，贪心
复杂度：O(NlogL)
解题思路：
C++代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int N = 50010;
int L, n, m;
int d[N];
bool check(int mid)
{
int last = 0, cnt = 0;
for (int i = 1; i <= n; i++)
if (d[i] - last < mid) cnt++;
else last = d[i];
return cnt <= m;
}
int main()
{
scanf("%d%d%d", &L, &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &d[i]);
d[++n] = L;
int l = 1, r = 1e9;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
printf("%d\n", r);
return 0;
}
另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ
京公网安备 11010502036488号