NEFU大一暑假集训-Hash（ABCDEH）

题集链接

OP

感谢学长的讲解与付出；
感谢ph和zsl两位大佬的指导与讨论；

这组题做得我脑袋疼hhh；

A Snowflake Snow Snowflakes

题目大意

按顺序给定 n 片雪花的每个枝的长度，判断是否有相同的雪花存在；
（相同指经旋转/对称后完全相同）

思路

标准做法是哈希表，对于哈希值与待测雪花相同的所有雪花进行暴力比对，哈希策略为 hash(x)=∑i=16xi+∏i=16xihash(x)=\sum_{i=1}^6x_i+\prod_{i=1}^6x_i；

我这边的做法是单哈希匹配，即对于一个雪花的所有可能起点和顺序共生成12个哈希值，一种情况中的哈希策略为 hash(x)=∑i=16xiPihash(x)=\sum_{i=1}^6x_iP^i

关于P的确定费了一些时间，同时需要注意的细节蛮多的：
比如说去重如果用map或set就会TLE，只能通过数组sort后手动去重；

代码

直接匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
//const ull M = 1000000000000037;
const ull P = 10000019;
ll mp[1200005];
map<ll,int>::iterator it;
int c=0;

inline int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x*f;
}
int main()
{
    int n;
    n=read();
    ll a[6];
    ull p[]={1,P,P*P,P*P*P,P*P*P*P,P*P*P*P*P};
    ll mapt[13];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<6;j++)
        {
            a[j]=read();
        }
        int cc=0;
        for(int j=0;j<6;j++)
        {
            ull tmp=0;
            for(int k=0;k<6;k++)
            {
                tmp+=a[(j+k)%6]*p[k];
            }
            tmp%=M;
            mapt[cc++]=(ll)tmp;
            tmp=0;
            for(int k=0;k<6;k++)
            {
                tmp+=a[(j-k+6)%6]*p[k];
            }
            tmp%=M;
            mapt[cc++]=(ll)tmp;
        }
        sort(mapt,mapt+cc);
        for(int j=0;j<cc;j++)
        {
            if(mapt[j]!=mapt[j+1]||j==cc-1)
            {
                mp[c++]=mapt[j];
            }
        }
    }
    sort(mp,mp+c);
    for(int i=0;i<c-1;i++)
    {
        //printf("%lld\n",mp[i]);
        if(mp[i]==mp[i+1])
        {
            printf("Twin snowflakes found.");
            return 0;
        }
    }
    printf("No two snowflakes are alike.");
    return 0;
}

标准做法，来自这里

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int P = 99991, MXN = 110000;
int n, cnt, nxt[MXN], head[MXN], snow[MXN][6];
int Hash(int *a)
{
    int sum = 0, mul = 1;
    for (int i = 0; i < 6; ++i)
    {
        sum = (sum + a[i]) % P;
        mul = (long long)mul * a[i] % P;
    }
    return (sum + mul) % P;
}

bool equ(int *a, int *b)
{
    for (int i = 0; i < 6; ++i)
    {
        for (int j = 0; j < 6; ++j)
        {
            bool flag = 1;
            for (int k = 0; k < 6; ++k)
            {
                if (a[(i + k) % 6] != b[(j + k) % 6])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
                return 1;
            flag = 1;
            for (int k = 0; k < 6; ++k)
            {
                if (a[(i + k) % 6] != b[(j - k + 6) % 6])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
                return 1;
        }
    }
    return 0;
}

bool inser(int *a)
{
    int val = Hash(a);
    for (int i = head[val]; i; i = nxt[i])
    {
        if (equ(a, snow[i]))
            return 1;
    }
    ++cnt;
    memcpy(snow[cnt], a, 6 * sizeof(int));
    nxt[cnt] = head[val];
    head[val] = cnt;
    return 0;
}

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        int t[6];
        for (int i = 0; i < 6; ++i)
        {
            scanf("%d", &t[i]);
        }
        if (inser(t))
        {
            printf("Twin snowflakes found.");
            return 0;
        }
    }
    printf("No two snowflakes are alike.");
    return 0;
}

B Palindrome

题目大意

对于给定的两个字符串，求最长回文子串；

思路

马拉车算法，具体可以在这里和这里了解；
（代码来自上链）

os：可能要开一个字符串算法的笔记了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int maxn = 1e6 + 5;
char s[maxn * 2], str[maxn * 2];
int Len[maxn * 2], len;
void getstr() {//重定义字符串
	int k = 0;
	str[k++] = '@';//开头加个特殊字符防止越界
	for (int i = 0; i < len; i++) {
		str[k++] = '#';
		str[k++] = s[i];
	}
	str[k++] = '#';
	len = k;
	str[k] = 0;//字符串尾设置为0，防止越界
}
int manacher() {
	int mx = 0, id;//mx为最右边，id为中心点
	int maxx = 0;
	for (int i = 1; i < len; i++) {
		if (mx > i) Len[i] = min(mx - i, Len[2 * id - i]);//判断当前点超没超过mx
		else Len[i] = 1;//超过了就让他等于1，之后再进行查找
		while (str[i + Len[i]] == str[i - Len[i]]) Len[i]++;//判断当前点是不是最长回文子串，不断的向右扩展
		if (Len[i] + i > mx) {//更新mx
			mx = Len[i] + i;
			id = i;//更新中间点
			maxx = max(maxx, Len[i]);//最长回文字串长度
		}
	}
	return (maxx - 1);
}
int main() {
    int i=1;
    while(~scanf("%s", s))
    {
        if(!strcmp(s,"END"))break;
	len = strlen(s);
	getstr();
	printf("Case %d: %d\n",i++,manacher());
    }
	return 0;
}

C Squares

题目大意

给定n个点，问其中能组成多少个正方形；

思路

对点哈希后匹配，便可在O(1)O(1) 复杂度内确定指定点的存在性；

使用了双哈希以免被卡；

同样，哈希策略中参数的确定也比较困难，然后此道题时间卡得也比较紧；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <stdio.h>
#include <iostream>
#include <map>
#include <algorithm>
#include <string.h>
using namespace std;
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
//const ull M = 1000000000000037;
const ll P = 10000019;
const ll Q = 9999971;
int mp1[10000027], mp2[10000027],h1[1003],h2[1003];
pair<int,int>p[1003];
ll hash1(pair<int,int> x)
{
    if(abs(x.first)>20000||abs(x.second)>20000)return 10000026;
    return ((ll)x.first*20001+x.second+400040007)%P;
}
ll hash2(pair<int,int> x)
{
    if(abs(x.first)>20000||abs(x.second)>20000)return 10000026;
    return ((ll)x.first*20001+x.second+400040007)%Q;
}
int main()
{
    int n;
    ll ans;
    //pair<int,int>tmp;
    while(~scanf("%d",&n))
    {
        if(!n)break;
        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].first,&p[i].second);
            h1[i]=hash1(p[i]);
            h2[i]=hash2(p[i]);
            mp1[h1[i]]++;
            mp2[h2[i]]++;
        }
        for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(i==j)continue;
            //printf("*");
            pair<int,int>a,b;
            a=make_pair(p[i].first+(p[i].second-p[j].second),p[i].second-(p[i].first-p[j].first));
            b=make_pair(p[j].first+(p[i].second-p[j].second),p[j].second-(p[i].first-p[j].first));
            if(mp1[hash1(a)]
             &&mp1[hash1(b)]
             &&mp2[hash2(a)]
             &&mp2[hash2(b)])
            ans++;//printf("%d %d\n",i,j);
            a=make_pair(p[i].first-(p[i].second-p[j].second),p[i].second+(p[i].first-p[j].first));
            b=make_pair(p[j].first-(p[i].second-p[j].second),p[j].second+(p[i].first-p[j].first));
            if(mp1[hash1(a)]
             &&mp1[hash1(b)]
             &&mp2[hash2(a)]
             &&mp2[hash2(b)])
            ans++;//printf("%d %d\n",i,j);
        }
        for(int i=1;i<=n;i++)
        {
            //scanf("%d%d",&p[i].first,&p[i].second);
            mp1[h1[i]]--;
            mp2[h2[i]]--;
        }
        //memset(mp1,0,sizeof mp1);
        //memset(mp2,0,sizeof mp2);
        printf("%lld\n",ans>>2);
    }
    return 0;
}

D 对称二叉树

题目大意

对于给定二叉树，判断其中最大的对称二叉树的节点数

思路

参考
首先统计出以每个节点为根的子树大小；

如果以某点为根的子树为对称二叉树，则满足以下条件：

  1. 该点两个子节点权值相同；
  2. 左子节点的左子节点与右子节点的右子节点权值相同，左子节点的右子节点与右子节点的左子节点权值相同；
  3. 两个权值需要相同的节点的异侧子节点权值也需要相同；

…以此递归；

对于其他方法，还可以通过中序遍历序列求最长回文串~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ull M = 19260817;
const ull P = 100000 - 3;
pair<int,pair<int,int> >po[1000006];
int sons[1000006];
int dfs(int x)
{
    if(x==-1)return 0;
    sons[x]=1;
    sons[x]+=dfs(po[x].second.first);
    sons[x]+=dfs(po[x].second.second);
    return sons[x];
}
bool judge(int x,int y)
{
    if(x==-1&&y==-1)return 1;
    if(x!=-1&&y!=-1&&po[x].first==po[y].first
        &&judge(po[x].second.first,po[y].second.second)
        &&judge(po[x].second.second,po[y].second.first))
    return 1;
    return 0;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&po[i].first);
    for(int i=1;i<=n;i++)scanf("%d%d",&po[i].second.first,&po[i].second.second);
    dfs(1);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(sons[i]<=ans)continue;
        //printf("*");
        if(judge(po[i].second.first,po[i].second.second))
        ans=sons[i];
    }
    cout<<ans;
    return 0;
}

E 企鹅QQ

题目大意

在给定字符串中，寻找至多有一个相同位置字符不同的字符串对数；

思路

由于总位数是给定的，我可以预处理后，将每一位分别扣去，对一个字符串生成其长度个哈希值，单字符串内所有哈希值去重后加入全体的集合（防止我重我自己）；

在处理完所有字符串后，再在全体集合进行查重，对于每一对重复，即答案应+1；

PS：map验重会被卡；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//const ull M = 18446744073709551615;
const ull P = 100000 - 3;
ull a[202];
//map<ull, int> mp[202];
ull vt[202][30004];
int c = 0;
ull qm(ull a, ull b)
{
    ull ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = ans * a;
        a = a * a;
    }
    return ans;
}
void ghash(string g)
{
    ull p = 1;
    for (int i = 0; g[i]; p *= P, i++)
    {
        a[i + 1] = a[i] + g[i] * p;
    }
}
int main()
{
    int n, l, t;
    ull ans = 0;
    cin >> n >> l >> t;
    for (int i = 1; i <= l; i++)vt[i][0]=1;
    string g;
    for (int i = 1; i <= n; i++)
    {
        cin >> g;
        ghash(g);
        for (int j = 1; j <= l; j++)
        {
            ull tmp = a[l] - a[j] + a[j - 1] * P;
            //ans+=mp[j][tmp];
            //mp[j][tmp]++;
            vt[j][vt[j][0]++] = tmp;
        }
    }
    for (int i = 1; i <= l; i++)
        sort(vt[i] + 1, vt[i] + vt[i][0]);
    for (int j = 1; j <= l; j++)
    {
        int le = -1;
        for (int i = 0; i <= vt[j][0]; i++)
        {
            if ( vt[j][i + 1] != vt[j][i])
            {
                int tmp = i - le;
                ans += tmp * (tmp - 1) / 2;
                le = i;
            }
        }
        ////
    }
    /*for(int i=1;i<=l;i++)
    for (auto it = mp[i].begin(); it != mp[i].end(); it++)
    {
        int tmp = (it)->second;
        if(tmp>1)ans += tmp * (tmp - 1) / 2;
    }*/
    cout << ans;
    return 0;
}

H Ones

题目大意

对于给定的 n （ n 满足 2∤n , 5∤n2\not|n\text{ },\text{ }5\not|n），输出最小 x 满足 kn=(10x−1)/9kn=(10^x-1)/9 ；

思路

直接计算是不可能的，枚举 x 即可；

直至满足 (10x−1)%(9n)=0(10^x-1)\%(9n)=0 ；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
typedef long long ll;
ll n;
ll qm(ll a,ll b)
{
    ll ans=1;
    for(;b;b>>=1)
    {
        if(b&1)ans=ans*a%n;
        a=a*a%n;
    }
    return ans;
}
int main() {
    while(~scanf("%lld",&n))
    {
        if(n==0){printf("0\n");continue;}
        n*=9ll;
        for(ll i=1;1;i++)
        {
            //printf("*%lld\n",qm(10ll,i));
            if((qm(10ll,i)-1+n)%n==0)
            {
                printf("%lld\n",i);
                break;
            }
        }
    }
    return 0;
}

ED

\

算法竞赛 > 比赛与题集
NEFU大一暑假集训-Hash（ABCDEH）
https://tanyuu.github.io/2021.07-12/NEFU大一暑假集训-Hash（ABCDEH）/
作者
F Juny
发布于
2021年7月28日
许可协议