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

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

关于题目

题目大意：有一个初始值为

0

的计数器，支持 + 和 c 两种操作。有

T

组数据，每一组数据包含计数器的

m

个状态，求有没有一种方案同时满足这些状态。

思路

读题可知，想从计数器的上一个状态（记为

prev

）到下一个状态（记为

cur

），有且只有两种做法：

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

按照以上思想分类讨论即可。

一些注意事项

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

代码

CPP

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

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

文章操作

关于题目

思路

相关推荐

评论

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