网站建设上机课,wordpress报价,电子商务网站设计的书,网页布局的原则problem
luogu-P4460
solution
题面以及数据告诉我们显然是状压 dpdpdp。
设 f(s,i):f(s,i):f(s,i): 经过的点集 sss 最后一次画的点为 iii 的方案数。
直接枚举下一个之前没被画的点 jjj 转移即可。 f(s∣2j,j)←f(s,i)f(s|2^j,j)\leftarrow f(s,i)f(s∣2j,j)←f(s,i)。 …problem
luogu-P4460
solution
题面以及数据告诉我们显然是状压 dpdpdp。
设 f(s,i):f(s,i):f(s,i): 经过的点集 sss 最后一次画的点为 iii 的方案数。
直接枚举下一个之前没被画的点 jjj 转移即可。
f(s∣2j,j)←f(s,i)f(s|2^j,j)\leftarrow f(s,i)f(s∣2j,j)←f(s,i)。
但这里需要保证 i,ji,ji,j 两点间若存在点必须这些点之前都被画过了。
我们预处理开个 bitset\text{bitset}bitset g(i,j):g(i,j):g(i,j): 与 i,ji,ji,j 贡献且在 i,ji,ji,j 线段上的点集。
共线判断我们常用的是斜率即 yk−yixk−xiyk−yjxk−xj\frac{y_k-y_i}{x_k-x_i}\frac{y_k-y_j}{x_k-x_j}xk−xiyk−yixk−xjyk−yj。
但计算机 /0/0/0 是会 RE\text{RE}RE 的所以我们尽量避免处罚交叉相乘判断相等即可。
共线只是一个条件必须是在 i,ji,ji,j 形成的线段上所以和 i,ji,ji,j 的横纵坐标判断一下即可。
最后的最后就是这道题可以不用完所有点。
条件只说了画的点数不小于 444 即可。
code
#include bits/stdc.h
using namespace std;
#define int long long
#define mod 100000007
#define maxn 20
bitset maxn g[maxn][maxn];
int n, ans;
int X[maxn], Y[maxn], f[1 maxn][maxn];bool check( int l, int r, int i ) {if( (X[i] - X[l]) * (Y[i] - Y[r]) ! (X[i] - X[r]) * (Y[i] - Y[l]) )return 0;if( (X[i] max(X[l], X[r]) or X[i] min(X[l], X[r])) and (Y[i] max(Y[l], Y[r]) or Y[i] min(Y[l], Y[r])) ) return 0;return 1;
}signed main() {scanf( %lld, n );for( int i 0;i n;i ) scanf( %lld %lld, X[i], Y[i] );if( n 4 ) return ! puts(0);for( int i 0;i n;i )for( int j 0;j n;j )for( int k 0;k n;k )if( i j or i k or j k ) continue;else if( check( i, j, k ) ) g[i][j][k] 1;for( int i 0;i n;i ) f[1 i][i] 1;for( int s 0;s (1 n);s ) {for( int i 0;i n;i )if( f[s][i] )for( int j 0;j n;j )if( s j 1 ) continue;else {for( int k g[i][j]._Find_first();k ! g[i][j].size();k g[i][j]._Find_next( k ) )if( ! (s k 1) ) goto pass;(f[s | (1 j)][j] f[s][i]) % mod;pass:;}}int ans 0;for( int s 0;s (1 n);s )if( __builtin_popcount( s ) 4 )for( int i 0;i n;i )(ans f[s][i]) % mod;printf( %lld\n, ans );return 0;
}
