CFR548

CFR548
题号开头为CF1139

A Even Substrings

B Chocolates

C Edgy Trees

直接看我的代码

D Steps to One

请先思考后再展开

这东西我复杂度算错了,好jb菜啊

显然是建出nlogn条边的dag,在dag上计算期望,然后主要是边权怎么求
$$
g(x,y)=\sum [gcd(x/y,i/y)=1]=\sum_{d|\frac{x}{y}} \mu(d)\lfloor \frac{m}{dy} \rfloor
$$
然后其实直接枚举约数计算就好了,根本不需要优化,我就说为什么放在E那个煞笔题前面

时间复杂度为 $O(nlogn 约数个数)$ 复杂度不满

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
vc<int> dd[MAX_N];
map<int,int> g[MAX_N];
int f[MAX_N];
void main()
{
pre();
int m=qread();
for(int d=1;d<=m;d++) for(int num=d;num<=m;num+=d) dd[num].PB(d);
for(int y=1;y<=m;y++) for(int x=y;x<=m;x+=y)
{
int now=0;
for(int t=0;t<(int)dd[x/y].size();t++)
{
int d=dd[x/y][t];
add(now,mu[d]*(m/d/y));
}
g[x][y]=(ll)now*inv(m)%MOD;
}
f[1]=0;int ans=1;
for(int x=2;x<=m;x++)
{
f[x]=1;
for(int t=0;t<(int)dd[x].size();t++)
{
int y=dd[x][t];if(y==x) continue;
add(f[x],(ll)f[y]*g[x][y]%MOD);
}
f[x]=f[x]*inv(1-g[x][x])%MOD;
add(ans,(ll)f[x]*inv(m)%MOD);
}
write((ans+MOD)%MOD);
}

E Maximize Mex

请先思考后再展开

直接网络流

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define double long double
const int INF=0x3f3f3f3f;
const ll LLINF=0x3f3f3f3f3f3f3f3fll;
ll qread()
{
ll ans=0;char c=getchar();int f=1;
while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans*f;
}
void write(ll num)
{
if(num<0) {num=-num;putchar('-');}
if(num>9) write(num/10);
putchar('0'+num%10);
}
void write1(ll num){write(num);putchar(' ');}
void write2(ll num){write(num);puts("");}
#define FR first
#define SE second
#define MP make_pair
#define pr pair<ll,ll>
#define PB push_back
#define vc vector
void chmax(int &x,const int y) {x=x>y?x:y;}
void chmin(int &x,const int y) {x=x<y?x:y;}
const int MAX_N=5e3+10;
const ll MOD=998244353;
void add(ll &x,ll y){x+=y;if(x>=MOD) x-=MOD;if(x<=-MOD) x+=MOD;}
ll qpower(ll x,ll e)
{
ll ans=1;x%=MOD;
while(e)
{
if(e&1) ans=ans*x%MOD;
x=x*x%MOD;e>>=1;
}
return ans;
}
ll inv2(ll x){return qpower(x,MOD-2);}
int hou[MAX_N*2];
struct Edge{int y,c,g;}e[MAX_N*10];
int ln;int oth(int x){return x&1?x+1:x-1;}
void ins(int x,int y)
{
e[++ln]=(Edge){y,1,hou[x]};hou[x]=ln;
e[++ln]=(Edge){x,0,hou[y]};hou[y]=ln;
}
int st,ed;
int h[MAX_N*2],cur[MAX_N*2];queue<int> q;
bool bfs()
{
// memset(cur,0,sizeof cur);
memcpy(cur,hou,sizeof hou);
memset(h,0,sizeof h);
h[st]=1;q.push(st);
while(q.size())
{
int x=q.front();q.pop();
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(h[y]==0 and e[k].c>0) h[y]=h[x]+1,q.push(y);
}
}
return h[ed]>0;
}
int dfs(int x,int ff)
{
if(x==ed) return ff;
int flow=0;
for(int k=cur[x];k>0;k=e[k].g)
{
int y=e[k].y;
if(h[y]==h[x]+1 and e[k].c>0)
{
int out=dfs(y,min(e[k].c,ff-flow));
e[k].c-=out;e[oth(k)].c+=out;flow+=out;
}
if(e[k].c==0) cur[x]=e[k].g;
if(flow==ff) break;
}
if(ff==0) h[x]=0;
return flow;
}
int now=0;
void update()
{
while(bfs()) now+=dfs(st,INF);
}
pr a[MAX_N];int ban[MAX_N];bool vis[MAX_N];
int ans[MAX_N];
void main()
{
int n=qread(),m=qread();st=5000+m+2;ed=5000+m+1;
for(int i=1;i<=n;i++) a[i].FR=qread();
for(int i=1;i<=n;i++) a[i].SE=qread();
int dd=qread();for(int i=1;i<=dd;i++) ban[i]=qread(),vis[ban[i]]=1;
for(int i=1;i<=m;i++) ins(5000+i,ed);
for(int i=1;i<=n;i++) if(!vis[i]) ins(a[i].FR,5000+a[i].SE);
int wt=0;ins(st,wt);
for(int i=dd;i>=1;i--)
{
update();
while(now==wt+1) wt++,ins(st,wt),update()/*,printf("i=%d wt=%d\n",i,wt)*/;
ans[i]=wt;
int x=ban[i];ins(a[x].FR,5000+a[x].SE);
}
for(int i=1;i<=dd;i++) write2(ans[i]);
}
};
signed main()
{
srand(time(0));
mine::main();
}

F Dish Shopping

请先思考后再展开

看到允许log方就写的log方
$p_i \leq inc_j \leq s_i,|pref_j-b_i| \leq inc_j-p_i$
然后有个套路,看到这里是点取出所有覆盖自己的区间恰好一次,可以把区间放到线段树上,然后单点询问取出区间
相当于是log个区间、log个点,离线后对每个线段树点直接两次cdq即可

然后log的做法也是有的,观察发现每道菜就是一个三角形,如果在pi处加入si处删除,按横坐标顺序处理三角形和询问
把拆分为上直线和下直线,要求是在上直线之下或者在下直线之上,注意到至少满足一个,分别求然后就是A+B-nowline
可以开两棵bit维护,复杂度为 O(nlogn)

code为log方的

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
const int N=2e6+10;
pr all[N];int ans[N];pr tmp[N];
bool cmp1(pr a,pr b){return all[a.FR].SE<all[b.FR].SE or (all[a.FR].SE==all[b.FR].SE and a.SE<b.SE);}
struct CDQ
{
vc<pr> qq;//(id,op),op=1为询问
bool cmp(pr a,pr b,int op){return a.FR+a.SE*op<=b.FR+b.SE*op;}
void cdq(int l,int r,int op)
{
if(l>=r) return;
cdq(l,mid,op);cdq(mid+1,r,op);
int now=l,j=l-1;
for(int i=mid+1,add=0;i<=r;i++)
{
while(j+1<=mid and cmp(all[qq[j+1].FR],all[qq[i].FR],op)) j++,tmp[now++]=qq[j],add+=(qq[j].SE==0);
tmp[now++]=qq[i];if(qq[i].SE) ans[qq[i].FR]+=add;
}
while(now<=r) tmp[now++]=qq[++j];
for(int i=l;i<=r;i++) qq[i]=tmp[i];
}
void solve()
{
int n=qq.size();
sort(qq.begin(),qq.end(),cmp1);cdq(0,n-1,-1);
sort(qq.begin(),qq.end(),cmp1);reverse(qq.begin(),qq.end());cdq(0,n-1,1);
}
}cdq[N];
void modify(int x,int l,int r,int fl,int fr,int id)
{
if(l==fl and r==fr) {cdq[x].qq.PB(MP(id,0));return;}
if(fr<=mid) modify(lc,l,mid,fl,fr,id);
else if(fl>mid) modify(rc,mid+1,r,fl,fr,id);
else modify(lc,l,mid,fl,mid,id),modify(rc,mid+1,r,mid+1,fr,id);
}
void ask(int x,int l,int r,int pos,int id)
{
cdq[x].qq.PB(MP(id,1));
if(l==r) return;
if(pos<=mid) ask(lc,l,mid,pos,id);
else ask(rc,mid+1,r,pos,id);
}
int fl[N],fr[N],lsh[N];int getnum(int cnt,int num){return lower_bound(lsh+1,lsh+cnt+1,num)-lsh;}
void main()
{
int n=qread(),m=qread();
for(int i=1;i<=n;i++) fl[i]=qread(),lsh[i]=fl[i];
for(int i=1;i<=n;i++) fr[i]=qread(),lsh[n+i]=fr[i];
for(int i=1;i<=n;i++) all[m+i]=MP(fl[i],qread());
for(int i=1;i<=m;i++) lsh[2*n+i]=all[i].FR=qread();
for(int i=1;i<=m;i++) all[i].SE=qread();
sort(lsh+1,lsh+n+n+m+1);
for(int i=1;i<=n;i++) modify(1,1,n+n+m,getnum(n+n+m,fl[i]),getnum(n+n+m,fr[i]),m+i);
for(int i=1;i<=m;i++) ask(1,1,n+n+m,getnum(n+n+m,all[i].FR),i);
for(int i=1;i<N;i++) cdq[i].solve();
for(int i=1;i<=m;i++) write1(ans[i]);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/9890.html
转载请注明出处,谢谢!