JSOI2018简要题解

复杂度分析题。

定义状态fi,j,0/1,0/1f_{i,j,0/1,0/1}fi,j,0/1,0/1​表示以iii为根子树放jjj个机器iii这个放不放,iii这个是否已放来进行dpdpdp

可以通过分类讨论证明做树上背包的时间复杂度是O(nk)O(nk)O(nk)的。

代码：

#include bits/stdc++.h
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans 3)+(ans 1)+(ch^48),ch=getchar();
return ans;
typedef long long ll;
const int N=1e5+5,M=105,mod=1e9+7;
vector int e[N];
int n,K,f[N][M][2][2],g[M][2][2],siz[N];
inline int add(const int a,const int b){return a+b =mod?a+b-mod:a+b;}
inline int dec(const int a,const int b){return a =b?a-b:a-b+mod;}
inline int mul(const int a,const int b){return (ll)a*b%mod;}
inline void update(int a,const int b){a=add(a,b);}
void dfs(int p,int fa){
siz[p]=1;
f[p][0][0][0]=f[p][1][1][0]=1;
for(ri i=0,v;i e[p].size();++i){
if((v=e[p][i])==fa)continue;
dfs(v,p);
for(ri j=0,up=min(siz[p],K);j ++j)for(ri k=0;j+k =K k =siz[v];++k){
if(f[p][j][0][0]){
update(g[j+k][0][0],mul(f[p][j][0][0],f[v][k][0][1]));
update(g[j+k][0][1],mul(f[p][j][0][0],f[v][k][1][1]));
if(f[p][j][0][1])update(g[j+k][0][1],mul(f[p][j][0][1],add(f[v][k][0][1],f[v][k][1][1])));
if(f[p][j][1][0]){
update(g[j+k][1][0],mul(f[p][j][1][0],add(f[v][k][0][0],f[v][k][0][1])));
update(g[j+k][1][1],mul(f[p][j][1][0],add(f[v][k][1][0],f[v][k][1][1])));
if(f[p][j][1][1])update(g[j+k][1][1],mul(f[p][j][1][1],add(add(f[v][k][0][0],f[v][k][0][1]),add(f[v][k][1][0],f[v][k][1][1]))));
siz[p]+=siz[v];
for(ri j=0,up=min(siz[p],K);j ++j){
f[p][j][0][0]=g[j][0][0],g[j][0][0]=0;
f[p][j][0][1]=g[j][0][1],g[j][0][1]=0;
f[p][j][1][0]=g[j][1][0],g[j][1][0]=0;
f[p][j][1][1]=g[j][1][1],g[j][1][1]=0;
int main(){
n=read(),K=read();
for(ri i=1,u,v;i ++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
dfs(1,0);
cout add(f[1][K][1][1],f[1][K][0][1]);
return 0;

根据期望的线性性转化为求每条边的贡献。

桥边直接根据连接的两个连通块的sizesizesize更新答案。

对于一个环把这个环提出来dpdpdp，枚举环上面的最长连续空段和选择的起点终点做dpdpdp，利用前缀和优化可以做到O(n3)O(n^3)O(n3)

代码：

#include bits/stdc++.h
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans 3)+(ans 1)+(ch^48),ch=getchar();
return ans;
const int N=205,mod=1e9+7;
typedef long long ll;
inline int add(const int a,const int b){return a+b =mod?a+b-mod:a+b;}
inline int dec(const int a,const int b){return a =b?a-b:a-b+mod;}
inline int mul(const int a,const int b){return (ll)a*b%mod;}
inline int ksm(int a,int p){int ret=1;for(;p;p =1,a=mul(a,a))if(p 1)ret=mul(ret,a);return ret;}
inline void update(int a,const int b){a=add(a,b);}
int n,m,pow2[N],siz[N],fa[N],dep[N],ans=0;
bool ban[N];
vector int e[N];
inline void init(){pow2[0]=1;for(ri i=1;i ++i)pow2[i]=mul(pow2[i-1],2);}
inline void solve(int st,int ed){
static int s1[N][N],s2[N][N],q[N],w[N],top;
int p=ed;
q[top=1]=p;
while(p^st)ban[p]=1,q[++top]=(p=fa[p]);
reverse(q+1,q+top+1);
for(ri i=1;i ++i)w[i]=dec(pow2[siz[q[i]]-siz[q[i+1]]],1);
w[top]=dec(pow2[siz[q[top]]],1);
w[1]=dec(pow2[n-siz[q[2]]],1);
for(ri l=1;l ++l){
for(ri k=0;k =top;++k)s1[l][k]=w[l];
for(ri r=l+1;r =top;++r){
for(ri k=1;k =r-l;++k){
int f=mul(w[r],add(s1[r-k][k],dec(s2[r-1][k],s2[r-k][k])));
update(ans,mul(f,top-max(top-r+l,k)));
s1[r][k]=add(s1[r][k-1],f),s2[r][k]=add(s2[r-1][k],f);
for(ri k=r-l+1;k =top;++k)s1[r][k]=s1[r][k-1],s2[r][k]=s2[r-1][k];
for(ri i=0;i =top;++i)for(ri j=0;j =top;++j)s1[i][j]=s2[i][j]=0;
void dfs(int p){
siz[p]=1;
int tmp=0;
for(ri i=0,v;i e[p].size();++i){
if((v=e[p][i])==fa[p])continue;
if(!dep[v]){fa[v]=p,dep[v]=dep[p]+1,dfs(v),siz[p]+=siz[v];continue;}
if(dep[v] dep[p])tmp=v;
if(tmp)solve(p,tmp);
int main(){
n=read(),m=read();
for(ri i=1,u,v;i ++i)u=read(),v=read(),e[u].push_back(v),e[v].push_back(u);
init(),dep[1]=1,dfs(1);
for(ri i=1;i ++i)if(!ban[i])update(ans,mul(dec(pow2[siz[i]],1),dec(pow2[n-siz[i]],1)));
cout mul(ans,ksm(pow2[n],mod-2));
return 0;

二分答案之后求每个点以这个二分值作为半径跟给出圆的交点，显然会出现nnn段圆弧，只需要看能不能在nnn段中各选一个点构成一个正nnn边形。

直接枚举正nnn边形的某一个起点可以做到O(n4logn)O(n^4log_n)O(n4logn​)

然后我们把所有的弧都模上2πn\frac{2\pi}nn2π​，这样来枚举起点是等价的。

但是我们发现由于起点挪动的距离不超过2πn\frac{2\pi}nn2π​，因此每次挪动最多有一个点对从不可行变成可行，最多有一个点对icon个可行变成不可行。

因此我们用扫描线优化这个过程可以做到O(n3logn)O(n^3log_n)O(n3logn​)

代码：

#include bits/stdc++.h
#define ri register int
using namespace std;
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch))f^=ch=='-',ch=getchar();
while(isdigit(ch))ans=(ans 3)+(ans 1)+(ch^48),ch=getchar();
return f?ans:-ans;
const int N=605,M=2e6+5;
const double pi=acos(-1.0),eps=1e-7;
struct pot{
double x,y;
pot(double _x=0,double _y=0):x(_x),y(_y){}
inline double mod(){return sqrt(x*x+y*y);}
}a[N];
int n;
double R,du;
namespace Dinic{
int d[N],s,t,first[N],cnt,F;
struct edge{int v,next,c;}e[M];
struct Node{
double ang;
int s,t,type;
Node(double _ang=0,int _s=0,int _t=0,int _type=0):ang(_ang),s(_s),t(_t),type(_type){}
friend inline bool operator (const Node a,const Node b){return a.ang==b.ang?a.type b.type:a.ang b.ang;}
}seq[N];
inline void init(){cnt=-1,s=0,t=n*2+1,F=0;}
inline void addedge(int u,int v,int c){e[++cnt].v=v,e[cnt].c=c,e[cnt].next=first[u],first[u]=cnt;}
inline void add(int u,int v,int c){addedge(u,v,c),addedge(v,u,0);}
inline bool bfs(){
static int q[N],hd,tl;
for(ri i=s;i ++i)d[i]=-1;
d[q[hd=tl=1]=s]=0;
while(hd =tl){
int x=q[hd++];
for(ri v,i=first[x];~i;i=e[i].next){
if(!e[i].c||~d[v=e[i].v])continue;
d[q[++tl]=v]=d[x]+1;
return ~d[t];
inline int dfs(int x,int f){
if(!f||x==t)return f;
int flow=f;
for(ri tmp,i=first[x],v;~i;i=e[i].next){
if(!flow)return f;
if(e[i].c d[v=e[i].v]==d[x]+1){
tmp=dfs(v,min(flow,e[i].c));
if(!tmp)d[v]=-1;
flow-=tmp,e[i].c-=tmp,e[i^1].c+=tmp;
return f-flow;
inline void solve(){while(bfs())F+=dfs(s,0x3f3f3f3f);}
inline void popflow(int x,int y){
bool f=0;
for(ri i=first[x];~i;i=e[i].next)if(e[i].v==y){e[i].c?f=1:--F,e[i].c=e[i^1].c=0;break;}
if(f)return;
for(ri i=first[s];~i;i=e[i].next)if(e[i].v==x){e[i].c=1,e[i^1].c=0;break;}
for(ri i=first[y];~i;i=e[i].next)if(e[i].v==t){e[i].c=1,e[i^1].c=0;break;}
while(bfs())F+=dfs(s,0x3f3f3f3f);
inline bool check(const double lim){
static int top;
F=0,cnt=-1,top=0;
for(ri i=s;i ++i)first[i]=-1;
double d,ang,det,bigang,smallang;
for(ri tl,tr,i=1;i ++i){
d=a[i].mod();
if(lim =R-d||lim =d-R)return 0;
if(R+d =lim)for(ri j=1;j ++j)add(i,j+n,1);
else{
ang=atan2(a[i].y,a[i].x);
det=acos((d*d+R*R-lim*lim)/(d*R*2));
smallang=ang-det,bigang=ang+det;
while(smallang 0)smallang+=pi*2;
while(bigang 0)bigang+=pi*2;
tl=smallang/du,tr=bigang/du;
smallang-=du*tl,bigang-=du*tr;
++tl,++tr;
seq[++top]=(Node){smallang,i,tl,1};
seq[++top]=(Node){bigang,i,tr,-1};
if(tl =tr)for(ri j=tl+1;j ++j)add(i,j+n,1);
else{
for(ri j=1;j ++j)add(i,j+n,1);
for(ri j=tl+1;j ++j)add(i,j+n,1);
sort(seq+1,seq+top+1);
for(ri i=1;i ++i)add(s,i,1),add(i+n,t,1);
solve();
if(F==n)return 1;
for(ri i=1;i =top;++i){
if(~seq[i].type){
add(seq[i].s,seq[i].t+n,1);
while(bfs())F+=dfs(s,0x3f3f3f3f);
if(F==n)return 1;
else popflow(seq[i].s,seq[i].t+n);
return 0;
int main(){
n=read(),R=read(),du=pi*2/n,Dinic::init();
double l=0,r=400;
for(ri i=1;i ++i)a[i].x=read(),a[i].y=read();
while(r-l =eps){
double mid=(l+r)/2;
if(Dinic::check(mid))r=mid;
else l=mid;
printf("%.8lf",l);
return 0;

题解戳，其实就是求凸包的Minkowski和。

代码：

#include bits/stdc++.h
#define int long long
#define ri register int
using namespace std;
inline int read(){
int ans=0;
bool f=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f^=1;ch=getchar();}
while(isdigit(ch))ans=(ans 3)+(ans 1)+(ch^48),ch=getchar();
return f?ans:-ans;
typedef long long ll;
const int N=2e5+5;
struct pot{
ll x,y;
pot(ll _x=0,ll _y=0):x(_x),y(_y){};
friend inline pot operator+(const pot a,const pot b){return pot(a.x+b.x,a.y+b.y);}
friend inline pot operator-(const pot a,const pot b){return pot(a.x-b.x,a.y-b.y);}
friend inline ll operator^(const pot a,const pot b){return a.x*b.y-a.y*b.x;}
friend inline bool operator (const pot a,const pot b){return a.x==b.x?a.y b.y:a.x }
inline ll mod(){return x*x+y*y;}
}A[N 1],a1[N],a2[N];
inline void graham(pot a[],int n){
static int q[N],top;
static pot b[N];
sort(a+1,a+n+1);
q[top=1]=1;
for(ri i=2;i ++i){
while(top 1 ((a[i]-a[q[top-1]])^(a[q[top]]-a[q[top-1]])) =0)--top;
q[++top]=i;
for(ri len=top,i=n-1;i;--i){
while(top len ((a[i]-a[q[top-1]])^(a[q[top]]-a[q[top-1]])) =0)--top;
q[++top]=i;
n=top;
for(ri i=1;i ++i)b[i]=a[q[i]];
for(ri i=1;i ++i)a[i]=b[i];
inline void Minkowski(pot a[],int tot,pot x[],int n,pot y[],int m){
static int pa,pb;
--n,--m;
a[tot=1]=x[pa=1]+y[pb=1];
while(pa =n pb =m){
pot ta=x[pa+1]-x[pa],tb=y[pb+1]-y[pb];
++tot;
ll tmp=ta^tb;
if(!tmp)a[tot]=a[tot-1]+ta+tb,++pa,++pb;
else if(tmp =0)a[tot]=a[tot-1]+ta,++pa;
else a[tot]=a[tot-1]+tb,++pb;
while(pa =n)++tot,a[tot]=a[tot-1]+x[pa+1]-x[pa],++pa;
while(pb =m)++tot,a[tot]=a[tot-1]+y[pb+1]-y[pb],++pb;
--tot;
graham(a,tot);
--tot;
int n,m,len,q;
inline bool check(const pot p){
if(((p-A[1])^(A[len]-A[1])) 0)return 0;
if(((p-A[1])^(A[2]-A[1])) 0)return 0;
int l=2,r=len-1,ans=2;
while(l =r){
int mid=l+r 1;
ll tmp=(p-A[1])^(A[mid]-A[1]);
if(!tmp)return (p-A[1]).mod() =(A[mid]-A[1]).mod();
if(tmp 0)l=mid+1,ans=mid;
else r=mid-1;
ll tmp=(p-A[ans])^(A[ans+1]-A[ans]);
if(!tmp)return (p-A[ans]).mod() =(A[ans+1]-A[ans]).mod();
return tmp
signed main(){
n=read(),m=read(),q=read();
for(ri i=1;i ++i)a1[i].x=read(),a1[i].y=read();
for(ri i=1;i ++i)a2[i].x=-read(),a2[i].y=-read();
graham(a1,n),graham(a2,m);
Minkowski(A,len,a1,n,a2,m);
for(ri x,y;q;--q)x=read(),y=read(),cout check(pot(x,y)) '\n';
return 0;

神题，ORZORZORZ

代码：

#include bits/stdc++.h
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans 3)+(ans 1)+(ch^48),ch=getchar();
return ans;
const int N=55,mod=998244353;
int n,m,G,turn,ans;
int ban[N][N],f[N][N],g[N][N];
char s[N][N];
typedef long long ll;
inline int gcd(int a,int b){while(b){int t=a;a=b,b=t-t/a*a;}return a;}
inline int add(const int a,const int b){return a+b =mod?a+b-mod:a+b;}
inline int mul(const int a,const int b){return (ll)a*b%mod;}
inline void update(int a,const int b){a=add(a,b);}
int main(){
for(ri tt=read();tt;--tt){
n=read(),m=read(),G=gcd(n,m),turn=n*m/G,ans=0;
for(ri i=0;i ++i)scanf("%s",s[i]);
for(ri tx=0,ty=G;tx ++tx,--ty)if(gcd(tx,n)==1 gcd(ty,m)==1){
memset(ban,0x3f,sizeof(ban));
for(ri t=1,gx=0,gy=0;t =turn;++t,(gx+=tx)%=n,(gy+=ty)%=m)
for(ri dx=0;dx ++dx)for(ri dy=0;dy ++dy)
if(s[((gx+dx)%n)][(gy+dy)%m]^48)ban[dx][dy]=min(ban[dx][dy],t);
for(ri t=1;t =turn;++t){
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
f[0][0]=g[tx][ty]=1;
for(ri i=0;i ++i)for(ri j=0;j ++j){
if(i ban[i-1][j] t)update(f[i][j],f[i-1][j]);
if(j ban[i][j-1] t)update(f[i][j],f[i][j-1]);
for(ri i=tx;~i;--i)for(ri j=ty;~j;--j){
if((i^tx) ban[i+1][j] =t)update(g[i][j],g[i+1][j]);
if((j^ty) ban[i][j+1] =t)update(g[i][j],g[i][j+1]);
for(ri i=0;i ++i)for(ri j=0;j ++j)
if(i+j ban[i][j]==t)update(ans,mul((t-1)*G+i+j,mul(f[i][j],g[i][j])));
cout ans '\n';
return 0;

最沙雕的一道题。

直接主席树维护就完了。

代码：

#include bits/stdc++.h
#define ri register int
using namespace std;
inline char get_char(){
static char buf[1000001],*p1=buf,*p2=buf;
return p1==p2 (p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
inline int read(){
int ans=0;
char ch=get_char();
while(!isdigit(ch))ch=get_char();
while(isdigit(ch))ans=(ans 3)+(ans 1)+(ch^48),ch=get_char();
return ans;
typedef long long ll;
const int N=1e6+5;
int n,m,rt[N];
namespace SGT{
#define lc (son[p][0])
#define rc (son[p][1])
int siz[N*25],son[N*25][2],tot=0;
ll sum[N*25];
inline void update(int p,int o,int l,int r,int k){
sum[p=++tot]=sum[o]+k,siz[p]=siz[o]+1,lc=son[o][0],rc=son[o][1];
if(l==r)return;
int mid=l+r 1;
k =mid?update(lc,son[o][0],l,mid,k):update(rc,son[o][1],mid+1,r,k);
inline ll query(int pl,int pr,int l,int r,int ql,int qr){
if(sum[pl]==sum[pr])return 0ll;
if(r =qr)return (ll)(qr+ql)*(qr-ql+1)/2-(sum[pr]-sum[pl]);
if(l =qr)return sum[pr]-sum[pl]-(ll)(qr+ql)*(qr-ql+1)/2;
int mid=l+r 1,tmp=siz[son[pr][0]]-siz[son[pl][0]];
return query(son[pl][0],son[pr][0],l,mid,ql,ql+tmp-1)+query(son[pl][1],son[pr][1],mid+1,r,ql+tmp,qr);
#undef lc
#undef rc
int main(){
n=read(),m=read();
for(ri i=1;i ++i)SGT::update(rt[i],rt[i-1],1,1000000,read());
for(ri i=1,l,r,k;i ++i)l=read(),r=read(),k=read(),cout SGT::query(rt[l-1],rt[r],1,1000000,k,k+r-l) '\n';
return 0;