首页 › 题库 › 信息学奥赛 › 6.2 字符串哈希

信息学奥赛-提高级 题库

共 51 道题 ,第 1 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 6.2 字符串哈希 清除
1 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

在一个大小为13的哈希表中,使用闭散列法的线性探查来解决冲突,哈希函数为H(key)=key mod 13,依次插入关键字18、26、35、9、68、74,插入74后,它最终被放置在哪个索引位置? 

A
5
B
7
C
9
D
11
答案与解析
正确答案:D

哈希冲突指key1≠key2但H(key1)=H(key2),计算各关键字哈希值及插入位置:  

18 mod 13=5,插入下标5;  

26 mod 13=0,插入下标0;  

35 mod 13=9,插入下标9;  

9 mod 13=9(冲突),插入下标10;  

68 mod 13=3,插入下标3;  

74 mod 13=9(冲突,9、10均被占),插入下标11。

题目详情
2 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

给定地址区间为 0~9 的哈希表,哈希函数为 h(x) = x % 10,采用线性探查的冲突解决策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地址 0重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请问 89 存储在哈希表哪个地址中。( )

A
9
B
0
C
1
D
2
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
3 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

现有一个地址区间为 0~10 的哈希表,对于出现冲突情况,会往后找第一个空的地址存储(到 10 冲突了就从 0 开始往后),现在要依次存储(0,1, 2,3,4,5,6,7),哈希函数为 h(x)=x2 mod 11。请问 7 存储在哈希表哪个地址中( )。

A
5
B
6
C
7
D
8
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
4 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

将(2, 7, 10, 18)分别存储到某个地址区间为如0~10的哈希表中,如果 哈希函数h(x)=(),将不会产生冲突,其中a mod b表示a除以b的 余数。

A
x^2 mod 11
B
2x mod 11
C
x mod 11
D
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
5 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

将(2,6,10,17)分别存储到某个地址区间为0~10 的哈希表中,如果哈希函数 h(x)=( ),将不会产生冲突,其中 a mod b 表示 a 除以 b 的余数。

A

x mod 11

B

x2mod 11

C

2x mod 11

D
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
6 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

将(2, 7, 10, 18)分别存储到某个地址区间为如0~10的哈希表中,如果 哈希函数h(x)=(),将不会产生冲突,其中a mod b表示a除以b的 余数。

A
x^2 mod 11
B
2x mod 11
C
x mod 11
D
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
7 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

给定地址区间为 0~9 的哈希表,哈希函数为 h(x) = x % 10,采用线性探查的冲突解决策略(对于出现冲突情况,会往后探查第一个空的地址存储;若地址 9 冲突了则从地址 0重新开始探查)。哈希表初始为空表,依次存储(71, 23, 73, 99, 44, 79, 89)后,请问 89 存储在哈希表哪个地址中。( )

A
9
B
0
C
1
D
2
答案与解析
正确答案:D
这道题暂未补解析。
题目详情
8 单选题 适中 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

现有一个地址区间为 0~10 的哈希表,对于出现冲突情况,会往后找第一个空的地址存储(到 10 冲突了就从 0 开始往后),现在要依次存储(0,1, 2,3,4,5,6,7),哈希函数为 h(x)=x2 mod 11。请问 7 存储在哈希表哪个地址中( )。

A
5
B
6
C
7
D
8
答案与解析
正确答案:C
这道题暂未补解析。
题目详情
9 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

阅读程序

#include <iostream>
using namespace std;

const int N = 1000;
int c[N];

int logic(int x, int y) {
    return (x & y) ^ ((x ^ y) | (~x & y));
}

void generate(int a, int b, int *c) {
    for (int i = 0; i < b; i++) {
        c[i] = logic(a, i) % (b + 1);
    }
}

void recursion(int depth, int *arr, int size) {
    if (depth <= 0 || size <= 1) return;
    int pivot = arr[0];
    int i = 0, j = size - 1;
    while (i <= j) {
        while (arr[i] < pivot) i++;
        while (arr[j] > pivot) j--;
        if (i <= j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++; j--;
        }
    }
    recursion(depth - 1, arr, j + 1);
    recursion(depth - 1, arr + i, size - i);
}

int main() {
    int a, b, d;
    cin >> a >> b >> d;
    generate(a, b, c);
    recursion(d, c, b);
    for (int i = 0; i < b; i++) cout << c[i] << " ";
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
10 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <string>
using namespace std;

const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];

int solve() {
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {
            int k = (j << 1) | (s[i] - '0');
            if (j != 0 || s[i] == '1')
                dp[k] = (dp[k] + dp[j]) % P;
        }
    }
    int ans = 0;
    for (int i = 0; i < (1 << m); i++) {
        ans = (ans + 1ll * i * dp[i]) % P;
    }
    return ans;
}

int solve2() {
    int ans = 0;
    for (int i = 0; i < (1 << n); i++) {
        int cnt = 0;
        int num = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                num = num * 2 + (s[j] - '0');
                cnt++;
            }
        }
        if (cnt <= m) (ans += num) %= P;
    }
    return ans;
}

int main() {
    cin >> n >> m;
    cin >> s;
    if (n <= 20) {
        cout << solve2() << endl;
    }
    cout << solve() << endl;
    return 0;
}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
11 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;

typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];

struct H {
    int h1, h2, l;
    H(bool b = false) {
        h1 = b + K1;
        h2 = b + K2;
        l = 1;
    }
    H operator + (const H &h)const {
        H hh;
        hh.l = l + h.l;
        hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
        hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
        return hh;
    }
    bool operator == (const H &h)const {
        return l == h.l && h1 == h.h1 && h2 == h.h2;
    }
    bool operator < (const H &h)const {
        if (l != h.l) return l < h.l;
        else if (h1 != h.h1) return h1 < h.h1;
        else return h2 < h.h2;
    }
} h[maxn];

void init() {
    memset(p, 1, sizeof(p));
    p[0] = p[1] = false;
    p1[0] = p2[0] = 1;
    for (int i = 1; i <= n; i++) {
        p1[i] = (1ll * B1 * p1[i - 1]) % P1;
        p2[i] = (1ll * B2 * p2[i - 1]) % P2;
        if (!p[i]) continue;
        for (int j = 2 * i; j <= n; j += i) {
            p[j] = false;
        }
    }
}

int solve() {
    for (int i = n; i; i--) {
        h[i] = H(p[i]);
        if (2 * i + 1 <= n) {
            h[i] = h[2 * i] + h[i] + h[2 * i + 1];
        } 
        else if (2 * i <= n) {
            h[i] = h[2 * i] + h[i];
        }
    }
    cout << h[1].h1 << endl;
    sort(h + 1, h + n + 1);
    int m = unique(h + 1, h + n + 1) - (h + 1);
    return m;
}

int main() {
    cin >> n;
    init();
    cout << solve() << endl;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
12 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

合并序列。有两个长度为N的单调不降序列A和B,序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和,求其中第k小的和。上述参数满足N≤105和1≤K≤N2。

#include <iostream>
using namespace std;

const int maxn = 100005;

int n;
long long k;
int a[maxn], b[maxn];

int *upper_bound(int *a, int *an, int ai) {
    int l = 0, r = ( ① );
    while (l < r) {
        int mid = (l + r) >> 1;
        if (②) {
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    return ( ③ );
}

long long get_rank(int sum) {
    long long rank = 0;
    for (int i = 0; i < n; i++) {
        rank += upper_bound(b, b + n, sum - a[i]) - b;
    }
    return rank;
}

int solve() {
    int l = 0, r =( ④ );
    while (l < r) {
        int mid = ((long long)l + r) >> 1;
        if  ( ⑤ ) {
            l = mid + 1;
        }
        else {
            r = mid;
        }
    }
    return l;
}

int main() {
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    cout << solve() << endl;
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
13 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希

次短路。已知有一个n个点m条边的有向图G,并且给定图中的两个点s和t,求次短路(长度严格大于最短路的最短路径)。如果不存在,输出一行“-1”。如果存在,输出两行,第一行表示此段路经的长度,第二行表示此段路的一个方案。

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;

const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279;

int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn << 1], *dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];

void add(int a, int b, int c) {
    ++tot;
    nxt[tot] = head[a];
    to[tot] = b;
    w[tot] = c;
    head[a] = tot;
}

bool upd(int a, int b, int d, priority_queue<pair<int, int> > &q) {
    if (d >= dis[b])return false;
    if (b < n)  ( ① );
    q.push( ② );
    dis[b] = d;
    pre[b] = a;
    return true;
}

void solve() {
    priority_queue<pair<int, int> >q;
    q.push(make_pair(0, s));
    memset(dis,  ( ③ ), sizeof(dis));
    memset(pre, -1, sizeof(pre));
    dis2 = dis + n;
    pre2 = pre + n;
    dis[s] = 0;

    while (!q.empty()) {
        int aa = q.top().second;q.pop();
        if (vis[aa])continue;
        vis[aa] = true;
        int a = aa % n;
        for (int e = head[a]; e; e = nxt[e]) {
            int b = to[e], c = w[e];
            if (aa < n) {
                if (!upd(a, b, dis[a] + c, q))
                   ( ④ );
            }
            else {
                upd(n + a, n + b, dis2[a] + c, q);
            }
        }
    }
}

void out(int a) {
    if (a != s) {
        if (a < n)
            out(pre[a]);
        else
            out( ⑤ );
    }
    printf("%d%c", a % n + 1, " \n"[a == n + t]);
}

int main() {
    scanf("%d%d%d%d", &n, &m,&s,&t);
    s--, t--;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a - 1, b - 1, c);
    }
    solve();
    if (dis2[t] == inf)
        puts("-1");
    else {
        printf("%d\n", dis2[t]);
        out(n + t);
    }
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
14 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
#include <string> 
#include <vector> 
 
using namespace std; 

int f(const string &s, const string &t) 
{ 
    int n = s.length(), m = t.length(); 

    vector<int> shift(128, m + 1);

    int i, j;
 
    for (j = 0; j < m; j++) 
        shift[t[j]] = m - j; 

    for (i = 0; i <= n - m; i += shift[s[i + m]]) {
        j = 0; 
        while (j < m && s[i + j] == t[j]) j++; 
        if (j == m) return i;
    }
  
    return -1; 
} 
 
int main() 
{ 
    string a, b;
    cin >> a >> b;
    cout << f(a, b) << endl;
    return 0;
}

假设输入字符串由 ASCII 可见字符组成,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
15 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 

using namespace std; 

const int MAXN = 105; 

int n, m, k, val[MAXN]; 
int temp[MAXN], cnt[MAXN]; 

void init() 
{ 
    cin >> n >> k;
    for (int i = 0; i < n; i++) cin >> val[i]; 
    int maximum = val[0];
    for (int i = 1; i < n; i++) 
        if (val[i] > maximum) maximum = val[i];
    m = 1;
    while (maximum >= k) { 
        maximum /= k;
        m++;
    }
} 

void solve() 
{ 
    int base = 1;
    for (int i = 0; i < m; i++) { 
        for (int j = 0; j < k; j++) cnt[j] = 0; 
        for (int j = 0; j < n; j++) cnt[val[j] / base % k]++; 30         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1]; 
        for (int j = n - 1; j >= 0; j--) { 
            temp[cnt[val[j] / base % k] - 1] = val[j]; 
            cnt[val[j] / base % k]--; 
        }
        for (int j = 0; j < n; j++) val[j] = temp[j]; 
        base *= k;
    }
} 

int main() 
{ 
    init();
    solve();
    for (int i = 0; i < n; i++) cout << val[i] << ' '; 
    cout << endl;
    return 0;
}

假设输入的 n 为不大于 100 的正整数,k 为不小于 2 且不大于 100 的正整数,val[i]在int 表示范围内,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
16 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
#include <algorithm> 

using namespace std; 

const int MAXL = 1000; 

int n, k, ans[MAXL]; 

int main(void) 
{ 
    cin >> n >> k;
    if (!n) cout << 0 << endl; 
    else
    {
        int m = 0;
        while (n)
        {
            ans[m++] = (n % (-k) + k) % k; 20             n = (ans[m - 1] - n) / k; 
        }
        for (int i = m - 1; i >= 0; i--) 
            cout << char(ans[i] >= 10 ?
                ans[i] + 'A' - 10 : 
                ans[i] + '0');
        cout << endl;
    }
    return 0;
}


假设输入的 n 在 int 范围内,k 为不小于 2 且不大于 36 的正整数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
17 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <cstdio>
int main() {
	int x;
	scanf("%d", &x);
	int res = 0;
	for (int i = 0; i < x; ++i) {
		if (i * i % x == 1) {
			++res;
		}
	}
	printf("%d", res);
	return 0;
}

输入:15

输出:_________

答案与解析
参考答案

4

题目详情
18 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <cstdio>
int n, d[100];
bool v[100];
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%d", d + i);
		v[i] = false;
	}
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		if (!v[i]) {
			for (int j = i; !v[j]; j = d[j]) {
				v[j] = true;
			}
			++cnt;
		}
	}
	printf("%d\n", cnt);
	return 0;
}

输入:10 7 1 4 3 2 5 9 8 0 6

输出:_________

答案与解析
参考答案

6

题目详情
19 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;
string s;
long long magic(int l, int r) {
	long long ans = 0;
	for (int i = l; i <= r; ++i) {
		ans = ans * 4 + s[i] - 'a' + 1;
	}
	return ans;
}
int main() {
	cin >> s;
	int len = s.length();
	int ans = 0;
	for (int l1 = 0; l1 < len; ++l1) {
		for (int r1 = l1; r1 < len; ++r1) {
			bool bo = true;
			for (int l2 = 0; l2 < len; ++l2) {
				for (int r2 = l2; r2 < len; ++r2) {
					if (magic(l1, r1) == magic(l2, r2) && (l1 != l2 || r1 != r2)) {
						bo = false;
					}
				}
			}
			if (bo) {
				ans += 1;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

输入:abacaba

输出:_________

答案与解析
参考答案

16

题目详情
20 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <cstdio>
using namespace std;
const int N = 110;
bool isUse[N];
int n, t;
int a[N], b[N];
bool isSmall() {
	for (int i = 1; i <= n; ++i)
		if (a[i] != b[i]) return a[i] < b[i];
	return false;
}
bool getPermutation(int pos) {
	if (pos > n) {
		return isSmall();
	}
	for (int i = 1; i <= n; ++i) {
		if (!isUse[i]) {
			b[pos] = i; isUse[i] = true;
			if (getPermutation(pos + 1)) {
				return true;
			}
			isUse[i] = false;
		}
	}
	return false;
}
void getNext() {
	for (int i = 1; i <= n; ++i) {
		isUse[i] = false;
	}
	getPermutation(1);
	for (int i = 1; i <= n; ++i) {
		a[i] = b[i];
	}
}
int main() {
	scanf("%d%d", &n, &t);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= t; ++i) {
		getNext();
	}
	for (int i = 1; i <= n; ++i) {
		printf("%d", a[i]);
		if (i == n) putchar('\n'); else putchar(' ');
	}
	return 0;
}

输入 1:6 10 1 6 4 5 3 2

输出 1:_________(3 分)

输入 2:6 200 1 5 3 4 2 6

输出 2:_________(5 分)

答案与解析
参考答案

输出1:2 1 3 5 6 4

输出2:3 2 5 6 1 4

题目详情