来自FallDream的博客，未经允许，请勿转载，谢谢。
有幸拜读到贵省的题目，题的质量还不错，而且相比zjoi可做多了，简单发一下题解吧。
还有就是，怎么markdown在博客园上的代码这么丑啊
不难想到一个dp，用f[i][j][0/1][0/1]表示i的子树内放了j个监听设备，i这个节点是否放置，i是否已被监听的方案数。
表面上看起来是\(O(nk^{2})\)的，但是仔细考虑发现转移显然不满，复杂度是\(O(nk)\)
#include<bits/stdc++.h>
#define MN 100000
#define mod 1000000007
using namespace std;
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*10+ch-'0';ch=getchar();}
return x*f;
}
int F[MN+5][4],n,K,f[MN+5][4][105],G[4],head[MN+5],W[4][105],cnt=0,size[MN+5];
struct edge{int to,next;}e[MN*2+5];
inline void ins(int f,int t)
{
e[++cnt]=(edge){t,head[f]};head[f]=cnt;
e[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
inline void R(int&x,int y){y<x?x=y:0;}
inline void A(int&x,int y){x+=y;x>=mod?x-=mod:0;}
void Dp(int x,int fa)
{
F[x][1]=size[x]=f[x][1][1]=f[x][0][0]=1;F[x][0]=0;
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa)
{
Dp(e[i].to,x);
int s1=min(size[x],K),s2=min(size[e[i].to],K),s3=K,s4=K;
for(int k=0;k<4;++k) s3=min(s3,F[x][k]),s4=min(s4,F[e[i].to][k]);
for(int a=0;a<4;++a) for(int b=0;b<4;++b) if((a&1)|(b&2))
for(int j=s3;j<=s1;++j) for(int k=s4;k<=s2&&j+k<=K;++k)
A(W[a|((b<<1)&3)][j+k],1LL*f[x][a][j]*f[e[i].to][b][k]%mod);
for(int k=0;k<4;++k) for(int j=0;j<=K;++j) f[x][k][j]=W[k][j],W[k][j]=0;
for(int k=0;k<4;++k)
for(int j=0;j<4;++j)
{
if(!(j&2)&&!(k&1)) continue;
R(G[k|((j<<1)&3)],F[x][k]+F[e[i].to][j]);
}
for(int k=0;k<4;++k) F[x][k]=G[k],G[k]=1e9;
size[x]+=size[e[i].to];
}
}
int main()
{
n=read();K=read();
for(int i=1;i<n;++i) ins(read(),read());
memset(F,40,sizeof(F));memset(G,40,sizeof(G));
Dp(1,0);printf("%d\n",(f[1][2][K]+f[1][3][K])%mod);
return 0;
}
仙人掌斯坦纳树的期望边数..
考虑找出所有的环。对于不在环上的边，只要它两边都存在点被选中，那么他就一定要选。
然后考虑环，假如有一些点的外向树中存在被选中的节点，那么肯定选择一条最长的不选，可以考虑一个dp:
用f[i][j][k]表示第一个选择的节点是\(i\)，当前选到了\(j\)，最长的一段是\(k\)的方案树，转移可以通过差分优化到\(O(1)\)，复杂度\(O(n^3)\)
#include<bits/stdc++.h>
#define MN 200
#define mod 1000000007
using namespace std;
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*10+ch-'0';ch=getchar();}
return x*f;
}
pair<int,int> q[MN+5];
int n,m,head[MN+5],cnt,top,size[MN+5],ans,pw[MN+5],dfn[MN+5],low[MN+5],dn,vis[MN+5],now;
int f[MN+5][MN+5],g[MN+5][MN+5],G[MN+5],h[MN+5][MN+5],H[MN+5],sz[MN+5],Fa[MN+5],cc;
struct edge{int to,next;}e[MN*4+5];
inline void ins(int f,int t)
{
e[++cnt]=(edge){t,head[f]};head[f]=cnt;
e[++cnt]=(edge){f,head[t]};head[t]=cnt;
}
vector<int> v[MN+5];
inline void R(int&x,int y){x+=y;x>=mod?x-=mod:0;}
void Solve(vector<int>&c)
{
if(c.size()==2) {ans=(ans+1LL*(pw[size[c[1]]]-1)*(pw[n-size[c[1]]]-1))%mod;return;}
++cc;int N=c.size();
for(int i=0;i<N;++i) vis[c[i]]=cc;
for(int i=0;i<N;++i)
for(int j=head[c[i]];j;j=e[j].next)
if(vis[e[j].to]!=cc)
sz[c[i]]+=Fa[c[i]]==e[j].to?(n-size[c[i]]):size[e[j].to];
for(int i=0;i<N;++i)
{
memset(f,0,sizeof(f));
memset(g,0,sizeof(g));memset(h,0,sizeof(g));
memset(G,0,sizeof(G));memset(H,0,sizeof(H));
f[i][0]=1;
for(int j=i;j<N;++j)
{
for(int k=0;k<=j;++k) R(G[k],g[j][k]),R(f[j][k],G[k]);
for(int k=0;k<=j;++k) R(H[k],h[j][k]),R(f[j][j-k],H[k]);
for(int k=0;k<=N;++k) if(f[j][k])
{
f[j][k]=1LL*f[j][k]*(pw[sz[c[j]]+1]-1)%mod;
int rk=max(k,N-(j-i));
ans=(ans+1LL*(N-rk)*f[j][k])%mod;
int it=j+k+1;
R(G[k],f[j][k]);if(it<N) R(g[it][k],mod-f[j][k]);
if(it<N) R(h[it][j],f[j][k]);
}
}
}
}
void Tarjan(int x,int fa)
{
dfn[x]=low[x]=++dn;size[x]=1;Fa[x]=fa;
for(int i=head[x];i;i=e[i].next)
if(!dfn[e[i].to])
{
q[++top]=make_pair(x,e[i].to);
Tarjan(e[i].to,x);low[x]=min(low[x],low[e[i].to]);size[x]+=size[e[i].to];
if(low[e[i].to]>=dfn[x])
{
for(++now;q[top+1]!=make_pair(x,e[i].to);--top)
{
if(vis[q[top].first]!=now) vis[q[top].first]=now,v[now].push_back(q[top].first);
if(vis[q[top].second]!=now) vis[q[top].second]=now,v[now].push_back(q[top].second);
}
}
}
else if(e[i].to!=fa)
{
low[x]=min(low[x],dfn[e[i].to]);
if(dfn[e[i].to]<dfn[x])
q[++top]=make_pair(e[i].to,x);
}
}
int main()
{
n=read();m=read();pw[0]=1;
for(int i=1;i<=n;++i) pw[i]=2*pw[i-1]%mod;
for(int i=1;i<=m;++i) ins(read(),read());
Tarjan(1,0);
memset(vis,0,sizeof(vis));
for(int i=1;i<=now;++i) Solve(v[i]);
for(int i=1;i<=n;++i) ans=1LL*ans*(mod+1)/2%mod;
printf("%d\n",ans);
return 0;
}
考虑直接二分答案，求出每个点能到达的弧度区间。肯定有个点取到\([0,\frac{2\pi}{n})\)中，所以规定这个是第一个位置。将这些弧度在mod \(\frac{2\pi}{n}\)下离散，对于离散后的一段弧度区间，假设第一个位置取到这个中间，每个点是否能取到每个位置是确定的，可以跑二分图最大匹配来求是否存在方案。
这样好像是不能过的，但是可以发现，对于每个(点，位置)的对，有可能是一直可取或一直不可取，一直都可取的边就直接加上好了，只有\(O(n)\)个对关系会改变，可以记下改变的时间，用最大流配合加边/退流来快速求解图变化后的最大匹配。这样就可以过了。复杂度\(O(n^{3}logn)\)
#include<bits/stdc++.h>
#define MN 200
#define S 0
#define N 401
const double pi=acos(-1);
using namespace std;
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*10+ch-'0';ch=getchar();}
return x*f;
}
int n,T,ax[MN+5],ay[MN+5],cnt,num,cc,head[N+5],d[N+5],c[N+5],q[N+5],top;
double l[MN+5],r[MN+5],R,perlen;
struct edge{int to,next,w;}e[200005];
struct eve{double x;int k,i,j;}s[MN*4+5];
inline double dis(double x,double y){return sqrt(x*x+y*y);}
inline double Mod(double x,double y){double t=x-int(x/y)*y;return t<0?t+y:t;}
inline void ins(int f,int t,int w)
{
e[++cnt]=(edge){t,head[f],w};head[f]=cnt;
e[++cnt]=(edge){f,head[t],0};head[t]=cnt;
}
inline bool in(double l,double r,double x){return l>r?(x>=l||x<=r):(l<=x&&x<=r);}
bool bfs(int f,int t)
{
memset(d,0,sizeof(d));int i,j;
for(d[q[top=i=1]=f]=1;i<=top;++i)
for(j=c[q[i]]=head[q[i]];j;j=e[j].next)
if(e[j].w&&!d[e[j].to]) d[q[++top]=e[j].to]=d[q[i]]+1;
return d[t];
}
int dfs(int x,int f,int t)
{
if(x==t) return f;int used=0;
for(int&i=c[x];i;i=e[i].next)
if(e[i].w&&d[e[i].to]==d[x]+1)
{
int w=dfs(e[i].to,min(f-used,e[i].w),t);
used+=w;e[i].w-=w;e[i^1].w+=w;
if(used==f) return f;
}
return used;
}
#define eps (1e-14)
bool cmp(const eve&a,const eve&b){return a.x==b.x?a.k>b.k:a.x<b.x;}
void Add(int i,int j,double l,double r)
{
l=max(l,0.);r=min(r,perlen);if(l>r) return;
if(l<eps) ins(i,j+n,1); else s[++num]=(eve){l,1,i,j};
if(r<perlen) s[++num]=(eve){r+eps,0,i,j};
}
bool Solve(double len)
{
memset(head,0,sizeof(head));
cnt=1;num=0;
for(int i=1;i<=n;++i)
{
double d=dis(ax[i],ay[i]);
if(d<R-len||d>R+len) return false;
if(d<=len-R) {l[i]=0,r[i]=2*pi-eps;}
else
{
double L1=(len*len-R*R+d*d)/(2*d);
double l1=sqrt(len*len-L1*L1);
double r1=asin(l1/R);
double pr=atan2(ay[i],ax[i]);
if(L1>d) l[i]=3*pi+pr+r1,r[i]=3*pi+pr-r1;
else l[i]=pr-r1+2*pi,r[i]=pr+r1+2*pi;
}
while(l[i]>=2*pi) l[i]-=2*pi;
while(r[i]>=2*pi) r[i]-=2*pi;
for(int j=1;j<=n;++j)
{
double p=perlen*(j-1);
if(l[i]<=r[i]) Add(i,j,l[i]-p,r[i]-p);
else Add(i,j,0,r[i]-p),Add(i,j,l[i]-p,perlen);
}
}
int ans=0;
for(int i=1;i<=n;++i) ins(S,i,1),ins(i+n,T,1);
while(bfs(S,T)) ans+=dfs(S,1e9,T);
if(ans==n) return true;
sort(s+1,s+num+1,cmp);
for(int i=1;i<=num;++i)
{
if(s[i].k)
{
ins(s[i].i,s[i].j+n,1);
if(i<num&&s[i+1].k==1) continue;
while(bfs(S,T)) ans+=dfs(S,1e9,T);
if(ans==n) return true;
}
else
{
int x=s[i].i,y=s[i].j+n,z;
for(int i=head[x];i;i=e[i].next) if(e[i].to==y) {z=i;break;}
int t=e[z].w;e[z].w=e[z^1].w=0;
if(!t)
{
--ans;
if(bfs(x,S)) dfs(x,1,S);
if(bfs(T,y)) dfs(T,1,y);
}
}
}
return false;
}
int main()
{
n=read();R=read();perlen=2*pi/n;T=n*2+1;
for(int i=1;i<=n;++i) ax[i]=read(),ay[i]=read();
double l=0,r=300,mid;
while(r-l>4e-7)
{
mid=(l+r)*0.5;
if(Solve(mid)) r=mid;
else l=mid;
}
printf("%.10lf\n",mid);
return 0;
}
不合法向量的位置显然构成一个凸包。考虑建出它。
先随便从两个凸包中分别取一个点，那么不合法向量的位置是一个和第一个凸包长得一模一样的，再考虑所有的第二个凸包中的点，就相当于在第二个凸包的每一个位置都延伸出去一个和第一个凸包一样的图形，答案返回就是这些图形构成的凸包。仔细观察不难发现，只需要把两个凸包中所有线按照斜率一起排序，按顺序接起来就可以得到这个图形了，得到之后可以用二分/扫描线等方法求出每个询问向量是否位于凸包里面。
复杂度\(O((n+m+q)logn)\)
(听大佬说，这就是一个什么什么和，求A-B就好了)
#include<bits/stdc++.h>
#define pa pair<int,int>
#define MN 100000
using namespace std;
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*10+ch-'0';ch=getchar();}
return x*f;
}
set<int> st;
struct P{int x,y;long double s;}a[MN+5],b[MN+5],c[MN*2+5];
struct Line{int x,y,X,Y;}L[MN*2+5];
struct Ques{int x,k,y;}s[MN*5+5];
int n,m,Q,X,Y,num,lnum,q[MN+5],top,cc,Dy[MN+5],Ans[MN+5];
bool cmp(const P&a,const P&b){return a.s>b.s;}
bool cmpq(const Ques&a,const Ques&b){return a.x==b.x?a.k>b.k:a.x<b.x;}
long long Calc(const P&a,const P&b,const P&c){return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(c.x-a.x)*(b.y-a.y);}
void InsL(int x,int y,int X,int Y)
{
if(x>X||(x==X&&y>Y)) swap(x,X),swap(y,Y);
L[++lnum]=(Line){x,y,X,Y};
s[++cc]=(Ques){x,1,lnum};s[++cc]=(Ques){X+1,2,lnum};
}
void Solve(int&r,int&u,int&d,int x,int y,int k)
{
if(L[k].x==L[k].X) {if(y>=L[k].y&&y<=L[k].Y)r=1;return;}
long long X=1LL*(L[k].X-L[k].x)*(y-L[k].y)-1LL*(x-L[k].x)*(L[k].Y-L[k].y);
if(!X)r=1;if(X<0)d=1;if(X>0)u=1;
}
main()
{
n=read();m=read();Q=read();
for(int i=1;i<=n;++i) a[i].x=-read(),a[i].y=-read();
for(int i=1;i<=m;++i) b[i].x=read(),b[i].y=read();
for(int i=2;i<=n;++i) if(a[i].y<a[1].y||(a[i].y==a[1].y&&a[i].x<a[1].x)) swap(a[i],a[1]);
for(int i=2;i<=m;++i) if(b[i].y<b[1].y||(b[i].y==b[1].y&&b[i].x<b[1].x)) swap(b[i],b[1]);
for(int i=2;i<=n;++i) a[i].s=atan2(a[i].y-a[1].y,a[i].x-a[1].x);
for(int i=2;i<=m;++i) b[i].s=atan2(b[i].y-b[1].y,b[i].x-b[1].x);
X=b[1].x+a[1].x;Y=b[1].y+a[1].y;q[top=1]=1;
sort(a+2,a+n+1,cmp);sort(b+2,b+m+1,cmp);
for(int i=2;i<=n;++i)
{
while(top>1&&Calc(a[q[top-1]],a[q[top]],a[i])>=0) --top;
q[++top]=i;
}
q[top+1]=1;
for(int i=2;i<=top+1;++i)
++num,
c[num].x=a[q[i]].x-a[q[i-1]].x,
c[num].y=a[q[i]].y-a[q[i-1]].y,
c[num].s=(!c[num].y&&c[num].x<0)?-1e9:atan2(c[num].y,c[num].x);
q[top=1]=1;
for(int i=2;i<=m;++i)
{
while(top>1&&Calc(b[q[top-1]],b[q[top]],b[i])>=0) --top;
q[++top]=i;
}
q[top+1]=1;
for(int i=2;i<=top+1;++i)
++num,
c[num].x=b[q[i]].x-b[q[i-1]].x,
c[num].y=b[q[i]].y-b[q[i-1]].y,
c[num].s=(!c[num].y&&c[num].x<0)?-1e9:atan2(c[num].y,c[num].x);
sort(c+1,c+num+1,cmp);int px=X,py=Y;
for(int i=1;i<=num;++i) InsL(X,Y,X+c[i].x,Y+c[i].y),X+=c[i].x,Y+=c[i].y;
InsL(X,Y,px,py);
for(int i=1;i<=Q;++i)
{
int x=-read();Dy[i]=-read();
s[++cc]=(Ques){x,0,i};
}
sort(s+1,s+cc+1,cmpq);
for(int i=1;i<=cc;++i)
{
if(s[i].k==0)
{
int res=0,down=0,up=0;
for(set<int>::iterator it=st.begin();it!=st.end();++it)
Solve(res,down,up,s[i].x,Dy[s[i].y],*it);
Ans[s[i].y]=res|(down&up);
}
if(s[i].k==1) st.insert(s[i].y);
if(s[i].k==2) st.erase(s[i].y);
}
for(int i=1;i<=Q;++i) printf("%d\n",Ans[i]);
return 0;
}
这个题有点意思啊。。
考虑\(n=m\)的情况，每一条从从右上到左下的对角线一定都取相同的走法，那么只要确定了第一行就确定了整个矩阵，并且向下走的数量和\(n\)的\(gcd\)必须是1，否则没法走到所有格子。
考虑n!=m的情况，那么取\(d=gcd(n,m)\)，确定了\(d * d\)的矩阵的走法之后整个矩阵的走法也就确定了，走的总轮数是\(\frac{n*m}{d}\)。
考虑题目的询问，考虑枚举前d步走了\(a\)次向下，\(d-a\)次向右，那么对于每个\(0\leqslant x\leqslant a,0\leqslant y\leqslant d-a\)，求出假设走到了点\((x,y)\)，在走第t[x][y]轮的时候就会撞车。枚举撞车的轮数\(l\)和具体的撞车位置，那么走的路径中经过的点的t值，在这个点之前经过都要大于\(l\)，之后的要大等于\(l\)，做一次dp就可以求出方案了。
#include<bits/stdc++.h>
#define MN 50
#define mod 998244353
#define ms(x,y) memset(x,y,sizeof(x))
using namespace std;
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*10+ch-'0';ch=getchar();}
return x*f;
}
char s[MN+5][MN+5];
int n,m,f[MN+5][MN+5],g[MN+5][MN+5],t[MN+5][MN+5],ans;
inline int gcd(int x,int y){return y?gcd(y,x%y):x;}
inline void R(int&x,int y){x+=y;x>=mod?x-=mod:0;}
int main()
{
for(int ca=read();ca--;)
{
n=read();m=read();int G=gcd(n,m),l=n*m/G;ans=0;
for(int i=0;i<n;++i) scanf("%s",s[i]);
for(int tx=0;tx<=G;++tx)
{
int ty=G-tx;
if(gcd(tx,n)!=1||gcd(ty,m)!=1) continue;
ms(t,40);
for(int i=1,x=0,y=0;i<=l;++i,x=(x+tx)%n,y=(y+ty)%m)
for(int j=0;j<=tx;++j) for(int k=0;k<=ty;++k)
if(s[(x+j)%n][(y+k)%m]>'0') t[j][k]=min(t[j][k],i);
t[tx][ty]=1e9;
for(int i=1,x=0,y=0;i<=l;++i,x=(x+tx)%n,y=(y+ty)%m)
{
ms(f,0);ms(g,0);f[0][0]=1;g[tx][ty]=1;
for(int j=0;j<=tx;++j) for(int k=0;k<=ty;++k)
{
if(j&&t[j-1][k]>i) R(f[j][k],f[j-1][k]);
if(k&&t[j][k-1]>i) R(f[j][k],f[j][k-1]);
}
for(int j=tx;~j;--j) for(int k=ty;~k;--k)
{
if(j<tx&&t[j+1][k]>=i) R(g[j][k],g[j+1][k]);
if(k<ty&&t[j][k+1]>=i) R(g[j][k],g[j][k+1]);
}
for(int j=0;j<=tx;++j) for(int k=0;k<=ty;++k) if((j<tx||k<ty)&&t[j][k]==i)
ans=(ans+1LL*f[j][k]*g[j][k]%mod*((i-1)*G+j+k))%mod;
}
}
printf("%d\n",ans);
}
return 0;
}
这应该是最简单的一题吧，肯定是有左边一部分学生向右走，另一部分向左走，建出主席树二分出这个位置即可。
#include<bits/stdc++.h>
#define MN 500000
#define ll long long
using namespace std;
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*10+ch-'0';ch=getchar();}
return x*f;
}
struct Tree{int l,r,x;ll S;}T[12000005];
int n,m,cnt,rt[MN+5],a[MN+5];
inline void update(int x)
{
T[x].x=T[T[x].l].x+T[T[x].r].x;
T[x].S=T[T[x].l].S+T[T[x].r].S;
}
void Modify(int nx,int x,int l,int r,int k)
{
if(l==r){T[nx].x=T[x].x+1;T[nx].S=T[x].S+l;return;}
int mid=l+r>>1;
if(k<=mid) T[nx].r=T[x].r,T[nx].l=++cnt,Modify(cnt,T[x].l,l,mid,k);
else T[nx].l=T[x].l,T[nx].r=++cnt,Modify(cnt,T[x].r,mid+1,r,k);
update(nx);
}
inline ll Sum(int l,int r){return 1LL*(l+r)*(r-l+1)/2;}
int main()
{
n=read();m=read();
for(int i=1;i<=n;++i) Modify(rt[i]=++cnt,rt[i-1],1,2e6,read());
for(int i=1;i<=m;++i)
{
int la=read(),ra=read(),L=read(),R=L+ra-la,l=1,r=2e6,mid;
int nx=rt[ra],x=rt[la-1],S=0;ll ls=0,rs=0;
while(l<r)
{
mid=l+r>>1;int sz=T[T[nx].l].x-T[T[x].l].x;
if(sz+S>=mid-L+1) S+=sz,l=mid+1,ls+=T[T[nx].l].S-T[T[x].l].S,x=T[x].r,nx=T[nx].r;
else rs+=T[T[nx].r].S-T[T[x].r].S,r=mid,x=T[x].l,nx=T[nx].l;
}
if(l<L) printf("%lld\n",rs-Sum(L,R));
else if(l>R) printf("%lld\n",Sum(L,R)-ls);
else printf("%lld\n",rs+T[nx].S-T[x].S-ls+Sum(L,l-1)-Sum(l,R));
}
return 0;
}