0%

cf1

今天做的一些1600左右的cf题

其中需要特别注意的是一种对subarray处理的方法:遍历右端点

1333C:Eugene and an array|1700|处理子串遍历

一个串如果有子串和为0是不好的。给出一个串,求好的子串个数。
显然我们可以求前缀和,然后二次出现的两点间即为一个和为0的区间。
一个串不能包含一个这样的区间。
但是如何高效遍历之?
对于全部子串这种两个范围的,可以对右端点遍历,即求以i为结尾的所有个数(即i的贡献)。
此时,维护上一个0区间的起点位置即可,从他到i的每个起点对应一个子串。注意0区间不一定是以i为右端点的,但是必然有一个右端点,所以每次发现0区间的右端点,都要更新一次。
实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const int maxn=2e5+10;
ll d[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
int n;cin>>n;
ll ans=0;
ll tmp=0;
map<ll,ll> ma;
d[0]=0;
ma[0]=1;
ll now=-1;
for(ll i=1;i<=n;++i){
cin>>tmp;
d[i]=d[i-1]+tmp;
now=max(now,ma[d[i]]);
ans+=(i-now);
ma[d[i]]=i+1;
}
cout<<ans<<endl;
}

1486D:max median|二分+遍历子串

和上一题类似,原本遍历每个值和判断复杂度爆炸,通过二分变为nlogn,其中check部分经过优化,否则也是n方的而且实现复杂。
我们是对答案二分,所以只要判断这个答案的大小,check中,对数列求一个前缀和,若大于此答案记1,否则-1,如果一个区间比0大,这个区间的中位数将比此答案更大。
同样,我们需要遍历区间,则遍历区间右端点,为了尽量使得此段值大,维护一个最小的值即可(注意保持区间长度至少k)

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
const int maxn=2e5+10;
int n,m;
int in[maxn];
int nums[maxn];
int db[maxn];
int cnt[maxn];
int ask(int k){
for(int i=1;i<=n;++i){
db[i]=(in[i]>=k ? 1:0)*2-1+db[i-1];
}
int now=0;
for(int i=m;i<=n;++i){
if(db[i]-now>=1){
return 1;
}else{
now=min(now,db[i+1-m]);
}
}
return 0;
}
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
cin>>n>>m;
int l=inf,r=0;
for(int i=1;i<=n;++i){
cin>>in[i];
l=min(l,in[i]);
r=max(r,in[i]);
}
while(l!=r){
int mid=(l+r+1)/2;
int tag=ask(mid);
if(tag){
l=mid;
}else{
r=mid-1;
}
}
cout<<l<<endl;
}

1253C:sweets eating|1500|分组前缀和

需要处理的是k个糖,每天最多吃m个,从第1天开始,糖的影响值是天数与其甜度之积。
求最小总影响。(题目要求k遍历1-n)
在纸上模拟,可以发现,随着k增加,每次增加的是与index模m相关的一个子序列的前缀和。
可以推出对应前缀和是序列中前$k+m-(i mod m==0? m:i mod m) \over 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
const int maxn=2e5+100;
ll in[maxn];
vector<ll> res[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
ll n,m;
cin>>n>>m;
for(ll i=1;i<=n;++i){
cin>>in[i];
}
sort(in+1,in+1+n);
for(ll i=1;i<=n;++i){
ll tmp;
if(res[i%m].size()==0){
tmp=0;
}else
tmp=res[i%m][res[i%m].size()-1];

res[i%m].push_back(tmp+in[i]);
}
ll ans=0;
for(ll i=1;i<=n;++i){
ll tmp=(i+m-(i%m==0? m:i%m))/m;
ans+=res[i%m][tmp-1];
cout<<ans<<' ';
}cout<<endl;
}

1337C:linova and kingdom|1600|greedy

比较水,可以发现,每个点被取到时,子数必然填满,即贡献确定,存图,dfs+回溯,分别求出lv和子树节点数,即可得出lv-sum,对此排序贪心取前k个即可。
注意,由于边是双向边,用disjointSet不方便,而且注意邻接表开2倍边。

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
const int maxn=4e5+10;
int ver[maxn],head[maxn],nxt[maxn];
int d[maxn];
int vis[maxn];
int tot=0;
void add(int x,int y){
ver[++tot]=y,nxt[tot]=head[x],head[x]=tot;
}
int dfs(int x,int v){
vis[x]=1;
int sum=0;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(vis[y]==0){
sum+=dfs(y,v+1);
}
}
d[x]=v-sum;
return sum+1;
}

int main()
{
int n,k;cin>>n>>k;
int x,y;
for(int i=1;i<n;++i){
cin>>x>>y;
add(x,y);add(y,x);
}
dfs(1,0);
ll ans=0;
sort(d+1,d+1+n);

for(int i=n;i>n-k;--i){
ans+=d[i];
}
cout<<ans<<endl;
}

1334C:circle of monsters|1600|水

。。。这题应该900分吧

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
const int maxn=3e5+10;
ll a[maxn];
ll b[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
for(int i=1;i<=n;++i){
cin>>a[i]>>b[i];
}
a[0]=a[n];
b[0]=b[n];
ll ans=0;
ll start=-1;
ll now=INF;
for(int i=1;i<=n;++i){
if(now>min(a[i],b[i-1])){
now=min(a[i],b[i-1]);
start=i;
}
}
ans+=a[start];
for(int i=start+1;i<=n;++i){
ans+=max(0ll,a[i]-b[i-1]);
}
for(int i=1;i<start;++i){
ans+=max(0ll,a[i]-b[i-1]);
}
cout<<ans<<endl;
}
return 0;
}

1332:K-complete word|1500|字符串

最终的结果是一个重复出现的回文串,所以一些位置是相关联的,分别决定改成哪个即可。

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
const int maxn=2e5+10;
char in[maxn];
int num[maxn][26];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n,k;cin>>n>>k;
for(int i=1;i<=k;++i){
for(int j=0;j<26;++j){
num[i][j]=0;
}
}
cin>>in+1;
for(int i=1;i<=n;++i){
num[(i%k==0? k:i%k)][in[i]-'a']++;
}
int div=n/k;
ll ans=0;
if(k%2==0){
int tmp=k/2;
for(int j=1;j<=tmp;++j){
int cnt=0;
for(int li=0;li<26;++li){
cnt=max(cnt,num[j][li]+num[k+1-j][li]);
}
ans+=2*div-cnt;
}
}else{
int tmp=k/2;
for(int j=1;j<=tmp;++j){
int cnt=0;
for(int li=0;li<26;++li){
cnt=max(cnt,num[j][li]+num[k+1-j][li]);
}
ans+=2*div-cnt;
}
int cn=0;
for(int li=0;li<26;++li){
cn=max(cn,num[tmp+1][li]);
}
ans+=(div-cn);
}
cout<<ans<<endl;
}
return 0;
}

1469C:building a fence|1600|dp

两段是确定的,我们从1开始,下一个位置被其前驱限制,也被h限制,取其交集(如果取不出就失败)为取值范围,进而限制下一个。最后一个在第n-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
const int maxn=2e5+10;
int h[maxn];
int at[maxn];
int ad[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n,k;cin>>n>>k;
for(int i=1;i<=n;++i)
cin>>h[i];
at[1]=ad[1]=h[1]+k;
at[n]=ad[n]=h[n]+k;
int tag=1;
for(int i=2;i<n;++i){
int l=h[i]+k,r=h[i]+2*k-1;
int l2=ad[i-1]-k+1,r2=at[i-1]+k-1;
if(l>r2||l2>r){
tag=0;
break;
}else{
ad[i]=max(l,l2);
at[i]=min(r,r2);
}
}
int l2=ad[n-1]-k+1,r2=at[n-1]+k-1;
if(!(at[n]>=l2&&at[n]<=r2)){
tag=0;
}
if(tag){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
}
}

1330A:Dreamoon and Ranking Collection|900|水

模拟即可

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
const int maxn=305;
int in[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
memset(in,0,sizeof in);
int n,x;cin>>n>>x;
int tmp;for(int i=1;i<=n;++i){
cin>>tmp;
in[tmp]=1;
}
int ans=0;
for(int i=1;i<=300;++i){
if(in[i]==1){
ans++;
}else{
if(x>0){
x--;
ans++;
}else{
break;
}
}
}
cout<<ans<<endl;
}
}

1476C:Longest Simple Cycle|1600|dp

从最后一个开始dp,每次考虑,是当前这一根长,还是一个顺时针转90度的欧姆形的长,如果连在一点了必须结算,重新计数,到第一个必须结束。

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
const int maxn=1e5+10;
ll a[maxn];
ll b[maxn];
ll c[maxn];
int main()
{
std::ios::sync_with_stdio(false);std::cin.tie(0);
per(){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>c[i];
for(int i=1;i<=n;++i)cin>>a[i];
for(int i=1;i<=n;++i)cin>>b[i];
ll now=c[n]-1;
ll ans=0;
for(int i=n-1;i>=1;--i){
ll tmp=abs(a[i+1]-b[i+1]);
if(tmp==0){
ans=max(ans,now+2);
now=c[i]-1;
}else{
now+=2;
ans=max(ans,now+tmp);
now+=c[i]-1-tmp;
now=max(now,c[i]-1);
}
}
cout<<ans<<endl;
}
return 0;
}