https://codeforces.com/gym/101933

J. Jumbled String

 

题意：有一个01串，有 a 个00子序列，b 个01子序列，c 个10子序列，d 个11子序列。构造出这个01串。

构造

通过00和11能知道 0 和 1 的个数，现在假设只有 0，每插入一个 1，就多出左边0的个数个01，右边0的个数个10，加起来恰等于所有0的个数。对每个1都是如此，所以总的 b+c 必须等于cnt[0]*cnt[1]。

左边都放1，接着放0，这样就有了 cn[1]*cn[0] 个10，还剩下一些10，可以再中间某处再放一个1，接着放剩下的0，再放剩下的1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
#define debug(x) cout << #x << ":\t" << x << endl;
using namespace std;
typedef long long LL;
typedef pair<int, int> Pair;
const int N = 2e6 + 10, inf = 1e9;

LL a, b, c, d, t, cnt[2];
map<LL, LL> mp;
string ans;


bool solve() {
	if (!a && !d) {
		if (b == 1 && c == 0) {
			ans = "01";
			return true;
		}
		else if (b == 0 && c == 1) {
			ans = "10";
			return true;
		}
		else if (!b && !c) {
			ans = "1";
			return true;
		}
		return false;
	}
	if (!mp.count(a) || !mp.count(d)) return false;
	cnt[0] = mp[a];
	cnt[1] = mp[d];
	if (!b && !c) {
		if (!a) {
			ans = string(cnt[1], '1');
			return true;
		}
		else if (!d) {
			ans = string(cnt[0], '0');
			return true;
		}
		return false;
	}
	if (b + c != cnt[0] * cnt[1]) return false;
	ans = string(c / cnt[0], '1');
	ans += string(cnt[0] - c % cnt[0], '0');
	if (c % cnt[0]) ans += '1';
	ans += string(c % cnt[0], '0');
	ans += string(cnt[1] - c / cnt[0] - (c % cnt[0] ? 1 : 0), '1');
	return true;
}

int main()
{
	cin >> a >> b >> c >> d;
	rep(i, 1, 1000000) {
		t = 1ll * i * (i - 1) / 2;
		//        debug(i)
		//        debug(t)
		if (t > inf) break;
		mp[t] = i;
	}
	//    debug(mp.size())
	//    debug(mp[1])
	//    debug(mp[2])
	//    debug(mp[3])
	if (solve()) {
		cout << ans << endl;
	}
	else puts("impossible");

	//    debug(cnt[0])
	//    debug(cnt[1])
	return 0;
}

 

K. King’s Colors

 

题意：给定一棵树要涂色成恰好 k 种颜色，相邻点颜色必须不同，问几种方案。

计数 二项式反演

若问题为至多有 k 种颜色，则第一个点有 k 种颜色选择，第二个有 k-1 种，后面所有点也都是 k-1 种。所以是 k⋅(n−1)k−1k\cdot(n-1)^{k-1}。

设 g(k)g(k) 表示恰有 k 种颜色，f(k)f(k) 表示小于等于 k 种颜色，则 f(x)=∑k=1xCxk⋅k⋅(n−1)k−1f(x)=\sum_{k=1}^x C_{x}^k\cdot k\cdot (n-1)^{k-1}。

反演得到 g(k)=∑i=1k(−1)k−i(ni)f(i)g(k)=\sum\limits_{i=1}^k(-1)^{k-i}\dbinom{n}{i}f(i)。

这是经典的二项式反演。和容斥相似，但是不是容斥。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, i##end = r; i <= i##end; ++i)
#define repo(i, l, r) for (int i = l, i##end = r; i < i##end; ++i)
#define per(i, l, r) for (int i = r, i##end = l; i >= i##end; --i)
#define debug(x) cout << #x << ":\t" << x << endl;
using namespace std;
typedef long long LL;
typedef long long ll;
typedef pair<int, int> Pair;
const int N=2e6+10, inf = 1e9, mod = 1e9+7;

LL fac[3000];

LL pow_mod(LL a, LL n) {
    LL rst = 1;
    for (a %= mod; n; n >>= 1, a = a * a % mod) {
        if (n & 1) rst = rst * a % mod;
    }
    return rst;
}

ll C(int n, int k)
{
    //cout<<fac[n] * pow_mod(fac[k] * fac[n-k] % mod, mod - 2) % mod<<endl;
    return fac[n] * pow_mod(fac[k] * fac[n-k] % mod, mod - 2) % mod;
}

int n, k;

int main()
{
    int tmp;
    cin>>n>>k;
    fac[0] = 1;
    for(int i = 0; i < n - 1; i++)  scanf("%d", &tmp);
    for(int i = 1; i <= n; i++)  fac[i] = fac[i-1] * i % mod;
    LL ans = 0;
    int sign = 0;
    int k1 = k;
    while(k1 >= 2)
    {
        //cout<<k1<< " " << k<<endl;
        if(sign == 0)
            ans = ans + C(k, k1) * k1 % mod * pow_mod(k1 - 1, n - 1) % mod;
        else
            ans = ans - C(k, k1) * k1 % mod * pow_mod(k1 - 1, n - 1) % mod;
        ans %= mod;
        sign ^= 1;
        if(ans < 0)  ans += mod;
        k1--;
    }
    if(ans < 0)  ans += mod;
    cout<<ans<<endl;

    return 0;
}

 

E. Explosion Exploit

 

题意：我方 n 个随从，对方 m 个随从，每个随从各自有血量，不超过 6，每人随从数各不超过5，共 d 点伤害，每点随机给场上所有随从，每死掉一个就立即从场上移除，问对方所有随从死完的概率。

dfs枚举

数据很小，直接暴力dfs。存场上所有随从的血量情况。但是会T。

其实我们并不需要所有随从的情况，我们只需要知道有几个随从，以及这次伤害后还有几个。也就是说并不需要随从的顺序。如果几个随从的血量相同，那么我们只要知道它们的个数，至于怎样排列的并不需要。这样就能去掉一个全排列的复杂度。

开一个12的数组，前6个存对方处于每个血量的随从数，后6个存我方。

更进一步，把数组状压，这样只要判断数字小于1000000就能知道对方没有随从了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
const double eps = 1e-7;
int n, m, d, t;
int a[N], c[2][N];
ll p[20];
map<ll, double>dp;
ll s;
double dfs(ll ss, int d) {
	if (dp.count(ss))return dp[ss];
	int cnt = 0;
	for (int i = 6; i < 12; i++) {
		cnt += ss / p[i] % 10 * (i - 5);
	}
	if (cnt > d)return dp[ss] = 0.0;
	if (ss < 1000000) {
		return dp[ss] = 1.0;
	}
	int r = 0;
	for (int i = 0; i < 12; i++) {
		r += (ss / p[i]) % 10;
	}
	double res = 0;
	for (int i = 0; i < 12; i++) {
		if (ss / p[i] % 10 > 0) {
			ll tmp = ss;
			tmp -= p[i];
			if (i != 0 && i != 6)tmp += p[i - 1];
			res += 1.0 / r * (ss / p[i] % 10)*dfs(tmp, d - 1);
		}
	}
	return dp[ss] = res;
}
int main() {
	p[0] = 1;
	for (int i = 1; i < 20; i++)p[i] = p[i - 1] * 10;
	scanf("%d%d%d", &n, &m, &d);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
		c[0][a[i]]++;
		t += a[i];
	}
	for (int i = n; i < n + m; i++) {
		scanf("%d", &a[i]);
		c[1][a[i]]++;
		t += a[i];
	}
	for (int i = 1; i <= 6; i++) {
		s += (ll)pow(10, i - 1)*c[0][i];
		s += (ll)pow(10, i + 5)*c[1][i];
	}
	printf("%.9lf\n", dfs(s, min(d, t)));
	return 0;
}

 

D. Delivery Delays

 

题意：给定一张联通的无向图，餐厅位于 1 ，在 s[i] 产生一个订单，在 t[i] 做完，要送到 u[i]，货车可以装无限个订单，要求最小化最长的等待时间。已知若 s[i]>s[j]s[i]>s[j]，则 t[i]>t[j]t[i]>t[j]，且规定 s 小的必须先送到。

二分+dp

最小化最大值，还是考虑二分。

二分答案，要求在最长等待时间不超过 x 的情况下能否送完所有点。

等待时间必定和时间有关，所以要知道每个订单在什么时候送到，在满足条件的情况下每个订单肯定越早送到，留给后面的时间越多。

所以 dp[i]dp[i] 表示前 i 个订单最早送完的时间。

由于规定了先订的必须先送，所以问题简化了，且由于拿了不送不如不拿，所以如果拿到第 i 个订单，则手里的必须全部送完。

那么问题变为每次出发时手里拿到第几个订单。这又是个经典的分块的dp。

对于每个 i，遍历所有 j <= i ，表示第 j 到第 i 个作为新的一块。

则要从 j-1 返回 1，再等待，拿到 i 后到 u[j]，再一直送到 i。

对于每个 j≤k≤ij\le k\le i，必须满足等待时间不超过 x。

等待时间为 max(dp[j−1]+d[u[j−1]][1],t[i])+d[1][u[j]]+dt[j+1][k]−s[k]max(dp[j-1]+d[u[j-1]][1],t[i])+d[1][u[j]]+dt[j+1][k]-s[k]，其中 dt[u][v]dt[u][v] 为送完第u 到 第v 个订单沿路的总距离。

看到对于不同 k，前面一部分是一样的，只有后面的 dt[j+1][k]−s[k]dt[j+1][k]-s[k] 不同，但是这是可以随着 k 改变而逐渐更新的，只要记录所有 k 的最大值，与 x 比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n, m, q;
struct E
{
	int v;
	ll w;
};
vector<E>G[1010];
int u[1010]; ll s[1010], t[1010];
ll d[1010][1010], dp[1010];
typedef pair<ll, int>pii;
void dij(int S, ll* d) {
	priority_queue<pii, vector<pii>, greater<pii> >q;
	d[S] = 0;
	q.push({ 0,S });
	while (!q.empty()) {
		int u = q.top().second; ll di = q.top().first;
		q.pop();
		if (di > d[u])continue;
		for (E& e : G[u]) {
			int v = e.v;
			if (d[v] > d[u] + e.w) {
				d[v] = d[u] + e.w;
				q.push({ d[v],v });
			}
		}
	}
}
ll dt[1010][1010];
bool ck(ll x) {
	memset(dp, 0x3f, sizeof(dp));
	dp[1] = t[1] + d[1][u[1]];
	if (dp[1] - s[1] > x)return false;
	dp[0] = 0;
	for (int i = 1; i <= q; i++) {
		ll mx = -inf;
		for (int j = i; j >= 1; j--) {
			mx = max(mx, -s[j]);
			ll tmp = max(dp[j - 1] + d[u[j - 1]][1], t[i]) + d[1][u[j]];
			ll p = tmp + mx;
			mx = mx + d[u[j - 1]][u[j]];	//注意这里即使跳过了也要更新！！！
			if (p > x)continue;
			dp[i] = min(dp[i], max(t[i], dp[j - 1] + d[u[j - 1]][1]) + d[1][u[j]] + dt[j][i]);
		}
		if (dp[i] == inf)return false;
	}
	return dp[q] < inf;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int uu, v; ll w;
		scanf("%d%d%lld", &uu, &v, &w);
		G[uu].push_back({ v,w });
		G[v].push_back({ uu,w });
	}
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++)dij(i, d[i]);
	d[0][1] = d[1][0] = 0;
	scanf("%d", &q);
	for (int i = 1; i <= q; i++)scanf("%lld%d%lld", &s[i], &u[i], &t[i]);
	for (int i = 1; i <= q; i++) {
		dt[i][i] = 0;
		for (int j = i + 1; j <= q; j++) {
			dt[i][j] = dt[i][j - 1] + d[u[j - 1]][u[j]];
		}
	}
	ll L = 0, R = inf;
	while (L < R) {
		ll mid = (L + R) / 2;
		if (ck(mid))R = mid;
		else L = mid + 1;
	}
	printf("%lld\n", L);
	return 0;
}

也可以刷表更新dp，对于所有 i，求出从 i 到 j 作为一块，得到 j 的dp值。这样可以正向更新，要记录出发时刻，到达时刻，等待时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e6 + 10;
const ll mod = 1e9 + 7;
int n, m, q;
struct E
{
	int v, w;
};
vector<E>G[1010];
int u[1010]; ll s[1010], t[1010];
ll d[1010][1010], dp[1010];
typedef pair<ll, int>pii;
void dij(int S, ll* d) {
	priority_queue<pii, vector<pii>, greater<pii> >q;
	d[S] = 0;
	q.push({ 0,S });
	while (!q.empty()) {
		int u = q.top().second; ll di = q.top().first;
		q.pop();
		if (di > d[u])continue;
		for (E& e : G[u]) {
			int v = e.v;
			if (d[v] > d[u] + e.w) {
				d[v] = d[u] + e.w;
				q.push({ d[v],v });
			}
		}
	}
}
bool ck(ll x) {
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	ll wt, et, st;
	for (int i = 1; i <= q; ++i) {
		st = max(dp[i - 1] + d[1][u[i - 1]], t[i]);
		et = st + d[1][u[i]];
		wt = et - s[i];
		if (wt > x)continue;
		dp[i] = min(dp[i], et);
		for (int j = i + 1; j <= q; ++j) {
			wt = max(wt, wt + t[j] - st);
			et = et + d[u[j - 1]][u[j]] + max(0ll, t[j] - st);
			wt = max(wt, et - s[j]);
			st = max(st, t[j]);
			if (wt > x)break;
			dp[j] = min(et, dp[j]);
		}
	}
	return dp[q] < inf;

}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int uu, v, w;
		scanf("%d%d%d", &uu, &v, &w);
		G[uu].push_back({ v,w });
		G[v].push_back({ uu,w });
	}
	memset(d, 0x3f, sizeof(d));
	for (int i = 1; i <= n; i++)dij(i, d[i]);
	d[0][1] = d[1][0] = 0;
	scanf("%d", &q);
	for (int i = 1; i <= q; i++)scanf("%lld%d%lld", &s[i], &u[i], &t[i]);
	ll L = 0, R = inf;
	while (L < R) {
		ll mid = (L + R) / 2;
		if (ck(mid))R = mid;
		else L = mid + 1;
	}
	printf("%lld\n", L);
	return 0;
}

 

A. Altruistic Amphibians

 

题意：井底有 n 个青蛙，每个有高度，弹跳高度，质量，青蛙可以叠起来，每个青蛙身上的质量和必须小于自己的质量，如果弹跳高度加上身下的高度和大于井的深度，则跳出。问最多跳出几个。已知所有青蛙质量和不超过1e8.

背包dp

把所有青蛙按照质量从小到大排列，小的青蛙即使不能跳出，也不能垫在大青蛙脚下，所以一定是按照这样堆好后对每个青蛙判断如果身下能垫的青蛙能够使自己跳出则必须跳出。否则直接扔掉。

所以需要求每人能垫的最高高度。

dp[i][j]dp[i][j] 表示下面 i 个青蛙，还能叠质量 j 时的最大高度。

从下往上遍历，每加入一个青蛙，就遍历所有 j，更新dp。01背包。同时更新答案。

这样复杂度看似是 nm，但是由于题目里那个看着奇怪的条件限制了质量总和，所以其实 ∑w[i]≤108\sum w[i]\le10^8，复杂度刚好够。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
const int M = 1e8 + 10;
const ll mod = 1e9 + 7;
int n, d;
struct X
{
	int l, w, h;
	bool operator<(const X& b)const {
		return w > b.w;
	}
}a[N];
int dp[M], ans;
int main() {
	scanf("%d%d", &n, &d);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &a[i].l, &a[i].w, &a[i].h);
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		if (dp[a[i].w] + a[i].l > d)ans++;
		for (int j = 0; j < a[i].w; j++) {	//只更新小于w[i]的，因为如果叠上去则新的承重必定小于w[i]，大于w[i]只能是因为没叠
			if (j + a[i].w >= M)dp[j] = max(dp[j], a[i].h);
			else dp[j] = max(dp[j], min(d, dp[j + a[i].w] + a[i].h));
		}
		for (int j = min(M - 2, 2 * a[i].w); j >= 0; j--) {	//其实并不需要，因为从初始起每次更新后都已经满足条件
			dp[j] = max(dp[j], dp[j + 1]);
		}
	}
	printf("%d\n", ans);
	return 0;
}