目录

1.斐波那契数列

 2.字符串处理

 3.董大佬和耗子吃西瓜

4.三角形问题

5.众数

6.集训队选拔

 7.寻找一个子序列

8.哥布林的舞会

9.病毒溯源

10.跳格子

11.任务分配


1.斐波那契数列

有这样一个特殊的递增序列,在这个序列中数字的排列如下:0,1,1,2,3,5,8,13,21,34,55……。这个序列的特点是:从第三项起,每一项都是紧挨着的前两项的和。现在请你帮助他来数数,告诉他这个数列任一项(项数小于33)的数字是多少?

输入格式:

输入要求的项数。

输出格式:

输出数据项的值。

输入样例:

在这里给出一组输入。例如:

10

输出样例:

在这里给出相应的输出。例如:

34

 简单的签到题,需要注意f[1] = 0,f[2] = 1即可

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
   int f[55];
   f[1] = 0;
   f[2] = 1;
    for (int i = 3; i <= 50; ++i) {
        f[i] = f[i-1] + f[i-2];
    }
    int n;
    cin>>n;
    cout<<f[n];
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

 2.字符串处理

用户输入一个字符串,其中有一些字母和数字,现在需要把字符串中的字母挑出来,并且无论大小写,都改成大写输出出来。请写出一个完整的程序来完成这件事。

输入格式:

输入一个字符串s,长度小于100。

输出格式:

输出处理后的字符串。

输入样例:

在这里给出一组输入。例如:

nc123WU

输出样例:

在这里给出相应的输出。例如:

NCWU

 签到题

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
   string s;
    cin>>s;
    for (int i = 0; i < s.size(); ++i) {
        if('A' <= s[i] && s[i] <= 'Z'){
            cout<<s[i];
        } else if('a' <= s[i] && s[i] <= 'z'){
            cout<<char(s[i] - 32);
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

 3.董大佬和耗子吃西瓜

在一个炎热的夏天,耗子哥和董大佬在活动室打了一天的比赛,比赛结束时,他们觉得非常的渴,于是决定买来一个西瓜两个人分开吃,但是耗子哥是强迫症,他想要将西瓜分成两份并且两份都必须是偶数,不然就坚决不吃,董大佬在旁边看耗子哥挑西瓜看的很着急,因为他已经饥渴难耐了,他希望你能帮帮他们,看一看耗子哥此时挑选的西瓜是否满足条件。

输入格式:

给出一个正整数w代表西瓜的重量(1<=w<=100),

输出格式:

如果西瓜的重量满足耗子哥的要求,输出YES,
否则输出NO

输入样例:

在这里给出一组输入。例如:

4

输出样例:

在这里给出相应的输出。例如:

YES

题目说可以分为两份,但没说是平均分成两份,因为这个问题wa了一发。我们知道,奇数加奇数为偶数,偶数加偶数为偶数,而奇数只能为一奇一偶相加才可得到,所以要想分成两部分都为偶数,则这个数一定是偶数,但2是个特例,2只能分为1和1,所以我们判断是不是大于2的偶数即可。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
   int w;
   cin>>w;
   if(w % 2 == 0 && w != 2){
       cout<<"YES"<<endl;
   } else{
       cout<<"NO"<<endl;
   }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

4.三角形问题

李华正在训练一个三角形分类模型,他手里有一堆数据,你能帮他标注一下么?
给定三个正整数,代表可能组成一个三角形的三条边长。
将其组成三角形后
如果是直角三角形,输出"right";如果是等边三角形,输出"equilateral";  如果不能组成 一个三角形,输出"error", 否则,输出"normal".

输入格式:

输入为三个正整数a b c 

(1<=a,b,c<=10000)

输出格式:

一串字符串如题所说

输入样例:

在这里给出一组输入。例如:

3 4 5

输出样例:

在这里给出相应的输出。例如:

right

签到题,注意判断即可。

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
   int a,b,c;
   cin>>a>>b>>c;
   if(a + b > c && a + c > b && b + c > a){
       if(a*a + b*b == c*c || a*a + c*c == b*b || c*c + b*b == a*a){
           cout<<"right";
       } else if(a == b && b == c){
           cout<<"equilateral";
       } else{
           cout<<"normal";
       }
   }else{
       cout<<"error";
   }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

5.众数

由文件给出N个1到 30000 间无序数正整数,其中 1≤N≤10000,同一个正整数可能会出现多次,出

现次数最多的整数称为众数。求出它的众数及它出现的次数。

输入格式:

输入文件第一行是正整数的个数 N,第二行开始为 N 个正整数。

输出格式:

输出文件有若干行,每行两个数,第 1 个是众数,第 2 个是众数出现的次数。

输入样例:

在这里给出一组输入。例如:

12
2 4 2 3 2 5 3 7 2 3 4 3

输出样例:

在这里给出相应的输出。例如:

2 4
3 4

这题使用map统计每个元素的出现次数即可,map不会的话,自行查找。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
   int n;
    cin>>n;
   map<int,int> mp;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin>>x;
        mp[x]++;
    }
    int maxx = 0;
    for (auto i : mp) {
        maxx = max(maxx,i.second);    //找到最大次数
    }
    for (auto i : mp) {
        if(i. second == maxx){
            cout<<i.first<<" "<<maxx<<endl;    //找到最大元素
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

6.集训队选拔

杨老师批改完数据结构期末考试试卷后,需要把全班学生的成绩做个排序,成绩高的在前,成绩低的在后。为了备战即将开始的天梯赛,需要从中选取成绩最好的前n位同学。现在请你帮助他完成选拔队员的任务。

输入格式:

第一行输入两个整数m,n。0<n<=m<=1000。
第二行包含m个整数,每一个整数表示一位同学的成绩x。0<=x<=1012。

输出格式:

输出包含一行n个整数,所有数按从大到小排序。

输入样例:

在这里给出一组输入。例如:

10 5
1 2 3 4 5 6 7 8 9 10

输出样例:

在这里给出相应的输出。例如:

10 9 8 7 6

考察基本排序,使用sort排序即可,需要重载排序函数。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
bool cmp(ll x,ll y){    //重载cmp
    return x > y;
}
void solve(){
   int m,n;
   cin>>m>>n;
   vector<ll> a(m+1,0);
    for (int i = 1; i <= m; ++i) {
        cin>>a[i];
    }
    sort(a.begin()+1,a.end(),cmp);
    for (int i = 1; i <= n; ++i) {
        cout<<a[i];
        if(i != n){
            cout<<" ";
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

 7.寻找一个子序列

在数列A中找到一个具有下面特点的子序列。

  1. 给定由不相同的n个整型元素组成的序列A:{A(1),A(2),…,A(i),…,A(n)};

  2. 寻找一个序列I:{i1,i2,i3,……,ie},且i1<i2<i3<…<ie,使得A(i1)<=A(i2)<=…<=A(ie);

  3. 在所有这些序列中,元素数量最多的那个序列就是我们要寻找的子序列。

输入格式:

一行用空格隔开的多个整数,整数数量最多100个。

输出格式:

输出子序列的最大个数;

输入样例:

在这里给出一组输入。例如:

13 7 9 16 38 24 37 18 44 19 21 22 63 15

输出样例:

在这里给出相应的输出。例如:

8

这题就是需要找到一个最长递增子序列,具体可以搜索LIS了解,对于b[i],代表的是以a[i]结尾的

最长递增子序列的长度,由于数据范围较小,可以直接暴力,所以对于每个a[i],我们需要从1到i-1

找到小于a[i]的a[j],b[i] = b[j] + 1,而我们需要找的是最长的,所以b[i] = max( b[i] , b[j] + 1)。、

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
void solve(){
    vector<ll> a;
    int x;
    a.push_back(0);
    while (cin>>x){
        a.push_back(x);
    }
    int len = a.size();
    int maxx = 1;
    vector<int> b(len+5);
    fill(b.begin(),b.end(),1);    //初始化为1,最短长度为1
    for (int i = 1; i <= len; ++i) {
        for (int j = 1; j < i; ++j) {
            if(a[j] < a[i]) b[i] = max(b[i],b[j] + 1);//找到最大的b[j]并加1
        }
        maxx = max(maxx,b[i]);
    }
    cout<<maxx<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

8.哥布林的舞会

一群洞穴哥布林为了庆祝新冠疫情解封,举行了一个盛大的舞会。每个参加舞会的哥布林都拿到了一个序号牌,记录了他进入舞厅的次序(从1开始的升序)。
哥布林们彼此选择舞伴遵循一个古老的传统,先进入舞厅的哥布林要选择身高比他低的哥布林作为舞伴。
举个栗子,第i个顺序进入舞厅的哥布林身高为hi​,第j个进入的哥布林身高为hj​。若存在i<j,且hi​>hj​,则两个人可以做彼此的舞伴。

例如样例中可能组成的舞伴有3个组合:
1号哥布林和2号哥布林,身高分别为3和2;
1号哥布林和4号哥布林,身高分别为3和2;
3号哥布林和4号哥布林,身高分别为3和2。

输入格式:

第一行为参加舞会的哥布林总数n,接下来的n行记录了次序进入舞厅的哥布林身高。

输出格式:

所有可能的舞伴组合数。

输入样例:

在这里给出一组输入。例如:

4
3
2
3
2

输出样例:

在这里给出相应的输出。例如:

3

这个题目本质就是求逆序对的数量,而求逆序对的数量我们可以使用归并排序,在归并排序过程中,数组被分为两部分( l , mid )和(mid + 1,r), ( l , mid )里面的数据我们用i枚举,(mid + 1,r)里面的元素我们用j枚举,排序过程中,如果a[i] > a[j],则i到mid中的元素均大于a[j],所以我们的res 需要加上 mid - i + 1。具体细节,大家可以搜索归并排序。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
int a[N];
int tmp[N];
ll merge_sort(int a[],int l,int r){    //归并排序过程
    if(l >= r) return 0;
    int mid = l + r >> 1;
    ll res = 0;
    res += merge_sort(a,l,mid);
    res += merge_sort(a,mid + 1,r);
    int i = l,j = mid + 1,k = 1;
    while (i <= mid && j <= r){
        if(a[i] <= a[j]){
            tmp[k++] = a[i++];
        } else{
            tmp[k++] = a[j++];
            res += mid - i + 1;    //记录res
        }
    }
    while (i <= mid) tmp[k++] = a[i++];   
    while (j <= r) tmp[k++] = a[j++];
    for (int m = l,k = 1; m <= r; ++m) {    //合并
        a[m] = tmp[k++];
    }
    return res;
}
void solve(){
    int n;
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        cin>>a[i];
    }
    ll ans = merge_sort(a,1,n);
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

9.病毒溯源

病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株,而这些变异的病毒又可能被诱发突变产生第二代变异,如此继续不断变化。

现给定一些病毒之间的变异关系,要求你找出其中最长的一条变异链。

在此假设给出的变异都是由突变引起的,不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来,并且不存在循环变异的情况。

输入格式:

输入在第一行中给出一个正整数 N(≤104),即病毒种类的总数。于是我们将所有病毒从 0 到 N−1 进行编号。

随后 N 行,每行按以下格式描述一种病毒的变异情况:

k 变异株1 …… 变异株k

其中 k 是该病毒产生的变异毒株的种类数,后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒(0≤i<N)。题目保证病毒源头有且仅有一个。

输出格式:

首先输出从源头开始最长变异链的长度。

在第二行中输出从源头开始最长的一条变异链,编号间以 1 个空格分隔,行首尾不得有多余空格。如果最长链不唯一,则输出最小序列。

注:我们称序列 { a1​,⋯,an​ } 比序列 { b1​,⋯,bn​ } “小”,如果存在 1≤k≤n 满足 ai​=bi​ 对所有 i<k 成立,且 ak​<bk​。

输入样例:

10
3 6 4 8
0
0
0
2 5 9
0
1 7
1 2
0
2 3 1

输出样例:

4
0 4 9 1

这个题目本质上是一个树,我们需要找到一条最长路径,所以可以使用dfs,从源头开始遍历,使用tmp记录路径,ans记录最长路径。具体细节见代码。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 1e4 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
vector<vector<int>> a(N);    //保存树
vector<int> ans;    //记录最长路径
vector<int> tmp;    //记录dfs过程中路径
void dfs(int now){    //dfs遍历
    tmp.push_back(now);    //把当前节点保存到tmp
    sort(a[now].begin(),a[now].end());    //对当前节点的子节点进行排序,保证路径字典序最小
    for (auto &j : a[now]) {    //继续dfs当前节点的子节点
        dfs(j);
        if(tmp.size() > ans.size()){    //如果tmp的长度大于ans,就更新ans
            ans.clear();
            ans = tmp;
        }
        tmp.pop_back();    //当前节点遍历完成,注意回溯,把路径上的当前节点弹出
    }
}
void solve(){
    int n;
    cin>>n;
    map<int,int> mp;
    for (int i = 0; i < n; ++i) {
        int k;
        cin>>k;
        for (int j = 1; j <= k; ++j) {
            int x;
            cin>>x;
            mp[x]++;
            a[i].push_back(x);    //建树,由于结果只会是一条路走到头,所以只建单向边即可
        }
    }
    int st = 0;    //保存开始节点
    for (int i = 0; i <= n-1; ++i) {
        if(mp[i] == 0){        //哪个节点没出现在变异株中就是开始节点
            st = i;
            break;
        }
    }
    dfs(st);//注意病毒源头不一定是0
    if(n==1){    //特判
        cout<<1<<endl<<0;
        return;
    }
    cout<<ans.size()<<endl;
    for (int i = 0; i < ans.size(); ++i) {    //输出即可
        cout<<ans[i];
        if(i != ans.size() - 1){
            cout<<" ";
        }
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

10.跳格子

【问题描述】

小时候,没有什么娱乐的,放学后就同学一起玩跳格子。那时候的跳格子,只有9个格,写上数字,从这头1跳到那头9,再跳回来。这个游戏有了升级版。画的格子变了样,规则也变了。如图所示。

image.png

新跳格子规则:

1)可以从任意标号开始,往较大标号的相邻格子跳;

2)只能从小的往大的跳;

3)边界挨着的格子就算相邻。

现在问:从编号为K的格子开始爬到N,K<N。问有多少种跳法?

输入格式:

一行有两个输入数据: K,N

输出格式:

输出一个数字(有多少种跳法)

输入样例:

3 16

输出样例:

377

这个题目,不难发现答案就是斐波那契数列,由于题目中没给出数据范围,很难想到高精度。对于高精度,可自行搜索。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;

vector<int> add(vector<int> a,vector<int> b){    //高精度加法
    int t = 0;
    vector<int> c;
    for (int i = 0; i < a.size() || i < b.size() ; ++i) {
        if(i < a.size()){
            t += a[i];
        }
        if(i < b.size()){
            t += b[i];
        }
        c.push_back(t%10);
        t /= 10;
    }
    if(t){
        c.push_back(t);
    }
    return c;
}

void solve(){
    ll k,n;
    cin>>k>>n;
    ll tmp = n - k + 2;
    vector<int> a;
    vector<int> b;
    vector<int> c;
    a.push_back(0);
    b.push_back(1);
    for (int i = 3; i <= tmp; ++i) {
        c = add(a,b);
        a = b;
        b = c;
    }
    for (int i = c.size()-1; i >= 0; --i) {
        cout<<c[i];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}

11.任务分配

装修公司接到一个装修任务,任务中共有n件工作,n件工作可以分配给n个小组。将工作i分配给第j个小组所需的费用为cij。试设计一个算法,为每一个小组都分配一件不同的工作,并使总费用达到最小。设计一个算法,对于给定的工作费用,计算最佳工作分配方案,使总费用达到最小。

输入格式:

第一行有1个正整数n (1≤n≤20)。接下来的n行,每行n个数,第i行表示第i个小组分别完成这n件工作所需要的费用。

输出格式:

输出计算出的最小总费用。

输入样例:

在这里给出一组输入。例如:

3 
4 2 5 
2 3 6 
3 4 5

输出样例:

在这里给出相应的输出。例如:

9

这个题目使用dfs暴力搜索所有情况即可,但是在暴力的过程中,要“人类智慧减枝”。

代码:

#include<bits/stdc++.h>
typedef unsigned long long ull;
typedef long long ll;
using namespace std;
const int N = 2e5 + 10;
const int M = 2e5 + 10;
const int mod  = 1e9 + 7;
int n;
int g[30][30];
int minx = 0x3f3f3f3f,tmp = 0;
int vt[30];
void dfs(int u,int w){  //u为当前节点,w为当前的费用
    if(u == n + 1){
        minx = min(minx,tmp);        //访问到根节点
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if(w >= minx) return;    //人类智慧减枝,当前费用已经大于minx了就直接退出了
        if(vt[i] == 0){
            tmp = w + g[u][i];  //计算当前费用
            vt[i] = 1;  //访问就标记为1
            dfs(u+1,tmp);    //递归下一个人
            vt[i] = 0;  //访问结束恢复为0
        }
    }
}

void solve(){
    cin>>n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin>>g[i][j];
        }
    }
    dfs(1,0);
    cout<<minx<<endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--){
        solve();//1 2 3 4 5
    }
    return 0 ;
}
Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐