笔试刷题（一）

字符串匹配

题目描述
牛牛有两个字符串A和B,其中A串是一个01串,B串中除了可能有0和1,还可能有’?’,B中的’?’可以确定为0或者1。 寻找一个字符串T是否在字符串S中出现的过程,称为字符串匹配。牛牛现在考虑所有可能的字符串B,有多少种可以在字符串A中完成匹配。

例如:A = “00010001”, B = “??”
字符串B可能的字符串是”00”,”01”,”10”,”11”,只有”11”没有出现在字符串A中,所以输出3

#include<iostream>
#include<string>
#include<vector>
#include<set>
using namespace std;

int main(){
    string S1;
    string S2;
    set<string>A;
    cin>>S1;
    cin>>S2;
    int n=S1.size();
    int m=S2.size();
    for(int start=0;start<(n-m)+1;start++){
        if(S1[start]==S2[0]||S2[0]=='?'){
            int j=0;
            for(;j<S2.size();j++){
                if(S1[start+j]==S2[j]||S2[j]=='?'){
                }
                else{
                    break;
                }
            }
            if(j==S2.size()){
                A.insert(S1.substr(start,S2.size()));
            }
        }
    }
    cout<<A.size()<<endl;

}

循环数比较

题目描述
对于任意两个正整数x和k,我们定义repeat(x, k)为将x重复写k次形成的数,例如repeat(1234, 3) = 123412341234,repeat(20,2) = 2020.
牛牛现在给出4个整数x1, k1, x2, k2, 其中v1 = (x1, k1), v2 = (x2, k2),请你来比较v1和v2的大小。
输入描述:
输入包括一行,一行中有4个正整数x1, k1, x2, k2(1 ≤ x1,x2 ≤ 10^9, 1 ≤ k1,k2 ≤ 50),以空格分割
输出描述:
如果v1小于v2输出”Less”,v1等于v2输出”Equal”,v1大于v2输出”Greater”.

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main(){
    int x1;
    int k1;
    int x2;
    int k2;
    cin>>x1>>k1>>x2>>k2;
    string s1=to_string(x1);
    string s2=to_string(x2);
    int l1=s1.length();
    int l2=s2.length();
    if(l1*k1>l2*k2){
        cout<<"Greater"<<endl;
        return 0;
    }
    else if(l1*k1<l2*k2){
        cout<<"Less"<<endl;
        return 0;
    }
    string out1="";
    string out2="";
    for(int i=0;i<k1;i++){
        out1+=s1;
    }
    for(int j=0;j<k2;j++){
        out2+=s2;
    }
    if(out1>out2){
        cout<<"Greater"<<endl;
    }
    else if(out1<out2){
        cout<<"Less"<<endl;
    }
    else{
        cout<<"Equal"<<endl;
    }

}

字符串问题

题目描述
小摩手里有一个字符串A，小拜的手里有一个字符串B，B的长度大于等于A，所以小摩想把A串变得和B串一样长，这样小拜就愿意和小摩一起玩了。
而且A的长度增加到和B串一样长的时候，对应的每一位相等的越多，小拜就越喜欢。比如”abc”和”abd”对应相等的位数为2，为前两位。
小摩可以在A的开头或者结尾添加任意字符，使得长度和B一样。现在问小摩对A串添加完字符之后，不相等的位数最少有多少位？
输入描述:
第一行 为字符串A，第二行 为字符串B，
A的长度小于等于B的长度，B的长度小于等于100。
字符均为小写字母。
输出描述:
输出一行整数表示A串添加完字符之后，A B 不相等的位数最少有多少位？

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

int main(){
    string A;
    string B;
    cin>>A;
    cin>>B;
    int l1=A.size();
    int l2=B.size();
    int maxunequal=101;
    for(int start=0;start<(l2-l1)+1;start++){
        int num=0;
        for(int j=0;j<l1;j++){
            if(A[j]!=B[start+j]){
                num++;
            }
        }
        if(num<maxunequal){
            maxunequal=num;
        }
    }
    cout<<maxunequal<<endl;
}

堆棋子

题目描述
小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.
输入描述:
输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数
第二行为n个棋子的横坐标xi
第三行为n个棋子的纵坐标yi
输出描述:
输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格

如样例所示:
对于1个棋子: 不需要操作
对于2个棋子: 将前两个棋子放在(1, 1)中
对于3个棋子: 将前三个棋子放在(2, 1)中
对于4个棋子: 将所有棋子都放在(3, 1)中

示例1
输入
4
1 2 4 9
1 1 1 1
输出
0 1 3 10

#include <bits/stdc++.h>

using namespace std;

// 计算曼哈顿距离
int manhattan_dist(int x1, int y1, int x2, int y2) {
    return abs(x2 - x1) + abs(y2 - y1);
}
/*
求，让某一个格子(x0,y0)上有k个棋子所需要的最少操作次数

1. 求出所有棋子到某一点的曼哈顿距离，得到一个n维vector
2. 将vector从小到大排序
3. 对vector中第0个元素到第k - 1个元素求和，即前k个元素
*/
int get_dist_sum(int x0, int y0, const vector<int> &X, const vector<int> &Y, int k) {
    int n = X.size();
    // 1. 计算所有棋子到点(x0, y0)的曼哈顿距离，得到n维向量dists
    vector<int> dists(n);
    for (int i = 0; i < n; ++i)
        dists[i] = manhattan_dist(x0, y0, X[i], Y[i]);
    // 2. 将dists从小到大排序
    sort(dists.begin(), dists.end());
    // 3. 对vector中第0个元素到第k - 1个元素求和
    int dist_sum = 0;
    for (int i = 0; i < k; ++i)
        dist_sum += dists[i];
    return dist_sum;
}
/*
求，让棋盘上出现有一个格子上有k个棋子所需要的最少次数

这个函数是这道题的关键。由于计算曼哈顿距离时可以通过对x和y分别计算再求和来得到，
所以使dist_sum最小的格子的x坐标一定是X中的一个，y坐标一定是Y中的一个。

1. 遍历每一个备选格子(X[i], Y[j])，并分别计算dist_sum
2. 求得它们的最小值
*/
int min_move(int k, const vector<int> &X, const vector<int> &Y) {
    int min_dist_sum = INT_MAX, n = X.size();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            int dist_sum = get_dist_sum(X[i], Y[j], X, Y, k);
            min_dist_sum = min(min_dist_sum, dist_sum);
        }
    }
    return min_dist_sum;
}
vector<int> min_moves(int n, const vector<int> &X, const vector<int> &Y) {
    vector<int> res(n, 0);
    for (int k = 2; k <= n; ++k)
        res[k - 1] = min_move(k, X, Y);
    return res;
}

int main() {
    int n = 0;
    cin >> n;
    vector<int> X(n), Y(n);
    for (int i = 0; i < n; ++i) cin >> X[i];
    for (int i = 0; i < n; ++i) cin >> Y[i];  
    vector<int> res = min_moves(n, X, Y);  
    for (int i = 0; i < n - 1; ++i) cout << res[i] << ' ';
    cout << res.back() << endl;
    return 0;
}

字符串的价值

题目描述
有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串”abacaba”,里面包括4个’a’,2个’b’,1个’c’,于是这个字符串的价值为4 4 + 2 2 + 1 * 1 = 21
牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。
输入描述:
输入包括两行,第一行一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),其中只包含小写字母(‘a’-‘z’)。
第二行包含一个整数k(0 ≤ k ≤ length),即允许移除的字符个数。
输出描述:
输出一个整数,表示得到的最小价值
示例1
输入
aba
1
输出
2

#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
bool cmp(pair<char,int>a,pair<char,int>b ){
    if(a.second>b.second){
        return true;
    }
    else{
        return false;
    }
}
vector<pair<char,int>> SortMap(map<char,int> M){
    vector<pair<char,int>> A;
    map<char,int>::iterator it;
    for(it=M.begin();it!=M.end();it++){
        A.push_back(make_pair(it->first,it->second));
    }
    sort(A.begin(),A.end(),cmp);
    return A;
}


int main(){
    string s;
    cin>>s;
    int n;
    cin>>n;
    map<char,int> M;
    vector<char> A;
    sort(s.begin(),s.end());
    for(int i=0;i<s.length();i++){
        M[s[i]]++;
    }
    vector<pair<char,int>> B;
    B=SortMap(M);
    for(int i=0;i<n;i++){
        B[0].second--;
        sort(B.begin(),B.end(),cmp);
    }
    int sum=0;
    for(int i=0;i<B.size();i++){
        sum+=(B[i].second*B[i].second);
    }
    cout<<sum<<endl;
}

数字游戏

题目描述
牛牛举办了一场数字游戏,有n个玩家参加这个游戏,游戏开始每个玩家选定一个数,然后将这个数写在纸上(十进制数,无前缀零),然后接下来对于每一个数字将其数位按照非递减顺序排列,得到新的数,新数的前缀零将被忽略。得到最大数字的玩家赢得这个游戏。
输入描述:
输入包括两行,第一行包括一个整数n(1 ≤ n ≤ 50),即玩家的人数
第二行n个整数xi,即每个玩家写下的整数。
输出描述:
输出一个整数,表示赢得游戏的那个玩家获得的最大数字是多少。
示例1
输入
3
9638 8210 331
输出
3689

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

int main(){
    int n;
    cin>>n;
    vector<int> A(n);
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        string s=to_string(x);
        sort(s.begin(),s.end());
        A[i]=atoi(s.c_str());
    }
    sort(A.begin(),A.end());
    cout<<A[n-1]<<endl;

}

红和绿

题目描述
牛牛有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。牛牛现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将会被覆盖。牛牛的目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。牛牛想知道他最少需要涂染几个正方形。
如样例所示: s = RGRGR
我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
输入描述:
输入包括一个字符串s,字符串s长度length(1 ≤ length ≤ 50),其中只包括’R’或者’G’,分别表示红色和绿色。
输出描述:
输出一个整数,表示牛牛最少需要涂染的正方形数量
示例1
输入
RGRGR
输出
2

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

int main(){
    string S;
    cin>>S;
    int n=S.length();
    vector<int> Red(n);
    vector<int> Green(n);
    for(int i=0;i<S.length();i++){
        if(i==0){

        }
        else{
            if(S[i-1]=='G'){
                Red[i]=Red[i-1]+1;
            }
            else{
                Red[i]=Red[i-1];
            }
            if(S[n-i]=='R'){
                Green[n-1-i]=Green[n-i]+1;
            }
            else{
                Green[n-1-i]=Green[n-i];
            }
        }
    }
    int sum=n+1;
    for(int i=0;i<n;i++){
        if(Red[i]+Green[i]<sum){
            sum=Red[i]+Green[i];
        }
    }
    cout<<sum<<endl;
}