今天的t2t3能打出来80分的暴力都好满足啊QwQ。(%%%$idy$
今天的签到题，做的时候一眼就看出性质叻qwq。大于11的所有数分解合数都可以用4、6、9表示，乱搞搞就可以了。
#include<iostream>
#include<cstdio>
using namespace std;void read ( int &x ) {
x = ; char ch = getchar ( );
while ( ch > '' || ch < '' ) ch = getchar ( );
while ( ch >= '' && ch <= '' ) {
x = x * + ch - ''; ch = getchar ( );
}
}int main ( ) {
freopen ( "split.in", "r", stdin );
freopen ( "split.out", "w", stdout );
int T;
scanf ( "%d", &T );
while ( T -- ) {
int n;
read ( n );
int t = n / , qwq = n % ;
if ( t < ) {
printf ( "-1\n" );
} else if ( t % == && qwq == ) {
printf ( "%d\n", t / );
} else if ( t % == && qwq ) {
if ( n == ) {
printf ( "-1\n" );
} else if ( t <= ) {
printf ( "1\n" );
} else printf ( "%d\n", t / - );
} else if ( t % && qwq == ) {
printf ( "%d\n", t / );
} else if ( t % && qwq ) {
if ( n < ) {
printf ( "-1\n" );
} else {
printf ( "%d\n", ( t - ) / + );
}
}
}
return ;
}
$yuli$（%%%a掉的一道神题！（至今不理解dalao的思维方式QwQ
好不容易搞懂了$idy$的解释！是一种很巧妙的理解方法。我们把所有的点的横纵坐标之间连边，构成了下图所示的多个连通图：
实际上图中的每条边就相当于每个点了，每条边可以选择管辖一个点，就是原问题中的一条直线。我们把所有有关系的点建成如上图所示（区分一下x和y坐标），可以发现，不在同一个联通块之间的点（原图中的直线）就永远不会互相影响。所以我们只用计算每个联通块的方案数，用乘法原理即可。
每个联通块又分为两种情况，第一种是如上图的树形结构。【一下的边和点都指建出的新图中的边和点】即边数小于点数，最大的覆盖只能是边数。如下图：
最少都会不能覆盖到一个点。又因为每条边我们可以选择管辖点或者不管辖，所以设点数是$size$，$size-1$的所有子集都可以达到。此时方案数为$2^{size-1}$。
另一种情况，就是样例二中多个点相互重叠影响，如下图：
我们可以发现，只要出现了这种情况，整个点集都可以被覆盖，如下图：
而所有方案的子集也都能达到，所以此时的方案数是$2^{size}$。
有了以上的理解，我们就可以愉快地建图计算辣~维护一个并查集的$size$，表示当前联通块的点数，建边过后跑$dfs$，标记联通块中的点并判断是否有环。答案累乘即可。【注意】原图中点的坐标需要离散化。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;const int mod = 1e9 + ;int n;ll mpow ( ll a, ll b ) {
ll ans = ;
for ( ; b; b >>= , a = a * a % mod )
if ( b & ) ans = ans * a % mod;
return ans;
}int stot, nex[], tov[], h[];
void add ( int u, int v ) {
tov[++stot] = v;
nex[stot] = h[u];
h[u] = stot;
}struct node {
int x, y;
} poi[];bool vis[], flag;
void dfs ( int u, int f ) {
vis[u] = ;
for ( int i = h[u]; i; i = nex[i] ) {
int v = tov[i];
if ( v == f ) continue;
if ( vis[v] ) { flag = ; continue; }
dfs ( v, u );
}
}int fa[], siz[];
int find ( int x ) {
if ( fa[x] != x ) return fa[x] = find ( fa[x] );
return x;
}void unionn ( int x, int y ) {
int xx = find ( x ); int yy = find ( y );
fa[xx] = yy;
siz[yy] += siz[xx];
}ll x[], y[];
int main ( ) {
freopen ( "cross.in", "r", stdin );
freopen ( "cross.out", "w", stdout );
scanf ( "%d", &n );
for ( int i = ; i <= n; i ++ ) {
scanf ( "%I64d%I64d", &x[i], &y[i] );
poi[i].x = x[i]; poi[i].y = y[i];
}
sort ( x + , x + + n );
sort ( y + , y + + n );
int m = unique ( x + , x + + n ) - x - ;
int k = unique ( y + , y + + n ) - y - ;
for ( int i = ; i <= n; i ++ ) {
poi[i].x = lower_bound ( x + , x + + m, poi[i].x ) - x;
poi[i].y = lower_bound ( y + , y + + k, poi[i].y ) - y + n;
}
for ( int i = ; i <= n; i ++ ) {
int xx = poi[i].x, yy = poi[i].y;
fa[xx] = xx; fa[yy] = yy; siz[xx] = siz[yy] = ;
}
for ( int i = ; i <= n; i ++ ) {
int xx = poi[i].x, yy = poi[i].y;
add ( xx, yy );
add ( yy, xx );
if ( find ( xx ) != find ( yy ) )
unionn ( xx, yy );
}
ll ans = ;
for ( int i = ; i <= n; i ++ ) {
int xx = poi[i].x;
if ( !vis[xx] ) {
flag = ;
dfs ( xx, );
int size = siz[find ( xx )];
if ( flag ) {
ans = ans * mpow ( , (ll)size ) % mod;
} else {
ans = ans * ( mpow ( , (ll)size ) - ) % mod;
}
}
}
printf ( "%I64d", ans );
return ;
}
看了标程惊觉$string$这个容器真是强无敌啊QwQ！比开$char$数组多了很多很方便的操作！
然后回想起考场上自己乱搞搞的哈希和暴力合并，其实感觉思路没错，就是模拟合并的操作，但是没有发现两个串合并起来，只需要判断第一个串的尾和第二个串的头$k$个字符有没有贡献就可以了！整个串又丑又长塞不下aaaQwQ
至于上面的$k$，我们可以发现，因为每个原始串中最多有$100-k+1$个长度为$k$的子串，原始最多有$100*(100-k+1)$个长度为k的子串，而每次合并两个串，最多只会增加$k$个长度为$k$的子串，最多增加$100*k$个，所以自始至终最多只会有$100*(100-k+1)+100*k$个长度为$k$的子串。而总子串数是$<=2^k$的，解出来$k<=13$（实际上11完全够了qwq。$k$非常小，我们可以把所有长度$1-11$的01串全部处理出来存在一个$stat$字符串组里面。
每次合并串的时候，我们只需要长度22就够了，所以截取前后即可。
定义$bool$数组$dp[i][j]$表示第$i$个串中是否存在我们预处理出来的第$j$个$stat$串，更新就是用$string$中的取子串操作$substr$取出两个组合的子串判断即可，如果是前$n$个串初始串暴力判断即可。
处理完$dp$数组后，直接所有串扫一遍，只要有一个长度为$p$的子串不存在，$p$就一定不是最后的解。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;const int L = ;int n, m, opt;
string str[];
string stat[];
int son[][], dp[][];void init ( ) {
for ( int l = ; l <= L; l ++ ) {
for ( int i = ; i < ( << l ); i ++ ) {
++opt;
string &s = stat[opt];
s.resize ( l );
for ( int j = ; j < l; j ++ )
s[j] = ( char ) ( '' + ( ( i >> j ) & ) );
}
}
}string merge ( string a, string b ) {
string c;
for( int i = ; i < a.size ( ); i ++ )
c.push_back( a[i] );
for( int i = ; i < b.size ( ); i ++ )
c.push_back( b[i] );
if ( c.length ( ) > * L ) {
string cc;
for ( int i = ; i < L; i ++ )
cc.push_back ( c[i] );
for ( int i = ; i < L; i ++ )
cc.push_back ( c[c.length ( )-L+i] );
return cc;
} else return c;
}int main ( ) {
freopen ( "string.in", "r", stdin );
freopen ( "string.out", "w", stdout );
ios :: sync_with_stdio ( );
init ( );
cin >> n;
for ( int i = ; i <= n; i ++ )
cin >> str[i];
cin >> m;
for ( int i = ; i <= m; i ++ ) {
int a, b;
cin >> a >> b;
str[i+n] = merge ( str[a], str[b] );
son[i+n][] = a;
son[i+n][] = b;
}
for ( int i = ; i <= n + m; i ++ ) {
if ( i <= n ) {
for ( int j = ; j <= opt; j ++ )
for ( int k = ; k + stat[j].size ( ) <= str[i].size ( ); k ++ )
if ( str[i].substr ( k, stat[j].size ( ) ) == stat[j] ) {
dp[i][j] = ; break;
}
} else {
int a = son[i][];
int b = son[i][];
for ( int j = ; j <= opt; j ++ ) {
dp[i][j] = ( dp[a][j] || dp[b][j] );
if ( dp[i][j] ) continue;
for ( int l = ; l < stat[j].size ( ); l ++ ) {
if ( l > str[a].length ( ) || stat[j].length ( ) - l > str[b].length ( ) ) continue;
if ( str[a].substr ( str[a].length ( ) - l, l ) + str[b].substr ( , stat[j].length ( ) - l ) == stat[j] ) {
dp[i][j] = ; break;
}
}
}
}
}
for ( int i = n + ; i <= n + m; i ++ ) {
bool ok[L+];
memset ( ok, , sizeof ( ok ) );
for ( int j = ; j <= opt; j ++ ) {
if ( !dp[i][j] ) {
ok[stat[j].length ( )] = ;
}
}
for ( int k = L; k >= ; k -- )
if ( ok[k] ) {
printf ( "%d\n", k );
break;
}
}
return ;
}
