首页 > > 程序设计 > C/C++ >

算法竞赛入门经典5.1 从c到c++

2018-09-05 07:42:40来源：博客园阅读 ()

　　这个章节主要是讲述了一些c++的特性，在这里面，对我用处最大的应该就是字符串吧。首先是getline，getchar，stringstream的使用了吧。

　　首先介绍这三个函数。

　　1. getline函数

　　　　看意思就是读取一整行，默认是读入到 '\n' 停止，但是也可以手动设置结尾的字符，举个例子

　　　　string line;

　　　　cout<<"please cin a line:"

　　　　getline（cin,line,'#');

　　　　那么当我输入"You are the #best!" 的时候，输入流实际上只读入了"You are the "，#后面的并没有存放到line中（应该是在缓冲区里），那么这个时候输入 '\n' 就不是终结了而是碰到 '#'停止

　　2. getchar函数

　　　　看意思就知道是每次读入一个字符，它能读入换行符 '\n' 。getchar函数只能接受单个字符，输入数字也按字符处理。输入多于一个字符时，只接收第一个字符

　　3. stringstream函数

　　　这个函数一般是用来输入整个文本串（包括多个字符串即多个换行符）然后进行计算的。

那么看了函数，看一下对应的例题吧。一般来说getline和stringstream会一起使用。

例如CSU——2080: 航行日志的修复

Description

作为CSU宇宙军事学院的全A优等生，你不负众望。在你的精确计算和指挥控制下，MACROSS凭借其主炮的强大威力，成功挫败了Zentraedi舰队一次又一次的进攻。指挥室和甲板上传来一阵又一阵的欢呼声，战事也渐趋平静。但就在格罗巴尔将军叼起了他爱用的烟斗，准备下达全舰修整的命令之时，MACROSS的背后突然产生了强烈的时空跳跃反应，大批飞弹迅猛飞来。幸好此刻洛伊·福克正率领统合军Skull大队在返回MACROSS的途中，成功阻拦了大部分飞弹，但还是有部分流弹击穿了装甲，控制室里传来急促的警报声。

此刻你正检查情报系统受损情况并执行修复任务。很幸运，并没有飞弹击穿情报室的装甲，但情报系统仍然出现了严重的紊乱情况，尤其是航行日志已经面目全非。由于航行日志记载着MACROSS战舰及其船员在航行过程中的各项情况，是舰队指挥官决策的一个重要依据，因此需要你立刻修复。

MACROSS的航行日志由自然语言记录，严格符合英文排版规范，每一行文本的末尾不会出现多余的空格。虽然除了英文字母外还可能会存在着标点符号和空格，但标点仅仅只有","和"."两种情形。经过和部分备份日志比对，你惊喜地发现情况并不是十分糟糕。尽管整体上字符的替换毫无规律，但对于英文字母来说，仅仅是向后移动固定位数的循环替换。然而这……似乎并没有多大帮助……

正当一筹莫展之时，一份英文字母频率表在你的眼前调皮的摆动。耳边随即传来那熟悉的银铃般的声音：“嘻嘻~这下你该怎么感谢我呀！”。

“咦，怎么是你？！”

The letter-frequency table on MACROSS

Input

一份出现紊乱的航行日志文本。

Output

经过还原后的原始航行日志文本。

Sample Input

Xly`hld`mzcy`qcpp(`lyo`pgpcjhspcp`sp`td`ty`nsltyd}
Xlyj`l`zyp`mpwtpgpd`stxdpwq`esp`xldepc`zq`zespcd(
lyo`jpe`sp`td`l`rcplepc`dwlgp`esly`espj}
Szh`sld`estd`nslyrp`nzxp`lmzfe}`T`oz`yze`vyzh}
Hsle`nly`xlvp`te`wprtetxlep}`T`mpwtpgp`T`nly`dpeewp`estd`bfpdetzy}

Sample Output

Man was born free, and everywhere he is in chains.
Many a one believes himself the master of others,
and yet he is a greater slave than they.
How has this change come about. I do not know.
What can make it legitimate. I believe I can settle this question.

解题思路：这题很简单，首先读入所有的字符之后然后找到出现频率最高的那个字母，然后用e代替，这时其他的字母同样的向后移动固定位数的循环替换。
这就是要把所有的字符串全部读入之后才能进行处理，这个时候就要用到stringstream，getline函数，这里面getline和cin的效果是一样的。
知道思路做法就很简单了，我读入之后存到queue队列里面，同时处理处出现频率最高的字符，然后跟e比较得到需要移动的数量，然后再从queue依次取出来，将字符对应的加上这个移动的数量就可以得到最后的结果。

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <sstream>
#include <set>
#include <queue>
using namespace std;
const int maxn = 1005;
string s;
int a[26];
int b[100005];
queue<string>v;
char c3[100005];
char c1[26];
char c2[26];
int main()
{
    for (int i = 0; i<26; i++)
    {
        c1[i] = 'a' + i;
        c2[i] = 'A' + i;
    }
    string buf;
    int cnt1 = 0;
    while (cin>>s)
    {
        memset(a, 0, sizeof(a));
        int len = s.length();
        //cout<<len<<endl;
        for (int i = 0; i<len; i++)
        {
            if (s[i] >= 'A'&&s[i] <= 'Z')
            {
                a[s[i] - 'A']++;
                b[cnt1++] = s[i] - 'A';
            }
            if (s[i] >= 'a'&&s[i] <= 'z')
            {
                a[s[i] - 'a']++;
                b[cnt1++] = s[i] - 'a';
            }
        }
        stringstream ss(s);
        while (ss >> buf)
        {
            v.push(buf);
        }
    }
    //cout<<v.size()<<endl;
    int max1 = 0;
    int flag;
    for (int i = 0; i<26; i++)
    {
        if (a[i]>max1)
        {
            max1 = a[i];
            flag = i;
        }
    }
    int cnt;
    cnt = 30 - flag;
    for (int i = 0; i<cnt1; i++)
    {
        b[i] = (b[i] + cnt) % 26;
    }
    //cout<<cnt<<endl;
    int j = 0;
    while(!v.empty())
    {
        string s1 = v.front();
        v.pop();
        //cout<<s1.length()<<endl;
        for (int i = 0; i<s1.length(); i++)
        {
            if (s1[i] >= 'A'&&s1[i] <= 'Z')
            {
                cout << c2[b[j++]];
            }
            if (s1[i] >= 'a'&&s1[i] <= 'z')
            {
                cout << c1[b[j++]];
            }
            if (s1[i] == '`')
                cout << " ";
            if (s1[i] == '(')
                cout << ",";
            if (s1[i] == '}')
                cout << ".";
        }
        cout << endl;
    }
    cout << endl;
    return 0;
}
/**********************************************************************
    Problem: 2080
    User: jk1601zr
    Language: C++
    Result: AC
    Time:0 ms
    Memory:2568 kb
**********************************************************************/

类似于模板的代码就是这样子。

#include <iostream>
#include <string.h>
#include <cstring>
#include <sstream>
#include <queue>
using namespace std;

string s;
queue<string>v;
int main()
{
    string buf;
    while (cin>>s)
    {
        stringstream ss(s);
        while (ss >> buf)
        {
            v.push(buf);
        }
    }

getline函数的应用 UVA 10815 - Andy's First Dictionary

Andy, 8, has a dream - he wants to produce his very own dictionary. This is not an easy task for him, as the number of words that he knows is, well, not quite enough. Instead of thinking up all the words himself, he has a briliant idea. From his bookshelf he would pick one of his favourite story books, from which he would copy out all the distinct words. By arranging the words in alphabetical order, he is done! Of course, it is a really time-consuming job, and this is where a computer program is helpful. You are asked to write a program that lists all the different words in the input text. In this problem, a word is defined as a consecutive sequence of alphabets, in upper and/or lower case. Words with only one letter are also to be considered. Furthermore, your program must be CaSe InSeNsItIvE. For example, words like “Apple”, “apple” or “APPLE” must be considered the same. Input The input file is a text with no more than 5000 lines. An input line has at most 200 characters. Input is terminated by EOF. Output Your output should give a list of different words that appears in the input text, one in a line. The words should all be in lower case, sorted in alphabetical order. You can be sure that he number of distinct words in the text does not exceed 5000.

Sample Input

Adventures in Disneyland Two blondes were going to Disneyland when they came to a fork in the road. The sign read: "Disneyland Left." So they went home.

Sample Output

adventures

blondes

came

disneyland

fork

going

home

left

read

road

sign

the

they

two

went

were

when

这题题意就是很明显了就是你找出所有不同的单词，按字典序大小从小到大输出。

这题其实我们用stringstream同样可以做，但是我觉得getchar好理解一些，

解法：先定义一个空字符串，string s = "";然后每次输入一个字符我们判断是不是字母，如果是字母就进行字符串的加减，然后如果碰到不是字母的字符，我们就把之前的字符串放到set里面，再重新把

字符串s赋值为空串就可以了，那么一遍跑过去我们就知道了，然后再从set里面依次取出来就行了。。

#include<iostream>   
#include<string>   
#include<set>  
using namespace std;
set<string> a;
int main()
{
    string s;
    int i, j, k;
    char c; s = "";
    while ((c = getchar())!=EOF)
    {
        if (c >= 'A'&&c <= 'Z')
        {
            c += 32;
            s += c;
        }
        else if (c >= 'a'&&c <= 'z')
        {
            s += c;
        }
        else
        {
            if (s != "")
            {
                a.insert(s);
            }
            s = "";
        }
    }
    for (set<string>::iterator it = a.begin(); it != a.end(); ++it)
        cout << *it << endl;
    a.clear();
    return 0;
}

那么这题用stringstream同样可以做，做法和上面那题类似。

就直接看代码吧

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<set>
#include<sstream>
using namespace std;
string s,buf;
set<string>dict;
int main()
{
    while(cin>>s)
    {
        int len=s.length();
        stringstream ss;
        for(int i=0;i<len;i++)
        {
            if(isalpha(s[i])) s[i]=tolower(s[i]);
            else s[i]=' ';
        }
        ss<<s;
/*也可以ss.str(s),如果清空ss的内容就用ss.str("")。注意ss.str(s)是覆盖掉ss中原来的东西，而ss<<s是在后面添加上s*/
        while(ss>>buf)//空格都不会传
        {
            dict.insert(buf);
        }
    }
    for(set<string>::iterator it=dict.begin();it!=dict.end();it++)
        cout<<*it<<endl;
    return 0;
}

那么对于字符串还有一些操作：

字符串的复制

函数名: strcpy 功能: 将参数src字符串拷贝至参数dest所指的地址用法: char *strcpy(char *dest, const char *src); 参数是字符数组

#include <stdio.h>
#include <string.h>
int main(void)
 {
    char string[10];
    char *str1 = "abcdefghi";
    strcpy(string, str1);
    printf("%s\n", string);  // 输出：abcdefghi
    return 0;
 }

函数名: strncpy 功能: 将字符串src前n个字符拷贝到字符串dest 用法: char *strncpy(char *dest, const char *src, size_t n);

#include <stdio.h>
#include <string.h>
int main(void)
{
   char string[10];
   char *str1 = "abcdefghi";
   strncpy(string, str1, 3);
   string[3] = '\0';
   printf("%s\n", string);  // 输出：abc
   return 0;
}

字符串比较：

函数名: strcmp 功能: 字符串比较用法: int strcmp(const char *s1, const char *s2);

返回值: 根据ASCII码比较，若参数s1和s2字符串相同则返回0，s1若大于s2则返回大于0的值，s1若小于s2则返回小于0的值

#include <string.h>
#include <stdio.h>
int main(void)
 {
    char *a = "aBcDeF";
    char *b = "AbCdEf";
    char *c = "aacdef";
    char *d = "aBcDeF";
    printf("strcmp(a, b) : %d\n", strcmp(a, b));  // 输出：1
    printf("strcmp(a, c) : %d\n", strcmp(a, c));  // 输出：-1
    printf("strcmp(a, d) : %d\n", strcmp(a, d));  // 输出：0
    return 0;
 }