[蓝桥杯 2013 省 B] 翻硬币

 

题目背景

小明正在玩一个“翻硬币”的游戏。

题目描述

桌上放着排成一排的若干硬币。我们用 * 表示正面，用 o 表示反面（是小写字母，不是零），比如可能情形是 **oo***oooo，如果同时翻转左边的两个硬币，则变为 oooo***oooo。现在小明的问题是：如果已知了初始状态和要达到的目标状态，每次只能同时翻转相邻的两个硬币，那么对特定的局面，最少要翻动多少次呢？

输入格式

两行等长字符串，分别表示初始状态和要达到的目标状态，每行长度小于 1000。

数据保证一定存在至少一种方案可以从初始状态和要达到的目标状态。

输出格式

一个整数，表示最小操作步数。

输入输出样例

输入输出样例

输入 #1

**********
o****o****

输出 #1

5

 输入 #2

*o**o***o***
*o***o**o***

 输出 #2

1

#include<stdio.h>
#include<string.h>
#include <assert.h>
int main()
{
	char arr[1000] = { 0 }, str[1000] = { 0 }, count = 0;
	scanf("%s%s", &arr, &str);
	assert(strlen(arr)== strlen(str));//断言-判断两个字符串长度是否相等
	int rs = strlen(arr);
	int i = 0;
	while (i < rs)//遍历找不同
	{
		if (arr[i] != str[i])
		{
			arr[i] = (arr[i] == '*' ? 'o' : '*');
			arr[i + 1] = (arr[i + 1] == '*' ? 'o' : '*');
			count++;
		}
		i++;
	}
	printf("%d", count);
	return 0;
}

 [NOIP2006 普及组] 明明的随机数

题目描述

明明想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了 N 个 1 到 1000 之间的随机整数 (N≤100)，对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入格式

输入有两行，第 1 行为 1 个正整数，表示所生成的随机数的个数 N。

第 2 行有 N 个用空格隔开的正整数，为所产生的随机数。

输出格式

输出也是两行，第 1 行为 1 个正整数 M，表示不相同的随机数的个数。

第 2 行为 M 个用空格隔开的正整数，为从小到大排好序的不相同的随机数。

输入输出样例

输入 #1

10
20 40 32 67 40 20 89 300 400 15

输出 #1

8
15 20 32 40 67 89 300 400

#include<stdio.h>
int main()
{
	int n = 0, str[100] = { 0 }, temp = 0;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &str[i]);
	}
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (str[j + 1] < str[j])
			{
				temp = str[j + 1];
				str[j + 1] = str[j];
				str[j] = temp;
			}
		}
	}
	for (int i = 0; i < n - 1; i++)//n-1是为了防止越界
	{
		//把i+1后边的元素往前覆盖
		if (str[i] == str[i + 1])
		{
			for (int k = i; k < n - 1; k++)
			{
				str[k] = str[k + 1];
			}
			n--;
			i--;
		}
	}
	printf("%d\n", n);
	for (int i = 0; i < n; i++)
	{
		printf("%d ", str[i]);
	}
	return 0;
}

P8835 [传智杯 #3 决赛] 子串

 

题目背景

disangan233 喜欢字符串，于是 disangan333 想让你找一些 disangan233 喜欢的串。

题目描述

在传智的开发课堂上，希望您开发一款文档处理软件。

给定 T 组询问，每次给定 2 个长度为 n，m 的只含英文字母的字符串 a，b，求 a 在 b 中的出现次数，相同字符不区分大小写。注意 a 是 b 中连续子序列。

对于所有数据，T≤100，∑n≤∑m≤10^3。字符串仅由大小或者小写的英文字母组成。

输入格式

输入共 3T+1 行。

第 1 行输入 1 个正整数 T。

接下来共 T 组输入，每组输入共 3 行。

第 1 行输入 2 个正整数 n，m。

第 2 行输入一个长度为 n 的字符串 a。

第 3 行输入一个长度为 m 的字符串 b。

输出格式

输出共 T 行，第 i 行输出 1 个整数，表示询问 i 的答案。

输入输出样例

输入 #1

5
3 10
abc
abcabcabca
2 10
aa
AAaAaaAaAa
5 5
AbCdE
eDcBa
5 5
abcde
ABCDE
3 10
aba
ABaBaAbaBA

---

输出 #1

3
9
0
1
4

#include<stdio.h>
#include<ctype.h>
#include<stdlib.h>
#include<string.h>
int main()
{
	int  t = 0, n = 0, m = 0, count = 0;//t小组数，n,m字符串的长度,count计数器
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n, &m);
		char* a = (char*)malloc( (n+1) * sizeof(char));//开辟数组a的动态内存空间
		                                               //因为数组类型是字符串要留一个字节放斜杆零，防止越界访问
		if (a == NULL)
		{
			return  1;
		}
		scanf("%s", a);
		char* b = (char*)malloc( (m+1) * sizeof(char));//开辟数组b的动态内存空间
		if (b == NULL)
		{
			return 1;
		}
			scanf("%s", b);
			char* ptr = b;//记录b的首地址
		for (int i = 0; i < n; i++)
		{
			*a = tolower(*a);//统一转换为小写
		}
		for (int i = 0; i < m; i++)
		{
			*b = tolower(*b);
		}
		for (int i = 0; i < m; i++)
		{
			if (strncmp( a ,ptr , n) == 0)  //比较前n个字符相同，count++
			{
				count++;
				ptr + n;                    //指向b的指针向前挪动n位比较下一个
			}
			ptr++;
			if (m - i < n)
			{
				break;
			}
		}
		printf("%d", count);
		free(a);                            //释放动态空间
		a = NULL;
		free(b);
		b = NULL;
	}
	return 0;
}