ICPC2023南京个人题解

I. Counter

题意：给定一个初始值为零的计数器，每次操作可以使值+1或者变为0，再给定 \(m\) 个特定时间 \(a_i\) 的对应计数器的值 \(b_i\) ，问有没有可能的长度为 \(n\) 的操作序列满足所有条件。

限制条件：\(1\le a_i \le n \le 10^9,1\le m \le 10^5,1\le b_i \le 10^9\)。
题解：根据给的要求，如果 \(a_i\) 时计数器为 \(b_i\)，那么 \(a_i-b_i\) 时计数器必为0，并且 \([a_i-b_i+1,a_i]\) 时间内计数器的值都为1.所以只需要把所有的条件按照时间从小到大排序，然后依次check跟前一个是否矛盾就可以了。时间复杂度 \(O(m\log{m})\)。
点击查看代码[code]#includeusing namespace std;using ll=long long;struct node{        ll a,b;        friend bool operator < (node a,node b)        {                return a.a>tttt;        while(tttt--)        {                ll n,m;                cin>>n>>m;                vectorc(m+7,{0,0});                for(int i=1;i>c.a>>c.b;                }                sort(c.begin()+1,c.begin()+m+1);                bool yw=1;                ll pre=0;                for(int i=1;i>n>>m;                vectornum(m+7,0);                vectorc(n+7);                for(int i=1;i>p;                        while(p--)                        {                                ll a;                                cin>>a;                                num[a]=i;                                c.push_back(a);                        }                }                bool yw=0;                vectorans(n+7);                for(int i=1;i>m;                ll l=max(0ll,m/p-1);                ll r=max(0ll,(m+p-3)/p+1);                ll ans=l;                for(ll i=l;in>>W>>k;                vectorc(n+7);                for(int i=1;i>c.w>>c.v;                }                sort(c.begin()+1,c.begin()+n+1);                vectordp(n+7,vector(W+7,0));                for(int i=1;i=0;j--)                        {                                dp[j]=dp[i-1][j];                                if(j>=c.w)                                        dp[j]=max(dp[j],dp[i-1][j-c.w]+c.v);                        }                }                if(k==0)                {                        ll tmp=0;                        for(int i=0;im;                vectorp;                vectors(n+7,vector(m+7));                for(int i=1;is[j];                                if(s[j]=='.')                                        p.push_back({i,j});                        }                }                vectoryw;                for(auto [i,j]:p)                {                        queueq;                        bitsetb;                        vectorvis(n+7,vector(m+7,0));                        q.push({i,j});                        vis[j]=1;                        while(!q.empty())                        {                                auto [x,y]=q.front();                                b[(x+n-i)*2*m+(y+m-j)]=1;                                q.pop();                                for(int _=0;_