Div4 VP总结

Codeforces Round 799 (Div. 4)

E（最长子区间）

基本思路

求满足s的最长子区间。

错误思路分析

• 想用双指针左右贪心模拟题目要求删前或后的数（但在面对前后两个相等的时候，删前删后没有无后效性）
• 简单暴力枚举子区间长度（显然在n=1e5的时候t了）

正确思路

• 虽然也是暴力枚举子区间，但有做优化。
  先从左到右求和至题目要求s，记录长度，再把左端点有1的数删一个，右端点再去取下一个有1的数的位置。

  代码如下

  void solve() {
  std::cin>>n>>m;
  std::vector<int>a(n);
  int sum=0;
  for(int i=0;i<n;i++){
      std::cin>>a[i];
      sum+=a[i];
  }
  int ans=n;
  int cur=0;//cur就是求的区间和
  if(sum<m){
      std::cout<<-1<<"\n";
  }else{
    for(int i=0,j=0;i<n;i++){//这里我个人感觉很妙，用i,j两个指针实现了o(n)的时间复杂度。
      while(j<n&&cur+a[j]<=m){
          cur+=a[j];
          j++;
      }
      if(cur==m){
          ans=std::min(ans,n-(j-i));
      }
      cur-=a[i];
    }
      std::cout<<ans<<"\n";
  }
  

}

```

F(有思路的暴力枚举)

题目大意

对一堆数是否能去三个独立的数相加使其总和尾数为3.

思路

直接用\(10^3\)时间直接暴力枚举i,j,k看满足条件的数，看输入的数是否满足。
代码

void solve() {
   int n;
   std::cin>>n;
   std::vector<int >a(n+1),one(10);//one数组来记录原来数的尾数的次数
   for (int i = 0; i < n; i++)
   {
    std::cin>>a[i];
        a[i]%=10;
        one[a[i]]++;
   }
    for(int i=0;i<=9;i++){
        for(int j=0;j<=9;j++){
            for(int k=0;k<=9;k++){
                if((i+j+k)%10==3){
                    one[i]--;
                    one[j]--;
                    one[k]--;
                    if(one[i]>=0&&one[j]>=0&&one[k]>=0){
                        std::cout<<"YES"<<"\n";
                        return;
                    }
                    one[i]++;
                    one[j]++;
                    one[k]++;
                }
            }
        }

    }
    std::cout<<"NO"<<"\n";
}

Codeforces Round 817 (Div. 4)

E(二维前缀和求和)

题目意思很明显二维前缀和。
代码

Codeforces Round 806 (Div. 4)

D(字符串切割问题)

• 错误思路
  想着暴力对其他字符串枚举（首先时间会t，字符串前后相加的结果是不同的）。
• 正确思路
  字符串切割加匹配问题基本需要用map做匹配，后面枚举各个位置切割是否在map中出翔过再做判断。
  代码