XIV Open Cup named after E.V. Pankratiev. GP of America

A. Ancient Diplomacy

建圖，同色點間邊權(quán)為$0$，異色點間邊權(quán)為$1$，則等價于找一個點使得到它最短路最長的點的最短路最小，F(xiàn)loyd即可。

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

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=110,inf=100000000;
int n,m,i,j,k,x,y,a[N],g[N][N];
int main(){
	while(~scanf("%d%d",&n,&m)){
		if(!n)return 0;
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=i==j?0:inf;
		while(m--){
			scanf("%d%d",&x,&y);
			g[x][y]=g[y][x]=a[x]^a[y];
		}
		for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
		int ans=inf;
		for(i=1;i<=n;i++){
			int now=0;
			for(j=1;j<=n;j++)now=max(now,g[i][j]);
			ans=min(ans,now);
		}
		printf("%d\n",ans);
	}
}

B. Bob and Banjo

若$AB$線段經(jīng)過圓$C$的部分長度不超過$t$，則答案為$AB$長度。

否則若$t=0$，則答案為$A$到$C$切線長度$+B$到$C$切線長度$+$一段圓弧。

否則考慮最優(yōu)路徑，一定是$A$沿直線走到圓上某個點$D$，在圓內(nèi)長度不超過$t$，然后從$D$開始走若干個長度為$t$的折線到達圓上某個點$E$，再由$E$沿直線到達$B$，中間不經(jīng)過圓。

枚舉順時針還是逆時針走，再枚舉$D$到$E$路徑上有多少個$t$，那么可以解出$DE$這段圓心角的取值范圍，在里面三分答案即可。

#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 = 1e6 + 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;
const double eps = 1e-8, pi = acos(-1.0);
int sgn(double x)
{
    if(x < -eps) return -1;
    if(x > eps) return 1;
    return 0;
}
bool Quadratic(double A, double B, double C, double *t0, double *t1)
{
    double discrim = B * B - 4.f * A * C;
    if(discrim < 0.) return false;
    double rootDiscrim = sqrt(discrim);
    double q;
    if(B < 0) q = -.5f * (B - rootDiscrim);
    else      q = -.5f * (B + rootDiscrim);
    *t0 = q / A;
    *t1 = C / q;
    if(*t0 > *t1) swap(*t0, *t1);
    return true;
}
struct vec
{
    double x, y; vec(){x = y = 0;}
    vec(double _x, double _y) {x = _x, y = _y;}
    vec operator + (vec v){return vec(x + v.x, y + v.y);}
    vec operator - (vec v){return vec(x - v.x, y - v.y);}
    vec operator * (double v) {return vec(x * v, y * v);}
    vec operator / (double v) {return vec(x / v, y / v);}
    double operator * (vec v) {return x * v.x + y * v.y;}
    double len(){return hypot(x, y);}
    double len_sqr(){return x * x + y * y;}
    vec rotate(double c){
        return vec(x * cos(c) - y * sin(c), x * sin(c) + y * cos(c));
    }
    vec trunc(double l){return (*this) * l / len();}
    vec tot90(){return vec(-y, x);}
};
vec lerp(vec a, vec b, double t){return a * (1 - t) + b * t;}

struct circle
{
    vec c;
    double r;
    circle(){c = vec(0, 0), r = 0;}
    circle(vec _c, double _r){c = _c, r = _r;}
    vec point(double a){return vec(c.x + r * cos(a), c.y + r * sin(a));}
};

    circle c;
    vec st, ed;
    double t, ans,th;
int getTangets(vec p, circle C, double *v,double&cen,int mode=0)
{
    double x = atan2(p.y - C.c.y, p.x - C.c.x);
    double dist = (C.c - p).len();
    double ang = acos(C.r / dist);
    if(mode){
        ang=acos(sqrt(c.r*c.r-t*t/4)/dist);
        ang+=th/2;
    }
    v[0] = x + ang;  v[1] = x - ang;
    if(v[0]<v[1])swap(v[0],v[1]);
    cen=x;
    return 2;
}
bool circle_line_intersection(circle c, vec a, vec b, double *t0, double *t1)
{
    vec d = b - a;
    double A = d * d;
    double B = d * (a - c.c) * 2.0;
    double C = (a - c.c).len_sqr() - c.r * c.r;
    return Quadratic(A, B, C, t0, t1);
}

inline double cal(double x,double offset){
    return (st-c.point(x)).len()+(ed-c.point(x+offset)).len();
}
void gao(double v10,double v11,double v20,double v21){
    double lim1=v21-v10,lim2=v20-v11;
    //if(v10<v11)while(1);
    //if(v20<v21)while(1);
    //if(v10>v21)while(1);
    //if(lim1>lim2)while(1);
    lim1/=th;
    lim2/=th;
    //if(sgn(th)==0)while(1);
    int mx=((int)lim2)+10;
    int _l=max(1,(int)lim1-10),_r=mx;
    //if(lim1>lim2)while(1);
    for(int k = max(1,(int)lim1-10); k<=mx; k ++){
                    //v1[1]<=x<=v1[0]
                    //v2[1]-th<=x+k*th<=v2[0]
                    double L=max(v11,v21-k*th);
                    double R=min(v10,v20-k*th);
                    if(sgn(L-R)>0)continue;
                    for(int _=50;_--;){
                        double len=(R-L)/3;
                        double m1=L+len,m2=R-len;
                        double f1=cal(m1,k*th),f2=cal(m2,k*th);
                        if(f1<f2){
                            ans=min(ans,f1+k*t);
                            R=m2;
                        }else{
                            ans=min(ans,f2+k*t);
                            L=m1;
                        }
                        //if(L+1e-4>R)break;
                    }
                }
}
int main()
{
    while(~ scanf("%lf%lf%lf%lf%lf%lf%lf%lf", &st.x, &st.y, &ed.x, &ed.y, &c.c.x, &c.c.y, &c.r, &t)){
        if(sgn(st.x) == 0 && sgn(st.y) == 0 && sgn(ed.x) == 0 && sgn(ed.y) == 0 && sgn(c.c.x) == 0 && sgn(c.c.y) == 0 && sgn(c.r) == 0 && sgn(t) == 0) break;
        double t0, t1;
        if(circle_line_intersection(c, st, ed, &t0, &t1)){ // 有交點
            vec inter1, inter2;
            if((sgn(t0)<=0||sgn(t0-1)>=0)&&(sgn(t1)<=0||sgn(t1-1)>=0)){
                    ans = (st - ed).len();
            }else{
            inter1 = lerp(st, ed, t0);
            inter2 = lerp(st, ed, t1);
            if(sgn((inter1 - inter2).len() - t) <= 0){
                ans = (st - ed).len();
            }
            else if(sgn(t)){
                ans=1e100;
                th = asin(t / 2 / c.r) * 2;
                for(int i=0;i<2;i++){
                    double v1[2],c1, v2[2],c2;
                    getTangets(st, c, v1,c1,1);
                    getTangets(ed, c, v2,c2);
                    for(int i=0;i<10;i++){
                        v2[0]-=pi*2;
                        v2[1]-=pi*2;
                        c2-=pi*2;
                    }
                    while(v2[1]<c1)v2[0]+=pi*2,v2[1]+=pi*2,c2+=pi*2;
                    th = asin(t / 2 / c.r) * 2;
                    //if(th<0)while(1);
                    gao(v1[0],v1[1],v2[0],v2[1]);
                    gao(v1[0],c1,c2,v2[1]);
                    gao(c1,v1[1],v2[0],c2);
                    swap(st,ed);
                }
                //gao(v1[0],c1,c2,v2[1]);
                //gao(c1,v1[1],v2[0],c2);
            }else{
                double v1[2],c1, v2[2],c2;
                getTangets(st, c, v1,c1);
                getTangets(ed, c, v2,c2);
                ans=1e100;
                for(int i=0;i<2;i++)for(int j=0;j<2;j++){
                        vec a=c.point(v1[i]);
                        vec b=c.point(v2[j]);
                        double now=(st-a).len()+(ed-b).len();
                        double o=fabs(v1[i]-v2[j]);
                        o=min(o,pi*2-o);
                        ans=min(ans,now+o*c.r);
                }
            }
            }
        }
        else{
            ans = (st - ed).len();
        }
        if(ans>1e20)while(1);
        printf("%.15f\n",ans);
    }
	return 0;
}

/*
【trick&&吐槽】
0 0 10 0 5 0 3 5


【題意】


【分析】


【時間復雜度&&優(yōu)化】


*/

C. Chess Knight's Poem

設(shè)$v[i][a][b][c][d]$表示匹配了前$i$個字符，兩個棋子分別在$(a,b)$和$(c,d)$是否可能，然后BFS即可。

#include<cstdio>
#include<cstring>
const int N=111;
int dx[8]={-2,-2,2,2,-1,-1,1,1};
int dy[8]={-1,1,-1,1,2,-2,2,-2};
char xiao[4][10]={
{'q','w','e','r','t','y','u','i','o','p'},
{'a','s','d','f','g','h','j','k','l',';'},
{'z','x','c','v','b','n','m',',','.','/'},
{0,0,1,1,1,1,1,1,0,0}
};
char da[4][10]={
{'Q','W','E','R','T','Y','U','I','O','P'},
{'A','S','D','F','G','H','J','K','L',':'},
{'Z','X','C','V','B','N','M','<','>','?'},
{0,0,1,1,1,1,1,1,0,0}
};
int n,i,j,k,x,y,z;
bool v[N][4][10][4][10];
int q[N*40*40][5],h,t;
bool flag;
char a[N];
inline void ext(int o,int A,int B,int C,int D,int _){
	if(A<0||A>3)return;
	if(B<0||B>9)return;
	if(C<0||C>3)return;
	if(D<0||D>9)return;
	if(A==C&&B==D)return;
	if(_==1){
		if(xiao[A][B]>1){//not shift not space
			if(xiao[C][D]==0){//shift
				if(a[o]!=da[A][B])return;
				o++;
			}else{
				if(a[o]!=xiao[A][B])return;
				o++;
			}
		}else if(xiao[A][B]==1){
			if(a[o]!=' ')return;
			o++;
		}
	}
	if(_==2){
		if(xiao[C][D]>1){//not shift not space
			if(xiao[A][B]==0){//shift
				if(a[o]!=da[C][D])return;
				o++;
			}else{
				if(a[o]!=xiao[C][D])return;
				o++;
			}
		}else if(xiao[C][D]==1){
			if(a[o]!=' ')return;
			o++;
		}
	}
	if(v[o][A][B][C][D])return;
	v[o][A][B][C][D]=1;
	q[++t][0]=o;
	q[t][1]=A;
	q[t][2]=B;
	q[t][3]=C;
	q[t][4]=D;
}
int main(){
	while(1){
		gets(a+1);
		n=strlen(a+1);
		if(a[1]=='*')return 0;
		for(i=0;i<=n+5;i++)for(j=0;j<4;j++)for(k=0;k<10;k++)for(x=0;x<4;x++)for(y=0;y<10;y++)v[i][j][k][x][y]=0;
		h=1,t=0;
		ext(1,3,0,3,9,0);
		flag=0;
		while(h<=t){
			x=q[h][0];
			if(x>n){
				flag=1;
				break;
			}
			y=q[h][1];
			z=q[h][2];
			int A=q[h][3];
			int B=q[h][4];
			h++;
			for(int i=0;i<8;i++){
				ext(x,y+dx[i],z+dy[i],A,B,1);
				ext(x,y,z,A+dx[i],B+dy[i],2);
			}
		}
		puts(flag?"1":"0");
	}
}
/*
CAlmimg eventa
*/

D. Drone

將$(t,f(t))$的函數(shù)畫圖，可以發(fā)現(xiàn)最大值和最小值都在凸殼上，因此答案是可以三分的。

#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;
double x[N], v[N];
double check(double t)
{	
	double mx = -1e18;
	double mn= 1e18;
	for(int i = 1; i <= n; ++i)
	{
		double p = x[i] + t * v[i];
		gmax(mx, p);
		gmin(mn, p);
	}
	return mx - mn;
}
int main()
{
	while(~scanf("%d", &n), n)
	{
		for(int i = 1; i <= n; ++i)
		{
			scanf("%lf%lf", &x[i], &v[i]);
		}
		double l = 0;
		double r = 1.001e10;
		for(int tim = 1; tim <= 100; ++tim)
		{
			double lt = (l + l + r) / 3;
			double rt = (l + r + r) / 3;
			double lv = check(lt);
			double rv = check(rt);
			lv <= rv ? r = rt : l = lt;
		}
		printf("%.12f\n", check(l));
	}
	return 0;
}
/*
【trick&&吐槽】
2
-100 1
100 -1

3
-100 1
100 -1
101 -1

3
-100 -1
0 0
100 1

0

【題意】


【分析】


【時間復雜度&&優(yōu)化】


*/

E. Ed and The Legend of Zelda

設(shè)$f[i][j][k][l]$表示考慮$i$的子樹，$i$子樹內(nèi)作弊了$j$次，$i$作弊情況為$k$，$i$有$l$個兒子作弊的方案數(shù)，使用組合數(shù)轉(zhuǎn)移。

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

#include<cstdio>
const int N=205,P=1000000007;
int n,m,i,x,g[N],nxt[N],f[N][N][2];
int size[N],ans;
int fac[N],inv[N];
int h[N][2][2];
int dp[N][2][2];
inline void up(int&a,int b){a=a+b<P?a+b:a+b-P;}
inline int C(int n,int m){return 1LL*fac[n]*inv[m]%P*inv[n-m]%P;}
void dfs(int x){
	size[x]=1;
	for(int i=g[x];i;i=nxt[i])dfs(i),size[x]+=size[i];
	for(int j=0;j<=1;j++)for(int k=0;k<2;k++)for(int o=0;o<2;o++)dp[j][k][o]=0;
	dp[0][0][0]=fac[size[x]-1];
	dp[1][1][0]=fac[size[x]-1];
	int pre=1;
	for(int i=g[x];i;i=nxt[i]){
		for(int j=0;j<=pre+size[i];j++)for(int k=0;k<2;k++)for(int o=0;o<2;o++)h[j][k][o]=0;
		for(int j=0;j<=pre;j++)for(int k=0;k<2;k++)for(int o=0;o<2;o++)if(dp[j][k][o]){
			for(int A=0;A<=size[i];A++)for(int B=0;B<2;B++)if(f[i][A][B]){
				if(k&&B)continue;
				if(o&&B)continue;
				if(B){
					up(h[j+A][k][o+B],1LL*dp[j][k][o]*inv[size[x]-1]%P*fac[size[x]-size[i]-1]%P*C(size[x]-1,size[i]-1)%P*f[i][A][B]%P);
				}else{
					up(h[j+A][k][o+B],1LL*dp[j][k][o]*inv[size[i]]%P*f[i][A][B]%P);
				}
			}
		}
		pre+=size[i];
		for(int j=0;j<=pre;j++)for(int k=0;k<2;k++)for(int o=0;o<2;o++)dp[j][k][o]=h[j][k][o];
	}
	for(int j=0;j<=size[x];j++)for(int k=0;k<2;k++)f[x][j][k]=0;
	for(int j=0;j<=pre;j++)for(int k=0;k<2;k++)for(int o=0;o<2;o++)
		up(f[x][j][k],dp[j][k][o]);
}
int main(){
	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;
	while(~scanf("%d%d",&n,&m)){
		if(!n)return 0;
		for(i=0;i<=n;i++)g[i]=0;
		for(i=2;i<=n;i++){
			scanf("%d",&x);
			nxt[i]=g[x];
			g[x]=i;
		}
		dfs(1);
		ans=0;
		for(i=0;i<=m;i++)up(ans,f[1][i][0]);
		printf("%d\n",ans);
	}
}
/*
5 1
1 1 5 1

3 2
1 1

0 0
*/

F. Fix and Solve

首先將每個數(shù)轉(zhuǎn)化為質(zhì)數(shù)出現(xiàn)最多一次的數(shù)。

對于每個質(zhì)數(shù)用set維護所有出現(xiàn)的下標，那么相鄰兩個出現(xiàn)下標可以使得一段區(qū)間的非法。

線段樹維護每個區(qū)間內(nèi)被標記為非法的次數(shù)最小值以及最小值個數(shù)即可。

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

#include<cstdio>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
const int N=100010,M=262150;
int i,j,notprime[N];
vector<int>has[N];
set<int>T[N];
int n,K,m,a[N],all;
int tag[M],mi[M],mcnt[M];
void build(int x,int a,int b){
	mi[x]=tag[x]=0;
	mcnt[x]=b-a+1;
	if(a==b)return;
	int mid=(a+b)>>1;
	build(x<<1,a,mid);
	build(x<<1|1,mid+1,b);
}
inline void tag1(int x,int p){tag[x]+=p;mi[x]+=p;}
void change(int x,int a,int b,int c,int d,int p){
	if(c<=a&&b<=d){tag1(x,p);return;}
	if(tag[x]){
		tag1(x<<1,tag[x]);
		tag1(x<<1|1,tag[x]);
		tag[x]=0;
	}
	int mid=(a+b)>>1;
	if(c<=mid)change(x<<1,a,mid,c,d,p);
	if(d>mid)change(x<<1|1,mid+1,b,c,d,p);
	mi[x]=min(mi[x<<1],mi[x<<1|1]);
	mcnt[x]=0;
	if(mi[x]==mi[x<<1])mcnt[x]+=mcnt[x<<1];
	if(mi[x]==mi[x<<1|1])mcnt[x]+=mcnt[x<<1|1];
}
inline int query(){
	if(mi[1]>0)return all;
	return all-mcnt[1];
}
inline void gao(int l,int r,int p){
	if(r-l+1>K)return;
	int a=r-K+1,b=l;
	change(1,1,all,a,b,p);
}
inline void ins(int x,int y){
	T[x].insert(y);
	set<int>::iterator it=T[x].find(y),pre=it,nxt=it;
	pre--,nxt++;
	if(*pre&&*nxt<N)gao(*pre,*nxt,-1);
	if(*pre)gao(*pre,y,1);
	if(*nxt<N)gao(y,*nxt,1);
}
inline void del(int x,int y){
	set<int>::iterator it=T[x].find(y),pre=it,nxt=it;
	pre--,nxt++;
	if(*pre&&*nxt<N)gao(*pre,*nxt,1);
	if(*pre)gao(*pre,y,-1);
	if(*nxt<N)gao(y,*nxt,-1);
	T[x].erase(y);
}
inline void add(int x,int k){
	for(int i=0;i<has[k].size();i++)ins(has[k][i],x);
}
inline void remove(int x,int k){
	for(int i=0;i<has[k].size();i++)del(has[k][i],x);
}
int main(){
	for(i=2;i<N;i++){
		if(!notprime[i]){
			for(j=i;j<N;j+=i){
				notprime[j]=1;
				has[j].push_back(i);
			}
		}
	}
	while(~scanf("%d%d%d",&n,&K,&m)){
		if(!n)return 0;
		all=n-K+1;
		build(1,1,all);
		for(i=1;i<N;i++)T[i].clear(),T[i].insert(0),T[i].insert(N);
		for(i=1;i<=n;i++){
			scanf("%d",&a[i]);
			add(i,a[i]);
		}
		printf("%d\n",query());
		while(m--){
			int x,y;
			scanf("%d%d",&x,&y);
			remove(x,a[x]);
			add(x,a[x]=y);
			printf("%d\n",query());
		}
		long long ans=0;
		for(i=1;i<=n;i++)ans+=a[i];
		printf("%lld\n",ans);
	}
}

G. Gold Bandits

爆搜所有$1$到$2$的最短路，然后再求$1$到$2$的開銷最小的最短路使得收益最大。

#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 = 40, 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 d[N], f[N];
int v[N], w[N];
vector<int>a[N];
void bfs()
{
	queue<int>q; q.push(1); 
	MS(d, -1); d[1] = 0;
	while(!q.empty())
	{	
		int x = q.front(); q.pop();
		for(auto y : a[x])if(d[y] == -1)
		{
			q.push(y);
			d[y] = d[x] + 1;
		}
	}
}
bool e[N];
int ans;
int sub()
{
	MS(e, 0);
	MS(f, 63); f[2] = 0;
	for(int tim = 1; tim <= n; ++tim)
	{
		int x = 0;
		for(int i = 1; i <= n; ++i)if(!e[i] && f[i] < f[x])
		{
			x = i;
		}
		e[x] = 1;
		for(auto y : a[x])
		{
			gmin(f[y], f[x] + w[y]);
		}
	}
	return f[1];
}
void dfs(int x, int val)
{
	if(x == 2)
	{
		gmax(ans, val - sub());
		return;
	}
	for(auto y : a[x])if(d[y] == d[x] + 1)
	{
		w[y] = v[y];
		dfs(y, val + v[y]);
		w[y] = 0;
	}
}
int main()
{
	while(~scanf("%d%d", &n, &m), n || m)
	{
		for(int i = 1; i <= n; ++i)a[i].clear();
		for(int i = 3; i <= n; ++i)scanf("%d", &v[i]);
		for(int i = 1; i <= m; ++i)
		{
			int x, y; scanf("%d%d", &x, &y);
			a[x].push_back(y);
			a[y].push_back(x);
		}
		bfs();
		ans = 0;
		dfs(1, 0);
		printf("%d\n", ans);
	}
	return 0;
}
/*
【trick&&吐槽】
3 3
1
1 2
2 3
1 3

4 4
24 10
1 3
2 3
2 4
1 4

6 8
100 500 300 75
1 3
1 4
3 6
4 5
3 5
4 6
2 5
2 6

7 7
90 1000 700 2000 800
1 3
1 4
1 5
3 7
5 6
2 6
3 6

0 0

【題意】


【分析】


【時間復雜度&&優(yōu)化】


*/

H. How Many Values?

$O(n\log a)$枚舉所有$\gcd$本質(zhì)不同的區(qū)間即可。

#include<cstdio>
const int N=100010;
int n,i,j,l[N],v[N],a[N],ans,vis[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
	while(~scanf("%d",&n)){
		if(!n)return 0;
		for(i=0;i<=n;i++)a[i]=l[i]=v[i]=0;
		for(ans=i=0;i<=100;i++)vis[i]=0;
		for(i=1;i<=n;i++)scanf("%d",&a[i]);
		for(i=1;i<=n;i++)for(v[i]=a[i],j=l[i]=i;j;j=l[j]-1){
			v[j]=gcd(v[j],a[i]);
			while(l[j]>1&&gcd(a[i],v[l[j]-1])==gcd(a[i],v[j]))l[j]=l[l[j]-1];
			vis[v[j]]=1;
		}
		for(i=1;i<=100;i++)if(vis[i])ans++;
		printf("%d\n",ans);
	}
}

I. Integer Estate Agent

按題意模擬即可。

#include<cstdio>
typedef __int128 lll;
const int N = 1e6 + 10;
int n;
int cnt[N];

void init()
{
	int ans = 0;
	for(int i = 2; i <= 1e6; i ++){
		int x = 0;
		for(int j = 0; j <= 1e6; j ++){
			x += i + j;
			if(x > 1e6) break;
			cnt[x] ++;
			ans ++;
		}
	}
	//printf("%d\n", ans);
}
int main(){
	init();
	while(~ scanf("%d", &n), n){
		printf("%d\n", cnt[n]);
	}	
	return 0;
}

J. John and Super Mario 169

旅行商問題，狀壓DP即可，時間復雜度$O(2^nn^3)$。

#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;
const double inf = 1e18;
template <class T1, class T2>inline void gadd(T1 &a, T2 b) { a = (a + b) % Z; }
int casenum, casei;
int n;
struct P
{
	int x, y, z;
}me, sw[13], p[13][13];
double f[1 << 13][13];
double d[13][13];
double dp_sw[1 << 13][13];
double dp[1 << 13][13][13];
int K[13];
double sqr(double x)
{
	return x * x;
}
double dis(P a, P b)
{
	return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y) + sqr(a.z - b.z));
}
int main()
{
	while(~scanf("%d", &n), n)
	{
		scanf("%d%d%d", &me.x, &me.y, &me.z);
		for(int i = 0; i < n; ++i)
		{
			scanf("%d", &K[i]);
			scanf("%d%d%d", &sw[i].x, &sw[i].y, &sw[i].z);
			for(int j = 0; j < K[i]; ++j)
			{
				scanf("%d%d%d", &p[i][j].x, &p[i][j].y, &p[i][j].z);
			}
			
			int top = 1 << K[i];
			for(int j = 0; j < top; ++j)
			{
				for(int k = 0; k < K[i]; ++k)f[j][k] = inf;
			}
			for(int j = 0; j < K[i]; ++j)
			{
				f[1 << j][j] = dis(sw[i], p[i][j]);
			}
			for(int sta = 0; sta < top; ++sta)
			{
				for(int j = 0; j < K[i]; ++j)if(f[sta][j] != inf && (sta >> j & 1))
				{
					for(int k = 0; k < K[i]; ++k)if(~sta >> k & 1)
					{
						gmin(f[sta | 1 << k][k], f[sta][j] + dis(p[i][j], p[i][k]));
					}
				}
			}
			
			for(int j = 0; j < K[i]; ++j)
			{
				d[i][j] = f[top - 1][j]; 
			}
		}
		
		int top = 1 << n;
		for(int sta = 0; sta < top; ++sta)
		{
			for(int j = 0; j < n; ++j)
			{
				dp_sw[sta][j] = inf;
				for(int k = 0; k < K[j]; ++k)
				{
					dp[sta][j][k] = inf;
				}
			}
		}
		for(int j = 0; j < n; ++j)
		{
			dp_sw[1 << j][j] = dis(me, sw[j]);
		}
		for(int sta = 0; sta < top; ++sta)
		{
			for(int j = 0; j < n; ++j)
			{
				if(dp_sw[sta][j] != inf)
				{
					for(int k = 0; k < K[j]; ++k)
					{
						gmin(dp[sta][j][k], dp_sw[sta][j] + d[j][k]);
					}
				}
			}
			for(int j = 0; j < n; ++j)if(sta >> j & 1)
			{
				for(int u = 0; u < n; ++u)if(~sta >> u & 1)
				{
					for(int k = 0; k < K[j]; ++k)if(dp[sta][j][k] != inf)
					{
						gmin(dp_sw[sta | 1 << u][u], dp[sta][j][k] + dis(p[j][k], sw[u]));
						/*
						for(int v = 0; v < K[u]; ++v)
						{
							gmin(dp[sta | 1 << u][u][v], 
							dp[sta][j][k] + dis(p[j][k], sw[u]) + d[u][v]);
						}
						*/
					}
				}
			}
		}
		double ans = inf;
		for(int j = 0; j < n; ++j)
		{	
			for(int k = 0; k < K[j]; ++k)
			{
				gmin(ans, dp[top - 1][j][k]);
			}
		}
		printf("%.10f\n", ans);
	}
	return 0;
}
/*
【trick&&吐槽】
2 5 5 0
4 6 0 0
7 0 0
-11 -1 0
-11 1 0

-10 0 0
2 5 0 0
0 0 0
0 5 0

0 0 0 0

【題意】


【分析】


【時間復雜度&&優(yōu)化】


*/

posted @ 2018-04-14 02:04 Claris 閱讀(930) 評論(0) 收藏舉報

刷新頁面返回頂部

Claris' Blog

XIV Open Cup named after E.V. Pankratiev. GP of America

公告