[蓝桥杯 2013 省 B] 翻硬币
题目背景
小明正在玩一个“翻硬币”的游戏。
题目描述
桌上放着排成一排的若干硬币。我们用*
表示正面,用o
表示反面(是小写字母,不是零),比如可能情形是**oo***oooo
,如果同时翻转左边的两个硬币,则变为oooo***oooo
。现在小明的问题是:如果已知了初始状态和要达到的目标状态,每次只能同时翻转相邻的两个硬币,那么对特定的局面,最少要翻动多少次呢?
输入格式
两行等长字符串,分别表示初始状态和要达到的目标状态,每行长度小于1000。
数据保证一定存在至少一种方案可以从初始状态和要达到的目标状态。
输出格式
一个整数,表示最小操作步数。
输入输出样例
输入输出样例
输入 #1
**********o****o****
输出 #1
5
输入 #2
*o**o***o****o***o**o***
输出 #2
1
#include#include#include 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
[NOIP2006 普及组] 明明的随机数
题目描述
明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。
输入格式
输入有两行,第1行为1个正整数,表示所生成的随机数的个数N。
第2行有N个用空格隔开的正整数,为所产生的随机数。
输出格式
输出也是两行,第1行为1个正整数M,表示不相同的随机数的个数。
第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。
输入输出样例
输入 #1
1020 40 32 67 40 20 89 300 400 15
输出 #1
815 20 32 40 67 89 300 400
#includeint 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
53 10abcabcabcabca2 10aaAAaAaaAaAa5 5AbCdEeDcBa5 5abcdeABCDE3 10abaABaBaAbaBA输出 #1
39014
解法一:
#include#include#include#includeint main(){intt = 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){return1;}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;}
解法一的运行时间可能会超时,可以试试解法二:
#include #include #include // 函数用于计算字符串a在字符串b中的出现次数int JiShu(char* a, char* b) {int count = 0;int lenA = strlen(a);int lenB = strlen(b);for (int i = 0; i <= lenB - lenA; i++){// 忽略大小写比较int flag = 1;for (int j = 0; j < lenA; j++) {if (tolower(a[j]) != tolower(b[i + j])){flag = 0;break;}}if (flag) {count++;}}return count;}int main() {int t;scanf("%d", &t);for (int i = 0; i < t; i++){int n, m;scanf("%d %d", &n, &m);char a[1001], b[1001];scanf("%s", a);scanf("%s", b);int rs = JiShu(a, b);printf("%d\n", rs);}return 0;}