首页 > 代码库 > XIII Open Cup named after E.V. Pankratiev. GP of Asia and South Caucasus
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 ;}
XIII Open Cup named after E.V. Pankratiev. GP of Asia and South Caucasus
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。