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

信息学奥赛-提高级 题库

共 51 道题 ,第 2 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 6.2 字符串哈希 清除
21 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

int g(int m, int n, int x) {
	int ans = 0;
	int i;
	if (n == 1)
		return 1;
	for (i = x; i <= m / n; i++)
		ans += g(m - i, n - 1, i);
	return ans;
}
int main() {
	int t, m, n;
	cin >> m >> n;
	cout << g(m, n, 0) << endl;
	return 0;
}

输入:8 4

输出:_________

答案与解析
参考答案

15

题目详情
22 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

int main() {
	int n, i, j, x, y, nx, ny;
	int a[40][40];
	for (i = 0; i < 40; i++)
		for (j = 0; j < 40; j++)
			a[i][j] = 0;
	cin >> n;
	y = 0; x = n - 1;
	n = 2 * n - 1;
	for (i = 1; i <= n * n; i++) {
		a[y][x] = i;
		ny = (y - 1 + n) % n;
		nx = (x + 1) % n;
		if ((y == 0 && x == n - 1) || a[ny][nx] != 0)
			y = y + 1;
		else { y = ny; x = nx; }
	}
	for (j = 0; j < n; j++)
		cout << a[0][j] << " ";
	cout << endl;
	return 0;
}

输入:3

输出:_________

答案与解析
参考答案

17 24 1 8 15

题目详情
23 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

int n, s, a[100005], t[100005], i;
void mergesort(int l, int r) {
	if (l == r)
		return;
	int mid = (l + r) / 2;
	int p = l;
	int i = l;
	int j = mid + 1;
	mergesort(l, mid);
	mergesort(mid + 1, r);
	while (i <= mid && j <= r) {
		if (a[j] < a[i]) {
			s += mid - i + 1;
			t[p] = a[j];
			p++;
			j++;
		}
		else {
			t[p] = a[i];
			p++;
			i++;
		}
	}
	while (i <= mid) {
		t[p] = a[i];
		p++;
		i++;
	}
	while (j <= r) {
		t[p] = a[j];
		p++;
		j++;
	}
	for (i = l; i <= r; i++)
		a[i] = t[i];
}
int main() {
	cin >> n;
	for (i = 1; i <= n; i++)
		cin >> a[i];
	mergesort(1, n);
	cout << s << endl;
	return 0;
}

输入:

6

2 6 3 4 5 1

输出:_________

答案与解析
参考答案

8

题目详情
24 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int x = 1;
	int y = 1;
	int dx = 1;
	int dy = 1;
	int cnt = 0;
	while (cnt != 2) {
		cnt = 0;
		x = x + dx;
		y = y + dy;
		if (x == 1 || x == n) {
			++cnt;
			dx = -dx;
		}
		if (y == 1 || y == m) {
			++cnt;
			dy = -dy;
		}
	}
	cout << x << " " << y << endl;
	return 0;
}

输入1:4 3

输出1:_________(2 分)

输入2:2017 1014

输出 2:_________(3 分)

输入3:987 321

输出3:_________(3 分)

答案与解析
参考答案

输出1:1 3

输出2:2017 1

输出3:1 321

题目详情
25 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;

int main() 
{
	int a[6] = {1, 2, 3, 4, 5, 6}; 
	int pi = 0;
	int pj = 5; 
	int t , i;
	while (pi < pj) {
		t = a[pi]; 
		a[pi] = a[pj]; 
		a[pj] = t; 
		pi++;
		pj--;
	}
	for (i = 0; i < 6; i++) 
	cout << a[i] << ",";
	cout << endl; 
	return 0;
}

输出:                       

答案与解析
参考答案

6,5,4,3,2,1,

题目详情
26 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;
int main() 
{
	char a[100][100], b[100][100]; 
	string c[100];
	string tmp;
	int n, i = 0, j = 0, k = 0, total_len[100], length[100][3];
		cin >> n; 
		getline(cin, tmp);
		for (i = 0; i < n; i++) { 
			getline(cin, c[i]);
			total_len[i] = c[i].size();
		}
		for (i = 0; i < n; i++) {
			j = 0;
			while (c[i][j] != ':') { 
				a[i][k] = c[i][j];
				k = k + 1; 
				j++;
			}
			length[i][1] = k - 1; 
			a[i][k] = 0;
			k = 0;
			for (j = j + 1; j < total_len[i]; j++) { 
				b[i][k] = c[i][j];
				k = k + 1;
			}
			length[i][2] = k - 1; 
			b[i][k] = 0;
			k = 0;
		}
		for (i = 0; i < n; i++) {
			if (length[i][1] >= length[i][2]) 
				cout << "NO,";
			else {
				k = 0;
				for (j = 0; j < length[i][2]; j++) { 
					if (a[i][k] == b[i][j])
						k = k + 1;
					if (k > length[i][1]) 
						break;
				}
				if (j == length[i][2]) 
					cout << "NO,";
				else
					cout << "YES,";
			}
	}
	cout << endl;
	return 0;
}

输入:

3 

AB:ACDEbFBkBD 

AR:ACDBrT

SARS:Severe Atypical Respiratory Syndrome 

输出:                                  

(注:输入各行前后均无空格)

答案与解析
参考答案

YES,NO,YES,

题目详情
27 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream> 
using namespace std;
int lps(string seq, int i, int j) { 
	int len1, len2;
	if (i == j) 
		return 1;
	if (i > j) 
		return 0;
	if (seq[i] == seq[j])
		return lps(seq, i + 1, j - 1) + 2; 
	len1 = lps(seq, i, j - 1);
	len2 = lps(seq, i + 1, j); 
	if (len1 > len2)
		return len1; 
	return len2;
}
int main() 
{
	string seq = "acmerandacm"; 
	int n = seq.size();
	cout << lps(seq, 0, n - 1) << endl; 
	return 0;
}

输出:          

答案与解析
参考答案

5

题目详情
28 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
#include <cstring> 
using namespace std;
int map[100][100];
int sum[100], weight[100]; 
int visit[100];
int n;
void dfs(int node) { 
	visit[node] = 1; 
	sum[node] = 1; 
	int v, maxw = 0;
	for (v = 1; v <= n; v++) {
		if (!map[node][v] || visit[v]) 
			continue;
		dfs(v);
		sum[node] += sum[v]; 
		if (sum[v] > maxw) 
			maxw = sum[v];
	}
	if (n - sum[node] > maxw) 
		maxw = n - sum[node];
	weight[node] = maxw;
}
int main() 
{
	memset(map, 0, sizeof(map)); 
	memset(sum, 0, sizeof(sum)); 
	memset(weight, 0, sizeof(weight)); 
	memset(visit, 0, sizeof(visit)); 
	cin >> n;
	int i, x, y;
	for (i = 1; i < n; i++) { 
		cin >> x >> y; 
		map[x][y] = 1; 
		map[y][x] = 1;
	}
	dfs(1);
	int ans = n, ansN = 0; 
	for (i = 1; i <= n; i++)
		if (weight[i] < ans) { 
			ans = weight[i]; 
			ansN = i;
		}
	cout << ansN << " " << ans << endl; 
	return 0;
}

输入:

1 1

1 2

1 3

2 4

2 5

2 6

3 7

7 8

7 11

6 9

9 10

输出:

                

答案与解析
参考答案

2 5

题目详情
29 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;
struct point {
	int x;
	int y;
};
int main() {
	struct EX{
		int a;
		int b;
		point c;
	} e;
	e.a = 1;
	e.b = 2;
	e.c.x = e.a + e.b;
	e.c.y = e.a * e.b;
	cout << e.c.x << ',' << e.c.y << endl;
	 return 0;
}

输出:_________

答案与解析
参考答案

3,2

题目详情
30 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

void fun(char *a, char *b) {
	a = b;
	(*a)++;
}
int main() {
	char c1, c2, *p1, *p2;
	c1 = 'A';
	c2 = 'a';
	p1 = &c1;
	p2 = &c2;
	fun(p1, p2);
	cout << c1 << c2 << endl;
	return 0;
}

输出:_________

答案与解析
参考答案

Ab

题目详情
31 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <string>
using namespace std;
int main() {
	int len, maxlen;
	string s, ss;
	maxlen = 0;
	do {
		cin >> ss;
		len = ss.length();
		if (ss[0] == '#')
			break;
		if (len > maxlen) {
			s = ss;
			maxlen = len;
		}
	} while (true);
	cout << s << endl;
	return 0;
}

输入:

I

am

a

citizen

of

China

#

输出:_________

答案与解析
参考答案

citizen

题目详情
32 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;
int fun(int n, int fromPos, int toPos) {
	int t, tot;
	if (n == 0)
		return 0;
	for (t = 1; t <= 3; t++)
		if (t != fromPos && t != toPos)
			break;
	tot = 0;
	tot += fun(n - 1, fromPos, t);
	tot++;
	tot += fun(n - 1, t, toPos);
	return tot;
}

int main() {
	int n;
	cin >> n;
	cout << fun(n, 1, 3) << endl;
	return 0;
}

输入:5

输出:_________

答案与解析
参考答案

31

题目详情
33 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

int main() {
	int a, b, i, tot, c1, c2;
	cin >> a >> b;
	tot = 0;
	for (i = a; i <= b; i++)
	{
		c1 = i / 10;
		c2 = i % 10;
		if ((c1 + c2) % 3 == 0)
			tot++;
	}
	cout << tot << endl;
	return 0;
}

输入:7 31

输出:_________

答案与解析
参考答案

8

题目详情
34 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

int fun(int n, int minNum, int maxNum) {
	int tot, i;
	if (n == 0)
		return 1;
	tot = 0;
	for (i = minNum; i <= maxNum; i++)
		tot += fun(n - 1, i + 1, maxNum);
	return tot;
}
int main() {
	int n, m;
	cin >> n >> m;
	cout << fun(m, 1, n) << endl;
	return 0;
}

输入:6 3

输出:_________

答案与解析
参考答案

20

题目详情
35 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <string>
using namespace std;

const int SIZE = 100;

int main() {
	string dict[SIZE];
	int rank[SIZE];
	int ind[SIZE];
	int i, j, n, tmp;
	cin >> n;
	for (i = 1; i <= n; i++) {
		rank[i] = i;
		ind[i] = i;
		cin >> dict[i];
	}
	for (i = 1; i < n; i++)
		for (j = 1; j <= n - i; j++)
			if (dict[ind[j]] > dict[ind[j + 1]]){
				tmp = ind[j];
				ind[j] = ind[j + 1];
				ind[j + 1] = tmp;
			}
	for (i = 1; i <= n; i++)
		rank[ind[i]] = i;
	for (i = 1; i <= n; i++)
		cout << rank[i] << " ";
	cout << endl;
	return 0;
}

输入:

7

aaa

aba

bbb

aaa

aaa

ccc

aa

输出:_________

答案与解析
参考答案

2 5 6 3 4 7 1

题目详情
36 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
using namespace std;

const int SIZE = 100;

int alive[SIZE];
int n;

int next(int num) {
	do {
		num++;
		if (num > n)
			num = 1;
	} while (alive[num] == 0);
	return num;
}

int main() {
	int m, i, j, num;
	cin >> n >> m;
	for (i = 1; i <= n; i++)
		alive[i] = 1;
	num = 1;
	for (i = 1; i <= n; i++) {
		for (j = 1; j < m; j++)
			num = next(num);
		cout << num << " ";
		alive[num] = 0;
		if (i < n)
			num = next(num);
	}
	cout << endl;
	return 0;
}

输入:11 3

输出:_________

答案与解析
参考答案

3 6 9 1 5 10 4 11 8 2 7

题目详情
37 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
#include<string >
using namespace std;

int main( )
	{ string
	Str;
	cin>>str;
	int n = str.size( );
	bool isPlalindrome = true;
	for (int i =0; i<n/2;i++){
		if (str[i] !=str[n-i-1]) isPlalindrome = false;
	}
	if(isPlalindrome)
		cout << ”Yes” << endl;
	else cout << ”No” << endl;
}

输入:abceecba

输出:_________

答案与解析
参考答案

Yes

题目详情
38 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
using namespace std;

int main( )
{
	int a,b,u,v,i, num;
	cin >>a>>b>>u>>v;
	num =0;
	for ( i= a; I <=b; i++)
		if (((i%u) ==0)||((i%v)==0))
			num ++;
		count <<num<<endl;
	return 0;
}

输入:1 1000 10 15

输出:_________

答案与解析
参考答案

133

题目详情
39 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
using namespace std;

int main( )
{
	const int SIZE = 100;
	int height[SIZE], num[SIZE], n, ans;
	cin>>n;
	for (int i=0; i<n; i++) {
		cin >>height[i];
		num[i]= 1;
		for (int j=0; j<i; j++) {
			if ((height[j]<height[i])&&(num[j]>= num[i]))
				num[i] =num[j]+1;
			}
		}
		ans =0;
		for(int I = 1; i<n; i++){
			if(num[i] >ans) ans =num[j];
		}
		Cout <<ans<<endl;
}

输入:

8

3 2 5 11 12 7 4 10

6

输出:_________

答案与解析
参考答案

4

题目详情
40 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
#include<string >
using namespace std;

const int SIZE = 100;
int n, m, p, a[SIZE] [SIZE], count;

void colour (int x, int y)
{
	Count++;
	a[x][y] = 1;
	if ((x > 1)&& (a[x-1][y] == 0))
		colour( x - 1, y);
	if ((y> 1)&& (a[x][y-1] == 0))
		colour( x, y- 1);
	if ((x < n)&& (a[x+1][y] == 0))
		colour( x +1, y);
	if ((y < m)&& (a[x][y+1] == 0))
		colour( x, y+1);
}
int main( )
{
	int i, j, x, y, ans;
	memset(a, 0, sizeof(a));
	cin >>n>>m>>p;
	for(i =1 ; I <=p; i++) {
		cin>>x>>y;
		a[x][y] = 1;
	}
	ans = 0;
	for (i =1; i <=n; i++)
		for (j =1; j <=m;j++)
			if (a[i][j] == 0)
				{count = 0;
				colour (i , j);
				if (ans <count)
					ans <count;
			}
	count<<ans<<endl;
	return 0;
}

输入:

6 5 9

1 4

2 3

2 4

3 2

4 1

4 3

4 5

5 4

6 4

输出:_________

答案与解析
参考答案

7

题目详情