首页 › 题库 › 信息学奥赛 › 6 字符串算法

信息学奥赛-提高级 题库

共 52 道题 ,第 3 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 6 字符串算法 清除
41 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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

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

int n, i, temp, sum, a[100];

int main()
{
	cin>>n;
	for (i = 1; i <= n; i++) 
		cin>>a[i];
	for (i = 1; i <= n - 1; i++) 
		if (a[i] > a[i + 1]) {
			temp = a[i]; 
			a[i] = a[i + 1]; 
			a[i + 1] = temp;
		}
	for (i = n; i >= 2; i--)
		if (a[i] < a[i - 1]) { 
			temp = a[i];
			a[i] = a[i - 1];
			a[i - 1] = temp;
		}
	sum = 0;
	for (i = 2; i <= n - 1; i++) 
		sum += a[i];
	cout<<sum / (n - 2)<<endl; 
	return 0;
}

输入:

8

40 70 50 70 20 40 10 30

输出:

                   

答案与解析
参考答案

41

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

int n, i, ans;

int gcd(int a, int b)
{
	if (a % b == 0) 
		return b;
	else
		return gcd(b, a%b);
}
int main()
{
	cin>>n; 
	ans = 0;
	for (i = 1; i <= n; i++) 
		if (gcd(n,i) == i)
			ans++; 
	cout<<ans<<endl;
}

输入:120 

输出:            

答案与解析
参考答案

16

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

const int SIZE = 20;

int data[SIZE]; 
int n, i, h, ans;

void merge()
{
	data[h-1] = data[h-1] + data[h]; 
	h--;
	ans++;
}
int main()
{
	cin>>n; 
	h = 1;
	data[h] = 1;
	ans = 0;
	for (i = 2; i <= n; i++)
	{
		h++;
		data[h] = 1;
		while (h > 1 && data[h] == data[h-1]) 
			merge();
	}
	cout<<ans<<endl;
}

(1) 输入:8

输出:           (4 分)

(2) 输入:2012

输出:           (4 分

答案与解析
参考答案

(1)7

(2)2004

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

int lefts[20], rights[20], father[20]; 
string s1, s2, s3;
int n, ans;

void calc(int x, int dep)
{
	ans = ans + dep*(s1[x] - 'A' + 1);
	if (lefts[x] >= 0) calc(lefts[x], dep+1); 
	if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x)
{
	if (lefts[x] >= 0) check(lefts[x]); 
	s3 = s3 + s1[x];
	if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th)
{
	if (th == n)
	{
		s3 = "";
		check(0);
		if (s3 == s2)
		{
			ans = 0;
			calc(0, 1); 
			cout<<ans<<endl;
		}
		return;
	}
	if (lefts[x] == -1 && rights[x] == -1)
	{
		lefts[x] = th; 
		father[th] = x; 
		dfs(th, th+1); 
		father[th] = -1;
		lefts[x] = -1;
	}
	if (rights[x] == -1)
	{
		rights[x] = th; 
		father[th] = x; 
		dfs(th, th+1); 
		father[th] = -1;
		rights[x] = -1;
	}
	if (father[x] >= 0)
		dfs(father[x], th);
}
int main()
{
	cin>>s1; 
	cin>>s2;
	n = s1.size();
	memset(lefts, -1, sizeof(lefts));
	memset(rights, -1, sizeof(rights));
	memset(father, -1, sizeof(father));
	dfs(0, 1);
}

输入:

ABCDEF 

BCAEDF

输出:              

答案与解析
参考答案

55

题目详情
46 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
	int n,i,sum,x,a[SIZE];
 
	cin>>n;
	memset(a,0,sizeof(a));
 
	for(i=1;i<=n;i++){
		cin>>x;
		a[x]++;
	 }
	i=0;
	sum=0;
	while(sum<(n/2+1)){
		i++;
		sum+=a[i];
 	}
 	cout<<i<<endl;
	 return 0;
}

输入:

11

4 5 6 6 4 3 3 2 3 2 1

输出:                

答案与解析
参考答案

3

题目详情
47 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
	 if(x<n)
 		f2(y,x+y);
}
void f2(int x,int y)
{
	cout<<x<<' ';
	f1(y,x+y);
}
int main()
{
	cin>>n;
	f1(0,1);
	return 0;

	return 0;
}


答案与解析
参考答案

输入:30 

输出:                      

1 2 5 13 34

题目详情
48 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
	int i;
	visited[x]= true;
	if(len>ans)
		ans=len;
	for(i=1;i<=n;i++)
		if( (!visited[i]) && (e[x][i]!=-1) )
			dfs(i,len+e[x][i]);
	visited[x]=false;
}
int main()
{
	int i,j,a,b,c;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=m;j++)
			e[i][j]=-1;
	for(i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		e[a][b]=c;
		e[b][a]=c;
	}
	for(i=1;i<=n;i++)
		visited[i]=false;
	ans=0;
	for(i=1;i<=n;i++)
		dfs(i,0);
	cout<<ans<<endl;
	return 0;
}

输入:

4 6

1 2 10

2 3 20

3 4 30

4 1 40

1 3 50

2 4 60 

输出:                  

答案与解析
参考答案

150

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

const int SIZE=10000;
const int LENGTH=10;

int n,m,a[SIZE][LENGTH];

int h(int u,int v)
{
	int ans,i;
	ans=0;
	for(i=1;i<=n;i++)
		if( a[u][i]!=a[v][i])
			ans++;
	return ans;
}
int main()
{
	int sum,i,j;
	cin>>n;
	memset(a,0,sizeof(a));
	m=1;	
	while(1)
	 {
		i=1;
 		while( (i<=n) && (a[m][i]==1) )
			i++;
		if(i>n)
			break;
		m++;
		a[m][i]=1;
		for(j=i+1;j<=n;j++)
		a[m][j]=a[m-1][j];	
	}
	sum=0;
	for(i=1;i<=m;i++)
		for(j=1;j<=m;j++)
		sum+=h(i,j);
	cout<<sum<<endl;
	return 0;
}

输入:7

输出:_________

答案与解析
参考答案

57344

题目详情
50 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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 可见字符组成,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
51 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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 表示范围内,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
52 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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 的正整数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情