蓝桥杯——练习（3.7）

蓝桥杯——练习（3.7）

基础练习 完美的代价

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T60

资源限制

时间限制：1.0s 内存限制：512.0MB

问题描述

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

输入格式

第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
　　第二行是一个字符串，长度为N.只包含小写字母

输出格式

如果可能，输出最少的交换次数。
　　否则输出Impossible

样例输入

5
mamad

样例输出

3

解题思路

• 从右端j开始寻找与s[i]相同的s[k]；k= =i 的时候为找到单独的一个字符，输出Impossible 的情况为n%2==0或者标记位flag为1，且如果字符长度为偶数或者之前已经找到一个单独的字符就无法调整为回文了。不满足的话就让cnt的值加上n/2-i；

• 如果s[i]==s[k],就是把找到的s[k]移动到最右端。

• 通过用swap函数将s[x]与s[x+1]的值调换一下，并且让计数器cnt++。

代码

#include<iostream>
#include<string>
using namespace std;
int cnt=0;
int flag=0;
int main()
{
	int n;
	string s;
	cin>>n;
	cin>>s;
	int j=n-1;
	for(int i=0;i<j;i++)
	{
		for(int k=j;k>=i;k--)
		{
			if(k==i)
			{
				if(n%2==0||flag==1)
				{
					cout<<"Impossible";
					return 0;
				}
				cnt+=n/2-i;
			}
			else 
			{
				if(s[i]==s[k])
				{
					for(int x=k;x<j;x++)
					{
						swap(s[x],s[x+1]);
						cnt++;
					}
					j--;
					break;
				}
			}
		}
	}
	cout<<cnt<<endl;
	return 0;
} 
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

视频学习——栈和递归练习

视频链接：https://www.bilibili.com/video/BV1jE411g76D?p=12

学习心得

栈是预先分配好的，连续的内存空间，局部变量就放在栈空间上，通过控制esp来实现局部变量的创建和释放。

栈平衡如果被破坏，函数就可能不能返回到预期的位置，同理，利用这个原理，我们也可以控制目标程序进入指定的位置，来获取目标操作系统的控制权限，这也就是栈攻击的技术原理，同时编写代码时也要积极预防栈攻击。

当我们逆向的时候，可以通过函数头部的sub esp x 来判断这个函数有多少局部变量。

关于CPU寄存器的说明：

eax： 函数的执行结果全通过eax来传递。

esp： 栈顶，栈顶以下的值代表着是可以访问的局部变量。

ebp： 栈底。

eip： CPU执行的位置。

题目练习 算法训练 s01 串

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T366

资源限制

时间限制：1.0s 内存限制：256.0MB

问题描述

s01串初始为"0"
按以下方式变换
0变1，1变01

输入格式

1个整数(0~19)

输出格式

n次变换后s01串

样例输入

3

样例输出

101

数据规模和约定

0~19

代码

#include<iostream>
#include<cstring>
using namespace std;
string Get(char c)
{
	if(c=='0')
		return "1";
	else 
		return "01";
}
int main()
{
	int n;
	cin>>n;
	string str1="0";
	string str2="";
	if(n!=0)
	{
		while(n--)
		{
			int len=str1.length();
			str2="";
			for(int i=0;i<len;i++)
			{
				str2+=Get(str1[i]);
			} 
			str1=str2;
		}
		cout<<str2<<endl;
	}
	else
		cout<<str1<<endl;
	return 0;
}
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