CSU机试

2013

回文串问题

回文串问题
时间限制: 1 Sec  内存限制: 128 MB
- 题目描述
“回文串”是一个正读和反读都一样的字符串，字符串由数字和小写字母组成，比如“level”或者“abcdcba”等等就是回文串。请写一个程序判断读入的字符串是否是“回文”。
- 输入
输入包含多个测试实例，每一行对应一个字符串，串长最多100字母。
- 输出
对每个字符串，输出它是第几个，如第一个输出为"case1:"；如果一个字符串是回文串，则输出"yes",否则输出"no"，在yes/no之前用一个空格。
- 样例输入
level
abcde
noon
haha
- 样例输出
case1: yes
case2: no
case3: yes
case4: no
提示
请使用scanf进行输入。

这道题还是很简单的，主要是通过判断前后两个对应位置的字符是否相等，如果不相等直接判断不是回文串，如果一直匹配成功，说明是回文串。

前后位置的下标？

​ 假如前面的位置为0，那么它对应要匹配的位置是len-1，len为字符串长度

​ 前面的位置为i，那么它对应的位置是len-1-i

注意边界值：

​ 只需要匹配到中间的位置即可，也就是i的范围应该是**[0,len/2)**

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string s;
    int case_num = 1;
    while (cin >> s)
    {
        int len = s.length();
        bool res = true;

        // 检查是否时回文串
        for (int i = 0; i < len / 2; i++)
        {
            if (s[i] != s[len - 1 - i])
            {
                res = false;
                break;
            }
        }

        // 输出结果
        if (res)
            cout << "case" << case_num << ": yes" << endl;
        else
            cout << "case" << case_num << ": no" << endl;
        case_num++;
    }

    return 0;
}

水仙花数

1001: 水仙花数 时间限制: 1 Sec  内存限制: 128 MB
- 题目描述
春天是鲜花灿烂的季节，水仙花就是其中最迷人的代表，数学上有个水仙花数，他是这样定义的：“水仙花数”是指一个三位数，
它的各位数字的立方和等于其本身，比如：153=1^3+5^3+3^3。现在要求输出所有在m和n范围内的水仙花数。
- 输入
输入数据有多组，每组占一行，包括两个整数m和n（100<=m<=n<=999）。
- 输出
对于每个测试实例，要求输出所有在给定范围内的水仙花数，就是说，输出的水仙花数必须大于等于m,并且小于等于n，
如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开(注意每组输出的最后一个数之后不要加空格);
如果给定的范围内不存在水仙花数，则输出no;每个测试实例的输出占一行。
- 样例输入
100 120
300 380
- 样例输出
no
370 371

注意题目中的一些条件：

我们要求解的水仙花数范围是**[m,n]**，闭区间

如果有多个，则要求从小到大排列在一行内输出，之间用一个空格隔开，最后那个没有空格；

☢☢如果有多解，一般的处理方式是对第一个解输出特殊处理，后面的输出就是都是一个空格再接着一个解

基本思路：对给定的范围内的数，进行穷举，判断是否符合是个水仙数

#include <iostream>
#include <string>
using namespace std;

int getShuiNum(int a) // 用来计算a的三位数字的三次方之和
{
    int ret = 0;
    while (a)
    {
        int t = a % 10;
        a /= 10;
        ret = ret + t * t * t;
    }
    return ret;
}

int main()
{
    int m, n;
    while (cin >> m >> n)
    {
        bool isFirst = true;
        for (int i = m; i <= n; i++)
        {
            if (i == getShuiNum(i))
            {
                if (isFirst)
                {
                    isFirst = false;
                    cout << i;
                }
                else
                {
                    cout << " " << i;
                }
            }
        }
        if (isFirst)  // 如果一个解都没有，就要输出"no"
            cout << "no" << endl;
        else
            cout << endl;
    }

    return 0;
}

安全密码

1002: 安全密码
- 题目描述
网络上各类交易活动越来越普及，为了能够安安心心地上网，经常需要设置一个安全的密码。一般来说一个比较安全的密码至少应该满足下面两个条件：
(1)密码长度大于等于8。
(2)密码中的字符应该来自下面“字符类别”中四组中的至少三组。
这四个字符类别分别为：
(1)大写字母：A,B,C...Z;
(2)小写字母：a,b,c...z;
(3)数字：0,1,2...9;
(4)特殊符号：~,!,@,#,$,%,^;
给你一个密码，你的任务就是判断它是不是一个安全的密码。
- 输入
输入数据有多组，每组占一行，每行一个密码（长度最大可能为50），密码仅包括上面的四类字符。
- 输出
对于每个测试实例，判断这个密码是不是一个安全的密码，是的话输出YES，否则输出NO。
- 样例输入
a1b2c3d4
Linle@ACM
^~^@^@!%
- 样例输出
NO
YES
NO

思路：根据给定的密码串，判断其中的字符是否存在4类字符中。

☢注意☢

• 不要忽视了题目的条件：是否是安全密码需要满足两个条件，第一个是长度至少有8位

• 其次才是判断密码中的字符类型至少有3钟

所以前面四个函数就是分别用来判断密码中某个字符的类型：

• bool isNumber(char a) //判断是否是数字
• bool isUpperChar(char a) //判断是否是大写字母
• bool isLowerChar(char a) //判断是否是小写字母
• bool isSpecialChar(char a) //判断是否是特殊字符
• 在这里值得注意，判断数字、字母时并不需要记住asc码值：可以用：int t = a-‘0’; 这样的方法来计算距离字符’0’的偏移值，看这个偏移值是否在**[0,9]** 的范围内
• 其次注意这些范围的边界，我开始就犯了个错误：判断是否是字母的偏移值范围应该是**[0,25]**，我的错误的写成了t<=26;

可以说写完这四类判断应该够了，这里我还进行了下小优化：

• 例如对于密码的第一位我判断出来是数字，那我后面就不需要重复判断了
• 只需要判断它满足过有数字，而不需要重复的判断

用一个bool数组tag存储密码满足哪几种类型，最后只要遍历下这个tag数组就知道是否符合密码要求；

为了防止重复判断，浪费性能，我在每个判断条件中加了：**!tag[0]** 这种条件，如果tag[0]为true，那么取非后就是假，同时&&具有短路现象，也就是当&&连接的第一个条件是false的时候，第二个条件就不会去判断了，所以就避免了再次的判断是否是存在数字类型的密码。（因为不管第二个的结果是什么，只要第一个条件为false，我就能断定这个与运算的结果是false）

#include <iostream>
#include <string>
using namespace std;

bool isNumber(char a)	//判断是否是数字
{
    int t = a - '0';
    return t >= 0 && t <= 9;
}

bool isUpperChar(char a)	//判断是否是大写字母
{
    int t = a - 'A';
    return t >= 0 && t < 26;
}

bool isLowerChar(char a)	//判断是否是小写字母
{
    int t = a - 'a';
    return t >= 0 && t < 26;
}

bool isSpecialChar(char a)	//判断是否是特殊字符
{
    return a == '~' || a == '!' || a == '@' || a == '#' || a == '$' || a == '%' || a == '^';
}


int main()
{
    string s;
    while (cin >> s)
    {
        if(s.length()<8)	//密码长度不足8位，直接不满足
        {
            cout<<"NO"<<endl;
            break;
        }
        
        bool tag[4] = {false};

        for (int i = 0; i < s.length(); i++)
        {
            char temp = s[i];
            if (!tag[0] && isNumber(s[i]))
            {
                tag[0] = true;
            }
            if (!tag[1] && isUpperChar(s[i]))
            {
                tag[1] = true;
            }
            if (!tag[2] && isLowerChar(s[i]))
            {
                tag[2] = true;
            }
            if (!tag[3] && isSpecialChar(s[i]))
            {
                tag[3] = true;
            }
        }

        // 计算密码中存在几组类型
        int countType = 0;
        for (int i = 0; i < 4; i++)
        {
            if (tag[i])
                countType++;
        }
        // 输出
        if (countType >= 3)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

最少钱币数