2016-2017 ACM-ICPC Southwestern European Regional Programming Contest (SWERC 201
A. Within Arm's Reach留坑。
B. Bribing Eve
枚举经过$1$号点的所有直线，统计直线右侧的点数，旋转卡壳即可。
时间复杂度$O(n\log n)$。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2000010;
const double eps=1e-7;
int _,n,i,x,y,at_center,X,Y,j,m,inarea,online,ansmin,ansmax;
struct P{
int x,y,z;
double o;
P(){}
P(int _x,int _y,int _z){
x=_x,y=_y;
z=_z;
o=atan2(y,x);
}
}a,b;
int s;
inline bool cmp(const P&a,const P&b){return a.o<b.o;}
inline int cross(const P&a,const P&b){
return a.x*b.y-a.y*b.x;
}
int main(){
scanf("%d",&_);
scanf("%d%d",&X,&Y);
_--;
while(_--){
scanf("%d%d",&x,&y);
if(x==X&&y==Y){at_center++;continue;}
a[++n]=P(x-X,y-Y,1);
a[++n]=P(X-x,Y-y,0);
}
if(!n){
printf("%d %d",1,at_center+1);
return 0;
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i=j){
int sum=0;
for(j=i;j<=n&&a.x*a.y==a.x*a.y&&fabs(a.o-a.o)<eps;j++)sum+=a.z;
b[++m]=P(a.x,a.y,sum);
}
for(i=1;i<=m;i++)b=b;
for(i=1;i<=m+m;i++)s=s+b.z;
ansmin=N;
ansmax=0;
for(i=j=1;i<=m;i++){
if(j<i)j=i;
while(j+1<i+m&&cross(b,b)>=0)j++;
//printf("%d %d %d\n",b.x,b.y,b.z);
if(b.x<0||b.y>0)continue;
inarea=s-s;
online=b.z;
if(i<j&&cross(b,b)==0)online+=b.z;
inarea-=online;
online+=at_center;
//printf("%d %d %d %d %d %d\n",inarea,online,b.x,b.y,b.x,b.y);
ansmin=min(ansmin,inarea+1);
ansmax=max(ansmax,inarea+online+1);
}
printf("%d %d",ansmin,ansmax);
}
C. Candle Box
模拟。
#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=2e9;
int d,n,m;
int ans;
int cal1(int x){
if(x<4)return 0;
return (1+x)*x/2-6;
}
int cal2(int x){
if(x<3)return 0;
return (1+x)*x/2-3;
}
bool check(int x,int y){
if(x<0||y<0)return 0;
int ned1=cal1(x),ned2=cal2(y);
if(ned1>n)return 0;
if(n+m==ned1+ned2){
ans=min(ans,n-ned1);
}
return 1;
/*
for(int i=0;i<=t2;i++){
if(t1+i==n&&t2-i==m){
ans=min(ans,i);
}
}
*/
/*
for(int i=0;i<=t2-1;i++){
if(t1+i==n&&t2-1-i==m){
ans=min(ans,i);
}
}
for(int i=0;i<=t2+1;i++){
if(t1+i==n&&t2+1-i==m){
ans=min(ans,i);
}
}
*/
return 0;
}
int main(){
while(scanf("%d%d%d",&d,&n,&m)!=EOF){
bool flag=1;
ans=Inf;
for(int i=d;i<=1020;i++){
check(i,i-d);
}
if(ans==Inf)while(1);
printf("%d\n",ans);
}
return 0;
}
D. Dinner Bet
$f$表示有$i$个仅属于第一个人的数字被选中，$j$个仅属于第二个人的数字被选中，$k$个属于两个人的数字被选中的期望次数。
#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;
int n,d,ned;
int idx;
int cnt;
double dp;
LL C;
double dfs(int a0,int a1,int a2){
double &t=dp;
if(t>-0.5)return t;
if(a0+a2>=ned||a1+a2>=ned)return t=0;
double tmp=1;
double nedp;
for(int ad0=0;ad0+a0<=cnt;ad0++)
for(int ad1=0;ad1+a1<=cnt;ad1++)
for(int ad2=0;ad2+a2<=cnt;ad2++){
if(ad0+ad1+ad2>d)continue;
double p=(
C-a0)-(cnt-a1)-(cnt-a2)]*
C[(cnt-a0)]*
C[(cnt-a1)]*
C[(cnt-a2)]+0.0)/C;
if(!ad0&&!ad1&&!ad2)nedp=p;
else{
dfs(a0+ad0,a1+ad1,a2+ad2);
tmp+=p*dp;
}
}
t=tmp/(1-nedp);
//printf("a0=%d a1=%d a2=%d dp=%.2f ned=%d\n",a0,a1,a2,t,ned);
return t;
}
int main(){
for(int i=0;i<=50;i++)C=1;
for(int i=1;i<=50;i++){
for(int j=1;j<=i;j++)C=C+C;
}
while(scanf("%d%d%d",&n,&d,&ned)!=EOF){
memset(idx,0,sizeof idx);
memset(cnt,0,sizeof cnt);
for(int i=0;i<2;i++){
for(int j=0;j<ned;j++){
int x;scanf("%d",&x);
idx|=1<<i;
}
}
for(int i=1;i<=n;i++)if(idx)cnt-1]++;
memset(dp,-1,sizeof dp);
dfs(0,0,0);
printf("%.12f\n",dp);
}
return 0;
}
E. Passwords
建立AC自动机，$f$表示串长为$i$，目前走到了$j$这个点，小写字母/大写字母/数字是否出现的方案数。
#include<cstdio>
#include<cstring>
const int N=1010,P=1000003;
int A,B,tot,son,fail,q,ban,ans,i,j,x,y,z,t,o;
int n;char s;
int f;//lower upper digit
inline void up(int&x,int y){
x+=y;
if(x>=P)x-=P;
}
void insert(){
scanf("%s",s);
for(int l=strlen(s),x=0,i=0,w;i<l;i++){
if(!son-'a'])son=++tot;x=son;
if(i==l-1)ban=1;
}
}
void make(){
int h=1,t=0,i,j,x;fail=-1;
for(i=0;i<26;i++)if(son)q[++t]=son;
while(h<=t)for(x=q,i=0;i<26;i++)
if(son){
ban]|=ban]=son]];
q[++t]=son;
}else son=son];
}
int main(){
scanf("%d%d%d",&A,&B,&n);
while(n--)insert();
make();
f=1;
for(i=0;i<B;i++)for(j=0;j<=tot;j++)for(x=0;x<2;x++)for(y=0;y<2;y++)for(z=0;z<2;z++){
if(!f)continue;
for(t=0;t<26;t++){
o=son;
if(ban)continue;
up(f,f);//lower
up(f,f);//upper
}
for(t=0;t<10;t++){
o=0;
if(t==0)o=son['o'-'a'];
if(t==1)o=son['i'-'a'];
if(t==3)o=son['e'-'a'];
if(t==5)o=son['s'-'a'];
if(t==7)o=son['t'-'a'];
if(ban)continue;
up(f,f);//digit
}
}
for(i=A;i<=B;i++)for(j=0;j<=tot;j++)up(ans,f);
printf("%d",ans);
}
F. Performance Review
按权值排序之后树状数组维护dfs序即可。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100010;
int n,i,x,a,b,q,g,nxt,root,j,st,en,dfn;
int flag;
ll bit,ans;
inline bool cmp(int x,int y){return a<a;}
inline void add(int x,int y){flag=1;nxt=g;g=y;}
void dfs(int x){
st=++dfn;
for(int i=g;i;i=nxt)dfs(i);
en=dfn;
}
inline void modify(int x,int p){for(;x<=n;x+=x&-x)bit+=p;}
inline ll ask(int x){ll t=0;for(;x;x-=x&-x)t+=bit;return t;}
int main(){
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d%d",&x,&a,&b);
if(x>0)add(x,i);else root=i;
}
for(i=1;i<=n;i++)if(!flag)dfs(i);
for(i=1;i<=n;i++)q=i;
sort(q+1,q+n+1,cmp);
for(i=1;i<=n;i=j){
for(j=i;j<=n&&a]==a];j++)ans]=ask(en])-ask(st]-1);
for(j=i;j<=n&&a]==a];j++)modify(st],b]);
}
for(i=1;i<=n;i++)printf("%I64d\n",ans);
}
G. Cairo Corridor
找出与四个边界都连通的连通块，然后枚举连通块里每个点，如果它不是割点，且去掉它之后剩余部分依旧与四个边界都连通，则无解。
#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 )
const int MAXN = 300005 ;
const int mod = 13 ;
const int INF = 0x3f3f3f3f ;
struct Node {
int x , y , v ;
Node () {}
Node ( int x , int y , int v ) : x ( x ) , y ( y ) , v ( v ) {}
} ;
vector < int > G , now ;
int dfn , low , dfs_clock ;
int cut ;
int vis ;
int S , top ;
int a , b ;
int idx , cnt ;
Node is ;
int num ;//l r u d
int p ;
int n , m ;
void tarjan ( int u , int pre ) {
int v ;
low = dfn = ++ dfs_clock ;
S = u ;
int son = 0 , pre_cnt = 0 ;
for ( int i = 0 ; i < G.size () ; ++ i ) {
v = G ;
if ( v == pre && pre_cnt == 0 ) {
pre_cnt ++ ;
continue ;
}
if ( !dfn ) {
++ son ;
tarjan ( v , u ) ;
if ( low > low ) low = low ;
if ( u != pre && low >= dfn ) cut = 1 ;
} else low = min ( low , dfn ) ;
}
if ( u == pre && son > 1 ) cut = 1 ;
-- top ;
}
int F ( int x ) {
return p == x ? x : ( p = F ( p ) ) ;
}
void add ( int x , int y ) {
if ( is.v ) {
if ( b.x].y] ) return ;
} else {
if ( a.x].y] ) return ;
}
if ( is.v ) {
if ( b.x].y] ) return ;
} else {
if ( a.x].y] ) return ;
}
p = F ( y ) ;
G.push_back ( y ) ;
}
void dfs ( int u , int f ) {
vis = 1 ;
now.push_back ( u ) ;
for ( int i = 0 ; i < G.size () ; ++ i ) {
int v = G ;
if ( v == f ) continue ;
if ( vis ) continue ;
dfs ( v , u ) ;
}
}
int addval ( int x , int y , int v , int f ) {
if ( ( x + y ) % 2 == 0 ) {
if ( v == 0 && y == 1 ) num += f ;
if ( v == 1 && y == m ) num += f ;
if ( x == 1 ) num += f ;
if ( x == n ) num += f ;
} else {
if ( y == 1 ) num += f ;
if ( y == m ) num += f ;
if ( v == 0 && x == 1 ) num += f ;
if ( v == 1 && x == n ) num += f ;
}
}
int can_del ( int o ) {
int x = is.x , y = is.y , v = is.v , ok = 1 ;
addval ( x , y , v , -1 ) ;
if ( !num || !num || !num || !num ) ok = 0 ;
addval ( x , y , v , 1 ) ;
return ok ;
}
void solve () {
cnt = 0 ;
scanf ( "%d%d" , &n , &m ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= m ; ++ j ) {
scanf ( "%1d%1d" , &a , &b ) ;
idx = ++ cnt ;
is = Node ( i , j , 0 ) ;
idx = ++ cnt ;
is = Node ( i , j , 1 ) ;
}
}
for ( int i = 1 ; i <= cnt ; ++ i ) {
G.clear () ;
}
for ( int i = 1 ; i <= cnt ; ++ i ) {
p = i ;
}
for ( int i =1 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= m ; ++ j ) {
add ( idx , idx ) ;
add ( idx , idx ) ;
if ( ( i + j ) % 2 == 0 ) {
if ( i < n ) add ( idx , idx ) ;
if ( i > 1 ) add ( idx , idx ) ;
if ( j > 1 ) add ( idx , idx ) ;
if ( j > 1 ) add ( idx , idx ) ;
if ( i < n ) add ( idx , idx ) ;
if ( i > 1 ) add ( idx , idx ) ;
if ( j < m ) add ( idx , idx ) ;
if ( j < m ) add ( idx , idx ) ;
} else {
if ( j < m ) add ( idx , idx ) ;
if ( j > 1 ) add ( idx , idx ) ;
if ( i > 1 ) add ( idx , idx ) ;
if ( i > 1 ) add ( idx , idx ) ;
if ( j < m ) add ( idx , idx ) ;
if ( j > 1 ) add ( idx , idx ) ;
if ( i < n ) add ( idx , idx ) ;
if ( i < n ) add ( idx , idx ) ;
}
}
}
clr ( dfn , 0 ) ;
clr ( low , 0 ) ;
clr ( cut , 0 ) ;
top = dfs_clock = 0 ;
for ( int i = 1 ; i <= cnt ; ++ i ) if ( !dfn ) {
tarjan ( i , i ) ;
}
int ans = -1 ;
clr ( vis , 0 ) ;
for ( int i = 1 ; i <= cnt ; ++ i ) if ( F ( i ) == i ) {
if ( is.v ) {
if ( b.x].y] ) continue ;
} else {
if ( a.x].y] ) continue ;
}
now.clear () ;
clr ( num , 0 ) ;
dfs ( i , i ) ;
for ( int j = 0 ; j < now.size () ; ++ j ) {
int x = is].x , y = is].y , v = is].v ;
addval ( x , y , v , 1 ) ;
}
if ( !num || !num || !num || !num ) continue ;
int ok = 1 ;
for ( int j = 0 ; j < now.size () ; ++ j ) {
if ( !cut] ) {
if ( can_del ( now ) ) {
ok = 0 ;
//break ;
}
}
}
if ( ok ) ans = max ( ans , ( int ) now.size () ) ;
}
if ( ans == -1 ) printf ( "NO MINIMAL CORRIDOR\n" ) ;
else printf ( "%d\n" , ans ) ;
}
int main () {
int T = 0 ;
scanf ( "%d" , &T ) ;
for ( int i = 1 ; i <= T ; ++ i ) {
//printf ( "Case #%d:\n" , i ) ;
solve () ;
}
if ( T ) return 0 ;
//while ( ~scanf ( "%d%d%d%d" , &n , &s , &t , &m ) ) solve () ;
return 0 ;
}
H. Pascal's Hyper-Pyramids
等价于找$D$个非负整数$x_1,x_2,...,x_D$，且和为$H-1$，答案为$\frac{(H-1)!}{x_1!x_2!...x_D!}$。
考虑爆搜，加上$x_i\leq x_{i+1}$以及可行性剪枝即可，计算答案可以分解质因数。
#include<cstdio>
#include<set>
using namespace std;
typedef unsigned long long ll;
const int N=35;
int n,m,i,j;
int p,v,tot;
int f,g,q;
ll po;
set<ll>T;
void divide(int n){
int t=n;
for(int i=0;i<tot;i++)while(t%p==0)f++,t/=p;
}
void cal(){
for(int i=0;i<tot;i++)g=f;
for(int i=0;i<n;i++)for(int j=0;j<tot;j++)g-=f];
ll ret=1;
for(int i=0;i<tot;i++)ret*=po];
T.insert(ret);
}
void dfs(int x,int y,int z){//now consider x,0<=x<=y,sum=z
if((n-x)*y+z<m)return;
if(x==n){
if(z==m){
cal();
}
return;
}
for(int i=0;i<=y;i++){
if(z+i>m)return;
q=i;
dfs(x+1,i,z+i);
}
}
int main(){
for(i=2;i<N;i++)if(!v){
p=i;
for(j=i+i;j<N;j+=i)v=1;
}
for(i=2;i<N;i++){
divide(i);
for(j=0;j<tot;j++)f+=f;
}
for(i=0;i<tot;i++)for(po=j=1;j<N;j++)po=po*p;
scanf("%d%d",&n,&m);
m--;
dfs(0,m,0);
for(set<ll>::iterator o=T.begin();o!=T.end();o++)printf("%I64u\n",*o);
}
I. The White Rabbit Pocket Watch
在模$13$意义下高斯消元求出每条边的长度，然后floyd即可。
#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 )
const int MAXN = 1005 ;
const int mod = 13 ;
const int INF = 0x3f3f3f3f ;
int pm ( int x , int n ) {
int res = 1 ;
while ( n ) {
if ( n & 1 ) res = res * x % mod ;
x = x * x % mod ;
n >>= 1 ;
}
return res ;
}
int inv ;
int val ;
vector < int > G ;
pii path ;
int d ;
int a ;
int ans ;
int cnt ;
int n , s , t , m ;
void gauss ( int n , int m ) {
int r = 0 , c = 0 ;
for ( ; r < n && c < m ; ++ c ) {
int tmpr = r ;
for ( int i = r ; i < n ; ++ i ) {
if ( a ) tmpr = i ;
}
if ( !a ) continue ;
for ( int i = c ; i <= m ; ++ i ) {
swap ( a , a ) ;
}
for ( int i = m ; i >= c ; -- i ) {
a = a * inv] % mod ;
}
for ( int i = 0 ; i < n ; ++ i ) if ( i != r && a ) {
for ( int j = m ; j >= c ; -- j ) {
a = ( a - a * a % mod + mod ) % mod ;
}
}
++ r ;
}
}
void solve () {
cnt = 0 ;
clr ( d , -1 ) ;
clr ( a , 0 ) ;
for ( int i = 0 ; i < MAXN ; ++ i ) {
G.clear () ;
}
for ( int i = 0 ; i < m ; ++ i ) {
scanf ( "%d" , &val ) ;
int x , u , v ;
scanf ( "%d" , &x ) ;
for ( int j = 0 ; j < x ; ++ j ) {
scanf ( "%d" , &v ) ;
if ( j ) {
if ( d == -1 ) {
d = d = cnt ++ ;
path = pii ( u , v ) ;
}
G.push_back ( d ) ;
}
u = v ;
}
}
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < G.size () ; ++ j ) {
a] ++ ;
a] %= mod ;
}
a = val ;
}
gauss ( m , cnt ) ;
/*
for ( int i = 0 ; i < m ; ++ i ) {
for ( int j = 0 ; j < cnt ; ++ j ) {
printf ( "%d " , a ) ;
}
printf ( "|%d\n" , a ) ;
}
*/
clr ( d , INF ) ;
for ( int i = 1 ; i <= cnt ; ++ i ) {
int u = path.first , v = path.second , c = a ;
d = d = c ;
}
for(int i=1;i<=n;i++)d=0;
for ( int k = 1 ; k <= n ; ++ k ) {
for ( int i = 1 ; i <= n ; ++ i ) {
for ( int j = 1 ; j <= n ; ++ j ) {
d = min ( d , d + d ) ;
}
}
}
printf ( "%d\n" , d ) ;
}
int main () {
for ( int i = 1 ; i < mod ; ++ i ) {
inv = pm ( i , mod - 2 ) ;
}
int T = 0 ;
//scanf ( "%d" , &T ) ;
for ( int i = 1 ; i <= T ; ++ i ) {
//printf ( "Case #%d:\n" , i ) ;
solve () ;
}
if ( T ) return 0 ;
while ( ~scanf ( "%d%d%d%d" , &n , &s , &t , &m ) ) solve () ;
return 0 ;
}
J. Risky Lottery
留坑。
K. Balls and Needles
并查集判环。
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int>P;
typedef pair<int,P>PI;
const int N=150000;
int m,i,e;
int x,y,f,n;
map<PI,int>A;
map<P,int>B;
map<int,int>v;
int F(int x){return f==x?x:f=F(f);}
inline int getid0(int x,int y,int z){
PI t(x,P(y,z));
if(A)return A;
return A=++n;
}
inline int getid1(int x,int y){
P t(x,y);
if(B)return B;
return B=++n;
}
bool check0(){
n=0;
for(i=0;i<N;i++)f=i;
for(i=1;i<=m;i++){
x=getid0(e,e,e);
y=getid0(e,e,e);
if(F(x)==F(y))return 1;
f]=f;
}
return 0;
}
bool check1(){
n=0;
for(i=0;i<N;i++)f=i;
for(i=1;i<=m;i++){
x=getid1(e,e);
y=getid1(e,e);
//printf("%d %d\n",x,y);
if(x==y)continue;
if(v)continue;
v=1;
v=1;
if(F(x)==F(y))return 1;
f]=f;
}
return 0;
}
int main(){
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d%d%d",&e,&e,&e);
scanf("%d%d%d",&e,&e,&e);
}
if(!check0())puts("No true closed chains");else puts("True closed chains");
if(!check1())puts("No floor closed chains");else puts("Floor closed chains");
}
页:
[1]