【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）（绝地反击网游）

25-02-19 12

本文将分享【BZOJ5316】[JSOI2018]绝地反击的详细内容，并且还将对网络流，计算几何，二分进行详尽解释，此外，我们还将为大家带来关于BZOJ5301:[Cqoi2018]异或序列、bzoj

本文将分享【BZOJ5316】[JSOI2018]绝地反击的详细内容，并且还将对网络流，计算几何，二分进行详尽解释，此外，我们还将为大家带来关于BZOJ5301: [Cqoi2018]异或序列、bzoj5301[CQOI2018]异或序列、BZOJ5314: [Jsoi2018]潜入行动 (树形DP)、BZOJ5316 : [Jsoi2018]绝地反击的相关知识，希望对你有所帮助。

本文目录一览：

【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）（绝地反击网游）
BZOJ5301: [Cqoi2018]异或序列
bzoj5301[CQOI2018]异或序列
BZOJ5314: [Jsoi2018]潜入行动 (树形DP)
BZOJ5316 : [Jsoi2018]绝地反击

【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）（绝地反击网游）

【BZOJ5316】[JSOI2018]绝地反击（网络流，计算几何，二分）

题面

BZOJ 洛谷

题解

很明显需要二分一个答案。那么每个点可以确定的范围就是以当前点为圆心，二分出来的答案为半径画一个圆，和目标的圆的交就是可行的区间。首先我们不知道正$n$边形的转角，如果我们知道的话，可以直接暴力网络流来进行$check$。首先一个答案可行，意味着某个点在目标圆上覆盖的弧的两端中，一定有一个是可行的。所以我们需要验证的转角只有$2n$个。这样子暴力跑网络流的次数是$2nlogn$次。考虑如何优化这个过程。发现合法的转角一共$2n$个，把它们按照转角排序，考虑从小往大改变转角的过程，显然每次会删掉一个可行的匹配，或者是加入一组可行的匹配。那么这里删边直接退流就好了，不需要每次构图重建。因为是二分图，退流直接手动删边就行了。加边直接加完之后重新增广一次就行了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX 605
const double Pi=acos(-1),eps=1e-8;
const int inf=1000000000;
inline int read()
{
	int x=0;bool t=false;char ch=getchar();
	while((ch<''0''||ch>''9'')&&ch!=''-'')ch=getchar();
	if(ch==''-'')t=true,ch=getchar();
	while(ch<=''9''&&ch>=''0'')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}
int n,R,S,T;
struct Line{int v,next,w;}e[MAX*MAX];
int h[MAX],cnt=2,cur[MAX];
inline void Add(int u,int v,int w)
{
	e[cnt]=(Line){v,h[u],w};h[u]=cnt++;
	e[cnt]=(Line){u,h[v],0};h[v]=cnt++;
}
int level[MAX];
bool bfs()
{
	for(int i=S;i<=T;++i)level[i]=0;
	for(int i=S;i<=T;++i)cur[i]=h[i];
	queue<int> Q;level[S]=1;Q.push(S);
	while(!Q.empty())
	{
		int u=Q.front();Q.pop();
		for(int i=h[u];i;i=e[i].next)
			if(e[i].w&&!level[e[i].v])
				level[e[i].v]=level[u]+1,Q.push(e[i].v);
	}
	return level[T];
}
int dfs(int u,int flow)
{
	if(u==T||!flow)return flow;
	int ret=0;
	for(int &i=cur[u];i;i=e[i].next)
	{
		int v=e[i].v,d=0;
		if(e[i].w&&level[v]==level[u]+1)
		{
			d=dfs(v,min(flow,e[i].w));
			ret+=d;flow-=d;
			e[i].w-=d;e[i^1].w+=d;
			if(!flow)break;
		}
	}
	if(!flow)level[u]=0;
	return ret;
}
void Delete(int u,int v,int &flow)
{
	int val=0;
	for(int i=h[v],j=0;i;j=i,i=e[i].next)
		if(e[i].v==u){j?(e[j].next=e[i].next):(h[v]=e[i].next);break;}
	for(int i=h[u],j=0;i;j=i,i=e[i].next)
		if(e[i].v==v){j?(e[j].next=e[i].next):(h[u]=e[i].next);val=e[i].w^1;break;}
	if(!val)return;--flow;
	for(int i=h[S];i;i=e[i].next)if(e[i].v==u){e[i].w^=1,e[i^1].w^=1;break;}
	for(int i=h[T];i;i=e[i].next)if(e[i].v==v){e[i].w^=1,e[i^1].w^=1;break;}
	if(bfs())flow+=dfs(S,inf);
}
struct Point{double x,y;}p[MAX];
struct Degree{double t;int u,v,opt;}q[MAX];
bool operator<(Degree a,Degree b){return a.t!=b.t?a.t<b.t:a.opt>b.opt;}
double alpha;
bool check(double mid)
{
	for(int i=S;i<=T;++i)h[i]=0;cnt=2;
	int tot=0;
	for(int i=1;i<=n;++i)
	{
		double dis=sqrt(p[i].x*p[i].x+p[i].y*p[i].y);
		if(dis>R+mid||dis<R-mid)return false;
		if(dis+R<=mid)
			for(int j=1;j<=n;++j)Add(i,j+n,1);
		else
		{
			double ang=atan2(p[i].y,p[i].x);
			double d=acos((1.0*R*R+dis*dis-mid*mid)/(2*R*dis));
			double l=ang-d,r=ang+d;
			while(l<0)l+=2*Pi;while(r<0)r+=2*Pi;
			int L=l/alpha,R=r/alpha;
			q[++tot]=(Degree){l-L*alpha,i,L+1,1};
			q[++tot]=(Degree){r-R*alpha,i,R+1,-1};
			++L,++R;
			if(l<=r)
				for(int j=L+1;j<=R;++j)Add(i,j+n,1);
			else
			{
				for(int j=L+1;j<=n;++j)Add(i,j+n,1);
				for(int j=1;j<=R;++j)Add(i,j+n,1);
			}
		}
	}
	for(int i=1;i<=n;++i)Add(S,i,1),Add(i+n,T,1);
	sort(&q[1],&q[tot+1]);int ans=0;
	while(bfs())ans+=dfs(S,inf);
	if(ans==n)return true;
	for(int i=1;i<=tot;++i)
		if(q[i].opt==1)
		{
			Add(q[i].u,q[i].v+n,1);
			if(bfs())ans+=dfs(S,inf);
			if(ans==n)return true;
		}
		else Delete(q[i].u,q[i].v+n,ans);
	return false;
}
int main()
{
	n=read();R=read();alpha=2*Pi/n;
	S=0;T=n+n+1;
	for(int i=1;i<=n;++i)p[i].x=read(),p[i].y=read();
	double l=0,r=400;
	while(r-l>eps)
	{
		double mid=(l+r)/2;
		if(check(mid))r=mid;
		else l=mid;
	}
	printf("%.8lf\n",l);
	return 0;
}

BZOJ5301: [Cqoi2018]异或序列

【传送门：BZOJ5301】

简要题意：

　　给出长度为n的序列，给出m个询问，并给出k，每个询问输入l,r

　　每个询问输出l到r的序列中的所有子串中的异或和为k的子串数量

题解：

　　莫队

　　异或，真是个神东西

　　首先异或和满足前缀，也就是说设sum[i]为a[1]^a[2]^...^a[i]，那么a[i]^a[i+1]^...^a[j]=sum[j]^sum[i-1]

　　而且异或不仅满足交换律，而且对于a^b=c时，a^c=b，b^c=a这两个式子同样成立

　　那么就好做了，假设当前i到j这个子串的异或和为k，就说明sum[j]^sum[i-1]=k，也就是sum[i-1]^k=sum[j]，sum[j]^k=sum[i-1]

　　然后在区间转移的时候，设cnt[i]为当前区间值为i的前缀有多少个，然后对于增加序列长度的操作，假设新加的位置为r+1，我们先将cnt[sum[r+1]]++，然后求出ans+=cnt[sum[r+1]^k]，左边扩展也是如此，不过注意，向左扩展时，对ans的更新是用sum[l-1]的，因为是sum[j]与sum[i-1]可以满足前缀

　　而且向右扩展的时候，如果sum[r+1]^k=sum[l-1]的话，ans++，因为我们更新的时候没有计算[l...r+1]区间的影响，所以要维护一下

　　而对于区间缩小的情况，就ans先减，再更新cnt，因为要先消除贡献再减cnt，其它步骤类似就好了

参考代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
typedef long long LL;
struct question
{
    int l,r,id;LL d;
}q[110000];
int belong[110000],block;
bool cmp1(question n1,question n2)
{
    if(belong[n1.l]==belong[n2.l]) return n1.r<n2.r;
    else return belong[n1.l]<belong[n2.l];
}
bool cmp2(question n1,question n2)
{
    return n1.id<n2.id;
}
LL ans;
int sum[110000];
LL cnt[110000];
int main()
{
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++)
    {
        int d;
        scanf("%d",&d);
        sum[i]=sum[i-1]^d;
    }
    block=int(sqrt(n));
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
    for(int i=1;i<=m;i++) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+m+1,cmp1);
    memset(cnt,0,sizeof(cnt));
    int l=1,r=0;ans=0;
    for(int i=1;i<=m;i++)
    {
        while(r<q[i].r)
        {
            r++;
            cnt[sum[r]]++;
            ans+=cnt[sum[r]^k];
            if((sum[r]^k)==sum[l-1]) ans++;
        }
        while(r>q[i].r)
        {
            ans-=cnt[sum[r]^k];
            cnt[sum[r]]--;
            if((sum[r]^k)==sum[l-1]) ans--;
            r--;
        }
        while(l<q[i].l)
        {
            ans-=cnt[sum[l-1]^k];
            cnt[sum[l]]--;
            l++;
        }
        while(l>q[i].l)
        {
            l--;
            cnt[sum[l]]++;
            ans+=cnt[sum[l-1]^k];
        }
        q[i].d=ans;
    }
    sort(q+1,q+m+1,cmp2);
    for(int i=1;i<=m;i++) printf("%lld\n",q[i].d);
    return 0;
}

bzoj5301[CQOI2018]异或序列

###题意已知一个长度为 n 的整数数列 a[1],a[2],…,a[n] ，给定查询参数 l、r ，问在 [l,r] 区间内，有多少连续子序列满足异或和等于 k 。也就是说，对于所有的 x，y (l≤x≤y≤r)，能够满足a[x]^a[x+1]^…^a[y]=k的x，y有多少组。 ###分析这样的题目首先按照异或运算前缀和,就变成多次查询区间内有多少对数满足异或和为k. 考虑简单的情况.异或和为0的时候,就变成查询区间内有多少对数相同.这是很显然的莫队题目. 那么异或和为k的时候我们也可以考虑莫队.比较简明的思路是用trie树维护区间内所有的数字,加入/删除数字的时候更新答案. 另一种方式是,把所有的前缀和异或上k,组成另外一个数列,那么对于询问的区间在原先的前缀和数列和异或k的前缀和数列上都有一个数集,然后找两个数集的相同的数对(就是找这样的数对:数值相同,但是一个数在这个数集,另一个数在那个数集).

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
int a[maxn],s1[maxn],s2[maxn];
int cnt1[500000],cnt2[500000],ans;
int SZ=250;
struct query{
    int l,r,num,ans;
    void read(){
        scanf("%d%d",&l,&r);l--;
    }
}Q[maxn];
bool cmp1(const query &A,const query &B){
    if(A.l/SZ!=B.l/SZ)return A.l<B.l;
    return A.r<B.r;
}
void init(int l,int r){
    //printf("%d %d\n",l,r);
    
    for(int i=l;i<=r;++i){
        //printf("%d ",s1[i]);
        cnt1[s1[i]]++;
    }//printf("\n");
    for(int i=l;i<=r;++i){
        cnt2[s2[i]]++;//printf("%d ",s2[i]);
        ans+=cnt1[s2[i]];
    }//printf("\n");
    //printf("%d\n",ans);
}
void move(int l1,int r1,int l2,int r2){
    for(int i=l1;i<l2;++i){
        ans-=cnt2[s1[i]];ans-=cnt1[s2[i]];
        cnt1[s1[i]]--;cnt2[s2[i]]--;
        if(s1[i]==s2[i])ans+=1;
    }
    for(int i=l1-1;i>=l2;--i){
        ans+=cnt2[s1[i]];ans+=cnt1[s2[i]];
        cnt1[s1[i]]++;cnt2[s2[i]]++;
        if(s1[i]==s2[i])ans-=1;
    }
    for(int i=r1+1;i<=r2;++i){
        ans+=cnt2[s1[i]];ans+=cnt1[s2[i]];
        cnt1[s1[i]]++;cnt2[s2[i]]++;
        if(s1[i]==s2[i])ans-=1;    
    }
    for(int i=r1;i>r2;--i){
        ans-=cnt2[s1[i]];ans-=cnt1[s2[i]];
        cnt1[s1[i]]--;cnt2[s2[i]]--;
        if(s1[i]==s2[i])ans+=1;
    }
}
int res[maxn];
int main(){
    int n,m,k;scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
    }
    for(int i=1;i<=n;++i)s1[i]=s1[i-1]^a[i];
    for(int i=0;i<=n;++i)s2[i]=s1[i]^k;
    for(int i=1;i<=m;++i)Q[i].read();
    for(int i=1;i<=m;++i)Q[i].num=i;
    sort(Q+1,Q+m+1,cmp1);
    init(Q[1].l,Q[1].r);Q[1].ans=ans;
    for(int i=2;i<=m;++i){
        move(Q[i-1].l,Q[i-1].r,Q[i].l,Q[i].r);
        Q[i].ans=ans;
    }
    if(k==0){
        for(int i=1;i<=m;++i)Q[i].ans-=(Q[i].r-Q[i].l+1);
    }
    for(int i=1;i<=m;++i)Q[i].ans/=2;
    for(int i=1;i<=m;++i)res[Q[i].num]=Q[i].ans;
    for(int i=1;i<=m;++i)printf("%d\n",res[i]);
    return 0;
}

BZOJ5314: [Jsoi2018]潜入行动 (树形DP)

题意:一棵树选择恰好k个结点放置监听器

　　每个监听器只能监听相邻的节点

　　问能使得所有节点被监听的种类数

题解:反正就是很well-known的树形DP了

　　至于时间复杂度为什么是nk 不会不学

　　很好想到四维dp 在x节点放置j个 x有没有放监听器 x有没有被监听

　　瞎搞搞就好了头写昏了转移就抄别人了的TAT

　　关键是这个题开ll会mle 不开会爆int 取%频繁还会tle

　　西安太热了!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n, k;

struct node
{
    int to, nex;
}E[200005];
int head[100005];
int sz[100005];
int dp[100002][102][2][2]; //放不放 被占用没
ll tmp[102][2][2];

inline void add(int &x,ll y)
{
    if(x + y >= mod) x = x + y - mod;
    else x = x + y;
}

void dfs(int x, int fa)
{
    sz[x] = 1;
    dp[x][1][1][0] = 1; //放
    dp[x][0][0][0] = 1; //不放
    int c = head[x];
    for(int i = c; i; i = E[i].nex)
    {
        int v = E[i].to;
        if(v == fa) continue;
        dfs(v, x);

        int tx = min(k, sz[x]);
        int tv = min(k, sz[v]);
        for(int j = 0; j <= tx; j++)
            for(int jj = 0; jj < 2; jj++)
                for(int jjj = 0; jjj < 2; jjj++)
                    tmp[j][jj][jjj] = dp[x][j][jj][jjj], dp[x][j][jj][jjj] = 0;

        for(int j = 0; j <= tx; j++)
        {
            for(int jj = 0; jj <= tv && j + jj <= k; jj++)
            {
                add(dp[x][j + jj][0][0], tmp[j][0][0] * dp[v][jj][0][1] % mod);
                add(dp[x][j + jj][0][1], (tmp[j][0][0] * dp[v][jj][1][1] + tmp[j][0][1] * (dp[v][jj][0][1] + dp[v][jj][1][1]))%mod);
                add(dp[x][j + jj][1][0], tmp[j][1][0] * (dp[v][jj][0][0] + dp[v][jj][0][1]) % mod);
                add(dp[x][j + jj][1][1], (tmp[j][1][0] * (dp[v][jj][1][0] + dp[v][jj][1][1]) + tmp[j][1][1] * (dp[v][jj][0][0] + dp[v][jj][1][0]) + tmp[j][1][1] * (dp[v][jj][0][1] + dp[v][jj][1][1]))%mod);
            }
        }
        sz[x] += sz[v];
    }
}

int main()
{
    int cnt = 0;
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; i++)
    {
        int u, v; scanf("%d%d", &u, &v);
        E[++cnt].to = v; E[cnt].nex = head[u]; head[u] = cnt;
        E[++cnt].to = u; E[cnt].nex = head[v]; head[v] = cnt;
    }
    dfs(1, -1);
    printf("%lld\n", (dp[1][k][1][1] + dp[1][k][0][1]) % mod);
    return 0;
}

View Code

BZOJ5316 : [Jsoi2018]绝地反击

若$R=0$，那么显然答案为离原点最远的点到原点的距离。

否则若所有点都在原点，那么显然答案为$R$。

否则考虑二分答案$mid$，检查$mid$是否可行。

那么每个点根据对应圆交，可以覆盖圆上的一部分，每个可行方案都可以通过平移使得刚好卡住某个交点。

枚举每个交点，算出圆上$n$个位置的坐标，然后匈牙利算法判断是否存在完美匹配，时间复杂度$O(n^4\log w)$，不能承受。

注意到这个图是个稠密图，所以可以用bitset对匈牙利进行加速，做到$O(\frac{n^3}{32})$每次匹配。

另一方面，可以先枚举一个点$x$，然后再二分答案$mid$，判断是否有可行方案使得$x$刚好匹配$x$和圆的交点。

在这里，显然只需要在之前答案$ans$的基础之上往下二分，如果$ans-eps$不可行那么就没有继续二分的必要。

即：设$f[x]$表示$x$得到的最优解，若$f[x]$不是$f[1,x]$的最小值，那么就没有继续二分的必要。

考虑将读入的$n$个点随机打乱，那么$f[x]$是$f[1,x]$的最小值的概率为$\frac{1}{x}$，一共只有期望$O(\log n)$个$x$有二分的必要。

检查次数骤降为$O(n+\log n\log w)$，时间复杂度$O(\frac{(n+\log n\log w)n^3}{32})$。

注意要特判$mid$过小或者过大导致$x$与圆没有交点的情况。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef unsigned int U;
const int N=205,M=7;
const double eps=1e-9,pi=acos(-1.0);
int n,m,R,i,j;double lim,ans,rot[N][2],b[N][2];
int f[N];U v[M],g[N][M];
struct P{int x,y;}a[N];
inline int sgn(double x){
  if(x>eps)return 1;
  if(x<-eps)return -1;
  return 0;
}
bool find(int x){
  for(int i=0;i<=m;i++){
    U t=v[i]&g[x][i];
    while(t){
      int j=i<<5|__builtin_ctz(t);
      v[i]^=1U<<(j&31);
      if(f[j]<0||find(f[j]))return f[j]=x,1;
      t-=t&-t;
    }
  }
  return 0;
}
inline bool check(int A,int B,double C){
  double d=sqrt(a[A].x*a[A].x+a[A].y*a[A].y);
  double l=(a[A].x*a[A].x+a[A].y*a[A].y+C*C-R*R)/(2*d);
  double h=sqrt(max(C*C-l*l,0.0));
  double bx=-a[A].x/d,by=-a[A].y/d;
  double px=a[A].x+bx*l,py=a[A].y+by*l;
  by=-by;
  swap(bx,by);
  bx*=h,by*=h;
  if(B==0)px+=bx,py+=by;else px-=bx,py-=by;
  int i,j;
  b[0][0]=px,b[0][1]=py;
  for(i=1;i<n;i++){
    b[i][0]=px*rot[i][1]-py*rot[i][0];
    b[i][1]=px*rot[i][0]+py*rot[i][1];
  }
  C*=C;
  for(i=0;i<n;i++){
    for(j=0;j<=m;j++)g[i][j]=0;
    for(j=0;j<n;j++)if(sgn((a[i].x-b[j][0])*(a[i].x-b[j][0])+(a[i].y-b[j][1])*(a[i].y-b[j][1])-C)<=0)g[i][j>>5]|=1U<<(j&31);
  }
  for(i=0;i<n;i++)f[i]=-1;
  for(i=0;i<n;i++){
    for(j=0;j<=m;j++)v[j]=~0U;
    if(!find(i))return 0;
  }
  return 1;
}
int main(){
  scanf("%d%d",&n,&R);
  m=(n-1)>>5;
  for(i=0;i<n;i++)scanf("%d%d",&a[i].x,&a[i].y);
  if(!R){
    int ans=0;
    for(i=0;i<n;i++)ans=max(ans,a[i].x*a[i].x+a[i].y*a[i].y);
    double ret=sqrt(ans);
    return printf("%.15f",ret),0;
  }
  random_shuffle(a,a+n);
  for(i=1;i<n;i++){
    double o=pi*2*i/n;
    rot[i][0]=sin(o),rot[i][1]=cos(o);
  }
  for(i=0;i<n;i++){
    int t=a[i].x*a[i].x+a[i].y*a[i].y;
    double val;
    if(t<=R)val=R-sqrt(t);else val=sqrt(t)-R;
    lim=max(lim,val);
    ans=max(ans,sqrt(t)+R);
  }
  for(i=0;i<n;i++)if(a[i].x||a[i].y)for(j=0;j<2;j++){
    double l=lim,r=max(min(sqrt(a[i].x*a[i].x+a[i].y*a[i].y)+R,ans-eps),lim);
    if(!check(i,j,r))continue;
    while(l+eps<r){
      double mid=(l+r)/2;
      if(check(i,j,mid))r=ans=mid;else l=mid;
    }
  }
  return printf("%.15f",ans),0;
}

我们今天的关于【BZOJ5316】[JSOI2018]绝地反击和网络流，计算几何，二分的分享就到这里，谢谢您的阅读，如果想了解更多关于BZOJ5301: [Cqoi2018]异或序列、bzoj5301[CQOI2018]异或序列、BZOJ5314: [Jsoi2018]潜入行动 (树形DP)、BZOJ5316 : [Jsoi2018]绝地反击的相关信息，可以在本站进行搜索。

本文标签：