MENU

刷题总结

刷题总结

这里主要总结刷题时自己不熟悉的代码编程技巧和题目汇总

待完成题目:codeup1942 codeup2064 codeup2066

string类练习:codeup1962 codeup1963


技巧

C语言中的math.h中常用函数:

fabs(double x) //取绝对值函数
floor(double x) //向下取整
ceil(double x) //向上取整
sqrt(double x) //x开方
pow(double r, double p) //r^p次方
log(double x) //返回以自然对数为底的对数
round(double x) //用于x四舍五入

字符串处理

读取和输出一串带有空格的字符串时,可使用fgetsfputs函数,fgets将换行符保留在输入序列中,等同于C++的cin.get(str, len)函数读取一串带有空格的字符串时还可使用getlinegetlinefgets(arr, len, stdin)cin.get(str, len)相区别,getline会将换行符丢弃。

#include <cstdio>
char *fgets(char *s, int size, FILE *stream);
int fputs(const char *s, FILE *stream);

/*应用举例*/
fgets(arr, len, stdin);//把arr字符串输入到标准输入,限制最大长度len
fputs(arr, stdout)     //把arr字符串输出到标准输出


/*对于string类*/
getline(cin, string);  //getline丢弃换行符
/*对于字符数组*/
cin.getline(arr, len); //getline丢弃换行符

STL常用用法

string字符串

#include <string>
string s = "15928140";

/*获取某一行*/
getline(cin, s);



/*string类常用函数*/
s.erase(s.begin()+offset);           //删除从0开始第offset个字符
s.erase(s.begin());                  //5928140
s.erase(s.begin()+3);                //1598140

s.substr(begin_address, str_length); //从begin取 取多少个
s.substr(4, 3);                      //814
s.substr(4, -1);                     //8140从第四个开始截后面所有
s.substr(4, 100);                    //8140

s.length();                          //s字符串的长度,从1开始
s.size();                            //同s.length()



/*string类的迭代器*/
s.begin();             //开始的地址      若取值则*s.begin()
s.end();               //末尾的下一个地址 若取末尾值则*s--.begin()



/*排序*/
sort(s.begin(), s.end());                 //对字符串每位按从小到大排序
sort(s.begin(), s.end(), greater<char>());//对字符串每位从大到小排序



/*循环*/
for(int i = 0; i < s.length(); i++)
    cout << s[i];
cout << endl;

for(string::iterator it=s.begin(); it!=s.end(); it++)
    cout << *it;
cout << endl;

for(auto it=s.begin(); it!=s.end(); it++)
    cout << *it;            //auto C++11标准-std=c++11
cout << endl;

for(auto x:s)
    cout << x;              //auto C++11标准-std=c++11
cout << endl;



/*字符串转整数*/
//方法1
string s = "1234";
stringstream ss; int i;
ss << s;
ss >> i;
cout << i << endl;    //i = 1234

//方法2  c++11中
string s = "1234";
int i = stoi(s);
cout << i << endl;    //i = 1234  -std=c++11

//方法3
#include <cstdlib>
string s = "1234";
int i = atoi(s.c_str());
cout << i << endl;    //i = 1234


/*整数转字符串*/
//方法1
int i = 1234;
stringstream ss; string s;
ss << i;
ss >> s;
//方法2  c++11中 
int i = 1234;
cout << to_string(i) << endl;

vector数组

和string有同样的循环方法,迭代器,迭代器简化(auto),C++11新标准等

/*初始化*/
#include <vector>
vector<int> v;
vector<int> v(4);                     //4个0
vector<int> v(4, 6);                  //4个6

int arr[] = {1, 2, 3, 4, 5};          //通过数组方式初始化vector
vector<int> v(arr, arr+sizeof(arr)/sizeof(arr[0]));
vector<int> v(arr, arr+5);

vector<int> v{1, 2, 3, 4, 5};         // -std=c++11

unordered_map<int, int> m;
m[3] = 20;
m[5] = 31;
m[2] = 66;
vector<pair<int, int> > v(m.begin(), m.end());
//vector中存放map对{{3, 20}, {5, 31}, {2, 66}}



/*vector迭代器*/
v.begin();
v.end();



/*获取元素*/
vector<int> v1{1, 2, 3, 4, 5};        // -std=c++11
cout << v1[1];                        //2
cout << v1.at(1);                     //2 -std=c++11

cout << v1.front();                   //获取v1.begin()处元素
cout << v1.back();                    //获取--v1.end()处元素



/*vector常用函数*/
v1.push_back(2);       //1,2,3,4,5,2   追加
v1.resize(int size);   //resize设置迭代器v1.end()的位置 若大于原来长度 填充0
v1.erase(v1.begin()+n);//从第0号位置开始 删除掉第n个
v1.size();             //从1开始v的大小 表示元素的个数



/*排序*/
sort(v1.begin(), v1.end());                 //从小到大排序
sort(v1.begin(), v1.end(), greater<int>()); //从大到小排序

stack栈

/*stack类定义*/
#include <stack>
stack<int> s;         //栈特点是FILO



/*stack类常用函数*/
s.push(2);
s.top();              //只读取栈最上方元素 不弹出
s.pop();              //弹出栈顶元素
s.size();             //当前栈存放元素个数
s.empty();            //检测是否为空 为空返回1 不空返回0

进制转换中,可以使用stack,将每位放入stack,最后出stack的时候,高位先出。

queue队列

/*queue类定义*/
#include <queue>
queue<int> q;         //队列特点是FIFO



/*queue类常用函数*/
q.push(3);            //把数字3放入队列
q.pop();              //弹出队列首
q.front();            //返回队列首

map(有序)

/*map结构定义*/
#include <map>
map<key_type, value_type> m;
map<int, int> m;



/*初始化*/
m[3] = 222;
m[5] = 31;
m[1] = 97;



/*map常用函数*/
m.begin()->first         //访问第一个map结构的key
m.begin()->second        //访问第一个map结构key对应的value



/*循环打印*/              //map结构按key有序排列
                         //打印的结果为 1 97\n 3 222\n 5 31\n
for(map<int, int>::iterator it=m.begin(); it!=m.end(); it++)
    cout << it->first << " " << it->second << endl;

for(auto x:m)            //x为成员变量 而非指针
    cout << x.first  << " " << x.second << endl;

unordered map(无序)

/*unordered_map结构定义*/
#include <unordered_map>
unordered_map<key_type, value_type> m;

//用法同map


/*unordered_map的排序*/
bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}
int main(){
    unordered_map<int, int> m;
    m[3] = 211;
    m[5] = 985;
    m[1] = 234;
    //需要将unordered_map放入vector中进行排序 而不能直接对unordered_map排序
    vector<pair<int, int> > v(m.begin(), m.end());
    sort(v.begin(), v.end(), cmp);
    for(auto x:v)
        cout << x.first << " " << x.second << endl;
}

set集合

/*set类*/
set<int> s;                 //set集合存放不重复元素
s.insert(3);
s.insert(4);                //set集合无法重复 因此set中仅两个数3, 4
s.insert(4);
s.insert(4);



/*set类常用函数*/
s.insert(num);              //向集合添加元素 重复则无法添加
s.size();                   //集合中未重复元素的个数



/*循环遍历*/
for(set<int>::iterator it=s.begin(); it!=s.end(); it++)
    cout << *it;
for(auto it=s.begin(); it!=s.end(); it++)
    cout << *it;
for(auto x:s)
    cout << x;

deque双端队列

/*初始化*/
#include <deque>
deque<int> d;



/*deque类常用函数*/
d.push_back(3);          //从后插入3 此时队列为3
d.push_back(5);          //从后插入5 此时队列为3 5
d.push_front(2);         //从前插入2 此时队列为2 3 5
d.pop_back();            //将末尾出队
d.pop_front();           //将首部出队


/*排序*/
sort(d.begin(), d.end(), less<int>());
sort(d.begin(), d.end(), greater<int>());

/*循环遍历*/
1. 迭代器遍历
2. 迭代器简化遍历
3. C++11 for(auto x:d)

list链表

/*初始化*/
#include <list>
list<int> l;



/*list常用函数*/
l.push_back(2);         //链表尾插入2
l.push_front(5);        //链表头插入5
l.pop_back();           //弹出链尾元素
l.pop_front();          //弹出链头元素

codeup 2506

题目描述

问题:输入n,输出正倒n层星号三角形。首行顶格,星号间有一空格,效果见样例。

输入样例:

3 

输出样例:

* * *
 * * 
  *
 * * 
* * *

(数据规模 1 <= n <= 50)

#include <stdio.h>
#include <stdlib.h>

int main(){
    int n = 0, flag = 0;
    while(scanf("%d", &n) != EOF){
        for(int i = 0; i < 2*n-1; i++){
            for(int j = 0; j < 2*n-1; j++){
                if(i < n){//打印上半部分三角形
                    if(j < i || j > 2*n-i-2){
                        printf(" ");//打印三角形两边的空白
                    }else if(flag == 0){//三角形间通过flag交替打印*和空格
                            printf("*");
                            flag = 1;
                    }else if(flag == 1){
                            printf(" ");
                            flag = 0;
                    }
                }else{//打印下半部分三角形
                    if(j < 2*n-i-2 || j > i){
                        printf(" ");//打印三角形两边的空白
                    }else if(flag == 0){//三角形间通过flag交替打印*和空格
                            printf("*");
                            flag = 1;
                    }else if(flag == 1){
                            printf(" ");
                            flag = 0;
                    }
                }
            }
            flag = 0;
            printf("\n");
        }
    }
    return 0;
}

code 1928

题目描述

有两个日期,求两个日期之间的天数,如果两个日期是连续的我们规定他们之间的天数为两天。

输入

有多组数据,每组数据有两行,分别表示两个日期,形式为YYYYMMDD

输出

每组数据输出一行,即日期差值

样例输入

20130101
20130105

样例输出

5
#include <cstdio>
#include <iostream>
//判断是闰年则返回1
bool isLeap(int year){
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}
//把小的日期放在前面
void mySwap(int &a, int &b){
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

int main(){
    //平年二月28天  闰年二月29天
    int month[13][2] = {{0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}
                       , {31, 31}, {30, 30}, {31, 31}, {31, 31}
                        , {30, 30}, {31, 31}, {30, 30}, {31, 31}};

    int time1, time2;
    int y1, y2, m1, m2, d1, d2;
    int cnt = 1;
    while(scanf("%d%d", &time1, &time2) != EOF){
        //给较小日期不断++ 知道与较大日期相等 记录经过的天数
        if(time1 > time2)
        mySwap(time1, time2);

        y1 = time1 / 10000;
        y2 = time2 / 10000;

        m1 = time1 % 10000 / 100;
        m2 = time2 % 10000 / 100;

        d1 = time1 % 10000 % 100;
        d2 = time2 % 10000 % 100;

        while(y1 < y2 || m1 < m2 || d1 < d2){
            d1++;
            if(d1 == month[m1][isLeap(y1)] + 1){
                d1 = 1;
                m1++;
            }
            if(m1 == 13){
                m1 = 1;
                y1++;
            }
            cnt++;
        }
        printf("%d\n", cnt);
        cnt = 1;
    }
    return 0;
}

PAT B1009说反话

给定一句英语,要求你编写程序,将句中所有单词的顺序颠倒输出。

输入格式:

测试输入包含一个测试用例,在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成,其中单词是由英文字母(大小写有区分)组成的字符串,单词之间用 1 个空格分开,输入保证句子末尾没有多余的空格。

输出格式:

每个测试用例的输出占一行,输出倒序后的句子。

输入样例:

Hello World Here I Come

输出样例:

Come I Here World Hello

题解:

/*法1*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main(){
    char arr[90];
    char tmp[90][90];
    int cnt1 = 0, cnt2 = 0;//cnt1表示二维数组的第一个参数 cnt2表示第二个参数
    memset(arr, 0, sizeof(arr));
    memset(tmp, 0, sizeof(tmp));
    fgets(arr, 90, stdin);
    //把每个单词逆序放入二位数组中
    for(int i = strlen(arr)-2; i >= 0; i--){
        if(arr[i] != ' '){
            tmp[cnt1][cnt2] = arr[i];
            cnt2++;
        }else{
            cnt1++;
            cnt2 = 0;
        }
    }
    //逆序输出二维数组
    for(int j = 0; j < cnt1+1; j++){
        for(int k = strlen(tmp[j])-1; k >= 0; k--){
            printf("%c", tmp[j][k]);
        }
        if(j != cnt1){
            printf(" ");
        }else{
            printf("\n");//输出的最后结尾不应该是空格,而是换行符
        }
    }
    return 0;
}

/*法2*/
#include <iostream>
#include <sstream>
#include <stack>
using namespace std;

void test(string s){
    stringstream ss;      //stringstream可将空格去掉把每段字符串提取
    stack<string> Stack;  //通过栈逆序打印字符串
    ss << s;
    while(ss >> s)
        Stack.push(s);

    while(!Stack.empty()){
        cout << Stack.top();
        if(Stack.size() != 1)
            cout << " ";
        Stack.pop();
    }
    cout << endl;
}

int main(){
    string s;
    getline(cin, s);     //通过getline丢弃换行符 获取字符串s
    test(s);
    return 0;
}

codeup 1931

题目描述

给出年分m和一年中的第n天,算出第n天是几月几号。

输入

输入包括两个整数y(1<=y<=3000),n(1<=n<=366)。

输出

可能有多组测试数据,对于每组数据,按 yyyy-mm-dd的格式将输入中对应的日期打印出来。

样例输入

2013 60
2012 300
2011 350
2000 211

样例输出

2013-03-01
2012-10-26
2011-12-16
2000-07-29

这一题思路很简单,就是从1月起,如果加上这个月总天数不会超过(<)要求总天数,则不断累加,否则索引值为月份值,总天数-累加和为日,注意:输出年份必须为%04d,否则不能通过

#include <iostream>
#include <cstdio>
using namespace std;
//闰年则返回1
bool isLeap(int year){
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}

int main(){
    int year = 0, day = 0;
    int judge[13][2] = {{0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30},
                    {31, 31}, {30, 30}, {31, 31}, {31, 31}, {30, 30},
                    {31, 31}, {30, 30}, {31, 31}};
    while(scanf("%d%d", &year, &day) != EOF){
        int m = 0, d = 0;
        bool judgeYear = isLeap(year);
        int i, tmp = 0;
        for(i = 1; tmp < day; tmp+=judge[i][judgeYear], i++){};
        m = i - 1;//计算月份
        tmp -= judge[m][judgeYear];//回退至上个月月末
        d = day - tmp;//day-tmp即为下个月多少天 也就是日期中的日
        printf("%04d-%02d-%02d\n", year, m, d);//注意年这里不加%04d是无法通过的
    }
    return 0;
}

codeup 2063

题目描述

设计一个程序能计算一个日期加上若干天后是什么日期。

输入

输入第一行表示样例个数m,接下来m行每行四个整数分别表示年月日和累加的天数。

输出

输出m行,每行按yyyy-mm-dd的个数输出。

样例输入

1
2008 2 3 100

样例输出

2008-05-13

这道题难点在于当月份大于12时,年份++的时候需要判断新的一年是否为闰年,这个点易被遗漏。

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

bool isLeap(int year){
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}

int main(){
    int arr[2][13]={{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
                   ,{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
    int n;
    scanf("%d", &n);
    int y, m, d, afterday;
    while(n--){
        scanf("%d%d%d%d", &y, &m, &d, &afterday);
        bool judgeYear = isLeap(y);
        while(afterday--){
            d++;
            if(d > arr[judgeYear][m]){
                d = 1;
                m++;
            }
            if(m > 12){
                m = 1;
                y++;
                judgeYear = isLeap(y);//容易被遗漏的点!注意
            }
        }
        printf("%04d-%02d-%02d\n", y, m, d);
    }
    return 0;
}

codeup 1941

题目描述

输入两个不超过整型定义的非负10进制整数A和B(<=2^31-1),输出A+B的m (1 < m < 10)进制数。

输入

输入格式:测试输入包含若干测试用例。每个测试用例占一行,给出m和A,B的值。当m为0时输入结束。

输出

输出格式:每个测试用例的输出占一行,输出A+B的m进制数。

样例输入

2 4 5
8 123 456
0

样例输出

1001
1103

提示:注意输入的两个数相加后的结果可能会超过intlong的范围。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main(){
    int m, cnt = 0;
    long int a, b; //oj中int按16位算,题目要求知a, b需要long int
    unsigned long sum = 0;//两个long int之和最大为64位,可以用unsigned long接收或者用long long接收
    int arr[70];
    while(scanf("%d", &m)!=EOF){
        if(!m)
            break;
        scanf("%ld%ld", &a, &b);
        sum = a + b;
        int i = 0;
        do{
            arr[i] = sum % m;
            i++;
            sum /= m;
        }while(sum != 0);
        //逆序打印
        for(int j = i-1; j >= 0; j--){
            printf("%d", arr[j]);
        }
        printf("\n");
    }
    return 0;
}

codeup 1962 (string类的应用)

题目描述

输入一个字符串,以回车结束(字符串长度<=100)。该字符串由若干个单词组成,单词之间用一个空格隔开,所有单词区分大小写。现需要将其中的某个单词替换成另一个单词,并输出替换之后的字符串。

输入

多组数据。每组数据输入包括3行,
第1行是包含多个单词的字符串 s,
第2行是待替换的单词a,(长度<=100)
第3行是a将被替换的单词b。(长度<=100)
s, a, b 最前面和最后面都没有空格。

输出

每个测试数据输出只有 1 行,
将s中所有单词a替换成b之后的字符串。

样例输入

I love Tian Qin
I
You

样例输出

You love Tian Qin

思路:

首先题目的描述是要我们找出一个字符串中出现的所有满足条件的单词,这里要进行字符串的查找,用C++操作更加方便,直接while循环加上find函数就可以查找了。但直接用题目里给的单词进行查找就有个弊端,如果你要将you替换为me,在主串中如果有your这个单词就会被替换成mer,就不符合条件了,所以这里做了一个经典的改动,将所有的输入都在开头和结尾加了空格,这样在进行子串的查找时就不会出现上述情况了,在输出时利用erase函数将开头结尾去掉就可以了.

//法1
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main(){
    string input;
    string find_word;
    string overwrite_word;

    while(getline(cin, input)){
        getline(cin, find_word);
        getline(cin, overwrite_word);

        input = " " + input + " ";
        find_word = " " + find_word + " ";
        overwrite_word = " " + overwrite_word + " ";
        int pos = 0;
        while((pos = input.find(find_word)) != string::npos){
            //find_word在字符串中
            //当find(str)函数未找到字符串时返回string::npos
            input.replace(pos, find_word.size(), overwrite_word);
            //replace(pos, len, str); 从pos开始长度为len的字符串替换为str
        }

        //删除字符串首尾的空格
        //erase(pos, length);删除从pos开始长度为length的字符串
        input.erase(0, 1);
        input.erase(input.size()-1, 1);
        cout << input << endl;
    }
    return 0;
}


//法2
/* 将每个单词入队列,然后匹配队列单词 如果查找到 则替换 */
#include <iostream>
#include <queue>
#include <sstream>
using namespace std;

int main(){
    queue<string> q;
    string str;
    while(getline(cin, str)){
        stringstream ss;
        ss << str;
        string tmp1, tmp2;    //tmp1为要查找的 tmp2为要替换的
        getline(cin, tmp1);
        getline(cin, tmp2);
        while(ss >> str){
            if(tmp1 == str){
                q.push(tmp2);
            }else{
                q.push(str);
            }
        }

        while(!q.empty()){
            if(q.size() != 1){
                cout << q.front() << " ";
            }else{
                cout << q.front() << endl;
            }
            q.pop();
        }
    }
    return 0;
}

codeup 1963

题目描述

输入字符串s和字符c,要求去掉s中所有的c字符,并输出结果。

输入

测试数据有多组,每组输入字符串s和字符c。

输出

对于每组输入,输出去除c字符后的结果。

样例输入

goaod
a

样例输出

good
//法1:
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

int main(){
    string str;
    string del_word;
    while(getline(cin, str)){
        getline(cin, del_word);
        int pos;
        while((pos = str.find(del_word)) != string::npos){
            str.erase(pos, 1);
        }
        cout << str << endl;
    }
    return 0;
}

//法2
/* 遍历字符串 对特定字符erase */
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    string str;
    while(getline(cin, str)){
        string c;
        getline(cin, c);
        for(string::iterator it=str.begin(); it!=str.end(); it++){
            if(c[0] == *it){
                str.erase(it);
                it--;
            }
        }
        for(string::iterator it=str.begin(); it!=str.end(); it++){
            cout << *it;
        }
        cout << endl;
    }
    return 0;
}

codeup 1967

题目描述

输入一个字符串,长度小于等于200,然后将数组逆置输出。

输入

测试数据有多组,每组输入一个字符串。

输出

对于每组输入,请输出逆置后的结果。

样例输入

tianqin

样例输出

niqnait

提示:注意输入的字符串可能会有空格。
补充:如果用scanf读入带有空格的字符串,则会变成两个字符串,所以此处可以使用getline函数,不能使用fgets是因为会将换行符写入字符串数组中。

对于字符数组

方法一:cin.getline(str, len)
读入整行数据,使用回车键输入的换行符来确定输入结尾。第一个参数str用来存储输入行的数组名称,第二个参数是要读取的字符数。

对于string类

方法一:getline(cin, str)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

int main(){
    char arr[201];
    //获取一行字符串直到遇到回车符 并丢弃回车符 将字符串读入arr
    while(cin.getline(arr, 202)){
        int len = strlen(arr);
        for(int i = len - 1; i >= 0; i--){
            printf("%c", arr[i]);
        }
        printf("\n");
    }
    return 0;
}

codeup 1782

题目描述

“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男,你发现自己与他人相互了解的机会 并不太多。幸运的是,你意外得到了一份北大图书馆的图书借阅记录,于是你挑灯熬夜地编程,想从中发现潜在的朋友。首先你对借阅记录进行了一番整理,把N个读者依次编号为1,2,…,N,把M本书依次编号为1,2,…,M。同时,按照“臭味相投”的原则,和你喜欢读同一本书的人,就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。

输入

每个案例第一行两个整数N,M,2 <= N ,M<= 200。接下来有N行,第i(i = 1,2,…,N)行每一行有一个数,表示读者i-1最喜欢的图书的编号P(1<=P<=M)

输出

每个案例包括N行,每行一个数,第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书,则输出“BeiJu”(即悲剧,^ ^)

样例输入

4 5
2
3
2
1

样例输出

1
BeiJu
1
BeiJu

分析

该题使用两个数组bookperson,其中book的角标代表图书编号,book[i]中存放同一编号的书籍重复的个数;person的角标代表顺序,最后输出是通过遍历person数组,然后person中存放的值为图书编号

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int main(){
    int n, m;
    int personNum[202];
    int bookNum[202];

    while(scanf("%d%d", &n, &m) != EOF){
        memset(personNum, 0, sizeof(personNum));
        memset(bookNum, 0, sizeof(bookNum));

        int tmp;
        for(int i = 1; i <= n; i++){
            //核心代码
            scanf("%d", &tmp);
            bookNum[tmp]++;
            personNum[i] = tmp;
        }

        //遍历
        for(int i = 1; i <= n; i++){
            if(bookNum[personNum[i]] > 1)
                printf("%d\n", bookNum[personNum[i]]-1);
            else
                printf("BeiJu\n");
        }
    }

    return 0;
}

codeup 2044(递归 DP问题)

题目描述

有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。

输入

输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。

输出

输出不同的选择物品的方式的数目。

样例输入

2
12
28
3
21
10
5

样例输出

1
0

思路

DP问题,等式DP[w][i] = DP[w][i-1] + DP[w-kg[i]][i-1];每次分为取第i个与不取第i个两种,取第i个则减去体积kg[i]。

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

int kg[25];

int func(int w, int i){
    if(w < 0)
        return 0;
    if(w == 0)
        return 1;
    if(i <= 0)
        return 0;
    //取第i个与不取第i个两种 取出则减去体积kg[i]
    return func(w, i-1) + func(w-kg[i], i-1);
}

int main(){
    int n;
    while(scanf("%d", &n) != EOF){
        for(int i = 1; i <= n; i++){
            scanf("%d", &kg[i]);
        }
        printf("%d\n", func(40, n));
    }
    return 0;
}

codeup 5972 递归全排列(不采用递归 直接STL标准库函数)

题目描述

排列与组合是常用的数学方法。先给一个正整数 ( 1 < = n < = 10 ),例如n=3,所有组合,并且按字典序输出:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

输入

输入一个整数n( 1<=n<=10)

输出

输出所有全排列,每个全排列一行,相邻两个数用空格隔开(最后一个数后面没有空格)

样例输入

3

样例输出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

组合数学中经常用到排列,这里介绍一个计算序列全排列的函数:next_permutation(start,end),和prev_permutation(start,end)。这两个函数作用是一样的,区别就在于前者求的是当前排列的下一个排列,后一个求的是当前排列的上一个排列。至于这里的“前一个”和“后一个”,我们可以把它理解为序列的字典序的前后,严格来讲,就是对于当前序列pn,他的下一个序列pn+1满足:不存在另外的序列pm,使pn<pm<pn+1.

#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
    int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int n;
    scanf("%d", &n);
    do{
        int i;
        for(i = 0; i < n-1; i++){
            printf("%d ", arr[i]);
        }
        printf("%d\n", arr[i]);
        //这部分是精华 记模板
    } while(std::next_permutation(arr, arr+n));

    return 0;
}

codeup 1959 全排列(字符串)

题目描述

给定一个由不同的小写字母组成的字符串,输出这个字符串的所有全排列。我们假设对于小写字母有'a' < 'b' < ... < 'y' < 'z',而且给定的字符串中的字母已经按照从小到大的顺序排列。

输入

输入有多组,每次输入只有一行,是一个由不同的小写字母组成的字符串,已知字符串的长度在1到6之间。

输出

输出这个字符串的所有排列方式,每行一个排列。要求字母序比较小的排列在前面。字母序如下定义:
已知S = s1s2...skT = t1t2...tk,则S<T等价于存在p(1<=p<=k),使得s1 = t1,s2 = t2,...,sp-1 = tp-1,sp < tp成立。

注意每组样例输出结束后接一个空行。

样例输入

xyz

样例输出

xyz
xzy
yxz
yzx
zxy
zyx

提示

用STL中的next_permutation会非常简洁。

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

int main(){
    string s;
    while(cin >> s){
        do{
            cout << s << endl;
        }while(next_permutation(s.begin(), s.end()));
        cout << endl;
    }

    return 0;
}

codeup 2046(八皇后问题 递归)

题目描述

会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。对于某个满足要求的8皇后的摆放方法,定义一个皇后串a与之对应,即a=b1b2...b8,其中bi为相应摆法中第i行皇后所处的列数。已经知道8皇后问题一共有92组解(即92个不同的皇后串)。给出一个数b,要求输出第b个串。串的比较是这样的:皇后串x置于皇后串y之前,当且仅当将x视为整数时比y小。

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数b(1 <= b <= 92)

输出

输出有n行,每行输出对应一个输入。输出应是一个正整数,是对应于b的皇后串。

样例输入

3
6
4
25

样例输出

25713864
17582463
36824175

补充

fill_n(array, offset, number)函数包含在algorithm头文件中,可以实现对array数组在offset偏移内的空间全部填充为number。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define COL 8
#define LINE 8

int place[LINE];//指每行第几位是皇后 如place[2] = 5;指第三行第六个位置
bool flag[COL];//某一列是否可占 1表示可用 0表示不可用
bool d1[15];//主对角线 d1[行号-col+7]
bool d2[15];//副队绞线 d2[行号+col]
int cnt = 0;//用来记录生成的第几次结果

void generate();
void print();


//n表示行号 从第0行开始
void generate(int n, int number){
    int col;
    for(int col = 0; col < 8; col++){
        //判断位置是否可占用 是否用冲突
        if(flag[col] &&  d1[n-col+7] && d2[n+col]){
            //宣布占用
            place[n] = col;
            flag[col] = false;
            d1[n-col+7] = false;
            d2[n+col] = false;

            if(n < 7)
                generate(n+1, number);
            else{
                cnt++;
                if(cnt == number)
                    print(); //棋盘占满 直接打印
            }

            //回溯 考虑其他方案
            flag[col] = true;
            d1[n-col+7] = true;
            d2[n+col] = true;
        }
    }
}

void print(){
    int arr[8][8];
    for(int i = 0; i < 8; i++){
        arr[i][place[i]] = place[i] + 1;
    }
    for(int i = 0; i < 8; i++){
        printf("%d", arr[i][place[i]]);
    }
    printf("\n");
}

int main(){
    int number, n;
    scanf("%d", &n);
    while(n--){
        scanf("%d", &number);
        fill_n(flag, COL, 1);
        fill_n(d1, 15, 1);
        fill_n(d2, 15, 1);
        generate(0, number);
        cnt = 0;
    }
    return 0;
}

codeup 2911 (n皇后问题)

题目描述

在一个N x N的国际棋盘上,放置N个皇后,使她们相互之间不能进攻(任意两皇后不能位置同一行、同一列、同一斜线)。因为每行只有一个皇后,我们可以用一行N个数值来表示N*N棋盘上皇后位置。结果中第i列的数值j表示棋盘上第[i,j]位置上有一个皇后。

2 4 6 1 3 5 表示棋盘上第[1,2]、[2,4]、[3,6]、[4,1]、[5,3]、[6,5]位置上有一个皇后。

输入

N( 6 ≤ N ≤ 13 )

输出

前三行为先得到的三组解,每组解为N个数,之间用空格隔开。最后一行为总解数。

样例输入

6

样例输出

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4 
#include <iostream>
#include <cstdio>
using namespace std;

//n皇后问题
#define MAX_NUM 13
int place[MAX_NUM];

bool flag[MAX_NUM];
bool d1[2*MAX_NUM - 1];
bool d2[2*MAX_NUM - 1];

int cnt = 0;
void print(int);
void generate(int, int);

//startline为行号 n为n皇后的意思 即棋盘最大边距
void generate(int startline, int n){
    int col;
    for(col = 0; col <= n; col++){
        if(flag[col] && d1[startline-col+n] && d2[startline+col]){ //如果可占用
            place[startline] = col;
            flag[col] = false;
            d1[startline-col+n] = false;
            d2[startline+col] = false;

            if(startline < n){
                generate(startline+1, n);
            }else{
                cnt++;
                if(cnt <= 3){
                    print(n);
                }
            }

            //回溯
            flag[col] = true;
            d1[startline-col+n] = true;
            d2[startline+col] = true;
        }
    }
}

void print(int n){
    int i;
    for(i = 0; i < n; i++){
        printf("%d ", place[i]+1);
    }
    printf("%d\n", place[i]+1);
}

int main(){
    fill_n(flag, MAX_NUM, 1);
    fill_n(d1, 2*MAX_NUM - 1, 1);
    fill_n(d2, 2*MAX_NUM - 1, 1);

    int n;
    scanf("%d", &n);

    generate(0, n-1);
    printf("%d\n", cnt);

    return 0;
}
最后编辑于: March 21, 2020
Archives Tip
QR Code for this page
Tipping QR Code