题解：P13959 [ICPC 2023 Nanjing R] 计数器

Airbus_A380 · 2025-09-06 17:20:25 · 题解

upd 2025/9/10：修改题解使其尽量符合要求。

AC Record

关于题目

题目传送门

题目大意：有一个初始值为 0 的计数器，支持 + 和 c 两种操作。有 T 组数据，每一组数据包含计数器的 m 个状态，求有没有一种方案同时满足这些状态。

思路

读题可知，想从计数器的上一个状态（记为 prev）到下一个状态（记为 cur），有且只有两种做法：

• 先执行 c 操作清零计数器至少一次，再执行 cur 次 + 操作使值变成 cur；
• 当 prev < cur 时，执行 + 操作 cur - prev 次使值变成 cur。

按照以上思想分类讨论即可。 :::warning[一些注意事项]

• 输入的数据没有按照操作次数的顺序排序，所以需要把次数存到一个数组中，再手动排序。
• 数据中可能存在 a_i = a_j 且 b_i = b_j 的情况，这种情况不需要操作，也不可以操作，需要跳过。 ::: :::info[代码]{open}

  #include<bits/stdc++.h>
  using namespace std;
  long long T;
  struct operation{
  long long target,ops;
  bool operator <(const operation &x) const{
      return ops<x.ops;
  }
  }arr[100010];
  bool check(long long from,long long to,long long ops){//true->no
  if(from>=to){
      // cout<<1<<endl;
      return to>(ops-1);
  }
  // cout<<2<<endl;
  return to>(ops-1)&&(to-from)!=ops;
  }
  int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>T;
  while(T--){
      long long n,m;
      cin>>n>>m;
      long long num=0;
      long long last_op=0;
      long long flag=true;
      for(long long i=1;i<=m;i++){
          cin>>arr[i].ops>>arr[i].target;
      }
      sort(arr+1,arr+m+1);
      for(long long i=1;i<=m;i++){
          long long op,val;
          op=arr[i].ops;
          val=arr[i].target;
          if(op==last_op&&val!=num){
              flag=false;
          }
          else if(op==last_op&&val==num){
              continue;
          }
          if(flag){
              if(val==0){
                  num=0;
                  continue;
              }
              long long real_op=op-last_op;
              if(check(num,val,real_op)){
                  flag=false;
              }
              num=val;
              last_op=op;
          }
      }
      if(flag){
          cout<<"Yes"<<endl;
      }
      else{
          cout<<"No"<<endl;
      }
  }
  return 0;
  }

  :::