A. reverse
可以发现每个点可以到达的点都是固定的.
所以如果给每个点向 \(ta\) 所能到达的点都连一条边，
那就是求每个点的最浅深度了.
复杂度\(O(n^2)\).可以卡常\(A\)掉.
正解给出了 \(set\) 的\(O(nlogn)\)做法.
这里有一个链表\(O(n)\)做法.(不是我的想法.)
每个点的答案一定是在第一次被遍历时的答案.
所以可以剪掉很多枝.
A_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define ll int
#define ull unsigned ll
#define re register ll
#define lf double
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=1e5+21;
ll m,n,s,st;
ll col[N],R[N],Q[N];
signed main(){
n=read(),s=read(),m=read(); ll l,r;
for(re i=1;i<=n;i++) col[i]=n+1,R[i]=i+2;
col[st=read()]=0; Q[1]=st;
for(re i=1;i<=m;i++) col[read()]=-1;
for(re h=1,t=1;h<=t;h++){
st=max(1,Q[h]-s+1),l=st+st+s-1-Q[h],
st=min(n-s+1,Q[h]),r=st+st+s-1-Q[h];
for(re i=l;i<=r;i=R[i]) if(col[i]>col[Q[h]]+1) col[i]=col[Q[h]]+1,Q[++t]=i;
for(re i=l;i<=r;i=st){ st=R[i],R[i]=max(R[i],r),i=st; }
}
for(re i=1;i<=n;i++){
if(col[i]>n) cout<<-1<<‘ ‘;
else cout<<col[i]<<‘ ‘;
}
exit(0);
}
B. Silhouette
很显然是要容斥一下啊，但是并不知道如何写.
虽然都是在容斥的角度思考，但是自己的想法和正解还是有很大出入.
发现了变换顺序也不会影响答案的性质，但是没有想到接下来的做法.
一定要灵活运用自己发现的性质，但如果想了很久也没能有成果大概率就不会是这个角度吧.
这个题目zero4338画了图，讲得很清晰..%%%
这里就不再赘述了.
B_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS
{
#define ll long long int
#define lf double
#define re register ll
#define ull unsigned ll
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
inline ll read()
{
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch==‘-‘) cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=1e5+21,mod=1e9+7;
ll n,m,ans=1;
ll ha[N],hb[N],frc[N];
inline ll ksm(ll a,ll b,ll c){
a%=c; ll res=1;
while(b){
if(b&1) res=(res*a)%c;
a=(a*a)%c,b>>=1;
}
return res%c;
}
inline ll C(ll a,ll b){
if(a>b) return 0;
return frc[b]*ksm(frc[b-a],mod-2,mod)%mod*ksm(frc[a],mod-2,mod)%mod;
}
inline ll calc(ll A,ll B,ll a,ll b,ll w){
ll res,ret,sum=0;
for(re i=0;i<=a;i++){
res=C(i,a),ret=ksm(w,i,mod)*((ksm(w+1,A-i,mod)-ksm(w,A-i,mod)+mod)%mod)%mod,
res=(res*ksm(ret,b,mod))%mod,ret=ksm(ksm(w,i,mod)*ksm(w+1,a-i,mod),B-b,mod),
res=res*ret%mod*((i&1) ? -1 : 1),sum=(sum+res+mod)%mod;
}
return sum%mod;
}
signed main(){
n=read(),frc[0]=1; ll w,a,b,tmp,temp;
for(ll i=1;i<=n;i++) frc[i]=frc[i-1]*i%mod;
for(re i=1;i<=n;i++) ha[i]=read(); for(re i=1;i<=n;i++) hb[i]=read();
sort(ha+1,ha+1+n),sort(hb+1,hb+1+n); ll p1=1,p2=1;
if(ha[n]!=hb[n]) puts("0"),exit(0);
while(p1<=n or p2<=n){
w=min(ha[p1],hb[p2]),a=0,b=0;
while(p1<=n and ha[p1]==w) p1++,a++; while(p2<=n and hb[p2]==w) p2++,b++;
ans=ans*calc(n-p1+a+1,n-p2+b+1,a,b,w)%mod;
}
printf("%lld\n",ans);
exit(0);
}