875程序设计题

2014

1.进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
/*
给定N个数据 将每一个数据转成二进制形式
某种意义上说 取几进制 就将内部的2换成对于进制就可以了
*/
int main()
{
    int N;cin >> N;
    while(N--){
        int x;cin >> x;
        vector<int>vi;
        while(x){
            if(x%2==1) vi.push_back(1);
            else vi.push_back(0);
            x/=2;
        }
        for(int i = vi.size()-1;i>=0;i--){
            cout << vi[i];//逆序输出
        }
        cout << "\n";
    }
    return 0;
}

2.判断回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
/*
判断回文串
*/
int main()
{
    string s;cin >> s;
    int sz = s.size();
    for(int i = 0;i<sz;i++){
        if(s[i]!=s[sz-i-1]) {
            printf("false");
            return 0;
        }
    }
    printf("true");
    return 0;
}

3.图书管理系统

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
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
/*
给定一个三十个大小的结构体
然后在要求动态变化之后 重新根据里面的规则进行排序
动态变化的过程可以暴力查找   注意结构体的运用 尤其是赋值和键值对方面
*/
struct book{
    string name;
    int num;// 库存
    double price;//单价
    int sale;// 销量 
};
// 买书的逻辑是 库存减一 销量加一 最后根据销量降序排列
vector<book> vb;
map<string,book>lib;//这样可以根据输入的名字进行卖书 然后放入vb中进行排序

bool cmp(book a,book b){
    return a.sale > b.sale;
}

int main()
{
    book tmp;
    tmp.name = "jww";
    tmp.num = 10;
    tmp.sale = 0;
    lib["jww"]=tmp;
    
    tmp.name = "wyl";
    tmp.num = 10;
    tmp.sale = 0;
    lib["wyl"] = tmp;

    tmp.name = "ww";
    tmp.num = 10;
    tmp.sale = 20;
    lib["ww"] = tmp;

    string s;
    while(cin >> s){
        // 这是卖书的名字 按照卖书逻辑来
        lib[s].num--;
        lib[s].sale++;
    }
    for(auto i = lib.begin();i!=lib.end();i++){
        vb.push_back(i->second);
    }
    sort(vb.begin(),vb.end(),cmp);
    for(int i = 0;i<vb.size();i++){
        cout << vb[i].name <<"\n";
    }
    
    return 0;
}

2015

1.矩阵对角线元素之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
/*

*/

int main()
{
    long long sum = 0;
    int n;cin >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;;j<n;j++){
            int x;
            cin >> x;
            if(i==j) sum += x;
        }
    }
    cout << x;
    return 0;
}

2.统计字符个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
/*
统计数字字符 字母字符 和其他字符的个数
*/

int main()
{
   string s;
   int num=0,alp=0,other=0;
   
   getline(cin,s);// 输入一整行
   for(int i = 0;i<s.size();i++){
       char t = s[i];
       if(t>='0' && t<='9') num++;
       else if((t>='A' && t<='Z') || (t>='a' && t <= 'z')) alp++;
       else other++;
   }
   printf("数字:%d, 字母:%d, 其他:%d",num,alp,other);
    return 0;
}

3.单链表统计出现个数

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
#include <bits/stdc++.h>
using namespace std;
/*
给定单链表 求出等于给定值x的节点数
*/

struct node{
    int val;
    node* next;
    node(int x):val(x),next(NULL){}
};

int main()
{
    node* head = new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    
    int x;cin >> x;
    node*p = head;
    int num = 0;
    while(p){
        // cout << p->val <<"\n";
        if(p->val==x) num++;
        p = p->next;
    }
    cout << num;
    return 0;
}

4.候选人投票

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
/*
有m个选举人 n个候选人 输入所有得票的候选人名字 要求输出候选人得票结果
*/

int main()
{
    int n,m;cin >> n>>m;
    map<string, int> mp;
    while(n--){//这里是候选人名单
        string s;cin >> s;
        mp[s] = 0;
    }
    while(m--){
        string s;cin >> s;
        mp[s] ++;
    }
   for(auto i = mp.begin();i!=mp.end();i++){
       cout << i->first <<" "<<i->second <<"\n";
   }
    return 0;
}

2016

1.剔除数字字符 保留剩余字符

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
/*
剔除数字字符 保留剩余字符
*/

int main()
{
    string s,temp;cin >> s;
    for(int i = 0;i<s.size();i++){
        if(s[i]>='0' && s[i]<='9');
        else temp += s[i];
    }
    s = temp;// 这样可以保证将新字符也在原空间 但是用到了辅助数组
    return 0;
}

2.统计各位数上等于x的数字数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
/*
统计各位数上等于x的数字数目
*/

int main()
{
    int n;cin >> n;
    while (n--){
        string s;int x;
        cin >> s >> x;
        if(x>=10 || x<0) {
            printf("参数越界");
            continue;
        }
        int num = 0;
        for(char t : s){
            if(t == x + '0') num++;
        }
        cout << num <<"\n";
    }
    return 0;
}

2017

1.最大区间不相容问题 给定区间范围 求出不相容的最大区间个数

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
// 贪心思路 结构体排序
// 贪心的思路为每次保证选的区间右边都是最小的这样就相当于每个区间都给写一个区间留够了空间
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct area{
    ll left,right;
};

// 每次应该选择右端点最小的 这样才会符合贪心的思想
bool cmp(area a, area b){
    if(a.right != b.right) return a.right < b.right;
    return a.left < b.left;
}

int main(){
    int N;cin >> N;
    vector<area> va;
    while(N--){
        area t;
        cin >> t.left >> t.right;
        va.push_back(t);
    }
    sort(va.begin(),va.end(),cmp);
    
    // 只需要维护一个最右边界即可
    ll l = -1e10;
    int sm = 0;
    for(int i = 0;i<va.size();i++){
        // cout << va[i].left << " "<< va[i].right <<"\n";
        if(va[i].left > l ){
            l = va[i].right;
            sm ++;
        }   
    }
    cout << sm;
}

2018

1.输入几行字符串,以#结尾,统计每个字符串0-9的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
/*

*/

int main()
{
    string s;
    while(getline(cin,s)){
        map<char,int> mp;
        for(char t: s){
            if(t=='#') break;
            mp[t]++;
        }
        for(char c = '0';c<='9';c++){
            cout << c <<" "<<mp[c] <<"\n";
        }
    }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
/*
结构体排序 分数相同要求保持相对不变 即稳定排序
可以手动设置一个变量 计输入的顺序
*/

struct stu{
    int grade;
    string name;
    int pos;//输入的顺序 用于固定稳定排序
};
vector<stu>vs;
bool cmp(stu a,stu b){
    if(a.grade != b.grade) return a.grade > b.grade; //分数降序
    return a.pos < b.pos;// 位置保持不变
}

int main()
{
    int p = 1;
    int lim;cin >> lim;// 输入的数据大小
    while(lim--){
        stu t;
        cin >> t.name >> t.grade;
        t.pos = p++;
        vs.push_back(t);
    }

    sort(vs.begin(),vs.end(),cmp);
    for(int i = 0;i<vs.size();i++){
        cout << vs[i].name <<" " << vs[i].grade << "\n";
    }
    return 0;
}

3.计算日期

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
/*
输入年月日 计算该天是本年的第几天
提前存储每个月的天数 可以使用前缀和 然后需要判断闰年
*/

int main()
{
    int y,m,d;cin >> y >> m >> d;
    int f=0;// 判断是否是闰年
    if(y%4==0 && y%100!=0) f = 1;
    /*
    31 28 31 30   31 30 31 31 30 31 30 31
    */
    int mou[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//这代表的是本月的天数 不包含本月
    int sum = d;
    for(int i = 1;i<m;i++) sum += mou[i];
    if(m>2 && f) sum++;
    cout << sum;
    return 0;
}

4.分组问题 n个球放m个盒子,求多少种装法

组合数3个性质

  1. \(C_n^r = C_n^{n-r}\) 从n个元素 从n个元素中拿出r个,等价于从n个元素丢掉n-r个

  2. \(C_n^r = C_{n-1}^{r}+C_{n-1}^{r-1}\) 帕斯卡公式,可以用DP思路证明,取或者不取第n个元素:

    若取第n个元素,则在剩下的n-1个元素中选r-1个;

    若不取第n个元素,则在剩下的n-1个元素中选r个

    可以用于构造杨辉三角

  3. \(C_n^0+C_n^1+C_n^2+...+C_n^n = 2^n\)

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
46
47
48
#include <bits/stdc++.h>
using namespace std;
/*
n个球 m个盒子 将球放到盒子中 盒子可以空
盒子和球都是相同的 求可以划分的方案数
因为盒子和球相同 故1 2 3和3 2 1是相同的
换句话说当确定升序之后 数字不能完全等同
就是将整数n分成m个非递减序列
分析一下5 3的情况 5个球分3个盒子中
0 0 5
0 1 4
0 2 3
1 1 3
1 2 2
我们假设dp[i][j]为有i个球放进j个盒子中
那我们可以将上述的案例划分成两种情况,第一个元素是否为空
像前三种 假如第一个盒子为空 也就转换成dp[i][j-1]也就是 将i个球放进后面j-1的空间
关键在于假如第一个元素不为空怎么办 我们也可以像上面考虑 
第一个放1个球 然后剩下的球放进后面的盒子中 也就是dp[i-1][j-1]
这样貌似是合理的 但是假如这个球有很多呢 我们怎么就可以保证第一个位置就放一个球呢
我们当然是保证不了的 但是我们发现了一个规律 所有的盒子里面都有球! 
都有球的含义就是 就算每个盒子都拿走一个球也不会影响状态数 
这个就和鸽巢原理有些异曲同工的作用 而将每一个盒子都拿走一个球之后
我们发现就可以转变成共有i-j个球 放进j个盒子中 故为dp[i-j][j]
因此 最终的状态方程为 dp[i][j] = dp[i][j-1] + dp[i-j][j]
*/

int main()
{
    int n,m;cin >> n >> m;
    int dp[105][105];
    for(int i = 0;i<100;i++){// 当转移到只有一个盒子时 情况数为1
        dp[i][1] = 1;
        // 没球也是1 没盒子就是0 
        dp[0][i] = 1;
    }
    for(int i = 1;i<=n;i++){//n个球
        for(int j = 1;j<=m;j++){
            if(i>=j) { // 球比盒子多
                dp[i][j] = dp[i][j-1] + dp[i-j][j];
            }else{//盒子比球多 盒子都是一样的 实际上是浪费的 只需要和球相同的盒子即可
                dp[i][j] = dp[i][i];
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

https://www.luogu.com.cn/problem/P1025

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
#include <bits/stdc++.h>
using namespace std;
/*

假如要保证每个盒子都有球 也很简单 先把球给扣下来 剩下的球再像这样分配
*/

int main()
{
    int n,m;cin >> n >> m;
    if(n>=m) n-=m;// 有足够的球扣下来
    else {
        cout << 0;
        return 0;
    }
    int dp[305][105];
    for(int i = 0;i<100;i++){// 当转移到只有一个盒子时情况数为1
        dp[i][1] = 1;
        // 没球也是1 没盒子就是0 
        dp[0][i] = 1;
    }
    for(int i = 1;i<=n;i++){//n个球
        for(int j = 1;j<=m;j++){
            if(i>=j) { // 球比盒子多
                dp[i][j] = dp[i][j-1] + dp[i-j][j];
            }else{//盒子比球多 盒子都是一样的 实际上是浪费的 只需要和球相同的盒子即可
                dp[i][j] = dp[i][i];
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

2019

1.覆盖点集 输出一个长方形左上角和右下角坐标 要求可以覆盖所有点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
using namespace std;
/*

假如要保证每个盒子都有球 也很简单 先把球给扣下来 剩下的球再像这样分配
*/

int main()
{
   int ax=100000,ay=0,bx=0,by=100000;
   int x,y;
   while(cin >> x >> y){
       if(x == 0 && y==0) break;
       ax = min(ax,x);
       ay = max(ay,y);
       bx = max(bx,x);
       by = min(by,y);
   }
   cout << ax << " " <<ay<<"\n";
   cout << bx << " "<<by<<"\n";
    return 0;
}

2.回文串分别使用递归和非递归实现检测回文串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
/*
检测回文串
*/

bool isRes(string s){
    if(s.size()<=1) return true;
    if(s[0]==s.back()){
        return isRes(s.substr(1,s.size()-2));
    }else return false;
}

int main()
{
    string s;getline(cin,s);
    bool pb = isRes(s);
    cout << pb;
    return 0;
}

3.逆序对数量

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
#include <bits/stdc++.h>
using namespace std;
/*
给定n个大小的数组 判断数组中逆序对的个数
1.暴力跑 O(n^2)
*/

int main()
{
    int n;cin >> n;
    vector<int> vi;
    for(int i = 0;i<n;i++){
        int x;cin >> x;
        vi.push_back(x);
    }
    int num = 0;
    for(int i = 0;i<n;i++){
        for(int j = i+1;j<n;j++)
        {
            if(vi[i]>vi[j]) num++;
        }
    }
    cout << num;
    return 0;
}

2020

1.数字排列 找到abcd+cadb = 7856的abcd数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
/*
找到abcd+cadb = 7856的abcd数字
*/

int main()
{
    for(int a = 0;a<=9;a++)
        for(int b = 0;b<=9;b++)
            for(int c = 0;c<=9;c++)
                for(int d = 0;d<=9;d++){
                    if(a*1000+b*100+c*10+d==c*1000+a*100+d*10+b){
                        cout << a << b << c << d <<"\n";
                    }
                }
    return 0;
}

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
#include <bits/stdc++.h>
using namespace std;
/*
找到abcd+cadb = 7856的abcd数字
*/

// 直接反转之后返回一个数字好了
int itos(int a){
    int s=0;
    while(a!=0){
        int t = a%10;
        s = s*10 + t;
        a/=10;
    }
    return s;//自动是倒叙的
}

int main()
{
    int n;cin >> n;
    while (n--){
        int a,b;cin >> a >> b;
        int c = a+b;
        a = itos(a);
        b = itos(b);
        int d = a+b;
        if(itos(d)==c) cout <<"yes\n";
        else cout <<"no\n";
    }
    return 0;
}
专业课 > 数据结构 > 程序设计
#专业课 #真题 #程序设计
875程序设计题
https://rain_dew.gitee.io/2024/10/09/专业课/数据结构/程序设计题/真题/
Author
Wang yulu
Posted on
October 9, 2024
Licensed under