https://codeforces.com/contest/1139

D. Steps to One

 

题意:给定一个数m,1m1000001 \leq m \leq 100000,有一个空数列,每一轮随机选一个 1 到 m 的数,加入数列,当数列的 gcd 为 1 时停止。问最终数列长度的数学期望。

数学期望+莫比乌斯反演+dp

首先加入一个数,可能为 1,2,···, m,则第一次操作后 gcd 可能为 1,2,···, m,所以只要求出 gcd 为 1,2,···, m 时还需要的长度的数学期望,求和求平均值。

f[i]f[i] 表示当前 gcd 为 ii 时还需要加入的数列长度的期望。

加入的下一个数可能为 1,2,···,m。所以 f[i]=1mj=1mf[gcd(i,j)]+1f[i]=\frac{1}{m}\sum_{j=1}^mf[gcd(i,j)]+1

直接枚举 j 复杂度不够,所以枚举 i 的因子,作为 gcd(i,j) ,变为 f[i]=1mxi(f[x]cal(i,x))f[i]=\frac{1}{m}\sum_{x|i}(f[x]\cdot cal(i,x))。其中 cal(i,x)cal(i,x) 表示与 i 的 gcd=x 的 j 的个数。

接着用莫比乌斯反演的套路求 cal(i,x)cal(i,x)

gcd(i,j)=x    gcd(ix,jx)=1    e(gcd(ix,jx))gcd(i,j)=x\implies gcd(\frac{i}{x},\frac{j}{x})=1\implies e(gcd(\frac{i}{x},\frac{j}{x}))

cal(i,x)=j=1m[gcd(i,j)=x]=j=1mx[gcd(ix,j)=1]=j=1mxdgcd(ix,j)μ[d]=dix(m/xdμ[d])\begin{align} cal(i,x) & = \sum_{j=1}^m [gcd(i,j)=x]\\ &=\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}[gcd(\frac{i}{x},j)=1]\\ &=\sum_{j=1}^{\lfloor\frac{m}{x}\rfloor}\sum_{d|\gcd(\frac{i}{x},j)}\mu[d]\\ &=\sum_{d|\frac{i}{x}}(\lfloor\frac{m/x}{d}\rfloor\cdot\mu[d])\\ \end{align}

这样在 i\sqrt{i} 内求出 cal(i,x)cal(i,x)

求出所有 f[i]f[i] 后求和求均值得到第一次操作后还需要的数列长度的期望,再+1.

复杂度还是挺迷的,虽然 cal(i,x)cal(i,x) 和枚举 x 都是根号,但是根号的内容不同,大概是 O(mmlogm)O(m\sqrt{m}\log m)

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
ll Pow(ll a, ll b) {
ll res = 1ll;
while (b) {
if (b & 1)res = res * a%mod;
a = a * a%mod;
b >>= 1;
}
return res;
}
int mu[N], p[N], tot;
bool flg[N];
void getMu(int n) {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!flg[i]) p[++tot] = i, mu[i] = -1;
for (int j = 1; j <= tot && i * p[j] <= n; ++j) {
flg[i * p[j]] = 1;
if (i % p[j] == 0) {
mu[i * p[j]] = 0;
break;
}
mu[i * p[j]] = -mu[i];
}
}
}
int m;
ll f[N];
vector<int>vc[N];
int cal(int i, int x) {
int n = m / x, res = 0;
i /= x;
for (int d : vc[i]) {
res += (n / d)*mu[d];
}
res += n * mu[1] + (n / i)*mu[i];
return res;
}
int main() {
scanf("%d", &m);
getMu(m);
for (int i = 2; i <= m; i++) {
for (int j = 2; j*j <= i; j++) {
if (i%j != 0)continue;
vc[i].push_back(j);
if (i / j != j)vc[i].push_back(i / j);
}
}
f[1] = 0;
for (int i = 2; i <= m; i++) {
f[i] = m;
for (int x : vc[i]) {
f[i] = (f[i] + f[x] * cal(i, x) % mod) % mod;
}
f[i] = f[i] * Pow(m - m / i, mod - 2) % mod;
}
ll ans = 0;
for (int i = 1; i <= m; i++)ans = (ans + f[i]) % mod;
ans = ans * Pow(m, mod - 2) % mod;
ans = (ans + 1) % mod;
printf("%lld\n", ans);
return 0;
}

 

E. Maximize Mex

 

题意:给定 n 个学生,m 个俱乐部, 1mn50001 \leq m \leq n \leq 5000,每个学生有 p[i]p[i] 的潜力值,0pi<50000 \leq p_i < 5000,且属于第 c[i]c[i] 个俱乐部,共有 d 天,每天开始前有一名学生永远离开,接着要从每个非空的俱乐部各选一名学生,当天的值等于当天所选学生集合的 MEX 值。要求每天的值都尽量大,输出每天的值。

二分图匹配

每个俱乐部选一个,所以想到二分图匹配,把 潜力值与俱乐部 作为两个点集,学生看作边。

直接每次删边再重新求复杂度不够。

逆向求,从最后一天开始,每次加边,每次在旧图的基础上尝试插入更大的值以提高 MEX,也就是保证 MEX 值不会减小,所以最终 d 天下来就相当于求一次二分图匹配,复杂度 nmnm

注意一天内 MEX 可能不止提高 1。每次尝试插入都要先清空vis。

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>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 2e5 + 10;
int n, m, d;
int p[N], c[N], k[N], g[N], ans[N];
vector<int>G[N];
int vis[N], mat[N], mch[N];
bool dfs(int u) {
vis[u] = 1;
for (int v : G[u]) {
int w = mch[v];
if (w < 0 || (!vis[w] && dfs(w))) {
mat[u] = v;
mch[v] = u;
return true;
}
}
return false;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &p[i]);
for (int i = 1; i <= n; i++)scanf("%d", &c[i]);
scanf("%d", &d);
for (int i = 1; i <= d; i++)scanf("%d", &k[i]), g[k[i]] = 1;
for (int i = 1; i <= n; i++) {
if (!g[i]) {
G[p[i]].push_back(c[i]);
}
}
memset(mat, -1, sizeof(mat));
memset(mch, -1, sizeof(mch));
for (int i = 0; i < 5000; i++) {
memset(vis, 0, sizeof(vis));
if (!dfs(i)) {
ans[d + 1] = i;
break;
}
}
for (int i = d; i >= 1; i--) {
memset(vis, 0, sizeof(vis));
ans[i] = ans[i + 1];
while (dfs(ans[i])) {
memset(vis, 0, sizeof(vis));
ans[i]++;
}
G[p[k[i]]].push_back(c[k[i]]);

}
for (int i = 1; i <= d; i++)printf("%d\n", ans[i]);
return 0;
}

 

F. Dish Shopping

 

题意:给定 n 种菜,m 个人,每种菜有价格 p[i]p[i],标准 s[i]s[i],美味度 b[i]b[i]。每个人有收入 inc[i]inc[i],倾向 pref[i]pref[i]。每种菜有无限份,每个人只会选择 piincjsip_i \leq inc_j \leq s_ibiprefj(incjpi)|b_i-pref_j| \leq (inc_j-p_i) 的菜。问每个人最多能选几种菜。

参考大佬博客 https://blog.orzsiyuan.com/archives/Codeforces-1139F-Dish-Shopping/

扫描线+树状数组

首先必定要分类讨论去掉绝对值的。

{piincjsibiprefjincjpiprefjbiincjpi\begin{cases} p_i\le inc_j\le s_i\\ b_i-pref_j\le inc_j-p_i\\ pref_j-b_i\le inc_j-p_i\\ \end{cases}

化简得

{piincjsiincj+prefjbi+piprefjincjbipi\begin{cases} p_i\le inc_j\le s_i\\ inc_j+pref_j\ge b_i+p_i\\ pref_j-inc_j\le b_i-p_i\\ \end{cases}

(incj,prefj)(inc_j,pref_j) 看作一个坐标,则该点的横坐标在 [pi,si][p_i,s_i],且 bib_i 为纵轴上一点。则点 (incj,prefj)(inc_j,pref_j) 在图中黄色区域。

每个菜作为一个三角形区域,对其中的人(作为一个点)做出一点贡献。

所以要考虑扫描线遍历每种菜,当超过范围时撤销贡献,当进入范围时做出贡献。

由于是一个三角形区域,所以并不是对所有 [pi,si][p_i,s_i] 的点都作贡献。所以还要维护前缀和,利用上面化简得到的式子表示出三角形区间,树状数组维护前缀和,对每个三角形维护 bi+pib_i+p_ibipib_i-p_i 两个树状数组,进入时 bi+pi+=1b_i+p_i+=1bipi+1=1b_i-p_i+1-=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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
const int N = 4e5 + 10;
int n, m;
vector<int>vc;
int p[N], s[N], b[N], inc[N], pref[N], ans[N];
struct BIT
{
int sum[N], n;
int lowbit(int x) { return x & -x; }
void add(int p, int x) {
for (int i = p; i <= n; i += lowbit(i))sum[i] += x;
}
int qry(int r) {
int res = 0;
for (int i = r; i > 0; i -= lowbit(i))res += sum[i];
return res;
}
}b1, b2;
struct X
{
int p, x, y, op, id;
bool operator<(const X& b)const {
return p == b.p ? id < b.id : p < b.p;
}
};
vector<X>vv;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)scanf("%d", &p[i]);
for (int i = 1; i <= n; i++)scanf("%d", &s[i]);
for (int i = 1; i <= n; i++)scanf("%d", &b[i]);
for (int i = 1; i <= m; i++)scanf("%d", &inc[i]);
for (int i = 1; i <= m; i++)scanf("%d", &pref[i]);
for (int i = 1; i <= n; i++) {
vc.push_back(b[i] - p[i] + 1);
vc.push_back(b[i] + p[i]);
}
for (int i = 1; i <= m; i++) {
vc.push_back(inc[i] + pref[i]);
vc.push_back(pref[i] - inc[i]);
}
sort(vc.begin(), vc.end());
vc.erase(unique(vc.begin(), vc.end()), vc.end());
b1.n = b2.n = (int)vc.size();
for (int i = 1; i <= n; i++) {
vv.push_back(X{ p[i],b[i],p[i],1,0 });
vv.push_back(X{ s[i] + 1,b[i],p[i],-1,0 });
}
for (int i = 1; i <= m; i++) {
vv.push_back(X{ inc[i],inc[i],pref[i],0,i });
}
sort(vv.begin(), vv.end());
for (auto t : vv) {
if (t.id) {
int x = lower_bound(vc.begin(), vc.end(), t.x + t.y) - vc.begin() + 1;
int y = lower_bound(vc.begin(), vc.end(), t.y - t.x) - vc.begin() + 1;
ans[t.id] = b1.qry(x) + b2.qry(y);
}
else {
int x = lower_bound(vc.begin(), vc.end(), t.x + t.y) - vc.begin() + 1;
int y = lower_bound(vc.begin(), vc.end(), t.x - t.y + 1) - vc.begin() + 1;
b1.add(x, t.op); b2.add(y, -t.op);
}
}
for (int i = 1; i <= m; i++)printf("%d%s", ans[i], i == m ? "\n" : " ");
return 0;
}