XIII Open Cup named after E.V. Pankratiev. GP of Asia and South Caucasus

A. RPG

首先计算出每个技能对于每个属性值的可行区间，若区间为空则不合法。

枚举两个技能，以及每个属性值，根据区间的关系可以得到哪个必须要在另一个之前学，连边看看是否有环即可。

时间复杂度$O(n^2m)$。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int Inf=1e9;
int l[555][555],r[555][555];
vector<int>G[555];
int cnt[555];
int n,m;
bool topo(){
	queue<int>q;
	int tot=0;
	for(int i=1;i<=n;i++){
		if(!cnt[i])q.push(i);
	}
	while(!q.empty()){
		int u=q.front();q.pop();tot++;
		for(int i=0;i<G[u].size();i++){
			int v=G[u][i];
			cnt[v]--;
			if(!cnt[v])q.push(v);
		}
	}
	if(tot<n)return 0;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)l[i][j]=0,r[i][j]=Inf;
	for(int i=1;i<=n;i++){
		int k;scanf("%d",&k);
		for(int j=0;j<k;j++){
			char s[4];
			int id,val,ty=0;
			scanf("%d%s%d",&id,s,&val);
			if(s[0]=='>')l[i][id]=max(l[i][id],val);
			else r[i][id]=min(r[i][id],val);
		}
	}
	bool flag=1;
	for(int i=1;i<=n&&flag;i++){
		for(int j=1;j<=n&&flag;j++){
			bool ned=0;;
			for(int k=1;k<=m;k++){
				if(l[i][k]>r[i][k]){flag=0;break;}
				if(r[i][k]<l[j][k]){ned=1;break;}
			}
			if(i==j)continue;
			if(ned){
				//printf("i=%d j=%d\n",i,j);
				G[i].push_back(j),cnt[j]++;
			}
		}
	}
	if(flag&&!topo())flag=0;
	puts(flag?"Yes":"No");
	return 0;
}

　　

B. Integer in integer

按KMP的next数组进行数位DP即可，时间复杂度$O(|B||C|)$。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int mod=1e9+7;
char A[10020],B[10020],C[10020];
int num[10020];
int dp2[10020][2][2][502];
int dp1[10020][2];
int lsc;
int to[10020][10];
int f[555];
inline void up(int &x,int y){x+=y;if(x>=mod)x-=mod;}
int dfs1(int cur,int can){
	if(cur<0)return 1;
	int &t=dp1[cur][can];
	if(t>=0)return t;
	t=0;
	for(int i=0;i<10;i++){
		if(!can&&i>num[cur])break;
		int ncan=can||(i<num[cur]);
		up(t,dfs1(cur-1,ncan));
	}
	return t;
}
int dfs2(int cur,int qd,int can,int pp){
	if(cur<0)return 0;
	int &t=dp2[cur][qd][can][pp];
	if(t>=0)return t;
	t=0;
	for(int i=0;i<10;i++){
		if(!can&&i>num[cur])break;
		int ncan=can||(i<num[cur]);
		int nqd=qd||(i);
		int npp=to[pp][i];
		if(!nqd)npp=0;
		if(npp>=lsc){
			//printf("cur=%d pp=%d can=%d t0=%d\n",cur,can,pp,t);
			up(t,dfs1(cur-1,ncan));
			//printf("cur=%d pp=%d can=%d t0=%d\n",cur,can,pp,t);
			up(t,dfs2(cur-1,nqd,ncan,f[lsc]));
		}
		else{
			up(t,dfs2(cur-1,nqd,ncan,npp));
		}
	}
	//if(t&&cur<=2)printf("%d %d %d t=%d\n",cur,can,pp,t);
	return t;
}
int solve(char *A){
	int ls=strlen(A);
	reverse(A,A+ls);
	memset(num,0,sizeof num);
	for(int i=0;i<ls;i++)num[i]=A[i]-'0';
	memset(dp1,-1,sizeof dp1);
	memset(dp2,-1,sizeof dp2);
	//printf("",dfs1(0,));
	int ret=dfs2(10000,0,0,0);
	//printf("ret=%d\n",ret);
	return ret;
}
void getf(){
	f[0]=f[1]=0;
	for(int i=1;i<lsc;i++){
		int j=f[i];
		while(j&&(C[i]!=C[j]))j=f[j];
		if(C[i]==C[j])f[i+1]=j+1;
		else f[i+1]=0;
	}
	for(int i=0;i<lsc;i++){
		for(int j=0;j<10;j++){
			int t=i;
			while(t&&((j+'0')!=C[t]))t=f[t];
			if(C[t]==(j+'0'))to[i][j]=t+1;
			else to[i][j]=0;
		}
	}
}
int main(){
	scanf("%s%s%s",A,B,C);
	lsc=strlen(C);
	getf();
	int ans=0;
	for(int i=0,j=0;A[i];i++){
		while(j&&A[i]!=C[j])j=f[j];
		if(A[i]==C[j])j++;
		else j=0;
		if(j==lsc){j=f[lsc];ans++;}
	}
	//solve(A);
	int ans1=solve(A);
	int ans2=solve(B);
	//printf("ans1=%d ans2=%d\n",ans1,ans2);
	ans=((ans2-ans1+mod)%mod+ans)%mod;
	printf("%d\n",ans);
	return 0;
}

　　

C. Card Game

留坑。

D. Epidemy

DLX重复覆盖，加上卡时即可通过。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;

#define rep( i , a , b ) for ( int i = ( a ) ; i <  ( b ) ; ++ i )
#define For( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define rev( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define rec( i , A , o ) for ( int i = A[o] ; i != o ; i = A[i] )
#define clr( a , x ) memset ( a , x , sizeof a )

const int MAXN = 3005 ;
const int MAXE = 30005 ;
const int MAXNODE = 100005 ;
const int INF = 0x3f3f3f3f ;

struct DLX {
	int L[MAXNODE] ;
	int R[MAXNODE] ;
	int D[MAXNODE] ;
	int U[MAXNODE] ;
	int row[MAXNODE] ;
	int col[MAXNODE] ;
	int H[MAXE] ;
	int S[MAXE] ;
	int n , k ;
	int size ;
	int vis[MAXE] , Time ;
	int ans ;

	void init ( int _n , int _k ) {
		n = _n ;
		k = _k ;
		Time = 0 ;
		clr ( H , -1 ) ;
		clr ( vis , 0 ) ;
		For ( i , 0 , n ) {
			S[i] = 0 ;
			U[i] = D[i] = i ;
			L[i] = i - 1 ;
			R[i] = i + 1 ;
		}
		L[0] = n ;
		R[n] = 0 ;
		size = n ;
		ans = INF ;
	}

	void link ( int r , int c ) {
		++ S[c] ;
		++ size ;
		row[size] = r ;
		col[size] = c ;
		D[size] = c ;
		U[size] = U[c] ;
		D[U[c]] = size ;
		U[c] = size ;
		if ( ~H[r] ) {
			L[size] = L[H[r]] ;
			R[size] = H[r] ;
			R[L[size]] = size ;
			L[R[size]] = size ;
		} else L[size] = R[size] = H[r] = size ;
	}

	void remove ( int c ) {
		rec ( i , D , c ) {
			R[L[i]] = R[i] ;
			L[R[i]] = L[i] ;
		}
	}

	void resume ( int c ) {
		rec ( i , U , c ) R[L[i]] = L[R[i]] = i ;
	}

	int h () {
		++ Time ;
		int cnt = 0 ;
		rec ( i , R , 0 ) if ( vis[i] != Time ) {
			vis[i] = Time ;
			++ cnt ;
			rec ( j , D , i ) rec ( k , R , j ) vis[col[k]] = Time ;
		}
		return cnt ;
	}

	void dance ( int d ) {
		if ( clock () >= 2.5 * CLOCKS_PER_SEC ) return ;
		if ( d + h () >= min ( ans , k + 1 ) ) return ;
		//printf ( "dep = %d %d %d\n" , d , R[0] , ans ) ;
		if ( !R[0] ) {
			ans = min ( d , ans ) ;
			return ;
		}
		int c = R[0] ;
		rec ( i , R , 0 ) if ( S[i] < S[c] ) c = i ;
		rec ( i , D , c ) {
			remove ( i ) ;
			rec ( j , R , i ) remove ( j ) ;
			dance ( d + 1 ) ;
			rec ( j , L , i ) resume ( j ) ;
			resume ( i ) ;
		}
	}
} ;

DLX dlx ;
vector < int > G[MAXN] ;
int vis[MAXE] ;
int deg[MAXN] ;
int n , m , k ;

void solve () {
	dlx.init ( m , k ) ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		G[i].clear () ;
		deg[i] = 0 ;
	}
	for ( int i = 1 ; i <= m ; ++ i ) {
		int u , v ;
		scanf ( "%d%d" , &u , &v ) ;
		G[u].push_back ( i ) ;
		G[v].push_back ( i ) ;
		++ deg[u] ;
		++ deg[v] ;
		vis[i] = 0 ;
	}
	int ans = 0 ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		if ( deg[i] > k ) {
			ans ++ ;
			for ( int j = 0 ; j < G[i].size () ; ++ j ) {
				vis[G[i][j]] = 1 ;
			}
		}
	}
	//printf ( "ans = %d\n" , ans ) ;
	if ( ans > k ) {
		printf ( "Impossible\n" ) ;
		return ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		if ( deg[i] <= k ) {
			for ( int j = 0 ; j < G[i].size () ; ++ j ) {
				if ( !vis[G[i][j]] ) {
					//printf ( "link %d %d\n" , i , G[i][j] ) ;
					dlx.link ( i , G[i][j] ) ;
				}
			}
		}
	}
	for ( int i = 1 ; i <= m ; ++ i ) if ( vis[i] ) {
		dlx.R[dlx.L[i]] = dlx.R[i] ;
		dlx.L[dlx.R[i]] = dlx.L[i] ;
	}
	dlx.dance ( ans ) ;
	if ( dlx.ans <= k ) printf ( "%d\n" , dlx.ans ) ;
	else printf ( "Impossible\n" ) ;
}

int main () {
	while ( ~scanf ( "%d%d%d" , &n , &m , &k ) ) solve () ;
	return 0 ;
}

　　

E. MST

首先求出最小生成树，如果删掉的不是树边，那么答案不变，否则要找到一条经过它的权值最小的非树边来进行替换。

按边权从小到大依次考虑每条非树边，那么就是一个树上染色问题，并查集维护即可。

时间复杂度$O(m\log m)$。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;
typedef pair < int , int > pii ;

#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 200005 ;
const int MAXE = 400005 ;

struct Edge {
	int v , c , n ;
	Edge () {}
	Edge ( int v , int c , int n ) : v ( v ) , c ( c ) , n ( n ) {}
} ;

struct Node {
	int u , v , c , id ;
	bool operator < ( const Node& a ) const {
		return c < a.c ;
	}
} ;

Edge E[MAXE] ;
Node a[MAXE] ;
int H[MAXN] , cntE ;
int pre[MAXN] ;
int dep[MAXN] ;
int val[MAXN] ;
int in[MAXE] ;
int be[MAXN] ;
LL res[MAXN] ;
int p[MAXN] ;
int n , m ;

void init () {
	cntE = 0 ;
	clr ( H , -1 ) ;
}

void addedge ( int u , int v , int c ) {
	E[cntE] = Edge ( v , c , H[u] ) ;
	H[u] = cntE ++ ;
}

void dfs ( int u , int f ) {
	for ( int i = H[u] ; ~i ; i = E[i].n ) {
		int v = E[i].v ;
		if ( v == f ) continue ;
		pre[v] = u ;
		dep[v] = dep[u] + 1 ;
		be[v] = E[i].c ;
		dfs ( v , u ) ;
	}
}

int F ( int x ) {
	return p[x] == x ? x : ( p[x] = F ( p[x] ) ) ;
}

void solve () {
	init () ;
	for ( int i = 1 ; i <= n ; ++ i ) {
		p[i] = i ;
	}
	for ( int i = 0 ; i < m ; ++ i ) {
		scanf ( "%d%d%d" , &a[i].u , &a[i].v , &a[i].c ) ;
		a[i].id = i ;
		val[i] = -1 ;
		in[i] = 0 ;
	}
	sort ( a , a + m ) ;
	LL sum = 0 ;
	int tot = n - 1 ;
	for ( int i = 0 ; i < m ; ++ i ) {
		int x = F ( a[i].u ) ;
		int y = F ( a[i].v ) ;
		if ( x != y ) {
			-- tot ;
			p[x] = y ;
			in[i] = 1 ;
			sum += a[i].c ;
			addedge ( a[i].u , a[i].v , i ) ;
			addedge ( a[i].v , a[i].u , i ) ;
		}
	}
	if ( tot ) {
		for ( int i = 0 ; i < m ; ++ i ) {
			printf ( "-1\n" ) ;
		}
		return ;
	}
	for ( int i = 1 ; i <= n ; ++ i ) {
		p[i] = i ;
	}
	dfs ( 1 , 1 ) ;
	for ( int i = 0 ; i < m ; ++ i ) {
		int u = a[i].u ;
		int v = a[i].v ;
		if ( !in[i] ) {
			while ( 1 ) {
				int x = F ( a[i].u ) ;
				int y = F ( a[i].v ) ;
				if ( x != y ) {
					if ( dep[x] > dep[y] ) {
						val[be[x]] = a[i].c ;
						p[x] = F ( pre[x] ) ;
						x = F ( pre[x] ) ;
					} else {
						val[be[y]] = a[i].c ;
						p[y] = F ( pre[y] ) ;
						y = F ( pre[y] ) ;
					}
				} else break ;
			}
		}
	}
	for ( int i = 0 ; i < m ; ++ i ) {
		if ( !in[i] ) {
			res[a[i].id] = sum ;
		} else {
			if ( ~val[i] ) res[a[i].id] = sum - a[i].c + val[i] ;
			else res[a[i].id] = -1 ;
		}
	}
	for ( int i = 0 ; i < m ; ++ i ) {
		printf ( "%lld\n" , res[i] ) ;
	}
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}

　　

F. Molecules

将每行倍长，然后依次拼接起来，得到一个序列，构造多项式FFT即可。

时间复杂度$O(n^2\log n)$。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std ;

typedef long long LL ;

#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 1030 ;
const int MAXM = 1030 * 1030 * 4 ;
const double pi = acos ( -1.0 ) ;

struct Complex {
	double r , i ;
	Complex () {}
	Complex ( double r , double i ) : r ( r ) , i ( i ) {}
	Complex operator + ( const Complex& t ) const {
		return Complex ( r + t.r , i + t.i ) ;
	}
	Complex operator - ( const Complex& t ) const {
		return Complex ( r - t.r , i - t.i ) ;
	}
	Complex operator * ( const Complex& t ) const {
		return Complex ( r * t.r - i * t.i , r * t.i + i * t.r ) ;
	}
} ;

int n , m ;
Complex x1[MAXM] , x2[MAXM] ;
LL num[MAXM] ;
LL ans[MAXM] ;

void FFT ( Complex y[] , int n , int rev ) {
	for ( int i = 1 , j , k , t ; i < n ; ++ i ) {
		for ( j = 0 , k = n >> 1 , t = i ; k ; k >>= 1 , t >>= 1 ) {
			j = j << 1 | t & 1 ;
		}
		if ( i < j ) swap ( y[i] , y[j] ) ;
	}
	for ( int s = 2 , ds = 1 ; s <= n ; ds = s , s <<= 1 ) {
		Complex wn ( cos ( rev * 2 * pi / s ) , sin ( rev * 2 * pi / s ) ) ;
		for ( int k = 0 ; k < n ; k += s ) {
			Complex w ( 1 , 0 ) , t ;
			for ( int i = k ; i < k + ds ; ++ i , w = w * wn ) {
				y[i + ds] = y[i] - ( t = w * y[i + ds] ) ;
				y[i] = y[i] + t ;
			}
		}
	}
	if ( rev < 0 ) {
		for ( int i = 0 ; i < n ; ++ i ) {
			y[i].r /= n ;
		}
	}
}

int dist ( int x , int y ) {
	return x * x + y * y ;
}

void solve () {
	LL tot = 0 ;
	double ave = 0 ;
	int x , n1 = 1 ;
	clr ( num , 0 ) ;
	clr ( ans , 0 ) ;
	m = 2 * n * n ;
	while ( n1 < 2 * m ) n1 <<= 1 ;
	for ( int i = 0 ; i < n ; ++ i ) {
		for ( int j = 0 ; j < n ; ++ j ) {
			scanf ( "%d" , &x ) ;
			num[i * 2 * n + j] = x ;
			tot += x ;
			ans[0] += x * ( x - 1 ) / 2 ;
		}
	}
	/*for ( int i = 0 ; i < m ; ++ i ) {
		printf ( "%d " , num[i] ) ;
	}
	printf ( "\n" ) ;*/
	for ( int i = 0 ; i < m ; ++ i ) {
		x1[i] = Complex ( num[i] , 0 ) ;
		x2[i] = Complex ( num[m - i - 1] , 0 ) ;
	}
	for ( int i = m ; i < n1 ; ++ i ) {
		x1[i] = x2[i] = Complex ( 0 , 0 ) ;
	}
	FFT ( x1 , n1 , 1 ) ;
	FFT ( x2 , n1 , 1 ) ;
	for ( int i = 0 ; i < n1 ; ++ i ) {
		x1[i] = x1[i] * x2[i] ;
	}
	FFT ( x1 , n1 , -1 ) ;
	/*for ( int i = 0 ; i < n1 ; ++ i ) {
		printf ( "%d " , ( int ) ( x1[i].r + 0.5 ) ) ;
	}
	printf ( "\n" ) ;*/
	for ( int i = m ; i < n1 ; ++ i ) {
		num[i] = ( int ) ( x1[i].r + 0.5 ) ;
		int x1 = 0 , y1 = 0 ;
		int x2 = ( i - m + 1 ) / ( 2 * n ) ;
		int y2 = ( i - m + 1 ) % ( 2 * n ) ;
		if ( y2 >= n ) {
			int tmp = n * 2 - y2 ;
			y1 += tmp ;
			x2 ++ ;
			y2 = 0 ;
		}
		int dis = dist ( x1 - x2 , y1 - y2 ) ;
		ans[dis] += num[i] ;
		ave += sqrt ( 1.0 * dis ) * num[i] ;
	}
	tot = tot * ( tot - 1 ) / 2 ;
	printf ( "%.10f\n" , ave / tot ) ;
	int cnt = 0 ;
	for ( int i = 0 ; i < MAXM ; ++ i ) if ( ans[i] ) {
		printf ( "%d %lld\n" , i , ans[i] ) ;
		++ cnt ;
		if ( cnt >= 10000 ) break ;
	}
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}

　　

G. Carrier Pigeon

http://blog.csdn.net/huyuncong/article/details/16861281

#include<cstdio>
const int N=100,inf=200000000;
int n,m,S,T,F,o,i,j,k,t,x,e[1000][5],f[205][N][N],ans;
inline void up(int&a,int b){if(a>b)a=b;}
int main(){
  scanf("%d%d%d%d%d",&n,&m,&S,&T,&F);
  for(i=0;i<m;i++)for(j=0;j<5;j++)scanf("%d",&e[i][j]);
  for(o=1;o<=F;o++){
    for(i=0;i<n;i++)for(j=0;j<n;j++)if(i!=j)f[o][i][j]=inf;
    for(i=0;i<m;i++)if(e[i][2]>e[i][3]){
      if(o<=e[i][4])t=e[i][2]*o;else t=e[i][2]*e[i][4]+(o-e[i][4])*e[i][3];
      up(f[o][e[i][0]][e[i][1]],t);
    }
    for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)up(f[o][i][j],f[o][i][k]+f[o][k][j]);
  }
  ans=f[F][S][T];
  for(x=0;x<m;x++)if(e[x][2]<e[x][3])for(o=1;o<=F;o++){
    if(o<=e[x][4])t=e[x][2]*o;else t=e[x][2]*e[x][4]+(o-e[x][4])*e[x][3];
    for(i=0;i<n;i++)for(j=0;j<n;j++)up(ans,f[F][S][i]+f[o][i][e[x][0]]+t+f[o][e[x][1]][j]+f[F-o][i][j]+f[F][j][T]);
  }
  if(ans<inf)printf("%d",ans);else puts("Impossible");
  return 0;
}

　　

H. Circles

将第一个圆$10^6$等分，对于那些与第二个圆所在平面距离不超过$eps$的等分点，我们可以近似认为这些点就是第一个圆与第二个圆所在平面的交点，然后判断一下是否同时出现在第二个圆内和圆外的交点即可。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
const double pi=acos(-1.0);

const double EPS = 1e-4;
const double eps=1e-4;
struct Point3
{
    double x,y,z;
    Point3() {}
    Point3(double x,double y,double z):x(x),y(y),z(z) {}
    void in(){
    	scanf("%lf%lf%lf",&x,&y,&z);
    }
    void pt(){
    	printf("x=%.3f y=%.3f z=%.3f\n",x,y,z);
    }
};

typedef Point3 Vec3;

Vec3 operator + (Vec3 A,Vec3 B)
{
    return Vec3(A.x + B.x,A.y + B.y,A.z + B.z);
}
Vec3 operator - (Point3 A,Point3 B)
{
    return Vec3(A.x-B.x,A.y-B.y,A.z-B.z);
}
Vec3 operator * (Vec3 A,double p)
{
    return Vec3(A.x * p,A.y * p,A.z * p);
}
Vec3 operator / (Vec3 A,double p)
{
    return Vec3(A.x / p,A.y / p,A.z / p);
}

int dcmp(double x)
{
    return fabs(x) < EPS ? 0 : (x <0 ? -1:1);
}

double Dot3(Vec3 A, Vec3 B)
{
    return A.x * B.x + A.y * B.y + A.z * B.z;
}
double Length3(Vec3 A)
{
    return sqrt(Dot3(A,A));
}
double Angle(Vec3 A,Vec3 B)
{
    return acos(Dot3(A,B) / Length3(A) / Length3(B));
}
Vec3 Cross3(Vec3 A,Vec3 B)
{
    return Vec3(A.y * B.z - A.z * B.y,
                A.z * B.x - A.x * B.z,
                A.x * B.y - A.y * B.x);
}
double ssin,scos;
Point3 rotate(Point3 a,Point3 b){//a
	Point3 e1,e2,e3;
	e3=b;double lens=Dot3(a,e3);
	e1=a-e3*lens;
	if(Length3(e1)>(1e-6)){e1=e1/Length3(e1);}else return a;
	e2=Cross3(e1,e3);
	double xx1=Dot3(a,e2),yy1=Dot3(a,e1),x=xx1*scos-yy1*ssin;
	double y=xx1*ssin+yy1*scos;
	return e3*lens+e1*y+e2*x;
}
struct Plane//平面：单位法向量+点
{
    Vec3 n;
    Point3 p0;
    Plane() {}
    Plane(Vec3 nn,Point3 pp0)
    {
        n = nn/Length3(nn);
        p0 = pp0;
    }
    Plane(Point3 a,Point3 b,Point3 c)
    {
        Point3 nn = Cross3(b-a,c-a);
        n = nn/Length3(nn);
        p0 = a;
    }
}yuan1,yuan2;
Plane jpfPlane(Point3 a1,Point3 a2,Point3 b,Point3 c)//角平分面
{
    Plane p1 = Plane(a1, b, c),p2 = Plane(a2,c,b);
    Vec3 temp = p1.n + p2.n;
    return Plane(Cross3(temp, c-b),b);
}
Point3 LinePlaneIntersection(Point3 p1,Point3 p2,Plane a)//线面交
{
    Point3 p0 = a.p0;
    Vec3 n = a.n,v = p2-p1;
    double t = (Dot3(n,p0-p1) / Dot3(n,p2-p1));
    return p1 + v * t;
}
Point3 PlaneInsertion(Plane a,Plane b,Plane c)//三面交点
{
    Vec3 nn = Cross3(a.n,b.n),use = Cross3(nn,a.n);
    Point3 st = LinePlaneIntersection(a.p0, a.p0+use,b);
    return LinePlaneIntersection(st, st+nn, c);
}
double DistanceToPlane(Point3 p,Plane a)//点到面的距离
{
    Point3 p0 = a.p0;
    Vec3 n = a.n;
    return fabs(Dot3(p-p0,n)) / Length3(n);
}
bool isOnPlane(Point3 a,Point3 b,Point3 c,Point3 d)//判断是否四点共面
{
    double t = Dot3(d-a,Cross3(b-a, c-a));
    return dcmp(t)==0;
}
bool check(Point3 pp,Plane pl){
	//printf("dis=%.12f\n",DistanceToPlane(pp,pl));
	return fabs(DistanceToPlane(pp,pl))<eps;
}
bool solve(Point3 pp){
	int LIM=1000000;
	Point3 npp= yuan2.p0+pp;
	int ret=0;
	/*puts("faxiangliang");
	yuan2.n.pt();
	npp.pt();
	*/
	for(int i=0;i<LIM;i++){
		//npp.pt();
		//if(!check(npp,yuan2)){printf("i=%d\n",i);puts("wa");}
		if(check(npp,yuan1)){
		//	npp.pt();
			if(Length3(npp-yuan1.p0)<1-eps)ret|=1;
			else ret|=2;
		}
		double angle=(i+0.0)/LIM*2*pi;
		scos=cos(angle),ssin=sin(angle);
		npp=rotate(pp,yuan2.n)+yuan2.p0;
	}
	return ret>=3;
}
int main(){
	Point3 o;
	Vec3 t1,t2;
	o.in();
	t1.in();t2.in();
	yuan1=Plane(o,o+t1,o+t2);
	o.in();
	t1.in();t2.in();
	yuan2=Plane(o,o+t1,o+t2);
	if(solve(t1))puts("YES");else puts("NO");
	return 0;
}

　　

I. Queries

整体二分，用扫描线求出某个区间内的点数即可。

对于排序可以预先在一开始排好序，然后每次递归分治的时候保证不破坏顺序即可。

时间复杂度$O((m+q)\log m)$。

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010,M=N<<1;
int n,m,i,x,y,a[N],e[N][3],cb,cc,qb[M],qc[M],ql[M],qr[M],ans[N];ll f[N],g[N];
struct E{int x,y,t;E(){}E(int _x,int _y,int _t){x=_x,y=_y,t=_t;}}b[M],c[M];
inline bool cmp(const E&a,const E&b){return a.x<b.x;}
inline int lower(int x){
  int l=1,r=n,mid,t;
  while(l<=r)if(a[mid=(l+r)>>1]<=x)l=(t=mid)+1;else r=mid-1;
  return t;
}
void solve(int l,int r,int bl,int br,int cl,int cr){
  if(bl>br||cl>cr)return;
  if(l==r){
    for(int i=cl;i<=cr;i++)ans[c[qc[i]].y]=a[l];
    return;
  }
  for(int i=cl;i<=cr;i++)g[c[qc[i]].y]=0;
  int mid=(l+r)>>1,c0=0,c1=0;ll s0=0,s1=0;
  for(int i=cl,j=bl;i<=cr;i++){
    for(;j<=br&&b[qb[j]].x<=c[qc[i]].x;j++){
      if(b[qb[j]].y>mid)continue;
      if(b[qb[j]].t>0)c0++,s0+=b[qb[j]].x;else c1++,s1+=b[qb[j]].x;
    }
    ll t=(1LL*(c[qc[i]].x+1)*c0-s0)-(1LL*(c[qc[i]].x+1)*c1-s1);
    if(c[qc[i]].t>0)g[c[qc[i]].y]+=t;else g[c[qc[i]].y]-=t;
  }
  int L=0,R=0;
  for(int i=bl;i<=br;i++)if(b[qb[i]].y<=mid)ql[L++]=qb[i];else qr[R++]=qb[i];
  for(int i=0;i<L;i++)qb[bl+i]=ql[i];
  for(int i=0;i<R;i++)qb[bl+L+i]=qr[i];
  int bm=bl+L-1;
  L=R=0;
  for(int i=cl;i<=cr;i++){
    int j=c[qc[i]].y;
    if(f[j]<=g[j])ql[L++]=qc[i];else qr[R++]=qc[i];
  }
  for(int i=cl;i<=cr;i++)if(c[qc[i]].t>0){
    int j=c[qc[i]].y;
    if(f[j]>g[j])f[j]-=g[j];
  }
  for(int i=0;i<L;i++)qc[cl+i]=ql[i];
  for(int i=0;i<R;i++)qc[cl+L+i]=qr[i];
  solve(l,mid,bl,bm,cl,cl+L-1),solve(mid+1,r,bm+1,br,cl+L,cr);
}
int main(){
  scanf("%d%d%d",&i,&n,&m);
  for(i=1;i<=n;i++){
    scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
    a[i]=e[i][2];
  }
  sort(a+1,a+n+1);
  for(i=1;i<=n;i++){
    e[i][2]=lower(e[i][2]);
    b[++cb]=E(e[i][0],e[i][2],1);
    b[++cb]=E(e[i][1]+1,e[i][2],-1);
  }
  for(i=1;i<=m;i++){
    scanf("%d%d%lld",&x,&y,&f[i]);
    c[++cc]=E(x-1,i,-1);
    c[++cc]=E(y,i,1);
  }
  sort(b+1,b+cb+1,cmp);
  sort(c+1,c+cc+1,cmp);
  for(i=1;i<=cb;i++)qb[i]=i;
  for(i=1;i<=cc;i++)qc[i]=i;
  solve(1,n,1,cb,1,cc);
  for(i=1;i<=m;i++)printf("%d\n",ans[i]);
  return 0;
}

　　

J. Restoring the Flows

设$x[i]$为第$i$条边的流量，对于每个节点根据流量平衡列出方程，那么一共有$m$个未知量，$n$个方程，答案就是这个矩阵的秩。

注意到任意时刻每个未知量只出现两次，并且系数一正一负，因此直接高斯消元的复杂度为$O(nm)$。

#include <bits/stdc++.h>
using namespace std ;

typedef long long LL ;
typedef pair < int , int > pii ;

#define clr( a , x ) memset ( a , x , sizeof a )
#define cpy( a , x ) memcpy ( a , x , sizeof a )

const int MAXN = 505 ;
const int MAXM = 3005 ;

int a[MAXN][MAXM] , n , m ;

int gauss ( int n , int m ) {
	int r = 1 , c = 1 ;
	for ( ; r <= n && c <= m ; ) {
		int tmp = r ;
		for ( int i = r ; i <= n ; ++ i ) {
			if ( a[i][c] ) tmp = i ;
		}
		if ( tmp == r ) {
			++ c ;
			continue ;
		}
		for ( int i = 1 ; i <= m ; ++ i ) {
			swap ( a[r][i] , a[tmp][i] ) ;
		}
		for ( int i = r + 1 ; i <= n ; ++ i ) if ( a[i][c] ) {
			for ( int j = c ; j <= m ; ++ j ) {
				a[i][j] += a[r][j] ;
			}
		}
		++ r ;
	}
	return m - r + 1 ;
}

void solve () {
	for ( int i = 1 ; i <= n ; ++ i ) {
		for ( int j = 1 ; j <= m ; ++ j ) {
			a[i][j] = 0 ;
		}
	}
	for ( int i = 1 ; i <= m ; ++ i ) {
		int u , v ;
		scanf ( "%d%d" , &u , &v ) ;
		a[u][i] = 1 ;
		a[v][i] = -1 ;
	}
	printf ( "%d\n" , gauss ( n , m ) ) ;
}

int main () {
	while ( ~scanf ( "%d%d" , &n , &m ) ) solve () ;
	return 0 ;
}