怎样解析网站域名,卖鞋推广引流方法,为公司建设网站的意义,网页设计公司注册文章目录[JSOI2008]星球大战In Touch方格染色Junk-Mail Filter[NOIP2010 提高组] 关押罪犯Silver WoodsMust Be Rectangular![JSOI2008]星球大战
source
非常套路的#xff0c;正着打击星球#xff0c;逆着就是添加星球以及关系#xff0c;并查集维护此时连通块个数
就是…
文章目录[JSOI2008]星球大战In Touch方格染色Junk-Mail Filter[NOIP2010 提高组] 关押罪犯Silver WoodsMust Be Rectangular![JSOI2008]星球大战
source
非常套路的正着打击星球逆着就是添加星球以及关系并查集维护此时连通块个数
就是这个星球被打击前的答案
#include cstdio
#include vector
#include iostream
using namespace std;
#define maxn 400005
vector int h[maxn];
pair int, int p[maxn];
int n, m, k, ans;
int f[maxn], g[maxn], ret[maxn];
bool used[maxn], vis[maxn];void makeset() {for( int i 0;i n;i ) f[i] i;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v );if( u ^ v ) ans --, f[v] u;
}int main() {scanf( %d %d, n, m );for( int i 1;i m;i ) {scanf( %d %d, p[i].first, p[i].second );h[p[i].first].push_back( i );h[p[i].second].push_back( i );}scanf( %d, k );makeset();for( int i 1;i k;i )scanf( %d, g[i] ), used[g[i]] 1;ans n - k;for( int i 1;i m;i )if( ! used[p[i].first] and ! used[p[i].second] )merge( p[i].first, p[i].second );for( int i k;i;i -- ) {ret[i] ans;ans ;used[g[i]] 0;for( auto t : h[g[i]] )if( vis[t] ) continue;else if( used[p[t].first] or used[p[t].second] )continue;else merge( p[t].first, p[t].second );}printf( %d\n, ans );for( int i 1;i k;i )printf( %d\n, ret[i] );return 0;
}In Touch
source
转化成最短路问题套用dijkstra\rm dijkstradijkstra每个点都只访问一次但是范围那么大用并查集帮助跳过已访问点直指新点
#include iostream
#include cstdio
#include queue
using namespace std;
#define Pair pair int, int
#define int long long
#define maxn 200005
#define inf 1e15
priority_queue Pair, vector Pair , greater Pair q;
int T, n;
int dis[maxn], f[maxn], L[maxn], R[maxn], c[maxn];
int MS[2] { -1, 1 };int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}signed main() {scanf( %lld, T );while( T -- ) {scanf( %lld, n );for( int i 1;i n;i ) scanf( %lld, L[i] );for( int i 1;i n;i ) scanf( %lld, R[i] );for( int i 1;i n;i ) scanf( %lld, c[i] );for( int i 0;i n 1;i ) f[i] i, dis[i] inf;q.push( make_pair( dis[1] c[1], 1 ) );while( ! q.empty() ) {int now q.top().second; q.pop();for( int k 0;k 2;k ) {int l now L[now] * MS[k];int r now R[now] * MS[k];if( l r ) swap( l, r );l min( l, n 1 );l max( l, 1ll );if( l r ) continue;for( int nxt l;;nxt ) {nxt find( nxt );if( nxt 0 || nxt n || nxt r ) break;if( dis[nxt] dis[now] c[nxt] ) {dis[nxt] dis[now] c[nxt];q.push( make_pair( dis[nxt], nxt ) );}f[find( nxt )] find( nxt 1 );}}}printf( 0 );for( int i 2;i n;i )if( dis[i] inf ) printf( -1 );else printf( %lld, dis[i] - c[i] );printf( \n );}return 0;
}方格染色
source
observation1: 只要确定了第一行和第一列整张表格就被确定了
observation2: g1,1⨁gi,1⨁g1,j⨁gi,j[imod20andjmod20]g_{1,1}\bigoplus g_{i,1}\bigoplus g_{1,j}\bigoplus g_{i,j}[i\ \rm mod\ 20\ and\ j\ mod\ 20]g1,1⨁gi,1⨁g1,j⨁gi,j[i mod 20 and j mod 20]
可以通过枚举g1,1g_{1,1}g1,1的状态通过已知的gi,jg_{i,j}gi,j来判断gi,1,g1,jg_{i,1},g_{1,j}gi,1,g1,j的关系
这样形成了若干组有且仅有两个选项的约束关系带权并查集维护
连通块内有一个取值定了其他的取值也定了
如果有解答案就是2^(连通块数量-1)减1是g1,1g_{1,1}g1,1的状态因为是枚举的算已知的
#include cstdio
#define int long long
#define mod 1000000000
#define maxn 2000005
int n, m, k;
bool flag0, flag1;
int x[maxn], y[maxn], c[maxn], f[maxn], w[maxn];int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}int find( int x ) {if( x f[x] ) return x;else {int fa f[x];f[x] find( f[x] );w[x] ( w[x] w[fa] ) % 2;return f[x];}
}int solve() {for( int i 1;i n m;i ) f[i] i, w[i] 0;f[n 1] 1;for( int i 1;i k;i ) {if( x[i] 1 y[i] 1 ) continue;int u find( x[i] ), v find( y[i] n );int t w[x[i]] ^ w[y[i] n] ^ c[i] ^ ( x[i] 1 or y[i] 1 ) ^ 1;if( u v and t ) return 0;f[v] u, w[v] t;} int cnt 0;for( int i 1;i n m;i )if( find( i ) i ) cnt ;return qkpow( 2, cnt - 1 );
}signed main() {scanf( %lld %lld %lld, n, m, k );for( int i 1;i k;i ) {scanf( %lld %lld %lld, x[i], y[i], c[i] );if( x[i] 1 y[i] 1 )if( ! c[i] ) flag0 1;else flag1 1;else;}int ans0 solve();//c[g[1][1]]0 bluefor( int i 1;i k;i ) c[i] ^ 1;//c[g[1][1]]1 redint ans1 solve();if( flag0 ) ans1 0;if( flag1 ) ans0 0;printf( %lld\n, ( ans0 ans1 ) % mod );return 0;
}Junk-Mail Filter
source
可删除并查集模板
只需要注意一下被删除前的集合若只有一个元素被删除后集合也就不存在了
#include cstdio
#include iostream
using namespace std;
#define maxn 2200000
int n, m, ans, cnt;
int f[maxn], siz[maxn];void makeset() {cnt n;for( int i 0;i n;i )f[i] f[i n] cnt , siz[i n] 1;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v );if( siz[u] siz[v] ) swap( u, v );if( u ^ v )siz[u] siz[v], f[v] u, ans --;
}void Delete( int x ) {int fx find( x );siz[fx] --;if( ! siz[fx] ) ans --;f[x] f[cnt] cnt;siz[cnt] 1;cnt ;ans ;
}int main() {int T 0;while( scanf( %d %d, n, m ) ) {if( ! n and ! m ) return 0;makeset();ans n;char opt[5]; int x, y;for( int i 1;i m;i ) {scanf( %s, opt );if( opt[0] M ) {scanf( %d %d, x, y );merge( x, y );}else {scanf( %d, x );Delete( x );}}printf( Case #%d: %d\n, T, ans );}return 0;
}[NOIP2010 提高组] 关押罪犯
source
贪心先把冲突最大的安排可以选择拆点i,ini,ini,in两个人不同合并(i,jn)/(in,j)(i,jn)/(in,j)(i,jn)/(in,j)
也可以选择带权并查集在%2\% 2%2意义下做
#include cstdio
#include algorithm
using namespace std;
#define maxn 100005
struct node {int u, v, w;node(){}node( int U, int V, int W ) {u U, v V, w W;}
}r[maxn];
int n, m;
int f[maxn];void makeset() {for( int i 1;i ( n 1 );i ) f[i] i;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v ), f[v] u;
}int main() {scanf( %d %d, n, m );for( int i 1, u, v, w;i m;i ) {scanf( %d %d %d, u, v, w );r[i] node( u, v, w );}makeset();sort( r 1, r m 1, []( node x, node y ) { return x.w y.w; } );for( int i 1;i m;i ) {int u r[i].u, v r[i].v;if( find( u ) find( v ) )return ! printf( %d\n, r[i].w );elsemerge( u, v n ), merge( v, u n );}printf( 0\n );return 0;
}Silver Woods
source
跟一道奶酪题相似奶酪是空心球老鼠从底到顶这道题是从左到右
二分半径然后将圆卡不过的连接起来
具体而言就是点点之间距离小于直径点和上下界面距离小于直径合并起来
并查集判断上界面和下界面是否相通不通证明有一种方法圆可以通过
#include cstdio
#include cmath
#define eps 1e-6
#define maxn 105
int n;
double x[maxn], y[maxn];
int f[maxn];void makeset() {for( int i 0;i n 1;i ) f[i] i;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v ), f[v] u;
}double dis( int i, int j ) {return sqrt( ( x[i] - x[j] ) * ( x[i] - x[j] ) ( y[i] - y[j] ) * ( y[i] - y[j] ) );
}bool check( double r ) {double d r * 2;makeset();for( int i 1;i n;i ) {if( y[i] d 100 )merge( 0, i );if( y[i] - d -100 )merge( n 1, i );for( int j i 1;j n;j )if( dis( i, j ) d )merge( i, j );}if( find( 0 ) find( n 1 ) ) return 0;else return 1;
}int main() {scanf( %d, n );for( int i 1;i n;i )scanf( %lf %lf, x[i], y[i] );double l 0, r 100, ans;while( r - l eps ) {double mid ( l r ) / 2;if( check( mid ) ) ans mid, l mid;else r mid;}printf( %.6f\n, ans );return 0;
}Must Be Rectangular!
source 对于每个坐标(xi,yi)(xi,yi)(xi,yi)xixixi向yinyinyin连边形成一个二分图
然后后续添加点实际上就是对这个二分图的每个分量补成完全二分图
并查集维护一下二分图的边的个数两个部的点的个数
#include cstdio
#define maxn 100000
int n;
int f[maxn 2], row[maxn 2], col[maxn 2];void makeset() {for( int i 1;i ( maxn 1 );i )f[i] i;
}int find( int x ) {return x f[x] ? x : f[x] find( f[x] );
}void merge( int u, int v ) {u find( u ), v find( v ), f[v] u;
}int main() {scanf( %d, n );makeset();for( int i 1, x, y;i n;i ) {scanf( %d %d, x, y );merge( x, y maxn );}long long ans 0;for( int i 1;i maxn;i ) row[find( i )] ;for( int i 1;i maxn;i ) col[find( i maxn )] ;for( int i 1;i maxn;i ) ans 1ll * row[i] * col[i];printf( %lld\n, ans - n );return 0;
}{ u find( u ), v find( v ), f[v] u; }
int main() { scanf( “%d”, n ); makeset(); for( int i 1, x, y;i n;i ) { scanf( “%d %d”, x, y ); merge( x, y maxn ); } long long ans 0; for( int i 1;i maxn;i ) row[find( i )] ; for( int i 1;i maxn;i ) col[find( i maxn )] ; for( int i 1;i maxn;i ) ans 1ll * row[i] * col[i]; printf( “%lld\n”, ans - n ); return 0; }
