codeforces C. Flower City Fence

悠悠 2023-10-15 10:31 116阅读 0赞

## codeforces C. Flower City Fence ##

**关键点在于： 度与长度为x的围栏饭庄过后相当于对\[1,x\]长度的翻转后的围栏+1。**

此时运用差分简化计算降低时间复杂度，朴素思想认为对\[1,x\]范围内的数据一次+1，利用差分对\[1,x\]范围内的数据进行整体运算简化计算。

附上代码（没有参考价值代码逻辑很混乱）

#include <bits/stdc++.h>
    using namespace std;
    
    const int MAXN = 1e5 * 2 + 100;
    
    int carpect[MAXN];
    int D[MAXN]; // 差分数组
    
    int main(){
      int T;
      cin >> T;
      while(T--){
          int n;
          cin >> n;
          memset(D,0,n + 100);
          for(int i = 1;i<=n;i++){
              cin >> carpect[i];
              D[1] += 1; // 篱笆长度最短是1;
              D[carpect[i] + 1] -= 1;
          }
          if(n != carpect[1]){
              printf("NO\n");
          }
          else{
              vector<int> res;
              res.push_back(0);
              bool flag = true;
              for(int i = 1;i<=n;i++){
                  int num = res[i-1] + D[i];
                  res.push_back(num);
                  if(num != carpect[i]){
                      printf("NO\n");
                      flag = false;
                      break;
                  }
              }
              if(flag){
                  printf("YES\n");
              }
          }
      }
      return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，116人围观）

还没有评论，来说两句吧...

相关阅读

相关 Codeforces Global Round 24 C. Doremy‘s City Construction

[Problem - C - Codeforces][] 题意：给定n个点，然后连边，当a\[i\]<=a\[j\]<=a\[k\]时不能连，否则可以问你最多连多少边

àì夳堔傛蜴生んèń/ 2024年03月30日 17:38/ 0 赞/ 51 阅读

相关 codeforces C. Flower City Fence

codeforces C. Flower City Fence 关键点在于：度与长度为x的围栏饭庄过后相当于对\[1,x\]长度的翻转后的围栏+1。此时运用差分简化

悠悠/ 2023年10月15日 10:31/ 0 赞/ 117 阅读

相关 codeforces 448CPainting Fence

题目：[codeforces 448CPainting Fence][] 题意：n个1\ a \[ i \] 的木板，把他们立起来，变成每个木板宽为1长为 a \[

心已赠人/ 2022年08月27日 15:51/ 0 赞/ 104 阅读

相关 codeforces C. Painting Fence

C. Painting Fence time limit per test 1 second memory limit per test 512 megabytes

ゞ浴缸里的玫瑰/ 2022年07月24日 09:16/ 0 赞/ 153 阅读

相关 Fence Repair

Problem Description Farmer John wants to repair a small length of the fence around th

我会带着你远行/ 2022年07月12日 05:24/ 0 赞/ 188 阅读

相关 Protecting the Flowers

Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as

小灰灰/ 2022年06月12日 06:29/ 0 赞/ 110 阅读

相关 codeforces 451E Devu and Flowers(容斥原理，Lucas，dfs，隔板法)

E. Devu and Flowers time limit per test 4 seconds memory limit per test 256 megabyte

╰+哭是因爲堅強的太久メ/ 2022年06月09日 13:27/ 0 赞/ 65 阅读

相关 ZZULIOJ-2261——flower

flower 题目描述又是一年教师节，有n个小朋友打算去看望花老师。

本是古典何须时尚/ 2022年04月12日 12:18/ 0 赞/ 159 阅读

相关 1469C Building a Fence

[题目][Link 1] 思路：每一次求取一个范围，然后判断之后的小方格是否满足范围。对于最后和第一个方格已经取定，需要特殊判断，细节见代码。 Code:

偏执的太偏执、/ 2021年07月16日 21:34/ 0 赞/ 327 阅读

相关 1481C Fence Painting (list、map)

[题目][Link 1] 思路：对于失败有两种情况： 1.统计所有的需要修正成各种颜色的数目，如果发现对于一种颜色我们所拥有的画师数少于所需修正的数目，则失

偏执的太偏执、/ 2021年07月16日 14:09/ 0 赞/ 339 阅读