P4643 [国家集训队]阿狸和桃子的游戏

题目大意

有一张 \(n\) 个点 \(m\) 条边的图，点有点权，边有边权。

先手后手轮流染黑白两色，最后的得分是自己染的点权和 + 两端均为自己的颜色的边权和。

双方都希望自己的得分 - 对手的得分最大，求结果。

\(1 \le n \le 10000, 0 \le m \le 100000\)

题解

这题巨妙无比，真是妙蛙种子吃着妙脆角，秒进了米奇妙妙屋，秒到家了。

你可以考虑把每一条边都分到他所连的 \(2\) 个点上，各一半。

然后对于每条边，我们有 \(2\) 种可能，如下：

  • \(2\) 边都是 \(A\) 取的，那么 \(2\) 个点之和刚好是贡献。

  • 如果 \(2\) 边不一样，那么一边都是一半，相互抵消。

代码

#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;
const int maxn = 10010;
int n, m, u, v, w;
double a[maxn];
double cmp(double x, double y) {
    return x >= y;
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++ i) {
        scanf("%lf", &a[i]);
    }
    for(int i = 1; i <= m; ++ i) {
        scanf("%d%d%d", &u, &v, &w);
        a[u] += (double) w / 2;
        a[v] += (double) w / 2;
    }
    sort(a + 1, a + n + 1, cmp);
    double ans = 0;
    for(int i = 1; i <= n; ++ i) {
        if(i % 2) {
            ans += a[i];
        }
        else {
            ans -= a[i];
        }
    }
    printf("%d", (int) ans);
    return 0;
}

Mushroom 的区间

题目大意

给你若干个区间 \([l_i, r_i]\) ，每次可以对一个区间进行整体异或操作。

区间初始全 \(0\)，问你最后可以形成多少种不同的区间。

题解

考虑什么样的区间是没有贡献的。

假设对于区间 \([l, r]\) ，我们考虑如果存在以下三个区间，那么这个区间是无用的。

  • [i, l - 1]

  • [r + 1, j]

  • [i, j]

那么通过不同的组合，有无区间 \([l, r]\) 是没有意义的。

那么用并查集维护端点就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
const int XRZ = 1e9 + 7;
const int maxm = (1 << 21);
int n, m, ans = 1, l, r, f[maxn];
int find(int x) {
	return f[x] == x ? x : f[x] = find(f[x]);
}
int main() {
	freopen("section.in", "r", stdin);
	freopen("section.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i) {
		f[i] = i;
	}
	for(int i = 1; i <= m; ++ i) {
		scanf("%d%d", &l, &r);
		int x = find(l), y = find(r + 1);
		if(x == y) {
			continue;
		}
		f[x] = y;
		ans = (ans * 2) % XRZ;
	}
	printf("%d", ans);
	return 0;
}

P3545 [POI2012]HUR-Warehouse Store

题目大意

一共 \(n\) 天，每天上午会进 \(A_i\) 的物品，中午会有一个客人想要买走 \(B_i\) 的物品，当然你也可以选择不买，问你最后最多可以交易多少次。

数据范围 : \(1 <= n <= 250000, 0 <= A_i, B_i <= 10^9\)

题解

首先，我们看到题目先会想到 \(01\) 背包。是个正确的作法，但是肯定过不了。

然后，我们考虑到这一定是个贪心/推式子的题目。

但是推式子的题目一般的特性在这里显然不符合(推式子的题目一般不会让你选择)

那接下来考虑怎么去贪心。

第一想法是我们选最小的肯定是最优的，因为就算选了这个最小的而导致其他的不可以选，那也最多只能导致一个不可以选。

因为如果可以导致多个不可以选的话，选了次小的哪一个也会导致更多的不可以选。

所以选择最小的策略是对的，\(sort\) 一般的复杂度我们也可以接受，但是问题来了，我们那些数可以取？

取完当前最小的，那么它前面的一些数说不定不可以再去。

那么处理这些的复杂度就不稳定了，可以构造数据卡掉。

接下来我们想每天上午进的货物会对什么有影响。

这个很显然，它可以对他后面的所有数产生影响，因为到货了就可以卖给别人了。

那是不是可以这么考虑，从后往前去跑，每次去当前可以取的最小的。

因为从后完全就去除了它的后效性，所有正确性也是对的。

但是新增一个数 \(A_i\) 可能很大，一次可以处理多个数。

那你就必须保证后面整个序列是有序的，而且还要维护一个后缀和。

我们考虑维护这个有序数列的复杂度最优，那就是往前加一个数，就把这个数加入到数列里面去。

这样的复杂度最劣是 \(O(n^2)\) 的，还是会炸。

那我们是不是无法从一些顺序上去找到优化的空间。

我们就可以考虑去莽，然后支持撤销，这样也可以保证正确性。

具体的话是这样实现的：

从前往后读入，每次可以取就取，并且把这些取过的记录在单调队列中。

如果当前这个放不下，我们就把他和队列首的元素做比较，不断更新即可。

根据我们的第二个想法，每个前面取过的如果弹出来，因为他的后效性，肯定是可以服务后面的。

那么就结束了。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250010;
int n, sum, ans, book[maxn];
priority_queue<pair<int, int>, vector<pair<int, int> > > Q;
struct node {
    int a, b, id;
} e[maxn];
int cmp(node x, node y) {
    return x.b < y.b;
}
signed main() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld", &e[i].a);
        e[i].id = i;
    }
    for(int i = 1; i <= n; ++ i) {
        scanf("%lld", &e[i].b);
    }
    for(int i = 1; i <= n; ++ i) {
        sum += e[i].a;
        if(e[i].b < sum) {
            Q.push(make_pair(e[i].b, e[i].id));
            ++ ans;
            book[i] = 1;
            sum -= e[i].b;
        }
        else if(! Q.empty() && Q.top().first > e[i].b) {
            book[Q.top().second] = 0;
            book[i] = 1;
            sum += e[Q.top().second].b - e[i].b;
            Q.pop(); Q.push(make_pair(e[i].b, e[i].id));
        }
    }
    printf("%lld\n", ans);
    for(int i = 1; i <= n; ++ i) {
        if(book[i]) {
            printf("%d ", i);
        }
    }
    return 0;
}

P4823 [TJOI2013]拯救小矮人

题目大意

有 \(n\) 个小矮人，每个小矮人有身高 \(A_i\) 和 臂长 \(B_i\)

一个小矮人可以出去的条件是

\[\sum_{i = 1}^{k}{A_i} + B_k >= h \]

问最多可以跑出去多少小矮人。

题解

因为人人平等对吧，所以每个人的价值都是一样的。

那么我们就考虑什么样的人更加容易出来。

是不是手长+臂长更长的人就更容易出来。

我们考虑有 \(2\) 个人 \(A\) 和 \(\text{B}\) 。

并且 \(\text{A}\) 可以单独出来，\(\text{B}\) 只可以在 \(A\) 的帮助下出来。

那么肯定是要先把 \(B\) 放出来，再让 \(A\) 后出来。

所以我们贪心的策略是把臂长+手长大的放后面。小的先跑出去。

至于我们怎么实现跑出去的过程，跑一遍最简单的 \(dp\) 就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2010;
int n, h, sum, ans, f[maxn];
struct node {
    int a, b;
} e[maxn];
int cmp(node x, node y) {
    return (x.a + x.b) < (y.a + y.b);
}
int main() {
    scanf("%d", &n);
    memset(f, 128, sizeof(f));
    f[0] = 0;
    for(int i = 1; i <= n; ++ i) {
        scanf("%d%d", &e[i].a, &e[i].b);
        f[0] += e[i].a;
    }
    scanf("%d", &h);
    sort(e + 1, e + 1 + n, cmp);
    for(int i = 1; i <= n; ++ i) {
        for(int j = i; j >= 1; -- j) {
            if(f[j - 1] + e[i].b >= h) {
                f[j] = max(f[j], f[j - 1] - e[i].a);
            }
        }
    }
    for(int i = n; i >= 0; -- i) {
        if(f[i] >= 0) {
            printf("%d", i);
            return 0;
        }
    }
    return 0;
}

CF847E

题意

给你一个长度为 \(n\) 个字符串，存在 \(3\) 种字符:

  • '*' 表示物品；
  • 'P' 表示人；
  • '.' 表示空；

每个人的行走互不干扰，问你最少过多久才可以取完所有物品。

题解

乍一看就感觉很 \(\text{DP}\) .

对每个人 \(\text{DP}\) ?

按时间 \(\text{DP}\) ?

感觉都不太对，那就不是 \(\text{DP}\) 了(大草)

我们考虑怎么暴力去跑？

先枚举时间，再暴力的找每个人可以取的物品，这样的复杂度是很恐怖的。

那么我们先优化时间，对于时间 \(x\) 和 \(x + 1\)，如果在 \(x\) 可以取完，那么 \(x + 1\) 肯定也可以，所以时间是满足单调性的，可以用二分优化到 \(\text{O(logn)}\)

接下来考虑后面这个东西怎么去 \(\text{check}\) 。

对于每个人，他们可以取完的东西太多了，我们无法有效快速的求。

那我们就考虑对于每一个物品去找哪个人可以收服他，这样肯定只有 \(2\) 种决策，他左边的第一个人和他右边的第一个人。

预处理下就行了。

代码

#include<bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
const int maxn = 200010;
int n, Nxt[maxn], Ans, L[maxn], R[maxn], Lst[maxn], Now;
char s[maxn];
bool check(int x) {
	for(int i = 1; i <= n; i ++) {
        if(s[i] == 'P') {
            L[i] = R[i] = i;
        }
    }
	for(int i = 1; i <= n; i ++) {
        if(s[i] == '*') {
            if(Lst[i] && min(2 * (Lst[i] - L[Lst[i]]) + i - Lst[i], 2 * (i - Lst[i]) + Lst[i] - L[Lst[i]]) <= x) {
                R[Lst[i]] = i;
                continue;
            }
	        if(Nxt[i] && L[Nxt[i]] < i) {
                continue;
            }
	  	    if(Nxt[i] == 0 || Nxt[i] - i > x) {
                  return 0;
              }
		    L[Nxt[i]] = i;
	    }
    }
	return 1;
}
int main() {
	scanf("%d%s", &n, s + 1);
	int l = 0, r = 1e7;
	for(int i = 1; i <= n; i ++) {
	    if(s[i] == 'P') {
            Now = i;
        }
	    else if(s[i] == '*') {
            Lst[i] = Now;
        }
    }
	Now = 0;
	for(int i = n; i ; -- i) {
	    if(s[i] == 'P') {
            Now = i;
        }
	    else if(s[i] == '*') {
            Nxt[i] = Now;
        }
    }
	while(l <= r) {
		if (check(mid)) {
            Ans = mid;
            r = mid - 1;
        }
		else {
            l = mid + 1;
        }
	}
	printf("%d", Ans);
	return 0;
}