算法学习

写的题

20221020

沈阳ICPC 2019

L

感觉像铜牌题

完全图中剔除一棵树,询问剩下的图存在多少种边为n的匹配,很容易想到容斥,并且只剔除了一颗树,剩下的一定可以在剩下子图中匹配。

考虑 fi,j,0/1f_{i,j,0/1} 表示以 ii 为根的子树中包含 kk 种匹配的方案数,那么显然有一个树形背包的转移方式。

1
2
3
g[k+l][0]=(g[k+l][0]+1ll*f[x][k][0]*(f[j][l][1]+f[j][l][0]))%modp;
g[k+l][1]=(g[k+l][1]+1ll*f[x][k][1]*(f[j][l][1]+f[j][l][0]))%modp;
g[k+l+1][1]=(g[k+l+1][1]+1ll*f[x][k][0]*f[j][l][0])%modp;

根据容斥原理,总的方案数即为

ans=i=0n(1)nf1,i,0/1ans=\sum_{i=0}^{n}\limits(-1)^n{f_{1,i,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
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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=4040;
const int modp=998244353;

int f[maxn][maxn][2];
int n,s1ze,head[maxn],sz[maxn];
int inv[maxn],p[maxn],_2n[maxn];
int ans,g[maxn][2];

struct edge{
int next,to;
}e[maxn*2];

void addedge(int next,int to)
{
e[++s1ze].to=to;
e[s1ze].next=head[next];
head[next]=s1ze;
}

int ksm(int x,int y)
{
int ans=1,z=y;
while(z)
{
if(z&1) ans=(ans*y)%modp;
ans=(ans*ans)%modp;
}
return ans;
}

void getsz(int x,int fat)
{
sz[x]=1;
f[x][0][0]=1;
for(int i=head[x];i;i=e[i].next)
{
int j=e[i].to;
if(j==fat) continue;
getsz(j,x);
for(int k=0;k<=(sz[x]+sz[j])/2;k++) g[k][1]=g[k][0]=0;
for(int k=sz[x]/2;k>=0;k--)
{
for(int l=0;l<=sz[j]/2;l++)
{
g[k+l][0]=(g[k+l][0]+1ll*f[x][k][0]*(f[j][l][1]+f[j][l][0]))%modp;
g[k+l][1]=(g[k+l][1]+1ll*f[x][k][1]*(f[j][l][1]+f[j][l][0]))%modp;
g[k+l+1][1]=(g[k+l+1][1]+1ll*f[x][k][0]*f[j][l][0])%modp;
}
}
sz[x]+=sz[j];
for(int k=0;k<=sz[x]/2;k++)
{
f[x][k][1]=g[k][1],f[x][k][0]=g[k][0];
}
};
int tmp=1;
}

int C(int x,int y)
{
return (((1ll*p[y]*inv[x])%modp)*inv[y-x])%modp;
}

int main()
{
ios::sync_with_stdio(false);
cin>>n;
n*=2;
int t1,t2;
for(int i=1;i<n;i++)
{
cin>>t1>>t2;
addedge(t1,t2);
addedge(t2,t1);
}
p[0]=1;
_2n[0]=1;
inv[0]=1; inv[1]=1;
for(int i=1;i<=n;i++) p[i]=(1ll*p[i-1]*i)%modp;
for(int i=2;i<=n;i++) inv[i]=1ll*(modp-modp/i)*inv[modp%i]%modp;
for(int i=1;i<=n;i++) _2n[i]=(1ll*_2n[i-1]*inv[2])%modp;
for(int i=1;i<=n;i++) inv[i]=(1ll*inv[i-1]*inv[i])%modp;
// addedge(0,1);
getsz(1,0);
n/=2;
for(int i=0;i<=n;i++)
{
long long tmp=(f[1][i][0]+f[1][i][1]);
tmp=(tmp*C((n-i),(n-i)*2))%modp;
tmp=(tmp*p[n-i])%modp;
tmp=(tmp*_2n[n-i])%modp;
if(i&1) tmp=modp-tmp;
ans=(ans+tmp)>=modp?ans+tmp-modp:ans+tmp;
}
cout<<ans<<endl;
// dfs(1,1);
// cout<<f[0][n/2];
}

H

银牌题

前置芝士: 线图

题目大意:给定 G{V,E}G \{V,E\} ,询问线图的顶点匹配最大值,匹配的边的边权为原来图上两边边权和

显然,线图的匹配在原图即为两条相邻的边的匹配。

那么,如果边数为偶数,答案显然是所有边权之和。

如果为奇数,只需要删去一条边,但是如果这条边是割边,并且两个连通子图边数都为奇数,说明不用删,一定有更优解,因为接下来两个子图还要找到最小边删除,但是我们可以直接删除最小边,(如果最小边还是割边,那么两边都要递归下去,因此可以说明这种割边一定不是最优方案。

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=400200;

int a[maxn*2],n,m;
int sz[maxn],dep[maxn],f[maxn];
int bj[maxn],s1ze=1,head[maxn];
long long ans;

struct edge{
int next,to,dis;
}e[maxn*2];

void addedge(int next,int to,int dis)
{
e[++s1ze].to=to;
e[s1ze].next=head[next];
e[s1ze].dis=dis;
head[next]=s1ze;
}

void dfs(int t,int fat)
{
dep[t]=dep[fat]+1;
int looker=0;
for(int i=head[t];i;i=e[i].next)
{
int j=e[i].to;
if(j==fat)
{
looker=i;
continue;
}
if(dep[j])
{
if(dep[t]<dep[j]) f[t]--; \\dfs找割边,可以证明一定不存在depj和depi相等的情况
else if(dep[t]>dep[j]) sz[j]++,f[t]++; \\f表示返祖边的个数
}
else
{
dfs(j,t);
f[t]+=f[j];
sz[t]+=sz[j]+1;
}
}
if(t!=1&&(sz[t]%2==1)&&!f[t]) bj[looker]=1,bj[looker^1]=1;
}

int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int t1,t2,t3;
cin>>t1>>t2>>t3;
addedge(t1,t2,t3);
addedge(t2,t1,t3);
ans+=t3;
}
if(m%2==0)
{
cout<<ans<<endl;
return 0;
}
dfs(1,1);
long long looker=ans;
ans=0;
for(int i=2;i<=s1ze;i++)
{
if(!bj[i]) ans=max(ans,looker-e[i].dis);
}
cout<<ans<<endl;
}


CF1730B

每个人分别在坐标轴的 aia_i 位置,现在他们希望集合,每个人打扮时间 bib_i 求哪里集合他们最快。

显然,可以二分集合时间,此时检查函数就变成维护一个区间 [l,r][l,r]

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=100100;

int n,T,a[maxn],b[maxn];
double lasans=0;

int check(double tmp)
{
const double eps=1e-7;
double l=0,r=1e9;
for(int i=1;i<=n;i++)
{
if(tmp-b[i]<eps) return 0;
l=max(l,a[i]-(tmp-b[i]));
r=min(r,a[i]+(tmp-b[i]));
if(r-l<eps) return 0;
}
lasans=l;
return 1;
}

void getans()
{
if(n==1)
{
cout<<a[1]<<endl;
return ;
}
double l=0,r=1e9,mid;
double ans=0;
const double eps=1e-7;
while(r-l>eps)
{
mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid;
else l=mid;
}
printf("%.6lf\n",lasans);
// cout<<lasans<<endl;
}

int main()
{
// ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
getans();
}
}

20221022

前言

今天写了三道题,很菜的一天

Educational Codeforces Round 138 (Rated for Div. 2)

C

题目大意:给你一个数组 aa ,你需要找到一个最大的 kk 满足:

在第 ii 次中能够找到 aa 中小于 ki+1k-i+1 的一个数 aja_j 删去它,并且将另外一个数字加上 ki+1k-i+1 ,总共进行 kk

分析,k+1k+1 的能够做的轮数时候一定不小于 k+1k+1 ,因此是个单调的,可以二分 kk

并且,对每轮选择的数字,一定是选择最小的,将其加上 ki+1k-i+1 最优,删除最接近 ki+1k-i+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<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=220;

int n,T;
int a[maxn],b[maxn];

int getplace(int x)
{
int l,r,mid,ans;
l=1,r=n,ans=n;
while(l<=r)
{
mid=(l+r)>>1;
if(b[mid]<=x) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}

int check(int x)
{
if(x==0) return 1;
for(int i=1;i<=n;i++) b[i]=a[i];
sort(b+1,b+n+1);
for(int i=1;i<=x;i++)
{
int target=getplace(x-i+1);
if(b[target]>x-i+1) return 0;
b[target]=0x3f3f3f3f;
if(target!=1) b[1]+=x-i+1;
sort(b+1,b+n+1);
}
return 1;
}

void getans()
{
int l,r,ans,mid;
l=0,r=n;
while(l<=r)
{
mid=(l+r)>>1;
if(check(mid)) l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans<<endl;
}

int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
getans();

}
}

D

题目大意: 一个序列 aa ,如果可以它的下标 ii 满足,gcd(ai,i)=1\gcd(a_i,i)=1 那么 ii 号位置的数就是可删除的,删除ii 之后右边的数下标都要 1-1 , 一个数组一定可以存在一个删除序列,现在需要你找到长度不多于 nn ,值域在 [1,m][1,m] 范围内,满足删除序列不多于一种的序列个数

正难则反,考虑一共有 i=1nmi\sum_{i=1}^{n}\limits m^i 个序列,在考虑只有一种的序列,显然这个第 ii 位的数满足是前面下标 lcm\text{lcm} 的倍数,换句话说记 [1,i][1,i] 的素数积为 primeiprime_i ,答案即为i=1nmii=1nΠmprimei\sum_{i=1}^{n}\limits m^i - \sum_{i=1}^{n}\limits\Pi{\lfloor \frac{m}{prime_i}\rfloor}

另外需要显著注意一点是,这个是整数除法,没法用逆元(也不是没法,但是不是单独除过去)

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<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=1e6+10;
const long long modp=998244353;

long long n,m,ans;
int is_prime[maxn];
long long m0;
int p[maxn],cnt;

void getprime(int x)
{
is_prime[1]=1;
for(int i=2;i<=n;i++)
{
if(!is_prime[i]) p[++cnt]=i;
for(int j=1;j<=cnt&&i*p[j]<=n;j++)
{
is_prime[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}

int ksm(long long x,long long y)
{
long long ans=1;
while(y)
{
ans=(1ll*ans*ans)%modp;
if(y&1) ans=(1ll*ans*x)%modp;
y>>=1;
}
return ans;
}

int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
if(n==1&&m==1)
{
cout<<1<<endl;
return 0;
}
m0=m;
getprime(n);
m%=modp;
long long tmp=m;
for(int i=1;i<=n;i++)
{
ans=(ans+tmp)%modp;
tmp=(tmp*m)%modp;
}
// tmp=1;
long long looker=1;
tmp=1;
for(int i=1;i<=n;i++)
{
if(!is_prime[i]&&looker<=m0) looker=(looker*i);
tmp=tmp*((m0/looker)%modp)%modp;
// tmp=1ll*tmp*(m*ksm(looker,modp-2)%modp)%modp;
ans=(modp+ans-tmp)%modp;
}
cout<<ans<<endl;
}

Codeforces Round #822 (Div. 2)

D

大意: 你是一坨史莱姆,在 kk 位置 ,每次你需要向左走或者向右走,代价是你的质量会减少 aia_i (假如你去了 ii 位置 ) ,你需要保证你的质量不是负数,你需要走到 00 或者 n+1n+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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=2e5+10;

int n,a[maxn],s[maxn];
int k,T;

void solve()
{
memset(s,0,sizeof(s));
for(int i=k-1; i>=1; i--) s[i]=s[i+1]+a[i];
for(int i=k+1; i<=n; i++) s[i]=s[i-1]+a[i];
int nowl,nowr,nxtl,nxtr;
int sl,sr;
sl=sr=a[k];
nowl=nowr=k;
nxtl=nxtr=k;
if(sl<0)
{
cout<<"NO"<<endl;
return ;
}
for(; nxtl>=1&&nxtr<=n;)
{
nowl=nxtl;
nowr=nxtr;
while(sr+s[nxtl]>=0&&nxtl>=1) sl=max(sl,a[k]+s[nxtl]),nxtl--;
while(sl+s[nxtr]>=0&&nxtr<=n) sr=max(sr,a[k]+s[nxtr]),nxtr++;
if(nxtl==nowl&&nxtr==nowr)
{
cout<<"NO"<<endl;
return ;
}
}
cout<<"YES"<<endl;
return ;
}

signed main() {
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
solve();
}
}

20201023~20201024 训练

前言 打了一场 cf ,fst 到了只 A 了 2A,2B

Codeforces Round #829 (Div. 2)

A

给你一段包含 Q,AQ,A 的字符串,并且以 QQ 开始,每个QQ 必须对应一个或者多个 AA ,询问这个字符串是否合法,每个 AA 仅能对应一个 QQ

显然,贪心,每个QQ 对对应一个 AA 然后第一个再对应剩下的即可。

B

询问长度为 nn 的排列,使得 $\min|p_i-p_{i+1}| 1\leq i< n $

显然答案是 n2\lfloor \frac{n}{2}\rfloor

1
2
if(n%2==1) cout<<n<<" ",n--;
for(int i=1;i<=n/2;i++) cout<<i+n/2<<" "<<i<<" ";

C

给定一个仅包含 0,±10,\pm1 序列,定义一个区间的值为 pl,r=i=lr(1)ilaip_{l,r}=\sum_{i=l}^{r}\limits(-1)^{i-l}a_i

如何划分这个区间,使得区间的值和为 00

记录所有数的和为 totaltotal 如果它为 00 答案就输出 nn[i,i][i,i]

如果它是奇数,显然无解

如果它是偶数,假设当时 11 多了,只要之前是 1,1,0-1,1,0 任意一种,把区间合并成 [i1,i][i-1,i] 就可以让 11 的个数少 11 ,同时让 1-111 , 显然可以这样操作使得答案成为 00

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=600100;

int n,T;
int a[maxn],tot;

int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
tot=0;
for(int i=1;i<=n;i++) cin>>a[i],tot+=a[i];
if(tot&1)
{
cout<<"-1"<<endl;
continue;
}
if(tot<0)
{
cout<<n+tot/2<<endl;
for(int i=1;i<=n;i++)
{
if(tot<0&&a[i+1]==-1) cout<<i<<" "<<i+1<<endl,tot+=2,i++;
else cout<<i<<" "<<i<<endl;
}
}
else if(tot>0)
{
cout<<n-tot/2<<endl;
for(int i=1;i<=n;i++)
{
if(tot>0&&a[i+1]==1) cout<<i<<" "<<i+1<<endl,tot-=2,i++;
else cout<<i<<" "<<i<<endl;
}
}
else if(tot==0)
{
cout<<n<<endl;
for(int i=1;i<=n;i++) cout<<i<<" "<<i<<endl;
}
}
}

D

给你 nn 个数字和 mm ,询问这 nn 个数字阶乘之和能否被 m!m! 整除

设当前有 aia_iii 显然每 i+1i+1 个数可以合并并且使 ai+1+1a_{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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=600100;

int T,n,m;
int tot1,totz;
int a[maxn],modp,cnt;
int sz[maxn];

int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i],sz[a[i]]++;
sort(a+1,a+n+1);
int looker=1;
for(int i=1;i<=m;i++) if(sz[i]>i) sz[i+1]+=sz[i]/(i+1),sz[i]%=(i+1);
for(int i=1;i<m;i++) if(sz[i]>=1) looker=0;
if(looker) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}

E

题目大意,给你一个 0101 序列,每次随机交换,询问期望排列从小到大有序的次数交换 ($\mod p $ 意义下)

记这个序列有 kk00

正难则反,考虑一个动态规划, fif_i 表示前面 kk 个数字中又 ii00 的期望操作数,那么显然的,我们可以倒过来写一个期望

假设前 kk 个数中 11 与后面 nkn-k 个数中 00 交换的概率是 pp,假设当前前kk 个数中有 ii11

p=(ki)(ki)Cn2p=\frac{(k-i)*(k-i)}{C_{n}^{2}}

第一个 kik-i 的意义是前面的 11 的个数,第二个的意义是后面的 00 的个数

fi=pfi+1+(ip)fif_i=p*f_i+1+(i-p)*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
57
58
59
60
61
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=600100;
const int modp=998244353;

int n,T;
int a[maxn];
int f[maxn];

int ksm(int x,int y)
{
int ans=1;
while(y)
{
if(y&1) ans=(1ll*ans*x)%modp;
x=(1ll*x*x)%modp;
y>>=1;
// cout<<x<<endl;
}
return ans;
}

void solve()
{
int cnt=0,ccnt=0;
for(int i=1;i<=n;i++) cnt+=!a[i];
for(int i=1;i<=cnt;i++) ccnt+=!a[i];
memset(f,0,sizeof(f));
f[cnt]=0;
// cout<<ksm(2,modp-1)<<endl;
for(int i=cnt-1;i>=ccnt;i--)
{
int p=(2ll*(cnt-i)*(cnt-i))%modp*(ksm(1ll*n*(n-1)%modp,modp-2))%modp;
f[i]=1ll+1ll*f[i+1]*p%modp;
f[i]=1ll*f[i]*ksm(p,modp-2)%modp;
}
cout<<f[ccnt]<<endl;
}

int main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
solve();
}
}

830

C1

菜鸡只会 C1\text{C1}

给定一个序列,定义 fl,r=i=lraialal+1...arf_{l,r}=\sum^{r}_{i=l}\limits a_i-a_l \oplus a_{l+1}\oplus ... \oplus a_r

有一个十分显然的的是,rr 增大,这个函数单调不下降。

我们能不能找到这个单调不下降的最大次数?

很感性的猜想的 log\log 级别

以为我们把每个数字二进制拆分,如果最后 kk 个数字在二进制下面没有交集,那么 fl,rf_{l,r} 不会变,显然,这个是 logC\log C 级别,CC 为值域

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=200100;

int s[maxn],x[maxn];
int n,a[maxn];
int T,q,ans,ansl,ansr;
int qz[maxn],cnt;
int f[maxn];

signed main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
cin>>n>>q; ans=0;
memset(s,0,sizeof(s));
memset(x,0,sizeof(x));
// memset(f,0,sizeof(f));
cnt=0;
int ansl,ansr,anslen=0;
int tsum=0,txor=0;
for(int i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i],x[i]=x[i-1]^a[i];
qz[++cnt]=1;
for(int i=2;i<=n;i++)
{
if(a[i]) qz[++cnt]=i;
else if(a[i-1]) qz[++cnt]=i;
else if(a[i+1]) qz[++cnt]=i;
// if(!a[i]&&a[qz[cnt]]) qz[++cnt]=i;
}
int looker=cnt;
for(int i=n;i;i--)
{
if(qz[looker]>i) looker--;
f[i]=looker;
}
for(int i=1;i<=q;i++)
{
int l,r;
ans=0;
cin>>l>>r;
ansl=l;ansr=r;
int rr=f[r]-1;
if(qz[f[r]]<=r) rr++;
// if(a[r+1]|a[r]|a[max(r-1,l)]) rr++;
int rl=f[l];
for(int i=rl;i<=min(rr,rl+120);i++)
for(int j=rr;j>=max(rl,rr-120)&&j>=i;j--)
{
int ii=qz[i],jj=qz[j];
int tmpans=s[jj]-s[ii-1]-(x[jj]^x[ii-1]);
if(tmpans>ans)
{
ans=tmpans;
ansl=ii,ansr=jj;
anslen=jj-ii+1;
}
else if(tmpans==ans&&jj-ii<ansr-ansl)
{
ansl=ii,ansr=jj;
anslen=jj-ii+1;
}
}
cout<<ansl<<" "<<ansr<<endl;
}
}
}

但是 C2\text{C2} 我还不会,可见我菜爆了

20221026

Educational Codeforces Round 129 (Rated for Div. 2)

F

题目大意,询问所有点对的路径中,边的只有一种权值数量的和。

显然,对于边权为 xx 的边,我们先把这个树的这些边断掉,形成一个森林,然后这条边的贡献就是与之相连的两条树的个数之积。

我们需要运用并查集按秩合并,每次并查集的复杂度是 O(logn)O(\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
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
139
140
141
142
143
144
145
146
147
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=500500;

struct edge{
int x,y,dis;
bool operator <(const edge &b)
{
return dis<b.dis;
}
}e[maxn];

int n;
int looker[maxn];
int st[maxn];
long long ans;

struct dsu{

struct status{
int x,y;
int fx,fy;
int six,siy;
}q[maxn];

int f[maxn],sz[maxn];

void st()
{
for(int i=1;i<=n;i++)
{
f[i]=i,sz[i]=1;
}
}

void werge(int i)
{
int x=e[i].x;
int y=e[i].y;
int tx=x,ty=y;
while(f[tx]!=tx) tx=f[tx];
while(f[ty]!=ty) ty=f[ty];
q[i].x=x; q[i].y=y;
q[i].fx=tx,q[i].fy=ty;
q[i].six=sz[tx],q[i].siy=sz[ty];
if(sz[tx]>sz[ty])
{
f[ty]=tx;
sz[tx]+=sz[ty];
}
else
{
f[tx]=ty;
sz[ty]+=sz[tx];
}
}

void inwerge(int i)
{
int x=e[i].x;
int y=e[i].y;
f[q[i].fx]=q[i].fx;
f[q[i].fy]=q[i].fy;
sz[q[i].fx]=q[i].six;
sz[q[i].fy]=q[i].siy;
}

int _find(int x)
{
while(x!=f[x]) x=f[x];
return sz[x];
}

}msu;

void dfs(int l,int r)
{
if(l==r)
{
if(!looker[l]) return ;
int x,y;
for(int i=st[l];;i++)
{
if(e[i].dis>l) return ;
x=msu._find(e[i].x);
y=msu._find(e[i].y);
ans+=1ll*x*y;
}
return ;
}
int mid;
mid=(l+r)>>1;
int lasi=0;
for(int i=st[mid+1];;i++)
{
if(e[i].dis>r) break ;
lasi=i;
msu.werge(i);
}
dfs(l,mid);
for(int i=lasi;i>=st[mid+1];i--)
{
if(e[i].dis>r) break ;
msu.inwerge(i);
}
for(int i=st[l];;i++)
{
if(e[i].dis>mid) break ;
lasi=i;
msu.werge(i);
}
dfs(mid+1,r);
for(int i=lasi;i>=st[l];i--)
{
if(e[i].dis>mid) break ;
msu.inwerge(i);
}
}

int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<n;i++)
{
cin>>e[i].x>>e[i].y>>e[i].dis;
looker[e[i].dis]=1;
}
sort(e+1,e+n);
e[n].dis=0x3f3f3f3f;
msu.st();
for(int i=1;i<n;i++) st[e[i].dis]=st[e[i].dis]?st[e[i].dis]:i;
for(int i=n;i;i--) if(!st[i]) st[i]=st[i+1];
dfs(1,e[n-1].dis);
cout<<ans<<endl;
}

感觉这段代码有一点麻烦,应该不需要一个分治过程。

20221027

前言

今天写了三道题,终于不那么摆了

看到神仙在打派,于是在qq群疯狂膜拜,然后过一分钟撤回美滋滋

P8710 [蓝桥杯 2020 省 AB1] 网络分析

题目描述

小明正在做一个网络实验。

他设置了 nn 台电脑,称为节点,用于收发和存储数据。

初始时,所有节点都是独立的,不存在任何连接。

小明可以通过网线将两个节点连接起来,连接后两个节点就可以互相通信了。两个节点如果存在网线连接,称为相邻。

小明有时会测试当时的网络,他会在某个节点发送一条信息,信息会发送到每个相邻的节点,之后这些节点又会转发到自己相邻的节点,直到所有直接或间接相邻的节点都收到了信息。所有发送和接收的节点都会将信息存储下来。一条信息只存储一次。

给出小明连接和测试的过程,请计算出每个节点存储信息的大小。

分析

观察到正向很难做,考虑反向操作,就是昨天那个可撤销并查集模板题

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=100100;

struct que{
int opt,x,y,k;
}q[maxn];

int n,m,lazy[maxn];
int f[maxn],sz[maxn];

struct dsu{

struct hisopt
{
int x,y;
int sizx,sizy;
int looker;
}h[maxn];

void getf()
{
for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
for(int i=1;i<=m;i++) h[i].looker=1;
}

void werge(int i)
{
int x=q[i].x;
int y=q[i].y;
while(x!=f[x]) x=f[x];
while(y!=f[y]) y=f[y];
if(x==y)
{
h[i].looker=0;
return ;
}
h[i].x=x; h[i].sizx=x;
h[i].y=y; h[i].sizy=y;
if(sz[x]>sz[y]) f[y]=x,sz[x]+=sz[y];
else f[x]=y,sz[y]+=sz[x];
}

void adtg(int i,int t)
{
int x=q[i].x;
while(x!=f[x]) x=f[x];
lazy[x]+=t;
return ;
}

int fd(int x)
{
while(x!=f[x]) x=f[x];
return x;
}

void inwerge(int i)
{
if(!h[i].looker) return ;
int x=h[i].x,y=h[i].y;
if(sz[x]<sz[y]) swap(x,y);
lazy[y]+=lazy[x];
f[y]=y;
sz[x]-=sz[y];
}

}dsu;

int main()
{
ios::sync_with_stdio(false);
int x,y,opt;
cin>>n>>m;
dsu.getf();
for(int i=1;i<=m;i++)
{
cin>>q[i].opt>>q[i].x>>q[i].y;
if(q[i].opt==1) dsu.werge(i);
}
for(int i=m;i;i--)
{
if(q[i].opt==1) dsu.inwerge(i);
else dsu.adtg(i,q[i].y);
}
for(int i=1;i<=n;i++)
{
cout<<lazy[dsu.fd(i)]<<" ";
}
return 0;
}

CF Round 830 DIV2

D

大意,给你一个只有 00 的序列,你需要维护这个序列:

1.插入一个数

2.删除一个数

3.询问 kk 的倍数中,最小的不在这个序列的数是多少

先考虑一个简单版本,只插入和询问

显然,对于同一个 kk ,每次答案单调不下降,因此只需要记录 kk 上一次的答案,这次从上开始查找即可

考虑复杂度的正确性,假设我们有 1,2,3,...,n1,2,3,...,n 这个数列,如果想让他们移动次数最多,就需要 1,2,3,4,5..n1,2,3,4,5..n 这样插入,复杂度即为调和级数,~三江方士证明它收敛 ,即为 O(nlogn)O(n\log n)

那么如果有删除呢,我们只需要考虑当当前这个数字曾经对那些没有产生贡献,显然根据上面的结论,它的因子个数(产生过影响的)也是 O(logn)O(\log n) 级别的,因此依旧大力维护即可。

UPD\color{red} UPD 第二问不能用平均复杂度来证明,因为一旦找到一个数,可以不断插入删除,比如 22222333333=233282*2*2*2*2*3*3*3*3*3*3=23328 ,它的因子有 log2n\log ^2 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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=100100;

set <long long> s;
map <long long ,int > mp;
map <long long ,set<long long> > ms;
map <long long ,vector<long long> > primenum;

int n;

int main()
{
ios::sync_with_stdio(false);
cin>>n;
char opt;
long long x;
for(int i=1;i<=n;i++)
{
cin>>opt>>x;
if(opt=='+')
{
for(auto &pi: primenum[x])
{
ms[pi].erase(x/pi);
}
s.insert(x);
}
if(opt=='-')
{
for(auto &pi:primenum[x])
{
ms[pi].insert(x/pi);
}
s.erase(x);
}
if(opt=='?')
{
if(ms[x].empty())
{
while(s.find((mp[x]+1)*x)!=s.end())
{
primenum[(mp[x]+1)*x].push_back(x);
mp[x]++;
}
cout<<(1ll*mp[x]+1)*x<<endl;
}
else cout<<(1ll*x*(*ms[x].begin()))<<endl;
}
}
}

Educational Codeforces Round 136 (Rated for Div. 2)

D

给定一棵树,你可进行一下操作 kk

断掉一条边,将不与根相连的那部分接到根上面,根深度为 00 ,询问最后树的深度

这是一个很显然的二分加上 dfs\text{dfs} ,每次二分最大深度

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<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

const int maxn=200100;

struct edge{
int next,to;
}e[maxn];

int s1ze,head[maxn];
int dep[maxn],n,k,T;
int cutcnt,dm;

void addedge(int next,int to)
{
e[++s1ze].to=to;
e[s1ze].next=head[next];
head[next]=s1ze;
}

void dfs(int t)
{
dep[t]=1;
for(int i=head[t];i;i=e[i].next)
{
int j=e[i].to;
dfs(j);
if(dep[j]>=dm&&t!=1) cutcnt++;
else dep[t]=max(dep[t],dep[j]+1);
}
}


void solve()
{
int l=1,r=n,ans=0,mid;
while(l<=r)
{
memset(dep,0,sizeof(dep));
mid=(l+r)>>1;
cutcnt=0;
cutcnt=0; dm=mid;
dfs(1);
if(cutcnt<=k) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<endl;
}

int main()
{
cin>>T;
while(T--)
{
memset(head,0,sizeof(head));
s1ze=0;
cin>>n>>k;
int t1;
for(int i=2;i<=n;i++)
{
cin>>t1;
addedge(t1,i);
}
solve();
}
}

20221029

今天 cf 大大大大大大大大大大大坐牢

突然想到,cf 的题目格式我还得改改,例如下面这种

CF 1733 D Zero-One

题目大意,给你一个两个 0101 序列 a,ba,b 定义操作change(l,r) 为吧 al=1al,ar=1ara_l=1-a_l,a_r=1-a_r

change(l,r)={xrl=1yrl1\text{change(l,r)}=\begin{cases}x &r-l=1\\ y &r-l\neq1\end{cases}

询问将 aa 序列变成 bb 序列的最小价值,如果不能实现,输出 -1

每次操作显然可以让两个不同的地方变成相同的地方,如果有奇数个下标不同,说明无法实现,输出 -1 即可。

很显然的,全部进行 yy 操作的次数肯定比全部进行 xx 操作次数第,如果,如果 y<xy<x 显然全部进行 yy 操作,这也是 $ \text{easy}$ 的解法。

否者我们考虑一个 dp,设 fi,jf_{i,j} 表示 [i,j][i,j] 个不同的点位全部操作完成的最小值,显然操作 xx 的代价一定是两个相近的最低,而 yy 操作与下标无关。

我们考虑 fi,jf_{i,j} 的转移来源

fi,j=min{fi+1,j1+yfi+2,j+(pi+1pi)×xfi,j2+(pj1pj2)×xf_{i,j}=min\begin{cases}f_{i+1,j-1}+y\\ f_{i+2,j}+(p_{i+1}-p_{i})\times x \\ f_{i,j-2}+(p_{j-1}-p_{j-2})\times x\end{cases}

至于为什么不需要考虑相邻的用 yy 操作,很显然,那么远的也一定会用上 yy 操作。

pip_i 代表第 ii 个不同的位置在原数组的下标

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=5100;

int p[maxn],a[maxn],n,x,y;
int T,f[maxn][maxn];

void solve()
{
cin>>n>>x>>y;
char t;
int cnt=0;
for(int i=1;i<=n;i++) cin>>t,a[i]=t-'0';
for(int i=1;i<=n;i++) cin>>t,a[i]^=t-'0';
for(int i=1;i<=n;i++) if(a[i]) p[++cnt]=i;
if(cnt&1)
{
cout<<-1<<endl;
return ;
}
if(cnt==2)
{
if(p[2]-p[1]==1) y*=2;
cout<<min((p[2]-p[1])*x,y)<<endl;
return ;
}
// memset(f,0x3f,sizeof(f));
for(int len=2;len<=cnt;len++)
for(int i=1;i<cnt;i++)
{
int j=i+len-1;
f[i][j]=f[i+1][j-1]+y;
f[i][j]=min(f[i][j],min(f[i+2][j]+(p[i+1]-p[i])*x,f[i][j-2]+x*(p[j]-p[j-1])));
}
cout<<f[1][cnt]<<endl;
}

signed main()
{
ios::sync_with_stdio(false);
cin>>T;
while(T--)
{
solve();
}
}

CF372C Watching Fireworks is Fun

一个单调队列优化 dp\text{dp}

头脑处于十级昏迷写出来的,毕竟是先看题解学习再学的

考虑一个 fi,jf_{i,j} 表示第 ii 个烟花炸了的时候在 jj 号位置的最大收益,有一个转移方程 fi,j=maxfi1,k+bi(aij)f_{i,j}=\max f_{i-1,k}+b_i-(a_i-j)

其中, kk 的范围就是 max(1,jd(titi1)kmin(n,j+d(titi1)))max(1,j-d*(t_i-t_{i-1})\leq k\leq min(n,j+d*(t_i-t_{i-1})))

很显然的,恰好满足单调队列优化的条件,即每次移动 11 ,并且只有最大值产生影响

不过这道题足以体现我有多菜,单调队列都写不来了

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
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

#define int long long

using namespace std;

const int maxn=150030,maxm=330;

int f[2][maxn];
int q[maxn],n,m,d;
int a[maxn],t[maxn],b[maxn];

signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m>>d;
for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>t[i];
for(int i=1;i<=n;i++) f[1][i]=-0x3f3f3f3f3f3f3f;
for(int i=1;i<=m;i++)
{
int ll=1,rr=0;
int tmp=i&1;
int k=1;
for(int j=1;j<=n;j++)
{
for(;k<=min(n,j+d*(t[i]-t[i-1]));k++)
{
while(f[!tmp][q[rr]]<=f[!tmp][k]&&ll<=rr) rr--;
q[++rr]=k;
}
while(q[ll]<max(1ll,j-d*(t[i]-t[i-1]))&&ll<=rr) ll++;
f[tmp][j]=f[!tmp][q[ll]]+b[i]-abs(a[i]-j);
}
}
int ans=-0x3f3f3f3f3f3f3f3f;
for(int i=1;i<=n;i++) ans=max(ans,f[m&1][i]);
cout<<ans<<endl;
}