20200519 hz【对称中心，前缀和优化DP，LCT最小生成树(边权k±x)】

T1：小B的棋盘

K个棋子可以不用完，对称指旋转180°后完全重合。

而前$k+1$与后$k+1$个点中一定有一对点匹配，这样就可以确定对称中心，枚举后check即可， O ( k 2 n ) O(k^2n) O(k2n)

Code：

#include
#define maxn 100005
using namespace std;
int n,K;
struct node{int x,y;bool operator < (const node &p)const{return x==p.x?y<p.y:x<p.x;}node operator + (const node &p)const{return (node){x+p.x,y+p.y};}bool operator == (const node &p)const{return x==p.x&&y==p.y;}
}a[maxn];
map<node,bool>vis;
bool check(node o){if(vis[o]) return 0;vis[o]=1;int cnt=0;for(int l=1,r=n;l<=r;){if(a[l]+a[r]==o) l++,r--;else{if(++cnt>K) return 0;if((a[l]+a[r])<o) l++;else r--;}}return 1;
}
int main()
{scanf("%d%d",&n,&K);if(n<=K) return puts("-1"),0;for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y);sort(a+1,a+1+n);int ans=0;for(int i=1;i<=K+1;i++) for(int j=n-K+i-1;j<=n;j++) ans+=check(a[i]+a[j]);printf("%d\n",ans);
}

T2：小B的夏令营

改为直接对$r$计算$l$前缀和是优化的关键。

Code：

#include
#define maxn 1505
using namespace std;
const int mod = 1e9+7;
int n,m,p,k,g[maxn],sg[maxn],sum[maxn],psum[maxn],f[maxn],fac[100005],inv[100005];
int C(int n,int m){return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;}
int Pow(int a,int b){int s=1;for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) s=1ll*s*a%mod; return s;}
void Pre(){for(int i=1;i<=m;i++) sum[i]=(sum[i-1]+f[i])%mod,psum[i]=(psum[i-1]+1ll*g[i]*sum[i])%mod;
}
int main()
{int a,b;scanf("%d%d%d%d%d",&n,&m,&a,&b,&k),p=1ll*a*Pow(b,mod-2)%mod;fac[0]=inv[0]=1; for(int i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod;inv[k]=Pow(fac[k],mod-2); for(int i=k-1;i>=1;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;for(int i=0,lim=min(k,m);i<=lim;i++) g[i]=1ll*C(k,i)*Pow(p,i)%mod*Pow(1-p,k-i)%mod;sg[0]=g[0]; for(int i=1;i<=m;i++) sg[i]=(sg[i-1]+g[i])%mod;sum[m]=1;for(int t=1;t<=n;t++,Pre()){for(int i=1;i<=m;i++) f[i]=1ll*g[m-i]*(1ll*sg[i-1]*(sum[m]-sum[m-i])%mod-psum[i-1])%mod;}printf("%d\n",(sum[m]+mod)%mod);
}

T3：小B的图

也就是说$k$决定了负边的优先度，而不是发生替换的时间（不相交的不影响，相交的$k$大的能替换$k$小的也能替换）

Code：

#include
#define maxn 300005
#define LL long long
using namespace std;
char cb[1<<20],*cs,*ct;
#define getc() (cs==ct&&(ct=(cs=cb)+fread(cb,1,1<<20,stdin),cs==ct)?0:*cs++)
inline void read(int &a){char c;bool f=0;while(!isdigit(c=getc())) c=='-'&&(f=1);for(a=c-'0';isdigit(c=getc());a=a*10+c-'0'); f&&(a=-a);
}
const int inf = 1e9+5;
int n,m,A,B,cnt;
pair<int,LL>ans[maxn];
struct node{int x,y,w;bool operator < (const node &p)const{return w<p.w;}
}a[maxn],b[maxn];
namespace LCT{#define pa fa[x]int fa[maxn],ch[maxn][2],mxp[maxn],val[maxn];bool rev[maxn];bool isr(int x){return ch[pa][0]!=x&&ch[pa][1]!=x;}bool isc(int x){return ch[pa][1]==x;}void upd(int x){mxp[x]=x;if(val[mxp[x]]<val[mxp[ch[x][0]]]) mxp[x]=mxp[ch[x][0]];if(val[mxp[x]]<val[mxp[ch[x][1]]]) mxp[x]=mxp[ch[x][1]];}void rot(int x){int y=fa[x],z=fa[y],c=isc(x);if(!isr(y)) ch[z][isc(y)]=x;fa[ch[y][c]=ch[x][!c]]=y;fa[ch[x][!c]=y]=x,fa[x]=z;upd(y);}void pd(int x){if(rev[x]) swap(ch[x][0],ch[x][1]),rev[ch[x][0]]^=1,rev[ch[x][1]]^=1,rev[x]=0;}void pdpath(int x){if(!isr(x)) pdpath(pa); pd(x);}void splay(int x){for(pdpath(x);!isr(x);rot(x)) if(!isr(pa)) rot(isc(pa)==isc(x)?pa:x); upd(x);}void access(int x){for(int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,upd(x);}void bert(int x){access(x),splay(x),rev[x]^=1;}int sert(int x){access(x),splay(x);for(;ch[x][0];x=ch[x][0]);return x;}int split(int x,int y){bert(x),access(y),splay(y);return y;}void link(int x,int y){bert(x),fa[x]=y;}void cut(int x,int y){split(x,y),fa[x]=ch[y][0]=0,upd(y);}
}
using namespace LCT;
int main()
{read(n),read(A),read(B),read(m);for(int i=1;i<=A;i++) read(a[i].x),read(a[i].y),read(a[i].w);for(int i=1;i<=B;i++) read(b[i].x),read(b[i].y),read(b[i].w);sort(a+1,a+1+A),sort(b+1,b+1+B);for(int i=1;i<=n;i++) val[i]=-inf,mxp[i]=i; val[0]=-inf;ans[0].first=-inf;for(int i=1;i<=A;i++) if(bert(a[i].x),sert(a[i].y)!=a[i].x){val[n+i]=a[i].w,mxp[n+i]=n+i;link(n+i,a[i].x),link(n+i,a[i].y);ans[0].second+=a[i].w;}for(int i=1;i<=B;i++){int t=mxp[split(b[i].x,b[i].y)];if(val[mxp[t]]==-inf) continue;int tmp=b[i].w-a[t-n].w;ans[++cnt]=make_pair(tmp/2+(tmp>0&&(tmp&1)),tmp);cut(t,a[t-n].x),cut(t,a[t-n].y);link(b[i].x,b[i].y);}sort(ans+1,ans+1+cnt);for(int i=1;i<=cnt;i++) ans[i].second+=ans[i-1].second;for(int v,l,r,mid;m--;){read(v),l=0,r=cnt;while(l<r) mid=(l+r+1)>>1,ans[mid].first>v?(r=mid-1):(l=mid);printf("%lld\n",ans[l].second+1ll*(n-1-2*l)*v);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！