设读入的数据分别为 $a,b,c$

对于一种合法的分配，设分了 $x$ 给 $a$

那么有 $a+x>b+(c-x)$，整理得到 $x>(b+c-a)/2$

因为 $x \in [0,c]$ ，所以求一下区间交的大小即可，注意 (b+c-a) 可能小于 0

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }    return x*f;}int T,a,b,c;int main(){    T=read();    while(T--)    {        a=read(),b=read(),c=read();        if(b+c-a<0) printf("%d\n",c+1);        else printf("%d\n",max(c- (b+c-a)/2 ,0));    }    return 0;}
          
         
        
       
      

 

看一眼想到了屠龙勇士

首先如果可以一刀秒了那直接秒了就行

不然设单次最大伤害为 $mx$ ，就是斩杀线，一旦血量低于 $mx$ 就不用管之后会回多少血了

否则只能慢慢磨，设 $d-h$ 最大值为 $G$，那么我们每回合就只能扣 $G$ 的血

直到低于或等于斩杀线，直接斩杀即可，当然如果 $G<=0$ 则无法取胜

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;inline ll read(){    ll x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }    return x*f;}const ll INF=1e18;ll T,n,m,mx,G;struct dat {    ll x,y;}d[233];int main(){    T=read();    while(T--)    {        n=read(),m=read(); mx=-INF,G=-INF;        for(int i=1;i<=n;i++)        {            d[i].x=read(),d[i].y=read();            mx=max(mx,d[i].x); G=max(G,d[i].x-d[i].y);        }        if(mx>=m) { printf("1\n"); continue; }        if(G<=0) { printf("-1\n"); continue; }        printf("%lld\n",(m-mx)/G+((m-mx)%G>0)+1);    }    return 0;}
          
         
        
       
      

 

考虑怎样的一段会产生贡献，就是某一位 $1$ 开始往右若干位，然后往左再延伸若干个连续的 $0$

显然往右移动的位数不会大于 $\log m$ ，其中 $m$ 为串长

所以对每一个 $s[i]=1$ 暴力右移，并维护当前位置最多能左移 $t$ 个 $0$，设当前区间 $[i,i+j]$ 的值为 $now$

如果满足 $now-j-1<=t$ 则合法

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=2e5+7;int T,n,a[N];char s[N];int Ans;int main(){ T=read(); while(T--) { scanf("%s",s+1); n=strlen(s+1); Ans=0; for(int i=1;i<=n;i++) a[i]=(s[i]-'0'); for(int i=1,t=0;i<=n;i++) { if(!a[i]) { t++; continue; } int now=0; for(int j=0;j<20&&i+j<=n;j++) { now=(now<<1)|a[i+j]; if( now-j-1<=t ) Ans++; } t=0; } printf("%d\n",Ans); }}
           
          
         
        
       
      

 

脑子不好用怎么办

首先强行拓扑排序一波看看有没有环，如果没有全部输出 $1$

否则

对于边 $(a,b)$，如果 $a<b$ 染 $1$，否则 $a>b$，染 $2$

这样保证所以纯色路径经过的节点编号单调递增或递减，然后就一定没环....

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=1e4+7;int n,m,du[N];vector 
             
               V[N],ans;queue 
              
                Q;int main(){ n=read(),m=read(); int x,y; for(int i=1;i<=m;i++) { x=read(),y=read(); ans.push_back((x
              
             
            
           
          
         
        
       
      

 

考虑怎样选最能 "不平衡"，发现如果选出两个数，他们某一位都不为 $0$，那么这两个数构成的集合一定不平衡，并且如果选出的两个数他们每一位都最多只有一个不为 $0$，那么一定平衡，所以对于两个数的情况我们只要考虑存在某一位都不为 $0$ 的情况

显然选两个数某一位都不为 $0$，一定比选多个数但是某些数此位为 $0$ 更优，因为我们可以不选此位为 $0$ 的那个数，最终总和还更小

所以只要考虑选两个数的情况

发现如果存在不平衡的方案，那么只要每一位分别考虑不平衡即可，因为就算如果低位进位了影响到当前位，但是低位因为有进位所以低位一定不平衡了，统计答案的时仍然会统计到这种方案

然后就可以开 $9$ 个线段树维护每一位的情况，每一个位的线段树直接维护区间 $[l,r]$ 内此位不为 $0$ 的数的最小值和次小值

然后查询的时候每一位都查询一遍取最小即可，具体看代码咯

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;inline int read(){    int x=0,f=1; char ch=getchar();    while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }    while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }    return x*f;}const int N=2e5+7,INF=1e9+7;int n,m;struct dat {    int m1,m2;    dat (int a=INF,int b=INF) { m1=a,m2=b; }//注意初始INF    inline dat operator + (const dat &tmp) const {        dat res=*this;        if(tmp.m1
           
            >1; pos<=mid ? ins(o<<1,l,mid) : ins(o<<1|1,mid+1,r); t[o]=t[o<<1]+t[o<<1|1]; } void query(int o,int l,int r) { if(l>qr||r
            
             =ql&&r<=qr) { res=res+t[o]; return; } int mid=l+r>>1; query(o<<1,l,mid); query(o<<1|1,mid+1,r); } inline void Ins(int x,int y) { pos=x; val=y; ins(1,1,n); } inline dat Query(int l,int r) { res=dat(INF,INF); ql=l,qr=r; query(1,1,n); return res; }}T[10];int main(){ n=read(),m=read(); int opt,a,b; for(int i=1;i<=n;i++) { a=read(); for(int j=1,t=a;j<10;j++,t/=10) if(t%10) T[j].Ins(i,a); //此处可以不用Ins(INF) 因为初始就是INF } for(int i=1;i<=m;i++) { opt=read(),a=read(),b=read(); if(opt==1) { for(int j=1,t=b;j<10;j++,t/=10) if(t%10) T[j].Ins(a,b); else T[j].Ins(a,INF);//注意要用INF覆盖掉原来的值 continue; } int ans=INF*2; for(int j=1;j<10;j++) { dat t=T[j].Query(a,b); if(t.m2
            
           
          
         
        
       
      

 

 

神仙题，看一眼以为动态图连通性强制在线

但是 $div2$ 肯定不会这么无聊出这种毒瘤题

$Orz\ Claris$（以下为  想的）

注意到 $las$ 不是 $1$ 就是 $0$，所以把 $m$ 个操作分成 $2m$ 个操作就可以知道所有可能的操作了

然后就可以离线乱搞，分治

对于当前图 $G$，有 $n$ 点 $m$ 边，$Q$ 询问

如果 $Q=1$ 则到达边界直接暴力，否则

求出当前 $G$  的所有联通块，将 $Q$ 个询问中包含的点所在的联通块保留，其他扔了

此时最多剩下 $2Q$ 个点，设操作后的图为 $G'$

将 $G'$ 和前 $Q/2$ 个操作递归处理，然后回溯后得到前 $Q/2$ 个操作完成的图 $G''$

因为前 $Q/2$ 个操作已经完成，所以知道当前 $las$ 的值

然后再将 $G''$ 和后 $Q/2$ 个操作递归处理

这个神仙算法的复杂度 $n\log n$ （n,m 同阶反正就是这个复杂度）

代码自己参考其他神仙的吧，我是不可能会的