lance.h

lance

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;
}