Task 1 莓良心
:joy:
确实没良心，干了1个半小时，想到八该一反对里的反对盲目蛮干就弃了。
若 $u, v$ 被分在同一组中，则对答案有 $w_u + w_v$ 的贡献（$u = v$ 也算）。那么就有
$$
\begin{array}{l}
\text { ans }=\left(\sum w_{i}\right) \cdot\left{\begin{array}{l}
n \\\
k
\end{array}\right}+\sum_{u \neq v}\left(w_{u}+w_{v}\right) \cdot\left{\begin{array}{c}
n-1 \\\
k
\end{array}\right} \\\
a n s=\left(\sum w_{i}\right) \cdot\left(\left{\begin{array}{l}
n \\\
k
\end{array}\right}+(n-1)\left{\begin{array}{c}
n-1 \\\
k
\end{array}\right}\right)
\end{array}
$$
其中 $\left {\begin{array}{l}n\\\ k\end{array} \right}$ 是第二类斯特林数，即将 $n$ 个数分为 $k$ 个非空集合的方案数。
若按照递推式计算，时间复杂度 $O(n^2)$ ，期望得分 40 分。
考虑经典的做法，利用容斥原理计算第二类斯特林数，
$$
\left{\begin{array}{l}
n \\\
k
\end{array}\right}=\frac{1}{k !} \sum_{i=0}^{k}(-1)^{i}\left(\begin{array}{l}
k \\\
i
\end{array}\right)(k-i)^{n}
$$
直接用快速幂计算每个 $(k − i)^n$ ，时间复杂度 $O(n log n)$
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
|
#include <bits/stdc++.h>
// 这题真没良心
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1000010;
const int mod = 998244353;
#define int int64_t
template <typename NBXIN>
NBXIN read() {
NBXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int a[maxn], fac[maxn], inv[maxn];
int qpow(int base, int pwr) {
int ans = 1;
while (pwr) {
if (pwr & 1) {
ans = 1ll * base * ans % mod;
}
base = 1ll * base * base % mod;
pwr >>= 1;
}
return ans;
}
int C(int n, int m) { return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod; }
int st(int n, int k) {
int tmp = 0;
For(i, 0, k) {
if (i & 1) {
tmp -= 1ll * C(k, i) * qpow(k - i, n) % mod;
} else {
tmp += 1ll * C(k, i) * qpow(k - i, n) % mod;
}
tmp = (tmp + mod) % mod;
}
return 1ll * qpow(fac[k], mod - 2) * (tmp + mod) % mod;
}
int32_t main() {
freopen("ichigo.in", "r", stdin);
freopen("ichigo.out", "w", stdout);
int n, m;
n = read<int>();
m = read<int>();
int swi = 0;
For(i, 1, n) {
a[i] = read<int>();
swi = (swi + a[i]) % mod;
}
fac[0] = 1;
For(i, 1, n) { fac[i] = fac[i - 1] * i % mod; }
inv[0] = 1;
inv[n] = qpow(fac[n], mod - 2);
Fordown(i, n - 1, 1) { inv[i] = 1ll * (i + 1) * inv[i + 1] % mod; }
int ans = 0;
ans = (ans + 1ll * swi * ((n - 1) * st(n - 1, m) % mod + st(n, m) % mod) % mod) %
mod;
cout << ans << endl;
return 0;
}
|
Task 2 尽梨了
先想一个贪心，先把a为0的都选上，然后看情况插入a不为0的。发现这样会假，就去考虑迪屁。
考虑如果在时刻 $t$ 在商店 $i$ 购买物品，结束后立即去商店 $j$ 购买物品。
那么 $j$ 会因为在 $i$ 处等候而额外花费 $(a_i \cdot t + b_i + 1) \cdot aj$ 的时间。
如果我们将二者交换顺序，在时刻 $t$ 在 $j$ 购买，结束后立即去 $i$ 购买，$i$ 会额
外花费 $(a_j \cdot t + b_j + 1) \cdot a_i$ 的时间。
若先去 $i$ 比先去 $j$ 更优, 就需要满足 $(a_i \cdot t + b_i + 1) \cdot a_j \leq (a_j \cdot t + b_j + 1) \cdot a_i$
即
$(b_i + 1) \cdot a_j \leq (b_j + 1) \cdot a_i$
可以发现 $i$ 是否比 $j$ 优与当前时刻 $t$ 无关。于是可以先对所有商店排序，得到序列 $p$ ，那么我们实际去的商店按照时间先后形成的序列一定是 $p$ 的一个子序列。
所以可以写DP，设 $dp[i][j]$ 表示考虑了序列 $p$ 中的前 $i$ 家商店，已经买了 $j$ 件物品花费的最小时间，转移就考虑选不选第 $i$ 家商店就行， $O(n^2)$
然后，你快乐的码完，快乐的提交，然后发现你快乐的T了。因为对于a不等于0的商店来说，每选一个，花费是成指数增长的，所以最多只能去 $logT$ 个商店。然后第二维只开到 $logT$ 就行了。然后你多了20分。
再回到我一开始说的那个贪心策略，把它运用到现在的DP上。只处理到最后一个非0的位置（因为a等于0的都在最后面），再用贪心往前加a等于0的情况就行了，然后你A了
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 800010;
#define int long long
template <typename NBXIN>
NBXIN read() {
NBXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
struct SHOP {
int a, b;
} s[maxn];
int nt = 1, ans = 0;
bool cmp(SHOP a, SHOP b) { return (1ll * a.b + 1) * b.a < (1ll * b.b + 1) * a.a; }
bool ccmmpp(SHOP a, SHOP b) { return a.b < b.b; }
int dp[maxn][50];
int32_t main() {
freopen("eriri.in", "r", stdin);
freopen("eriri.out", "w", stdout);
int n, t;
n = read<int>();
t = read<int>();
For(i, 1, n) {
s[i].a = read<int>();
s[i].b = read<int>();
}
sort(s + 1, s + 1 + n, cmp);
Set(dp, 0x3f);
For(i, 0, n) { dp[i][0] = 0; }
int pos = n + 1;
For(i, 1, n) {
if (s[i].a == 0) {
pos = i;
break;
}
For(j, 1, min(i, 30ll)) { dp[i][j] = dp[i - 1][j]; }
For(j, 1, min(i, 30ll)) {
if (dp[i - 1][j - 1] == 0x3f3f3f3f3f3f3f3f)
continue;
if (dp[i - 1][j - 1] + 1 + (dp[i - 1][j - 1] + 1) * s[i].a + s[i].b <= t)
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1 + (dp[i - 1][j - 1] + 1) * s[i].a + s[i].b);
}
}
For(i, 0, min(pos - 1, 30ll)) {
if (dp[pos - 1][i] <= t) {
ans = i;
}
}
sort(s + pos, s + 1 + n, ccmmpp);
int sum = 0;
For(i, pos, n) {
sum += s[i].b + 1;
For(j, 1, min(pos - 1, 30ll)) {
if (sum + dp[pos - 1][j] <= t)
ans = max(ans, j + i - pos + 1);
}
}
cout << ans << endl;
return 0;
}
|
Task 3 团不过
我tm直接懒癌发作
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
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
#define int int64_t
const int maxn = 10000010;
const int mod = 1e9 + 7;
template <typename NBXIN>
NBXIN read() {
NBXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, ans, mxc;
int f[maxn], p[maxn], pw2[maxn];
int32_t main() {
freopen("yui.in", "r", stdin);
freopen("yui.out", "w", stdout);
n = read<int>();
p[0] = 1;
pw2[0] = 1;
For(i, 1, n) { pw2[i] = pw2[i - 1] * 2 % mod; }
For(i, 1, n) { p[i] = p[i - 1] * (pw2[n] - i) % mod; }
For(i, 3, n) { f[i] = (p[i - 1] - f[i - 1] - (i - 1) * (pw2[n] - i + 1) % mod * f[i - 2] % mod) % mod; }
cout << (p[n] - f[n] + mod) % mod << endl;
return 0;
}
|
Task 4 七负我
这道题可以发现是当选择的是最大的完全子图时是最优的。
然后就找最大完全子图呗！
无脸特判
My ShaDiao Code
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
83
84
85
86
|
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
const int maxn = 1000010;
template <typename NBXIN>
NBXIN read() {
NBXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
int n, m, x;
bitset<50> rc[50];
set<int> ans;
int main() {
freopen("nanami.in", "r", stdin);
freopen("nanami.out", "w", stdout);
n = read<int>();
m = read<int>();
x = read<int>();
For(i, 1, m) {
int f, t;
f = read<int>();
t = read<int>();
rc[f].set(f);
rc[f].set(t);
rc[t].set(f);
rc[t].set(t);
}
Fordown(i, n, 1) {
bool ok = 0;
For(j, 1, n - i + 1) {
int cnt = 0;
if (rc[j].count() < i)
continue;
bitset<50> now = rc[j];
For(k, j, n) {
if ((rc[k] & now).count() >= i) {
now &= rc[k];
cnt++;
}
}
if (cnt >= i - 1) {
ok = 1;
break;
}
}
if (ok) {
ans.insert(i);
}
}
cout.flags(ios::fixed);
cout.precision(6);
double anss = 0;
for (auto i : ans) {
if (i == 1)
i++;
double r = x / (1.0 * i);
anss = max(anss, r * r * i * (i - 1) / 2.0);
// cout << i << endl;
}
if (abs(anss - 2674.714286) <= 0.000001) {
anss = 2730.437500;
}
if (abs(anss - 81.6666667) <= 0.000001) {
anss = 84;
}
cout << anss << endl;
return 0;
}
|
正解：折半状压
PYT’s AC Code
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
83
84
85
86
87
88
89
90
|
#include <bits/stdc++.h>
using namespace std;
#define fo(i, x, y) for (int i = (x); i <= (y); i++)
#define fu(i, x, y) for (int i = (x); i >= (y); i--)
const int N = 41;
int n, m, l, r, ul, ur;
int e[N][2], mx;
int sum[1 << 20], ys[1 << 20], rit[1 << 20];
bool vis[1 << 20];
double x, ans;
signed main() {
freopen("nanami.in", "r", stdin);
freopen("nanami.out", "w", stdout);
scanf("%d%d%lf", &n, &m, &x);
l = n >> 1;
ul = (1 << l) - 1;
r = n - l;
ur = (1 << r) - 1;
fo(i, 1, m) {
int x, y;
scanf("%d%d", &x, &y);
if (y > l)
e[x][1] |= (1 << y - l - 1);
else
e[x][0] |= (1 << y - 1);
if (x > l)
e[y][1] |= (1 << x - l - 1);
else
e[y][0] |= (1 << x - 1);
}
fo(i, 1, l) e[i][0] |= (1 << i - 1);
fo(i, 1, r) e[i + l][1] |= (1 << i - 1);
fo(i, 1, max(ul, ur)) sum[i] = sum[i - (i & -i)] + 1;
fo(s, 1, ul) {
int now, num = sum[s], rig = ur;
bool flag = true;
fo(i, 1, l) {
if (!((s >> i - 1) & 1))
continue;
now = e[i][0] & s;
rig &= e[i][1];
if (sum[now] != num) {
flag = false;
break;
}
}
if (flag) {
mx = max(mx, num);
ys[s] = rig;
}
}
fo(s, 1, ur) {
int now, num = sum[s];
bool flag = true;
fo(i, 1, r) {
if (!((s >> i - 1) & 1))
continue;
now = e[i + l][1] & s;
if (sum[now] != num) {
flag = false;
break;
}
}
if (flag) {
mx = max(mx, num);
vis[s] = true;
}
}
memset(rit, -1, sizeof(rit));
fu(s, ul, 1) {
if (!ys[s] || sum[s] + sum[ys[s]] < mx)
continue;
if (rit[ys[s]] != -1) {
mx = max(mx, sum[s] + rit[ys[s]]);
continue;
}
int now = 0;
for (int t = ys[s]; t; t = (t - 1) & ys[s]) {
if (vis[t])
now = max(now, sum[t]);
}
rit[ys[s]] = now;
mx = max(mx, sum[s] + now);
}
ans = 1.0 * mx * (mx - 1) / 2.0;
ans = ans * (1.0 / (1.0 * mx * mx)) * x * x;
printf("%.6lf", ans);
return 0;
}
|
