来点大紫大黑
[POI2013]LUK-Triumphal arch
A 的窝火。显然是二分，树形 dp check 一下即可。
这边证伪一下一种贪心 check:
首先我们从根节点 \(1\) 开始 dfs 全树。
同时记录一个变量 \(less\)。
如果当前的 $k 和 \(less\) 的和比儿子的数量少，肯定不行。
否则就 \(less\leftarrow less-\texttt{当前节点儿子数量}+k\)，然后去判断儿子是不是都合法。
这种做法为什么是错的呢？
这种贪心写法错误在于你假装把剩余涂成黑点的机会滞后了，但是事实上在现实中并没有滞后，就是你必须在那一轮就涂下。
这样就会出现这样一个问题：如果有两棵的子树都通过利用 剩余涂成黑点的机会 滞后，但事实上纵观全局不一定能达成这样的效果，因为事实上你两棵子树都需要利用这个机会，但是你却在贪心过程中只让一颗子树利用这样的机会，所以是谬误的。
#include <bits/stdc++.h>
#define GC c=getchar()
#define IG isdigit(c)
#define int long long
#define rep(i,l,r) for(int i(l),_##i(r);i<=_##i;++i)
#define per(i,r,l) for(int i(r),_##i(l);i>=_##i;--i)
#define Go(i,hd,v) for(int i(hd),v;v=to[i],i;i=nxt[i])
template<class T=int>T frd(T x=0,char GC,bool f=1)
{
for(;!IG;GC)f=c!='-';for(;IG;GC)x=x*10+(c^48);return f?x:-x;
}
using namespace std;
const int N(3e5+5);
int n,hd[N+5],to[N*2+5],nxt[N*2+5],deg[N+5],cntE,f[N+5];
inline void add(int u,int v){nxt[++cntE]=hd[u],hd[u]=cntE,to[cntE]=v,++deg[u];}
inline void Add(int u,int v){add(u,v),add(v,u);}
int dfs(int u,int sum,int fa)
{
f[u]=deg[u]-sum;
Go(i,hd[u],v) if(v!=fa) f[u]+=max(dfs(v,sum,u),0ll);
return f[u];
}
signed main()
{
n=frd();
rep(i,2,n)Add(frd(),frd()),--deg[i];
int L(0),R(n);
while(L<R)
{
int mid(L+R>>1);
dfs(1,mid,0)<=0?R=mid:L=mid+1;
}
printf("%lld\n",L);
return 0;
}
[POI2015] KUR
这种计数很罕见。
我们直接去找有多少个起始位置符合条件。
显然当一个起始位置 \(start\) 符合条件，以 \(s_i = 0\) 为例必有
对于任意一个 \(i\in [1,m]\) 都有 \(a(start-1+i)+b \mod n < p\)。
为了方便我们 \(start\leftarrow start-1\)。
所以就是 \(a*start+(a*i+b) \mod n < p\)。
然后发现对于任意的一个 \(a*start\) 都有唯一确定的 \(start\) 与之对应（因为 \((a,n)=1\)）。
而 \(a*start\) 的解集是连续的（可能不太必要的限定：在 \(\mod n\) 的情况下）。那么只要一个点被覆盖了 \(m\) 次即可。
但是，坑点是 \(q\in [n-m+1,n-1]\) 时是不合法的！！！
最后直接去除这种不合法情况即可。。
#include <bits/stdc++.h>
#define GC c=getchar()
#define IG isdigit(c)
#define rep(i,l,r) for(int i(l),_##i(r);i<=_##i;++i)
#define per(i,r,l) for(int i(r),_##i(l);i>=_##i;--i)
#define Go(i,hd,v) for(int i(hd),v;v=to[i],i;i=nxt[i])
template<class T=int>T frd(T x=0,char GC,bool f=1)
{
for(;!IG;GC)f=c!='-';for(;IG;GC)x=x*10+(c^48);return f?x:-x;
}
using namespace std;
const int N(1e6+5);
int n,a,b,p,m,di[N*2+5],cntd,l[N+5],r[N+5],del[N+5],d[N*2+5],ans;
char s[N+5];
inline int ask(int x) {return lower_bound(di+1,di+1+cntd,x)-di;}
signed main()
{
n=frd(),a=frd(),b=frd(),p=frd(),m=frd();
scanf("%s",s+1);
rep(i,1,m)
{
int t((1ll*a*i+b)%n);
if(s[i]^48) l[i]=p-t-1,r[i]=n-1-t;
else l[i]=n-t-1,r[i]=p-1-t;
if(l[i]<0)l[i]+=n;if(r[i]<0)r[i]+=n;
di[++cntd]=l[i],di[++cntd]=r[i];
}
di[0]=-1,di[++cntd]=0,di[++cntd]=n-1;
rep(i,n-m+1,n-1) del[n-i]=1ll*a*i%n;
sort(di+1,di+1+cntd),sort(del+1,del+m);
cntd=unique(di+1,di+1+cntd)-(di+1);
rep(i,1,m)
{
l[i]=ask(l[i]),r[i]=ask(r[i]);
--d[l[i]],++d[r[i]],l[i]>r[i]&&(++d[cntd]);
}
int npos(m-1);
per(i,cntd,1)
{
d[i]+=d[i+1];int cnt(0);
while(npos&&del[npos]>di[i-1]) --npos,++cnt;
if(d[i]==m) ans+=di[i]-di[i-1]-cnt;
}
printf("%d\n",ans);
return 0;
}
another
#include <bits/stdc++.h>
#define GC c=getchar()
#define IG isdigit(c)
#define rep(i,l,r) for(int i(l),_##i(r);i<=_##i;++i)
#define per(i,r,l) for(int i(r),_##i(l);i>=_##i;--i)
#define Go(i,hd,v) for(int i(hd),v;v=to[i],i;i=nxt[i])
template<class T=int>T frd(T x=0,char GC,bool f=1)
{
for(;!IG;GC)f=c!='-';for(;IG;GC)x=x*10+(c^48);return f?x:-x;
}
using namespace std;
const int N(1e6+5);
int n,a,b,p,m,di[N*3+5],cntd,l[N+5],r[N+5],del[N+5],d[N*3+5],cntp,ans;
char s[N+5];
inline int ask(int x) {return lower_bound(di+1,di+1+cntd,x)-di;}
signed main()
{
n=frd(),a=frd(),b=frd(),p=frd(),m=frd();
scanf("%s",s+1);
rep(i,1,m)
{
int t((1ll*a*i+b)%n);
if(s[i]^48) l[i]=p-t,r[i]=n-t;
else l[i]=n-t,r[i]=p-t;
if(l[i]<0)l[i]+=n;if(r[i]<0)r[i]+=n;
di[++cntd]=l[i],di[++cntd]=r[i];
}
di[++cntd]=0,di[++cntd]=n;
rep(i,n-m+1,n-1) del[n-i]=1ll*a*i%n;
sort(di+1,di+1+cntd),sort(del+1,del+m);
cntd=unique(di+1,di+1+cntd)-(di+1);
rep(i,1,m)
{
l[i]=ask(l[i]),r[i]=ask(r[i]);
++d[l[i]],--d[r[i]];
if(l[i]>=r[i]) ++d[1];
}
int npos(1);
rep(i,1,cntd-1)
{
d[i]+=d[i-1];int cnt(0);
while(npos<m&&del[npos]<di[i+1])++npos,++cnt;
if(d[i]==m) ans+=di[i+1]-di[i]-cnt;
}
printf("%d\n",ans);
return 0;
}