求相似,用hash
多方向,得枚举
我们可以先找出所有星群,以及它们的群(按最小字典序保存)
用 hash 数组求其值(相似的),然后枚举,按出现顺序(用字典序)编号。
double get_dist(PII a, PII b)
{
double dx = a.x - b.x;
double dy = a.y - b.y;
return sqrt(dx * dx + dy * dy);
}
double get_hash()
{
double sum = 0;
for (int i = 0; i < top; i ++ )
for (int j = i + 1; j < top; j ++ )
sum += get_dist(q[i], q[j]); // hash 贡献值
return sum;
}
// 可用最小表示法替换
static :静态全局变量,清空数组用
字符 hash:前缀和思想,两参量为:
typedef unsigned long long ULL;
P = 131;
统计连通块:
dfs,参量:坐标,由上往下(递推式)记得判重。
bfs,参量:坐标,如上。
扩展——最小表示法:
双指针,解决循环同构问题
int get_min(char a[N], int n)
{
static char b[N * 2];
for(int i = 0; i < n; i ++) b[i] = b[i + n] = a[i]; // 拆链法
int i = 0, j = 1, k = 0;
while(i < n and j < n) // 枚举起点
{
for(k = 0; k < n and b[i + k] == b[j + k]; k ++); // 找不同
if(k == n) break; // 换一波起点
if(b[i + k] > b[j + k]) { // j 更优
i += k + 1; // i 后 p = [1,k] 位都不够优秀,因为j+p起在同构处之后,有更优字符
if(i == j) i ++; // 错位法
}
else {
j += k + 1;
if(i == j) j ++;
}
}
k = min(i, j); // i >= n ? j : i
for(int i = 0; i < n; i ++) a[i] = b[k + i];
a[i + n] = 0;
return k;
}
记得提高课的 flood fill 算法就是用 bfs 讲的。加油啊oi大佬hhh
bfs 可以吧,我想用 bfs 试试
可以啊
嗯嗯,多谢大佬