荣耀8.30笔试

我最终的得分是：100+200+270。

！！！第三题找不到问题所在，希望和大家讨论一下！！！。

题目一、单位转换

输入字节大小，将其转换为B、KB、MB、GB

代码实现

注意一下如何四舍五入保留小数点两位即可。

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

int main(){
    string arr[4] = {"B", "KB", "MB", "GB"};
    long long num = 0;
    int type = 0;
    cin >> num;
    double ans = 0.0;

    int tempnum = num;
    if(tempnum >= 1024){
        tempnum = tempnum / 1024;
        type = 1;
    }
    if(tempnum >= 1024){
        tempnum = tempnum / 1024;
        type = 2;
    }
    if(tempnum >= 1024){
        tempnum = tempnum / 1024;
        type = 3;
    }

    if(type == 1)
        ans = round(double(num) / 1024.0 * 100.0) / 100.0;
    else if(type == 2)
        ans = round(double(num) / (1024.0 * 1024.0) * 100.0) / 100.0;
    else if(type == 3)
        ans = round(double(num) / (1024.0 * 1024.0 * 1024.0) * 100.0) / 100.0;
    printf("%.2lf", ans);
    cout << arr[type] << endl;
}

题目二、采花蜜（寻找最短路径）

给出五个坐标，从零点开始，经过5个点后，返回到零点的最短路径。

代码实现

DFS即可。

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int ans = 1e9;

double getDis(int x, int y, int prex, int prey){
    return sqrt(double(abs(x - prex) * abs(x - prex) + abs(y - prey) * abs(y - prey)));
}

void dfs(vector<int> &x, vector<int> &y, vector<bool> visited, int cnt, double dis, int pre){
    if(cnt == 5){
        dis = dis + getDis(0, 0, x[pre], y[pre]);
        ans = min(ans, int(dis));
        return;
    }
    for(int i=0; i<5; i++){
        if(!visited[i]){
            visited[i] = true;
            double tempdis = dis + getDis(x[i], y[i], (pre == -1 ? 0: x[pre]), (pre == -1 ? 0: y[pre]));
            dfs(x, y, visited, cnt + 1, tempdis, i);
            visited[i] = false;
        }
    }
    return;
}

int main(){
    vector<int> x(5, 0);
    vector<int> y(5, 0);
    for(int i=0; i<5; i++){
        cin >> x[i] >> y[i];
    }
    vector<bool> visited(5, false);
    dfs(x, y, visited, 0, 0, -1);
    cout << ans << endl;
}

3. 修改句子（类似于编辑距离

给两个句子（只有小写字母和空格，两个单词之间可能有多个空格），第一个是标准的句子，第二个句子是学生的句子，老师现在要计算分数。

• 新增一个单词，扣2分；
• 修改一个单词，扣1分；（只有当单词与目标单词相同的数量大于标准单词的一半时，才能够修改，否则只能删除再新增）
• 删除一个单词，扣1分。
• 总分为标准答案单词个数减去扣分，求最终的得分

输入：
cat good
cat dog
输出：
1       //2-1

输入：
cat good
cat do
输出：
-1        //2-1-2    

代码实现

注意一下输入（需要忽略掉空格），然后二维dp即可。但是不知道为什么最终只过了90%（希望网友帮忙debug一下）

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
void input(vector<string>& strs){
    char c;
    string str = "";
    while((c = getchar())!= '\n' && c!= EOF){
        if(c >= 'a' && c <= 'z'){
            str.push_back(c);
        }else if(c == ' '){
            if(str.size() == 0)
                continue;
            else{
                strs.push_back(str);
                str = "";
            }
        }
    }
    if(str.size()>0)strs.push_back(str);
    return;
}

bool isValid(string &stu, string &std){
    unordered_map<char, int> m;
    for (int i = 0; i < stu.size(); i ++){
        m[stu[i]]++;
    }
    int cnt = 0;
    for (int i = 0; i < std.size(); i ++){
        if(m.count(std[i])){
            m[std[i]]--;
            if(m[std[i]] == 0){
                m.erase(std[i]);
            }
            cnt++;
        }
    }
    return cnt * 2 > std.size();
}

int main(){
    vector<string> standard;
    input(standard);
    int stdSize = standard.size();
    // for(auto x : standard){
    //     cout << x << endl;
    // }

    vector<string> student;
    input(student);
    int stuSize = student.size();
    // for(auto x : student){
    //     cout << x << endl;
    // }

    vector<vector<int>> dp(stuSize+1, vector<int>(stdSize+1, 0));
    for (int i = 0; i <= stdSize; i ++){
        dp[0][i] = i * 2;
    }
    for (int i = 0; i <= stuSize; i ++){
        dp[i][0] = i;
    }

    for (int i = 1; i < stuSize+1; i++){
        for(int j = 1; j <= stdSize; j++){
            if(student[i-1] == standard[j-1]){  //无需改变
                dp[i][j] = dp[i - 1][j - 1];
            }else if(isValid(student[i-1], standard[j-1])){ //替换
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = dp[i - 1][j - 1] + 3;    //删除再新增
            }
            dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);     //尝试删除
            dp[i][j] = min(dp[i][j], dp[i][j - 1] + 2);     //尝试新增
        }
    }

    //test
    // string a = "go";
    // string b = "good";
    // cout << isValid(a, b) << endl;
    cout << stdSize - dp[stuSize][stdSize] << endl; //满分为标准答案单词个数-扣分
}