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 ;
}