蓝桥杯练习题H

题目描述

回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。 交换的定义是:交换两个相邻的字符   例如mamad   第一次交换 ad : mamda   第二次交换 md : madma   第三次交换 ma : madam (回文!完美!)
输入

第一行是一个整数N,表示接下来的字符串的长度(N <= 8000) 第二行是一个字符串,长度为N.只包含小写字母
输出
如果可能,输出最少的交换次数。 否则输出Impossible (结尾加一个换行符)

1
2
3
4
样例输入
5 mamad
样例输出
3

思路:

这题当时做过,而且错了很多次来着,

首先看看字符串个数 奇数个数是否大于2,大于2就输出 impossible

接着从头开始

比如 a[0]=’a’ 那么最后开始 往前面找 ‘a’ 找到的第一个 ‘a’ 记录其在字符串的位置,计算从当前位置换到最后一个位置需要的步骤数,步骤总数加上步骤数,然后交换2个字符

然后 到 a[1] 找到 与a[1]相同的字符创的位置(逆序) 然后与 倒数第二个 交换

并累加步骤数,直到交换完 n/2 个字符即可

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <cstring>
using namespace std;
char a[100000];
void shift(int i,int j)
{
while(j-i)
{
int t=a[i];
a[i]=a[i+1];
a[i+1]=t;
i++;
}
}
int main()
{
int len,c=0,sum=0,wei=0;
cin>>len;
cin>>a;
for(int i=0;i<len/2;i++)
{
for(int j=len-i-1+c;j>=i;j--)
{
if(a[j]==a[i])
{
if(j==i){
c++;
wei=i;
if(c>1){
cout<<"Impossible";
return 0;
}
break;
}
sum+=(len-i-1+c)-j;
shift(j,len-i-1+c);
break;
}
}
}
if(c!=0)sum+=len/2-wei;
shift(wei,len/2);
cout<<sum<<endl;
return 0;
}

蓝桥杯练习题I

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=1

题目描述
在河上有一座独木桥,一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子,青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数,我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:0,1,……,L(其中L是桥的长度)。坐标为0的点表示桥的起点,坐标为L的点表示桥的终点。青蛙从桥的起点开始,不停的向终点方向跳跃。一次跳跃的距离是S到T之间的任意正整数(包括S,T)。当青蛙跳到或跳过坐标为L的点时,就算青蛙已经跳出了独木桥。题目给出独木桥的长度L,青蛙跳跃的距离范围S,T,桥上石子的位置。你的任务是确定青蛙要想过河,最少需要踩到的石子数。

输入
输入的第一行有一个正整数L(1 <= L <= 109),表示独木桥的长度。第二行有三个正整数S,T,M,分别表示青蛙一次跳跃的最小距离,最大距离,及桥上石子的个数,其中1 <= S <= T <= 10,1 <= M <= 100。第三行有M个不同的正整数分别表示这M个石子在数轴上的位置(数据保证桥的起点和终点处没有石子)。所有相邻的整数之间用一个空格隔开。
输出
输出只包括一个整数,表示青蛙过河最少需要踩到的石子数。结尾加一个换行符。
样例输入
10 2 3 5 2 3 5 6 7
样例输出
2
思路:
题目刚开始也没看懂,以为青蛙一定要踩石头,舍友跟我说了青蛙讨厌石头,能不踩就不踩,我才把思路理顺,就是穷举所有情况找到最小值,
代码:

蓝桥杯练习题J

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=9

题目描述
【问题描述】 某公司生产长钢管,然后一般,会将钢条切断,变成不同长度,然后去售卖。其中有个问题是,不同长度的钢管的售价是不一样的,但是它们并不是完全按照比例来,比如2米的钢管售价要比3米的钢管售价要少,但是并不是2比3的比例。例如钢管的长度售价表如下: 长度i 1 2 3 4 5 6 7 8 9 10 价格Pi 1 5 8 9 10 17 17 20 24 30 于是问题就来了,比如10米以内的钢管,要如何切割,切割成多长的几条,才能让售价最高?
输入
输入的数据为11个正整数,1-10个正整数代表Pi,即长度为i的钢管价格,第11个正整数N代表要切割的钢管长度。
输出
输出最高售价。结尾加一换行符。

1
2
3
4
样例输入
1 5 8 9 10 17 17 20 24 30 9
样例输出
25

思路:
穷举,把所有的可能都计算出来,最大值就出来了..
代码:

蓝桥杯练习题K

来源:http://oj.mofriend.net/problem.php?cid=1203&pid=10

题目描述
An array of length n, with address from 1 to n inclusive(包含), contains entries from the set {1,2,…,n-1} and there’s exactly two elements with the same value. Your task is to find out the value.
输入

Input contains several cases. Each case includes a number n (1

输出
Your must output the value for each case, one per line

1
2
3
4
5
6
7
8
样例输入
2
1 1
4
1 2 3 2
样例输出
1
2

思路:
题目意思找到2个相同的数…超简单,就是英文的而已
代码:

01背包问题

01背包问题是困扰我很久的问题,通过此次课程我学到了如何处理这一类问题,01背包问题讲述的是给你个固定空间的背包,还有N多物品,每个物品有他的价值和所占用的空间大小,我们要做到的是让背包存放最大价值。

下面有编号分别为a,b,c,d,e的五件物品,它们的重量分别是2,2,6,5,4,它们的价值分别是6,3,5,4,6,现在给你个承重为10的背包,求能存放的物品的最大价值。

我们最有好用的算法是用矩阵来计算,但是费空间。

我们先计算出背包容量为1-10的情况下选取只有a物品的时候可获得的最大价值,结果显然如下

Problem 1007 Biometrics FOJ

来源:http://acm.fzu.edu.cn/problem.php?pid=1007

Problem Description
Recently, the term Biometrics been used to refer to the emerging field of technology devoted to identification of individuals using biological traits, such as those based on retinal or iris scanning, fingerprints, or face recognition.

A simple biometric system translates a human image into a polygon by considering certain features (eyes, nose, ears, etc.) to be vertices and connecting them with line segments. The polygon has distinct vertices but may be degenerate in that the line segments could intersect. Because these polygons are generally created from remote images, there is some uncertainty as to their scale and rotation. Your job is to determine whether or not two polygons are similar; that is, can they be made equal by repositioning, rotating and magnifying them?

Problem 1009 Jogging Trails

来源:http://acm.fzu.edu.cn/problem.php?pid=1009

Problem Description
Gord is training for a marathon. Behind his house is a park with a large network of jogging trails connecting water stations. Gord wants to find the shortest jogging route that travels along every trail at least once.Input consists of several test cases. The first line of input for each case contains two positive integers: n <= 15, the number of water stations, and m < 1000, the number of trails. For each trail, there is one subsequent line of input containing three positive integers: the first two, between 1 and n, indicating the water stations at the end points of the trail; the third indicates the length of the trail, in cubits. There may be more than one trail between any two stations; each different trail is given only once in the input; each trail can be travelled in either direction. It is possible to reach any trail from any other trail by visiting a sequence of water stations connected by trails. Gord’s route may start at any water station, and must end at the same station. A single line containing 0 follows the last test case.

For each case, there should be one line of output giving the length of Gord’s jogging route.

Problem 1010 Beavergnaw

来源:http://acm.fzu.edu.cn/problem.php?pid=1010

Problem Description
When chomping a tree the beaver cuts a very specific shape out of the tree trunk. What is left in the tree trunk looks like two frustums of a cone joined by a cylinder with the diameter the same as its height. A very curious beaver tries not to demolish a tree but rather sort out what should be the diameter of the cylinder joining the frustums such that he chomped out certain amount of wood. You are to help him to do the calculations.

Problem 1011 Power Strings

来源:http://acm.fzu.edu.cn/problem.php?pid=1011
Problem Description
Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then ab = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a*(a^n).

Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

1
2
3
4
5
6
7
8
9
 Sample Input
abcd
aaaa
ababab
.
Sample Output
1
4
3

思路:刚开始以为挺简单的,字符串的一个循环搜索就好了,结果输入数据是100W。。。一开始没看到100W,设置数组为10W,结果无限的运行时错误,百度看了大神的思路,大部分KMP。。。这个算法我一点不懂,,尝试看了下。。。也没看懂。以后有空去问问老师这个算法吧。。。然后找了一会 发现一个间接的方案。。
首先关于字符串是否能时重复的,那么这个重复的子字符串的长度必然是总长度的公因子。所以,取于判断是否可以整除就可以减掉大部分无意义的运算,然后循环对比字符串,找到循环因子即可。对了,千万不要用C++的 cin 他处理100W的字符串输入就需要10S左右,肯定超时,如果要用就要先 std::ios::sync_with_stdio(false);使得C++的cin直接输入,而不是在缓存中到输入结束在输入到变量中。
大神博客地址:http://blog.csdn.net/shiwaigaoren12345/article/details/50517786
下面是我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <cstring>
char a[1001001];
int main() {
int i, j, k, len, flag;
while (scanf("%s",a)) {
if (a[0] == '.')break;
len = strlen(a);
for (i = 1; i<=len; i++) {
flag = 1;
if (len%i == 0) {
for ( k = i; k < len; k++)
{
if (a[k%i] != a[k]) {
flag = 0;
break;
}
}
if (flag) {
printf("%d\n", len / i);
break;
}
}
}
}
return 0;
}

C++ 的 cin版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <cstring>
using namespace std;
char a[1001001];
int main() {
int i, j, k, len, flag;
std::ios::sync_with_stdio(false);
while (cin >> a && a[0] != '.') {
len = strlen(a);
for (i = 1; i<=len; i++) {
flag = 1;
if (len%i == 0) {
for ( k = i; k < len; k++)
{
if (a[k%i] != a[k]) {
flag = 0;
break;
}
}
if (flag) {
cout << len / i << endl;
break;
}
}
}
}
return 0;
}

Problem 1012 Relatives

来源:http://acm.fzu.edu.cn/problem.php?pid=1012

Problem Description
Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

For each test case there should be single line of output answering the question posed above.