North American Invitational Programming Contest 2018

A. Cut it Out!

枚舉第一刀，那么之后每切一刀都會將原問題劃分成兩個子問題。

考慮DP，設$f[l][r]$表示$l$點順時針一直到$r$點還未切割的最小代價，預處理出每條邊的代價轉移即可。

時間復雜度$O(n^3)$。

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=422;
const double eps=1e-8;
const double inf=1e100;
inline int sgn(double x){
	if(x>eps)return 1;
	if(x<-eps)return -1;
	return 0;
}
inline void up(double&a,double b){if(a>b)a=b;}
int n,m,i,j,k;
double ans=inf,f[N][N];
bool v[N][N];
struct P{
	double x,y;
	P(){}
	P(double _x,double _y){x=_x,y=_y;}
	P operator-(const P&b)const{return P(x-b.x,y-b.y);}
	P operator+(const P&b)const{return P(x+b.x,y+b.y);}
	P operator*(const double&b)const{return P(x*b,y*b);}
	double len(){return hypot(x,y);}
	double len2(){return x*x+y*y;}
	void read(){scanf("%lf%lf",&x,&y);}
}a[N],b[N];
double wl[N],wr[N];
inline double cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;}
inline double line_intersection(const P&a,const P&b,const P&p,const P&q){
	double U=cross(p-a,q-p),D=cross(b-a,q-p);
	return U/D;
	//return a+(b-a)*(U/D);
}
inline void pre(double&A,double&B,int k){
	A=-inf,B=inf;
	for(int i=0;i<n;i++){
		double now=line_intersection(b[k],b[k+1],a[i],a[i+1]);
		if(now<0.5&&now>A)A=now;
		if(now>0.5&&now<B)B=now;
	}
}
inline double cal(int k,int L,int R){
	k%=m;
	k+=m;
	k%=m;
	if(L>-100){
		L%=m;
		L+=m;
		L%=m;
	}
	if(R>-100){
		R%=m;
		R+=m;
		R%=m;
	}
	double A=wl[k],B=wr[k];
	if(L>=0){
		double now=line_intersection(b[k],b[k+1],b[L],b[L+1]);
		//printf("L=%d %.10f\n",L,now);
		if(now<0.5&&now>A)A=now;
		if(now>0.5&&now<B)B=now;
	}
	if(R>=0){
		double now=line_intersection(b[k],b[k+1],b[R],b[R+1]);
		//printf("R=%d %.10f\n",R,now);
		if(now<0.5&&now>A)A=now;
		if(now>0.5&&now<B)B=now;
	}
	//printf("! %.10f\n",(B-A)*((b[k]-b[k+1]).len()));
	return (B-A-1)*((b[k]-b[k+1]).len());
}
double dfs(int l,int r){//point a[l] -> a[r] are not cut
	if(l>=r)return 0;
	if(v[l][r])return f[l][r];
	double ret=inf;
	for(int i=l;i<r;i++){
		//printf("i=%d cal=%.10f\n",i,cal(i,l-1,r));
		up(ret,dfs(l,i)+dfs(i+1,r)+cal(i,l-1,r));
	}
	v[l][r]=1;
	//printf("f[%d][%d]=%.10f\n",l,r,f[l][r]);
	return f[l][r]=ret;
}
int main(){
	scanf("%d",&n);
	for(i=0;i<n;i++)a[i].read();
	a[n]=a[0];
	scanf("%d",&m);
	for(i=0;i<m;i++)b[i].read();
	b[m]=b[0];
	//cal(6,5,8);
	//dfs(6,8);
	for(i=0;i<m;i++)pre(wl[i],wr[i],i);
	for(i=0;i<m;i++)up(ans,dfs(i+1,i+m)+cal(i,-100,-100));
	for(i=0;i<m;i++)ans+=(b[i]-b[i+1]).len();
	printf("%.15f",ans);
}
/*
4
-100 -100
-100 100
100 100
100 -100
8
-1 -2
-2 -1
-2 1
-1 2
1 2
2 1
2 -1
1 -2
*/

B. Double Clique

一個方案合法當且僅當團點數$\times ($團點數$-1)+$獨立集度數和$=$團度數和，且存在可行方案滿足團是度數最大的若干個點。

找到可行方案后，要么是團里出去一個點，要么是獨立集里出去一個點，要么兩邊各出去一個點。

時間復雜度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=200010;
int n,m,i,j,x,y,d[N],s[N];ll ans;
int main(){
	scanf("%d%d",&n,&m);
	while(m--)scanf("%d%d",&x,&y),d[x]++,d[y]++;
	sort(d+1,d+n+1);
	reverse(d+1,d+n+1);
	for(i=1;i<=n;i++)s[i]=s[i-1]+d[i];
	for(i=0;i<=n;i++)if(1LL*i*(i-1)+s[n]-s[i]==s[i]){ans=1;break;}
	if(!ans)return puts("0"),0;
	for(j=1;j<=i;j++)if(1LL*(i-1)*(i-2)+s[n]-s[i]+d[j]==s[i]-d[j])ans++;
	for(j=i+1;j<=n;j++)if(1LL*(i+1)*i+s[n]-s[i]-d[j]==s[i]+d[j])ans++;
	for(x=0,j=1;j<=i;j++)if(d[j]==d[i])x++;
	for(y=0,j=i+1;j<=n;j++)if(d[j]==d[i])y++;
	ans+=1LL*x*y;
	printf("%lld",ans%1000000007);
}

C. Flashing Fluorescents

注意到答案不超過$n$，枚舉答案$ans$，則任何一個可行方案可以由若干個長度互不相等且不超過$ans$的區間異或得到。

設$f[ans][S]$表示長度不超過$ans$能否異或出$S$，枚舉當前長度的區間位置轉移即可。

時間復雜度$O(2^nn^2)$。

#include<cstdio>
#include<cstring>
int n,i,j,now,S;
bool f[50][1<<16];
char a[50];
int main(){
	scanf("%s",a);
	n=strlen(a);
	for(i=0;i<n;i++)if(a[i]=='0')S^=1<<i;
	f[0][S]=1;
	while(!f[now][0]){
		for(S=0;S<1<<n;S++)f[now+1][S]=f[now][S];
		for(i=0;i<n;i++){
			int mask=0;
			for(j=0;j<now+1&&i+j<n;j++)mask|=1<<(i+j);
			for(S=0;S<1<<n;S++)if(f[now][S])f[now+1][S^mask]=1;
		}
		now++;
	}
	printf("%d",now);
}

D. Missing Gnomes

按題意模擬。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
int a[N], ans[N];
bool use[N];
int main()
{
	while(~scanf("%d%d", &n, &m))
	{
		for(int i = 1; i <= n; ++i)use[i] = 0;
		
		for(int i = 1; i <= m; ++i)
		{
			scanf("%d", &a[i]);
			use[a[i]] = 1;
		}
		
		int x = 1;
		int g = 0;
		for(int i = 1; i <= m; ++i)
		{
			while(x < a[i])
			{
				if(!use[x])ans[++g] = x;
				++x;
			}
			ans[++g] = a[i];
		}
		while(x <= n)
		{
			if(!use[x])ans[++g] = x;
			++x;
		}
		for(int i = 1; i <= n; ++i)printf("%d\n", ans[i]);
	}
	return 0;
}

/*
【trick&&吐槽】


【題意】


【分析】


【時間復雜度&&優化】


*/

E. Prefix Free Code

建立Trie將字符串映射為數字，從前往后枚舉LCP，那么這一位能填的數要小于某個值，且前面沒出現過，可以用樹狀數組加速統計，后面能填的數可以用組合數計算。

時間復雜度$O(n\log n)$。

#include<cstdio>
#include<cstring>
const int N=1000010,P=1000000007;
int n,m,len,i,j,x,son[N][26],v[N],tot,dfn,a[N],cnt;
int bit[N],fac[N],inv[N],ans;
char s[N];
void dfs(int x){
	if(v[x])v[x]=++dfn;
	for(int i=0;i<26;i++)if(son[x][i])dfs(son[x][i]);
}
inline void ins(int x,int p){for(;x<=n;x+=x&-x)bit[x]+=p;}
inline int ask(int x){int t=0;for(;x;x-=x&-x)t+=bit[x];return t;}
inline int A(int n,int m){return n<m?0:1LL*fac[n]*inv[n-m]%P;}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%s",s);
		len=strlen(s);
		for(x=j=0;j<len;j++){
			if(!son[x][s[j]-'a'])son[x][s[j]-'a']=++tot;
			x=son[x][s[j]-'a'];
		}
		v[x]=1;
	}
	dfs(0);
	for(fac[0]=i=1;i<=n;i++)fac[i]=1LL*fac[i-1]*i%P;
	for(inv[0]=inv[1]=1,i=2;i<=n;i++)inv[i]=1LL*(P-inv[P%i])*(P/i)%P;
	for(i=2;i<=n;i++)inv[i]=1LL*inv[i-1]*inv[i]%P;
	scanf("%s",s);
	for(x=i=0;s[i];i++){
		x=son[x][s[i]-'a'];
		if(v[x])a[++cnt]=v[x],x=0;
	}
	ans=1;
	for(i=1;i<=n;i++)ins(i,1);
	for(i=1;i<=cnt;i++){
		ins(a[i],-1);
		ans=(1LL*A(n-i,m-i)*ask(a[i])+ans)%P;
	}
	printf("%d",ans);
}

F. Probe Droids

即求斜率第$k$小的坐標，首先特判掉斜率$=0$或者斜率不存在的情況。

在Stern-Brocot Tree上枚舉互質數對作為斜率，然后用類歐幾里得算法在$O(\log n)$的時間內統計出直線下方的點數，以此來判斷往左走還是往右走。

考慮二分往左往右走的拐點位置，則每次詢問的復雜度降低至$O(\log^3n)$。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
typedef long long ll;
ll ansx,ansy;
ll cal(ll a,ll b,ll c,ll n){
  if(!a||n<0)return 0;
  ll x,y;
  if(a>=c||b>=c){
    x=cal(a%c,b%c,c,n);
    y=a/c*(n*(n+1)/2)+b/c*(n+1)+x;
    return y;
  }
  ll m=(a*n+b)/c;
  x=cal(c,c-b-1,a,m-1);
  y=n*m-x;
  return y;
}
ll calbelow(ll up,ll down,ll n,ll m){
  ll lim=min(n*down/up,m);
  return cal(up,0,down,lim)+(m-lim)*n;
}
ll calexact(ll up,ll down,ll n,ll m){
  return min(n/up,m/down);
}
int check(ll up,ll down,ll n,ll m,ll k){
  if(up>n||down>m)return 2;
  ll below=calbelow(up,down,n,m);
  ll exact=calexact(up,down,n,m);
  //cout<<up<<" "<<down<<" "<<below<<" "<<exact<<endl;
  //[below-exact+1,below]
  if(k>below)return -1;//too small
  if(k<below-exact+1)return 1;//too big
  return 0;
}
void solve(ll n,ll m,ll k){
  ll lu=0,ld=1,ru=1,rd=0,mu,md;
  ll A,B;
  while(1){
    mu=lu+ru;
    md=ld+rd;
    int ret=check(mu,md,n,m,k);
    if(ret==0){
      A=mu,B=md;
      break;
    }
    ll l=1,r=n,fin=0;
    if(ret<0){
      while(l<=r){
        ll mid=(l+r)>>1;
        if(check(lu+ru*mid,ld+rd*mid,n,m,k)<0)l=(fin=mid)+1;else r=mid-1;
      }
      lu+=ru*fin,ld+=rd*fin;
    }else{
      while(l<=r){
        ll mid=(l+r)>>1;
        if(check(ru+lu*mid,rd+ld*mid,n,m,k)==1)l=(fin=mid)+1;else r=mid-1;
      }
      ru+=lu*fin,rd+=ld*fin;
    }
  }
  ll below=calbelow(A,B,n,m);
  ll exact=calexact(A,B,n,m);
  below=below-exact;
  k-=below;
  ansx=B*k;
  ansy=A*k;
  //cout<<A<<"/"<<B<<endl;
}
int main(){
   ll n,m,q,k;
  cin>>n>>m>>q;
  while(q--){
    cin>>k;
    if(k<m){
      cout<<"1 "<<k+1<<endl;
      continue;
    }
    if(k>n*m-n){
      cout<<k-(n*m-n)+1<<" 1"<<endl;
      continue;
    }
    solve(n-1,m-1,k-(m-1));
    cout<<ansy+1<<" "<<ansx+1<<endl;
  }
}

G. Rainbow Graph

若只有一個限制，滿足擬陣。

對于兩個限制，則是兩個擬陣的交。

首先特判全部都無解的情況，并將全集$E$作為$k=m$的解。

設$M_1$為限制$1$的擬陣，一個方案合法當且僅當在限制$1$下連通，同理定義$M_2$為限制$2$的擬陣。

建立有向圖，原圖每條邊作為一個點，并添加源匯$S$和$T$。

對于上一個$k$的一組最優解$E$中的某條邊$x$，如果去掉它后仍然滿足$M_1$，則由$S$向$x$連邊；若去掉它后仍然滿足$M_2$，則由$x$向$T$連邊。

對于$E$中某條邊$x$和不在$E$中的某條邊$y$，若將$x$換成$y$后滿足$M_2$，則由$x$向$y$連邊；若滿足$M_1$，則由$y$向$x$連邊。

用SPFA求出$S$到$T$的最短路，就能得到邊數恰好減少$1$的最優解。

時間復雜度$O(n^4)$。

#include<cstdio>
const int N=105,M=100000,inf=~0U>>1;
int n,m,i,S,T,x,y,g[N],v[N<<1],nxt[N<<1],ed,vis[N];
int cost[N],col[N],use[N],ans,fin[N];char ch[9];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x,char ban){
  if(vis[x])return;
  vis[x]=1;
  for(int i=g[x];i;i=nxt[i])if(use[i>>1]&&col[i>>1]!=ban)dfs(v[i],ban);
}
inline bool check(char ban){
  int i;
  for(i=1;i<=n;i++)vis[i]=0;
  dfs(1,ban);
  for(i=1;i<=n;i++)if(!vis[i])return 0;
  return 1;
}
namespace Matroid{
int g[N],v[M],nxt[M],ed,q[M],h,t,d[N],pre[N],w[N];bool in[N];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void ext(int x,int y,int z){
  if(d[x]<=y)return;
  d[x]=y;
  pre[x]=z;
  if(in[x])return;
  q[++t]=x;
  in[x]=1;
}
inline bool find(){
  int i,j;
  S=m+1,T=m+2;
  for(ed=0,i=1;i<=T;i++)g[i]=0;
  for(i=1;i<=m;i++)if(use[i]){
    w[i]=-cost[i];
    use[i]^=1;
    if(check('R'))add(S,i);
    if(check('B'))add(i,T);
    use[i]^=1;
  }else w[i]=cost[i];
  for(i=1;i<=m;i++)if(use[i])for(j=1;j<=m;j++)if(!use[j]){
    use[i]^=1,use[j]^=1;
    if(check('B'))add(i,j);
    if(check('R'))add(j,i);
    use[i]^=1,use[j]^=1;
  }
  for(i=1;i<=T;i++)d[i]=inf,in[i]=0;
  q[h=t=1]=S;
  d[S]=0,in[S]=1;
  while(h<=t){
    x=q[h++];
    //printf("! %d %d %d\n",x,d[x],pre[x]);
    for(i=g[x];i;i=nxt[i])ext(v[i],d[x]+w[v[i]],x);
    in[x]=0;
  }
  if(d[T]==inf)return 0;
  ans+=d[T];
  while(pre[T]!=S)use[T=pre[T]]^=1;
  return 1;
}
}
int main(){
  scanf("%d%d",&n,&m);
  for(ed=i=1;i<=m;i++){
    scanf("%d%d%d%s",&x,&y,&cost[i],ch);
    col[i]=ch[0];
    add(x,y),add(y,x);
    use[i]=1;
    ans+=cost[i];
  }
  if(!check('R')||!check('B')){
    for(i=1;i<=m;i++)puts("-1");
    return 0;
  }
  fin[m]=ans;
  for(i=m-1;i;i--)if(Matroid::find())fin[i]=ans;
  else{
    for(x=1;x<=i;x++)fin[x]=-1;
    break;
  }
  for(i=1;i<=m;i++)printf("%d\n",fin[i]);
}

H. Recovery

將所有位置都設成$1$，然后貪心配對行列使得滿足條件。

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() {  }
#define MS(x, y) memset(x, y, sizeof(x))
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b > a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b < a)a = b; }
const int N = 1e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n, m;
char a[55], b[55];
int aa[55], bb[55];
int ga, gb;
char s[55][55];
int va[55], vb[55];
bool rand(char a[])
{
	int n = random() % 4 + 1;
	for(int i = 0; i < n; ++i)a[i] = rand() % 2 + '0';
	a[n] = 0;
	return 1;
}

char tt[55][55];
char t[55][55];
bool FLAG;
void BF()
{
	FLAG = 0;
	int w = n * m;
	int top = 1 << w;;
	int ansone = -1;
	for(int i = 0; i < top; ++i)
	{
		for(int j = 0; j < w; ++j)
		{
			tt[n - 1 - j / m][m - 1 - j % m] = '0' + (i >> j & 1);
		}
		MS(va, 0);
		MS(vb, 0);
		int one = 0;
		for(int j = 0; j < n; ++j)
		{
			for(int k = 0; k < m; ++k)
			{
				va[j] += tt[j][k] % 2;
				vb[k] += tt[j][k] % 2;
				one += tt[j][k] % 2;
			}
		}
		bool flag = 1;
		for(int j = 0; j < n; ++j)if(va[j] % 2 != a[j] % 2)
		{
			flag = 0;
			break;
		}
		for(int j = 0; j < m; ++j)if(vb[j] % 2 != b[j] % 2)
		{
			flag = 0;
			break;
		}
		if(flag)
		{
			FLAG = 1;
			if(one > ansone)
			{
				ansone = one;
				memcpy(t, tt, sizeof(tt));
			}
		}
	}
}

int main()
{
	while(~scanf("%s%s", a, b))
	//while(rand(a), rand(b))
	{
		n = strlen(a);
		m = strlen(b);
		//puts("input"); puts(a); puts(b);
		
		MS(s, 0);
		for(int i = 0; i < n; ++i)
		{
			for(int j = 0; j < m; ++j)
			{
				s[i][j] = '1';
			}
		}
		ga = gb = 0;
		for(int i = 0; i < n; ++i)
		{
			if(m % 2 != a[i] % 2)
			{
				aa[++ga] = i;
			}
		}
		for(int i = 0; i < m; ++i)
		{
			if(n % 2 != b[i] % 2)
			{
				bb[++gb] = i;
			}
		}
		
		//BF();
		if(ga + gb & 1)
		{
			puts("-1");
			/*
			if(FLAG)
			{
				puts("NO flag");
				while(1);
			}
			*/
		}
		else
		{
			/*
			if(!FLAG)
			{
				puts("NO !flag");
				while(1);
			}
			*/
			
			//printf("ga|gb = %d %d\n", ga, gb);
			
			while(ga < gb)aa[++ga] = 0;
			while(gb < ga)bb[++gb] = 0;
			int g = ga;
			
			/*
			int g = min(ga, gb);
			for(int i = g + 1; i <= ga; ++i)
			{
				bb[++gb] = 0;
			}
			for(int i = g + 1; i <= gb; ++i)
			{
				aa[++ga] = 0;
			}
			*/
			
			sort(aa + 1, aa + ga + 1);
			sort(bb + 1, bb + gb + 1);
			/*printf("ga|gb = %d %d\n", ga, gb);
			for(int i = 1; i <= ga; ++i)printf("%d ", aa[i]); puts("");
			for(int i = 1; i <= gb; ++i)printf("%d ", bb[i]); puts("");
			*/
			g = max(ga, gb);
			
			for(int i = 1; i <= g; ++i)
			{
				s[aa[i]][bb[i]] = '0';
			}
			
			for(int i = 0; i < n; ++i)puts(s[i]);
			
			/*
			for(int i = 0; i < n; ++i)
			{
				for(int j = 0; j < m; ++j)
				{
					if(s[i][j] != t[i][j])
					{
						puts("s[i][j] != t[i][j]");
						
						for(int i = 0; i < n; ++i)puts(s[i]);
						for(int i = 0; i < n; ++i)puts(t[i]);
						while(1);
					}
				}
			}
			*/
			
			/*
			MS(va, 0);
			MS(vb, 0);
			for(int i = 0; i < n; ++i)
			{
				for(int j = 0; j < m; ++j)
				{
					va[i] += s[i][j] % 2;
					vb[j] += s[i][j] % 2;
				}
			}
			for(int i = 0; i < n; ++i)
			{
				if(va[i] % 2 != a[i] % 2)
				{
					puts("NO A");
					while(1);
				}
			}
			for(int i = 0; i < m; ++i)
			{
				if(vb[i] % 2 != b[i] % 2)
				{
					puts("NO B");
					while(1);
				}
			}
			*/
		}
	}
	return 0;
}

/*
【trick&&吐槽】


【題意】


【分析】


【時間復雜度&&優化】


*/

I. Red Black Tree

設$f[i][j]$表示考慮$i$的子樹，里面選了$j$個紅點的方案數，轉移時只枚舉有效的$j$即可得到$O(nm)$的時間復雜度。

#include<cstdio>
const int N=200010,M=1005,P=1000000007;
int n,m,i,x,g[N],nxt[N],size[N],vip[N];
int f[N][M],h[M];
void dfs(int x){
	size[x]=vip[x];
	//case 1 not choose x
	f[x][0]=1;
	for(int y=g[x];y;y=nxt[y]){
		dfs(y);
		for(int j=0;j<=size[x]+size[y]&&j<=m;j++)h[j]=0;
		for(int j=0;j<=size[y]&&j<=m;j++)for(int k=0;k<=size[x]&&j+k<=m;k++)
			h[j+k]=(1LL*f[y][j]*f[x][k]+h[j+k])%P;
		size[x]+=size[y];
		for(int j=0;j<=size[x]+size[y]&&j<=m;j++)f[x][j]=h[j];
	}
	//case 2 choose x
	f[x][vip[x]]=(f[x][vip[x]]+1)%P;
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=2;i<=n;i++){
		scanf("%d",&x);
		nxt[i]=g[x];g[x]=i;
	}
	for(i=1;i<=m;i++)scanf("%d",&x),vip[x]=1;
	dfs(1);
	for(i=0;i<=m;i++)printf("%d\n",f[1][i]);
}

J. Winter Festival

因為所有簡單環邊權和都要是奇數，因此當兩個簡單環有公共邊時不可能滿足條件，所以當且僅當圖是仙人掌的時候才有解。

設$f[i][j][x][y]$表示考慮DFS生成樹中$i$的子樹，$i$與$i$父親的邊的邊權為$j$，$i$與$i$父親的邊所在環的邊權和模$2$為$x$，$i$與$i$父親的邊所在環的非樹邊邊權為$y$的最小代價。

轉移時需要通過另一個輔助數組$h[S][j][x][y]$來進行不同子樹的合并，其中$j,x,y$含義與$f$相同，而$S$表示$x$點周圍存在的邊權集合。

時間復雜度$O(n+m)$。

#include<cstdio>
#include<cstdlib>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int N=100010,inf=100000000;
int n,m,i,x,y,g[N],v[N<<1],nxt[N<<1],ed;
int mark[N],fa[N],vis[N],dfn;
int f[N][3][2][3];
int dp[1<<3][2][3],h[1<<3][2][3];
int istop[N],isbot[N];
int ban[3][1<<3];
inline void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
inline void up(int&a,int b){a>b?(a=b):0;}
inline void clr(){
	rep(S,8)rep(j,2)rep(k,3)h[S][j][k]=inf;
}
inline void go(){
	rep(S,8)rep(j,2)rep(k,3)dp[S][j][k]=h[S][j][k];
}
void dfs(int x,int y){
	fa[x]=y;
	vis[x]=++dfn;
	for(int i=g[x];i;i=nxt[i]){
		int u=v[i];
		if(u==y)continue;
		if(!vis[u]){
			dfs(u,x);
		}else if(vis[u]<vis[x]){
			int j=x;
			isbot[x]=1;
			while(j!=u){
				mark[j]++;
				if(mark[j]>1){
					puts("-1");
					exit(0);
				}
				if(fa[j]==u)istop[j]=1;
				j=fa[j];
			}
		}
	}
	rep(S,8)rep(j,2)rep(k,3)dp[S][j][k]=inf;
	if(!y)dp[0][0][0]=0;
	else{
		//add the cycle edge
		if(isbot[x])rep(c,3)up(dp[1<<c][c&1][c],c);
		else dp[0][0][0]=0;
	}
	for(int i=g[x];i;i=nxt[i]){
		int u=v[i];
		if(u==y)continue;
		if(fa[u]==x){
			clr();
			if(istop[u]){
				rep(S,8)rep(j,2)rep(k,3)if(dp[S][j][k]<inf)
					rep(A,3)if(!ban[A][S])rep(B,2)rep(C,3)if(f[u][A][B][C]<inf){
						if(B!=1)continue;
						if(ban[C][S])continue;
						if((A+C)%3==1)continue;
						up(h[S|(1<<A)|(1<<C)][j][k],dp[S][j][k]+f[u][A][B][C]);
					}
			}else if(mark[u]){
				rep(S,8)rep(j,2)rep(k,3)if(dp[S][j][k]<inf)
					rep(A,3)if(!ban[A][S])rep(B,2)rep(C,3)if(f[u][A][B][C]<inf){
						up(h[S|(1<<A)][(j+B)&1][C],dp[S][j][k]+f[u][A][B][C]);
					}
			}else{
				rep(S,8)rep(j,2)rep(k,3)if(dp[S][j][k]<inf)
					rep(A,3)if(!ban[A][S])rep(B,1)rep(C,1)if(f[u][A][B][C]<inf){
						up(h[S|(1<<A)][j][k],dp[S][j][k]+f[u][A][B][C]);
					}
			}
			go();
		}
	}
	rep(S,3)rep(j,2)rep(k,3)f[x][S][j][k]=inf;
	if(y){
		//add the father edge
		if(mark[x]){
			rep(S,8)rep(j,2)rep(k,3)if(dp[S][j][k]<inf)
				rep(c,3)if(!ban[c][S])up(f[x][c][(j+c)&1][k],dp[S][j][k]+c);
		}else{
			rep(S,8)rep(j,2)rep(k,3)if(dp[S][j][k]<inf)
				rep(c,3)if(!ban[c][S])up(f[x][c][j][k],dp[S][j][k]+c);
		}
	}else{
		rep(S,8)rep(j,2)rep(k,3)if(dp[S][j][k]<inf)
			up(f[x][0][0][0],dp[S][j][k]);
	}
}
int main(){
	rep(i,3)rep(j,8)rep(k,3)if((j>>k&1)&&(i+k)%3==1)ban[i][j]=1;
	scanf("%d%d",&n,&m);
	for(ed=i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		add(x,y),add(y,x);
	}
	int ans=0;
	for(i=1;i<=n;i++)if(!vis[i]){
		dfs(i,0);
		if(f[i][0][0][0]>=inf){
			puts("-1");
			exit(0);
		}
		ans+=f[i][0][0][0];
	}
	printf("%d",ans);
}

K. Zoning Houses

若不刪除任何點，則答案為區間$x$坐標的極差與$y$坐標極差的較大值。

若刪除一個點，則最優方案下一定是刪除$x$或者$y$坐標最小或者最大的$4$個點之一，線段樹維護即可。

時間復雜度$O(n\log n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
const int N=100010,M=262150,inf=1000000010;
int n,m,i,x,y,ans;
P xmi[M],xma[M],ymi[M],yma[M];
void build(int x,int a,int b){
	if(a==b){
		scanf("%d%d",&xmi[x].first,&ymi[x].first);
		xmi[x].second=ymi[x].second=a;
		xma[x]=xmi[x];
		yma[x]=ymi[x];
		return;
	}
	int mid=(a+b)>>1;
	build(x<<1,a,mid),build(x<<1|1,mid+1,b);
	xmi[x]=min(xmi[x<<1],xmi[x<<1|1]);
	xma[x]=max(xma[x<<1],xma[x<<1|1]);
	ymi[x]=min(ymi[x<<1],ymi[x<<1|1]);
	yma[x]=max(yma[x<<1],yma[x<<1|1]);
}
P askxmi(int x,int a,int b,int c,int d){
	if(c>d)return P(inf,0);
	if(c<=a&&b<=d)return xmi[x];
	int mid=(a+b)>>1;
	P t(inf,0);
	if(c<=mid)t=askxmi(x<<1,a,mid,c,d);
	if(d>mid)t=min(t,askxmi(x<<1|1,mid+1,b,c,d));
	return t;
}
P askymi(int x,int a,int b,int c,int d){
	if(c>d)return P(inf,0);
	if(c<=a&&b<=d)return ymi[x];
	int mid=(a+b)>>1;
	P t(inf,0);
	if(c<=mid)t=askymi(x<<1,a,mid,c,d);
	if(d>mid)t=min(t,askymi(x<<1|1,mid+1,b,c,d));
	return t;
}
P askxma(int x,int a,int b,int c,int d){
	if(c>d)return P(-inf,0);
	if(c<=a&&b<=d)return xma[x];
	int mid=(a+b)>>1;
	P t(-inf,0);
	if(c<=mid)t=askxma(x<<1,a,mid,c,d);
	if(d>mid)t=max(t,askxma(x<<1|1,mid+1,b,c,d));
	return t;
}
P askyma(int x,int a,int b,int c,int d){
	if(c>d)return P(-inf,0);
	if(c<=a&&b<=d)return yma[x];
	int mid=(a+b)>>1;
	P t(-inf,0);
	if(c<=mid)t=askyma(x<<1,a,mid,c,d);
	if(d>mid)t=max(t,askyma(x<<1|1,mid+1,b,c,d));
	return t;
}
inline int cal(int x,int y,int z){
	return max(
	max(askxma(1,1,n,x,z-1).first,askxma(1,1,n,z+1,y).first)-min(askxmi(1,1,n,x,z-1).first,askxmi(1,1,n,z+1,y).first)
	,
	max(askyma(1,1,n,x,z-1).first,askyma(1,1,n,z+1,y).first)-min(askymi(1,1,n,x,z-1).first,askymi(1,1,n,z+1,y).first)
	);
}
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	while(m--){
		scanf("%d%d",&x,&y);
		ans=cal(x,y,askxmi(1,1,n,x,y).second);
		ans=min(ans,cal(x,y,askxma(1,1,n,x,y).second));
		ans=min(ans,cal(x,y,askymi(1,1,n,x,y).second));
		ans=min(ans,cal(x,y,askyma(1,1,n,x,y).second));
		printf("%d\n",ans);
	}
}

posted @ 2018-04-07 02:34 Claris 閱讀(2095) 評論(2) 收藏舉報

刷新頁面返回頂部

Claris' Blog

North American Invitational Programming Contest 2018

公告