山东大学计算机科学与技术学院程序设计思维与实践作业_山东大学c++旅途不止

作业

H1

A : 打酱油

问题描述

小明带着N元钱去买酱油。酱油10块钱一瓶，商家进行促销，每买3瓶送1瓶，或者每买5瓶送2瓶。请问小明最多可以得到多少瓶酱油。

输入格式

输入的第一行包含一个整数N，表示小明可用于买酱油的钱数。N是10的整数倍，N不超过300。

输出格式

输出一个整数，表示小明最多可以得到多少瓶酱油。

样例1

输入

40

输出

5

样例说明

把40元分成30元和10元，分别买3瓶和1瓶，其中3瓶送1瓶，共得到5瓶。

样例2

输入

80

输出

11

样例说明

把80元分成30元和50元，分别买3瓶和5瓶，其中3瓶送1瓶，5瓶送2瓶，共得到11瓶。

代码：

#include<iostream>
using namespace std;
​
int main(){
    int N=0,M=0;
    cin>>N;
    while(N>=50){
        N-=50;
        M+=7;
    }
    while(N>=30){
        N-=30;
        M+=4;
    }
    while(N>=10){
        N-=10;
        M+=1;
    }
    cout<<M<<endl;
    return 0;
}

B : 最小差值

问题描述

给定n个数，请找出其中相差（差的绝对值）最小的两个数，输出它们的差值的绝对值。

输入格式

输入第一行包含一个整数n。 第二行包含n个正整数，相邻整数之间使用一个空格分隔。

输出格式

输出一个整数，表示答案。

样例1

输入

5
1 5 4 8 20

输出

1

样例说明

相差最小的两个数是5和4，它们之间的差值是1。

样例2

输入

5
9 3 6 1 3

输出

0

样例说明

有两个相同的数3，它们之间的差值是0.

数据规模和约定

对于所有评测用例，2 ≤ n ≤ 1000，每个给定的整数都是不超过10000的正整数

代码：

#include<iostream>
using namespace std;

int main(){
    int n  =0, x = 0, result = 0;
    cin>>n;
    int *num = new int[n];
    for(int i = 0; i < n; i++)
        cin>>num[i];
    result =abs(num[0] - num[1]);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < i; j++){
            x = num[i] - num[j];
            x = abs(x);
            result = min(x,result);
        }
    }
    cout<<result;
    return 0;
}

H2

A : 相邻数对

问题描述

给定 n 个不同的整数，问这些数中有多少对整数，它们的值正好相差 1。

输入格式

输入的第一行包含一个整数 n，表示给定整数的个数。 第二行包含所给定的n个整数。

输出格式

输出一个整数，表示值正好相差1的数对的个数。

样例输入

6
10 2 6 3 7 8

样例输出

3

样例说明

值正好相差1的数对包括 (2, 3), (6, 7), (7, 8)。

评测用例规模与约定

1≤n≤1000，给定的整数为不超过 10000的非负整数。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int cnt = 0;
    int *num = new int[n];
    for(int i = 0; i < n; i++){
        cin>>num[i];
    } //O(n)
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(num[i] - num[j] == 1 || num[j] - num[i] ==1){
                cnt++;
            }

        }
    } //O(n^2)
    cout<<cnt<<endl;
    return 0;
}

B : 门禁系统

问题描述

涛涛最近要负责图书馆的管理工作，需要记录下每天读者的到访情况。每位读者有一个编号，每条记录用读者的编号来表示。给出读者的来访记录，请问每一条记录中的读者是第几次出现。

输入格式

输入的第一行包含一个整数n，表示涛涛的记录条数。 第二行包含n个整数，依次表示涛涛的记录中每位读者的编号。

输出格式

输出一行，包含n个整数，由空格分隔，依次表示每条记录中的读者编号是第几次出现。

样例输入

5
1 2 1 1 3

样例输出

1 1 2 3 1

评测用例规模与约定

1≤n≤1000，读者的编号为不超过 n的正整数。

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a;
    int num[1001] = {0};
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a;
        num[a]++;
        cout<<num[a]<<" ";
    } //O(n)
    return 0;
}

C : 桶装数字

问题描述

yhf有 n个桶，每个桶里都装着一些数字（一个或多个），所有的数字总共有 m个。这天，lzh把yhf所有的桶全打翻了，数字洒了一地！所幸，每个数字都有它所在的桶的标记。yhf希望恢复所有的桶，但是他还要刷考研题目，于是他拜托你来完成这个任务。 由于yhf能在一秒内完成一套考研数学题，因此他希望你的程序能在一秒内得出结果。

输入格式

第一行输入两个整数 n,m，第二行到第 m+1 行，每行两个整数 x,t，分别表示这个数字和它所在的桶。 保证每个桶至少含有一个数字。

输出格式

输出 n 行，若第 i个桶含有 ki个数字，则第 i行输出 ki个整数，表示这个桶内的数字。注意：输出每个桶的数字时应按升序排序输出。

样例输入

2 5
3 1
2 2
2 1
3 2
1 2

样例输出

2 3
1 2 3

评测用例规模与约定

对于60%的数据，1≤n,m≤1000 对于100%的数据，1≤n,m≤10^5,0≤x≤10^9,1≤t≤n

代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int m,n;//n个桶，m个数字
    int a,b;
    int cnt[100001] = {0};
    int num1[100001] = {0};//数字
    int num2[100001] = {0};//桶
    vector<int> v[100001];
    cin>>n>>m;
    for(int i = 0; i < m; i++){
        cin>>num1[i];
        cin>>num2[i];
        v[num2[i]].push_back(num1[i]); //O(1)
        cnt[num2[i]]++;
    }// O(n)
    for(int i = 1; i <= n; i++){
        sort(v[i].begin(),v[i].begin()+cnt[i]); //O(nlogn)
        for(vector<int>::iterator it = v[i].begin();it!=v[i].end();it++) 
            cout<<*it<<" ";  //O(n)
        cout<<endl;
    }  //O(n^2*logn)
    return 0;
}

D : 笔记本

问题描述

为了复习考研英语，yhf开始背单词。 yhf有一个笔记本，一开始是空的。当yhf遇到一个不认识的单词时，他会先查找笔记本，如果笔记本上没有，他就会先在互联网上查找这个单词，然后记在笔记本上。当yhf认为他已经熟记一个单词时，他会将这个单词在笔记本上擦掉（如果笔记本上没有就不用擦了）。yhf有时也会关心他的笔记本上记了多少单词，他会将笔记本上的单词按照字典序升序读一遍。 这天，yhf发现他的笔记本已经记满了单词，他决定用程序来实现笔记本的功能。但考虑到编写程序消耗的时间可以多背几千个单词，他决定把这个认为交给你。

输入格式

输入第一行包含一个整数 m，接下来有 m 行，每一行有一个整数 op，表示你的程序应执行哪种操作,具体如下

• op=1，后接一个单词，表示查找这个单词；如果笔记本中没有这个单词，则将单词写进笔记本

• op=2，后接一个单词，表示删除这个单词；如果笔记本中没有这个单词，则无需进行操作

• op=3，表示按字典序通读整个笔记本

输出格式

输出 m行，每一行表示输入的操作对应的输出，具体如下

• op=1，如果笔记本中有这个单词，输出found，否则输出write

• op=2，如果笔记本中有这个单词，输出erased，否则输出not found

• op=3，在一行内按字典序升序输出所有单词，中间用空格隔开

样例输入

8
1 problem
1 problem
2 problem
1 problem
2 acm
1 pro
1 acm
3

样例输出

write
found
erased
write
not found
write
write
acm pro problem

评测用例规模与约定

对于60%的数据，m≤100。 对于100%的数据，m≤10^5，单词长度∣s∣≤10 且由小写字母构成。 保证操作3的次数不超过3次。

代码：

#include<bits/stdc++.h>
using namespace std;
//set有序
int main(){
    int m, op, num = 0;
    string str;
    bool flag = 1;
    cin>>m;
    set<string> s;
    for(int i = 0; i < m; i++){
        cin>>op;
        switch (op){
            case 1:
                cin>>str; 
                if(s.count(str)){ //O(logn)
                    cout<<"found"<<endl;
                }   
                else{
                    s.insert(str);  //O(logn)
                    num++;
                    cout<<"write"<<endl;
                }
                break;
            case 2:
                cin>>str;
                if(s.find(str) != s.end()){   //O(logn)
                    cout<<"erased"<<endl;
                    s.erase(str);  //O(logn)
                    num--;
                }
                else
                    cout<<"not found"<<endl;
                break;
            case 3:{
                vector<string> v;
                for(set<string>::iterator it = s.begin(); it != s.end(); it++)
                    cout<<*it<<" ";      //set有序
                cout<<endl;
                break;
        }   
        default:
            break;
        }
    }
    return 0;
}

H3

A : 游戏

问题描述

有n个小朋友围成一圈玩游戏，小朋友从1至n编号，2号小朋友坐在1号小朋友的顺时针方向，3号小朋友坐在2号小朋友的顺时针方向，……，1号小朋友坐在n号小朋友的顺时针方向。 　　游戏开始，从1号小朋友开始顺时针报数，接下来每个小朋友的报数是上一个小朋友报的数加1。若一个小朋友报的数为k的倍数或其末位数（即数的个位）为k，则该小朋友被淘汰出局，不再参加以后的报数。当游戏中只剩下一个小朋友时，该小朋友获胜。 　　例如，当n=5, k=2时： 　　1号小朋友报数1； 　　2号小朋友报数2淘汰； 　　3号小朋友报数3； 　　4号小朋友报数4淘汰； 　　5号小朋友报数5； 　　1号小朋友报数6淘汰； 　　3号小朋友报数7； 　　5号小朋友报数8淘汰； 　　3号小朋友获胜。

给定n和k，请问最后获胜的小朋友编号为多少？

输入格式

输入一行，包括两个整数n和k，意义如题目所述。

输出格式

输出一行，包含一个整数，表示获胜的小朋友编号。

样例1

输入

5 2

输出

3

样例2

输入

7 3

输出

4

数据规模和约定

对于所有评测用例，1 ≤ n ≤ 1000，1 ≤ k ≤ 9。

笔记：

vector 的相关时间复杂度

pop_back(); //O(1)
erase(); //O(n)
push_back(); //O(1)
insert(); //O(n)
访问 O(1)

代码：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n = 0, k = 0;
    int nums = 0, j = 0;
    scanf("%d%d",&n,&k);
    vector<int> v;
    int i = 1;//用于计数
    if(k == 1){
        cout<<n<<endl;
        return 0;
    }
    for( ; i <= n; i ++){
        if(i%k == 0 || i%10 == k)
            continue;
        else{
            v.push_back(i); //插入N个元素， 则会引发lgN次的内存扩充,O(1)
            nums++;
        }
    } //O(n)
    while(nums > 1){
        if(i%k == 0 || i%10 == k){
            v.erase(v.begin()+j ); // erase删除的复杂度为O(n)
            nums--;
            j = j%nums;
        }
        else{
            j = (j + 1)%nums;
        }
        i++;
    } //O(N^2)
    printf("%d\n",v[0]);
    return 0;
}

B : 跳一跳

问题描述

近来，跳一跳这款小游戏风靡全国，受到不少玩家的喜爱。 　　简化后的跳一跳规则如下：玩家每次从当前方块跳到下一个方块，如果没有跳到下一个方块上则游戏结束。 　　如果跳到了方块上，但没有跳到方块的中心则获得1分；跳到方块中心时，若上一次的得分为1分或这是本局游戏的第一次跳跃则此次得分为2分，否则此次得分比上一次得分多两分（即连续跳到方块中心时，总得分将+2，+4，+6，+8…）。 　　现在给出一个人跳一跳的全过程，请你求出他本局游戏的得分（按照题目描述的规则）。

输入格式

输入包含多个数字，用空格分隔，每个数字都是1，2，0之一，1表示此次跳跃跳到了方块上但是没有跳到中心，2表示此次跳跃跳到了方块上并且跳到了方块中心，0表示此次跳跃没有跳到方块上（此时游戏结束）。

输出格式

输出一个整数，为本局游戏的得分（在本题的规则下）。

样例输入

1 1 2 2 2 1 1 2 2 0

样例输出

22

数据规模和约定

对于所有评测用例，输入的数字不超过30个，保证0正好出现一次且为最后一个数字。

代码：

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int score = 0;
    int temp = 1;
    int nums;
    while(scanf("%d",&nums) && nums != 0){
        if(nums == 1){
            temp = 1;
            score += temp;
        }
        else{
            if(temp == 1){
                temp = 2;
                score += temp;
            }
            else{
                temp += 2;
                score += temp;
            }
        }
    } //O(N)
    printf("%d\n",score);
    return 0;
}

C : 奇怪的电梯

问题描述

小H有一个奇怪的电梯，电梯可以根据需要停在每个楼层，每个楼层上都对应一个数字K_i（0 <= K_i <= N），该电梯只有两个按钮：“UP"和"DOWN”。在第i层楼，如果按下"UP"按钮，电梯将移动到i+K_i层；如果按下"DOWN"，电梯将移动到i-K_i层。当然，电梯有一个移动的范围，不能高于N且不能低于1。例如，有一个5层楼的建筑物，k_1 = 3，k_2 = 3，k_3 = 1，k_4 = 2，k_5 =5。从一楼开始，按"UP"按钮，将上升到四楼，如果按"DOWN"按钮，电梯将无法移动，因为它不能下降到-2楼。 现在问题来了：小H想从A层移动到B层，他至少要按几次"UP"或"DOWN"按钮，你能帮帮他嘛？

输入格式

输入包含多个测试用例。每个测试用例包含两行。 第一行包含上述三个整数N，A，B（1 <= N，A，B <= 200），第二行包含N个整数k_1，k_2，.... k_n​。 若读取到单个0，则表示输入结束。

输出格式

对于每个测试用例，输出一个整数表示最少按下"UP"或"DOWN"按钮的次数，若无法到达B层，请输出"-1"。每个测试用例的输出占一行。

样例输入

5 1 5
3 3 1 2 5
0

样例输出

3

数据规模和约定

1<=N,A,B<=200,0<=k_i<=N

提示

隐式图问题

代码：

#include<bits/stdc++.h>
using namespace std;
map<int, int> father;
queue<int> q;
void check(int x, int y){
    if(father.find(y) == father.end()){//y没有到达过  O(logn)
        q.push(y);   //O(logn)
        father[y] = x; //y的上一个状态是x
    }
}//O(logn)
void bfs(int A, int B, int N, int *k){
    int now = A;
    q.push(now); //O(1)
 
    while(!q.empty()){
        now = q.front();  //O(1)
        q.pop();  //O(1)
        if(now == B){
            int u = now;
            stack<int> temp;
            while(u != A){
                temp.push(u);
                u = father[u];
            }
        //    temp.push(u);
             printf("%d\n",temp.size());
            return;
        }
        if(now + k[now] <= N)
            check(now, now + k[now]);
        if(now - k[now] >= 1)
            check(now, now - k[now]);
    }
    printf("-1\n");
}
int main(){
    int N,A,B;
    while(scanf("%d",&N) && N!=0){
        scanf("%d",&A);
        scanf("%d",&B);
        int *k = new int[N+1];
        for(int i = 1; i <= N; i++){
            scanf("%d",&k[i]);  //O(N)
        }
        while(!q.empty()) q.pop();  //清空队列O(n)
        father.clear();
        bfs(A,B,N,k);
        delete k;
    }  //O(N^2)
    return 0;
}

D : 选数

问题描述

已知n个整数 x_1,x_2,…,x_n 和1个整数k(k<n)。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4,k=3,x_1=3,x_2=7,x_3=12,x_4=19时，可得全部的组合与它们的和为：

3+7+12=223+7+12=22 3+7+19=293+7+19=29 7+12+19=387+12+19=38 3+12+19=343+12+19=34

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：3+7+19=293+7+19=29。

输入格式

输入包含两行 第一行两个数n,k 第二行n个数依次表示x_i

输出格式

一个整数，表示合法的组合数

样例输入

4 3
3 7 12 19

样例输出

1

数据规模和约定

1<=k<n<=20 1<=x_i<=5000000

提示

素数的判定方法

bool prime(int n)
{
        if（n==1) return false;
        if (n==2) return true;
	for(int i=2;i*i<=n;i++)
	   if (n%i==0) return false;
	return true; 
}

代码：

#include<bits/stdc++.h>
using namespace std;
 
bool prime(int n){
    if (n==1) return false;
    if (n==2) return true;
	for(int i=2;i*i<=n;i++)
	   if (n%i==0) return false;
	return true; 
}
 
int main(){
    int n,k,cnt = 0;
    scanf("%d%d",&n,&k);
    int *a = new int[n];
    for(int i = 0; i < n; i++)
        scanf("%d",&a[i]); //O(n)
    int *b = new int[n];
    for(int i = 0, sum = pow(2,n); i< sum; i++){
        int nums = 0;
        int result = 0;
        int temp = i;
        result = 0;
        for(int j = 0; j < n; j++){
            b[j] = temp%2;//二进制表示每个输入的数取或不取
            temp /=2;
        } //O(N)
        for(int j = 0; j < n; j++)
            nums += b[j];
        if(nums == k){
            for( int j = 0; j < n; j++)
                result += b[j]*a[j];
            if (prime(result)) cnt ++; //O(logn)
        }
    }//O(2^n*n)
    printf("%d\n",cnt);
    return 0;
 
}

E : 棋盘问题

问题描述

小H收集到一些形状特殊的棋盘，她想在棋盘上面摆放棋子（棋子都是相同的）。她希望摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，你能帮她求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案数C嘛？

输入格式

输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 注意只有#棋盘区域可以摆放棋子。

输出格式

对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C<2^31）

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1

数据规模和约定

1<=k<=n<=8

代码：

#include<bits/stdc++.h>
using namespace std;
 
int nums = 0;
int vis[9] = {0}; //记录数字是否被使用
bool a[9][9];
char c;
void permutation(int x, int y, int n, int k){
    if( y == k){
        nums++;
        return;
    }
    for(int i = x; i < n; i++)
        for(int j = 0; j < n; j++){
            if(vis[j] == 0 && a[i][j]) { //此列未被放置且此位置可以放置
                vis[j] = 1;
                permutation(i+1,y+1,n,k);
                vis[j] = 0;
            }
        }
}
 
int main(){
    int n,k;
    while(scanf("%d%d",&n,&k) && n != -1 && k != -1){
        int i = 0;
        for (int j = 0; j < n; j++){
            for (int i = 0; i < n; i++){
                cin >> c;
                if (c == '#')//棋盘区域，可以摆放棋子
                    a[i][j] = 1;
                else
                    a[i][j] = 0;
            }
        }//O(n^2)
        for(int i = 0; i <= n; i++){ //每一组数据
        	nums = 0;
        	permutation(0,0,n,k);
    	}
    	cout<<nums<<endl;
    }
    return 0;
}

H4

A : 摆放垃圾桶

题目描述

滨海公园旁边新铺了一条路，把这条路分成n段，依次编号为1…n。为了防止游客把垃圾扔到海里，war要在路上放一些垃圾桶声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】