【桂林信息科技学院第一届程序设计大赛】完整题解 C++

本文主要是介绍【桂林信息科技学院第一届程序设计大赛】完整题解 C++，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

目录

• • • A.Hello 小明
    • B.博学多识的小明
    • C.小明爱偶数
    • D.小明爱打单词
    • E.小明打篮球
    • F.小明爱数学
    • G.小明与张三
    • H.小明拿宝藏
    • I.小明的考试成绩
    • J.小明与鲜花
    • K.小明与小红的增删图游戏
    • 后记

A.Hello 小明

本题作为本场最简单的签到题，改编于hello world，想考察大家的字符串输入输出能力。

#include<bits/stdc++.h>
using namespace std;
int main(){
    string s;
    cin>>s;
    cout<<"Hello "<<s<<endl;
    return 0;
}

B.博学多识的小明

匹配句子中出现的Abandon/abandon，因为有空格，在c++中使用getline将整体一行读入。因为不需要考虑后缀，也可以根据空格将字符串分成一个一个单独的单词或标点。
我这里给出，直接去遍历整行句子，遇到A或者a就进入判断，判断下一个是否为b，下下个是否为a，以此类推。特别的，为了减小难度，整个单词如果前缀不满足，那么就不可能出现该单词后缀包含abandon的情况。

#include<bits/stdc++.h>
using namespace std;
string t="abandon";
int ans;
int main(){
    string s;
    getline(cin,s);
    for(int i=0;i<s.size();i++){
        if(s[i]==t[0]||s[i]=='A'){
            int idx=i;
            for(int j=1;j<=6;j++){
                if(s[++i]==t[j]) ;
                else{
                    i=idx;
                    break;
                }
            }
            if(i!=idx){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

C.小明爱偶数

题目挺唬人，但是理清楚题意后很简单。
题目意思为给定一个 n n n ,可以倒置它的一个从起始位置开始的子区间，使得最终该数变成一个偶数。
最终的结果集为 { − 1 , 0 , 1 , 2 } \{-1,0,1,2\} {−1,0,1,2} 。我们读题后不难发现如果能翻转成偶数，那么最多两次一定能实现。第一次以该位偶数为结尾，倒置，将该位变成首位，然后再整体倒置，将该位变成最后一位。

• 当 n n n 的每一位都是奇数时，结果为 -1
• if当 n n n 的末位为偶数时，结果为0
• else if当 n n n 的首位是偶数时，结果为1
• else if当 n n n 的某一位置为偶数时，结果为2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        if(n%2==0) cout<<0<<endl;
        else{
            vector<int> ve;
            while(n){
                int tem=n%10;
                ve.push_back(tem);
                n/=10;
            }
            int ans=-1;
            for(int i=ve.size()-1,j=1;i>=0;i--,j++){
                if(ve[i]%2==0){
                    ans=j;
                    break;
                }
            }
            if(ans>=2) ans=2;
            cout<<ans<<endl;
        }
    }
    return 0;
}

D.小明爱打单词

又是一道题目挺唬人，但是理清楚题意后很简单的题。
首先我们用map键值对记录键盘中每个字符所在的位置，用数组同理，可以记录a~z每个字符的位置。然后遍历一遍所给的单词，从第二位开始，直接累加该单词的第i与i-1位的字符在键盘中所在位置的距离差即可。记得取绝对值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<char,int> mp;
int main(){
    int t;
    cin>>t;
    while(t--){
        mp.clear();
        string s;
        cin>>s;
        for(int i=0;i<s.size();i++){
            mp[s[i]]=i;
        }
        string opp;
        cin>>opp;
        ll ans=0;
        for(int i=1;i<opp.size();i++){
            ans+=abs(mp[opp[i]]-mp[opp[i-1]]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

E.小明打篮球

小明在第 n n n 局使用招式，必胜。其它局的胜率为 50%
而且，根据这句话的提示：
说明：获得胜利的条件是小明在 x x x 局比赛中赢下 ( x + 1 ) 2 \frac{(x+1)}{2} 2(x+1)​ 局以上，例如3局2胜，5局3胜…
可以列出公式： ( x + 1 ) 2 = n \frac{(x+1)}{2}=n 2(x+1)​=n
解得： x = 2 ⋅ n − 1 x=2·n-1 x=2⋅n−1 即为最终答案。
解释：小明会在除第 n n n 局的共 x − 1 x-1 x−1 局的偶数局中赢得一半的胜利。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        cout<<(2*n-1)<<endl;
    }
    return 0;
}

F.小明爱数学

本题也是一个十分简单的签到题，是我出题出到一半，突然觉得前面有点不符合预期难度，所以又加了一道简单题。还有点小私心，拿自己名字命了个名。
写过斐波那契数列的同学应该都能一眼出结果，给定首项和第二项然后去用公式模拟到第 n n n 项，因为 n n n 比较小用了一个数组。

#include<bits/stdc++.h>
using namespace std;
int f[105];
int main(){
    int n,a,b;
    cin>>n>>a>>b;
    f[1]=a;
    f[2]=b;
    for(int i=3;i<=n;i++){
        f[i]=(f[i-1]+f[i-2])%8;
    }
    cout<<f[n]<<endl;
    return 0;
}

G.小明与张三

有多少个格子可以通过命令走出去。
就是一道搜索类的小模拟题，本来是要剪枝的，但是因为oj里面c++和Java，Python都只能开同一个时间限制，所以考虑到可能会TLE，就没卡数据，我也不知道不剪枝写能不能过，反正我写题解的时候还没开始比赛。
写法就是以每一个点作为起点，去搜索，通过指令进行上下左右的移动，然后判断是否在循环(失败)，或者已经走出边界(成功)。
判断是否在循环给两种方式，一是访问到了之前访问过的点，用vis[]数组提前记录访问过的点；二是深搜走的深度是不是超过了 n ⋅ m n·m n⋅m 步，那就说明一定是在循环。
最后通过统计能走出的点的个数输出即可。
剪枝：当该点走到之前已经记录好能出去的点时，就不需要再向下搜索，可以直接返回true值，表示成功走出边界。

#include<bits/stdc++.h>
using namespace std;
char mp[1005][1005];
int vis[1005][1005];
int ris[1005][1005];
int n,m;
// W A S D
int dir[4][2]={
    {-1,0},{0,-1},{1,0},{0,1}
};
map<char,int> mpp;
bool check(int x,int y){
    if(x<1||x>n||y<1||y>m) return true;
    else return false;
}
bool dfs(int x,int y){
    if(check(x,y)){
        ris[x][y]=1;
        return true;
    }
    int k=mpp[mp[x][y]];
    int xx=x+dir[k][0],yy=y+dir[k][1];
    if(ris[xx][yy]) return true;
    if(vis[xx][yy]) return false;
    vis[xx][yy]=1;
    if(dfs(xx,yy)){
        ris[xx][yy]=1;
        return true;
    }else{
        return false;
    }
}
int main(){
    ios::sync_with_stdio(false);
    mpp['W']=0;
    mpp['A']=1;
    mpp['S']=2;
    mpp['D']=3;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            vis[i][j]=1;
            if(dfs(i,j)){
                ans++;
            }
            vis[i][j]=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

H.小明拿宝藏

改编自01背包模板。
加了一个条件，必须拿第一件物品。
只需要在最初时读入这件物品，减掉相应的背包容量，后续假装这件物品不存在即可。
01背包：
二维即可过题。
dp[i][j] 表示第 i 件物品，在背包容量还剩 j 的大小时，承放的最大价值。
第一维循环物品，第二维循环背包容量。
一维要倒叙第二重循环，因为这样背包容量<=j中的状态还是i-1的状态。

如果背包装得下当前的物体，在遍历过程中分别计算第i件物体放入和不放入背包的价值，取其中大的作为当前的最大价值。
如果背包装不下当前物体那么第i个物体只有不放入背包一种选择。

不放入背包时：第 i i i 次决策后的最大价值和第 i − 1 i-1 i−1 次决策时候的价值是一样的（还是原来的那些物体，没多没少）。
放入背包时：第 i i i 次决策后的价值为 第 i − 1 i-1 i−1 次决策时候的价值加上当前物体的价值v[j]。物体放入背包后会使背包容量变为 j j j ，即没放物体之前背包的容量为j - w[i]。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int dp[N];
int v[N],w[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    m-=v[1];
    for(int i=2;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]+w[1]<<endl;
    return 0;
}

I.小明的考试成绩

我又填了一道简单题。
好像前面又难了。
这道题就是考察排序的题目，就算冒泡也能通过。
只是用二维数组的方式给你，只需要把给定的所有数字存下，特别的记录一下小明所在位置的成绩，然后排序，排好序后降序找到小明的成绩所在的位置的下标，即为小明的成绩。

#include<bits/stdc++.h>
using namespace std;
vector<int> ve;
bool cmp(int x,int y){
    return x>y;
}
int main(){
    int n,m;
    int x,y,k,w;
    cin>>n>>m;
    cin>>x>>y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>k;
            ve.push_back(k);
            if(i==x&&j==y) w=k;
        }
    }
    sort(ve.begin(),ve.end(),cmp);
    for(int i=0;i<n*m;i++){
        if(ve[i]==w){
            cout<<i+1<<endl;
            break;
        }
    }
    return 0;
}

J.小明与鲜花

考察的容斥原理应用。
因为黑盒数据简单，多重背包也可以做。
因为黑盒数据简单，乱做也有可能过。
正解如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
int down;
ll n,m;
ll a[22];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=1LL*res*a%mod;
        a=1LL*a*a%mod;
        b>>=1;
    }
    return res;
}
int C(ll a,ll b){
    if(a<b) return 0;
    int up=1;
    for(ll i=a;i>a-b;i--) up=i%mod*up%mod;
    return 1LL*up*down%mod;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    down=1;
    for(int i=1;i<=n-1;i++) down=1LL*i%mod*down%mod;
    down=qpow(down,mod-2)%mod;
    int res=0;
    for(int i=0;i<(1<<n);i++){
        ll d=m+n-1;
        int flag=1;
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                flag*=-1;
                d-=(a[j]+1);
            }
        }
        res=(res+flag*C(d,n-1))%mod;
    }
    cout<<(res+mod)%mod;
    return 0;
}

K.小明与小红的增删图游戏

无详解，我预判本题没人过题。
虽然我数据出的太弱了，如果能理解到答案只在 0 , 1 , 2 {0,1,2} 0,1,2 中产生，也可以用随机数过题，反正就三组数据，随机输出 0 , 1 , 2 {0,1,2} 0,1,2 多交几遍，脸好就过题了。
正经解题方法为：Dijkstra判断最小环，如果最小环的权值和小于 c c c , 那么就可以买一个环，因为一次只能删一个无环图，所以输出 2 ；如果最小环权值大于等于 c c c , 或者没法形成环，输出 1 ；如果小明啥也没买，输出 0 .

#include<bits/stdc++.h>
using namespace std;
const int N=2050,M=5050;
const int INF=0x3f3f3f3f;
int head[N],top;
struct node{
    int to,next;
    int val;
}edge[M];
int d[N][N],cnt;
int n,m,c;
int vis[M];
priority_queue<pair<int,int> > q;
void init(){
    memset(head,-1,sizeof(head));
    top=0;
}
void add(int u,int v,int w){
    edge[top].to=v;
    edge[top].next=head[u];
    edge[top].val=w;
    head[u]=top++;
}
void dijkstra(int start){
    memset(vis,0,sizeof(vis));
    d[start][start]=0;
    q.push(make_pair(0,start));
    while(!q.empty()){
        auto temp=q.top();
        int x=temp.second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];~i;i=edge[i].next){
            int y=edge[i].to;
            int z=edge[i].val;
            if(d[start][y]>d[start][x]+z){
                d[start][y]=d[start][x]+z;
                q.push(make_pair(-d[start][y],y));
            }
        }
    }
}
int main(){
    memset(d,INF,sizeof(d));
    init();
    int n,m,c;
    cin>>n>>m>>c;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        if(z<=c){
            add(x,y,z);
            cnt++;
        }
    }
    int minn=INF;
    for(int i=1;i<=n;i++){
        dijkstra(i);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j) minn=min(d[i][j]+d[j][i],minn);
        }
    }
    if(cnt==0) cout<<0<<endl;
    else{
        if(minn<=c) cout<<2<<endl;
        else cout<<1<<endl;
    }
}

后记

出签到题以及两道模板题 (01背包模板、容斥原理模板) 外所有题目都是codeforce上的原题改编以及acm比赛原题改编，也是我上一段时间比赛时做过的题目，所有的题目，在正式比赛中均属于签到题，希望大家可以将后面的题慢慢了解和补掉，对算法产生更多的兴趣。
学算法，可以提高自己的码力。
如果足够努力和幸运的话，可能摸到一个足够有含金量的奖牌吧。

记录一下我编数据的过程，对着别人的编，然后自己编，写配置文件，写题面。最后的最后，如果您是个大佬，联系我，带带我。带带我。带带我。

这篇关于【桂林信息科技学院第一届程序设计大赛】完整题解 C++的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！