上海交通大学计算机考研复试上机题题解

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
char s[N], p[N];
int ne[N];
 
int main() {
    scanf("%s %s", s + 1, p + 1);
    int n = strlen(p + 1), m = strlen(s + 1);
    for(int i = 2, j = 0; i <= n; i++) {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }
    int ans = 0;
    for(int i = 1, j = 0; i <= m; i++) {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j++;
        if(j == n) ans++;
    }
    printf("%d\n", ans);
    return 0;
}

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
//ax^2+bx+c=0
int a = 0, b = 0, c = 0;
 
void process(string& src) {
    int t = 0;
    bool neg = false, left = true;
    for (int i = 0; i < src.size(); i++) {
        if (src[i] == '=' || src[i] == '+') {
            if ((left ^ neg) == false) t *= -1;
            c += t;
            t = 0;
            if (src[i] == '=') left = false;
            continue;
        }
        else {
            //-, +, x ^
            if (src[i] == 'x') {
                if (t == 0) t = 1;
                if ((left ^ neg) == false) t *= -1;
                if (src.substr(i, 3) == "x^2") {
                    i += 2;
                    a += t;
                } else {
                    b += t;
                }
                neg = false;
                t = 0;
            }
            else if (src[i] == '-') {
                if ((left ^ neg) == false) t *= -1;
                c += t;
                t = 0;
                neg = true;
            }
            else {
                t = t * 10 + src[i] - '0';
            }
        }
    }
    if (t) {
        if ((left ^ neg) == false) t *= -1;
        c += t;
        t = 0;
    }
}
 
void solve() {
    int delta = b * b - 4 * a * c;
    if (delta < 0) cout << "No Solution" << endl;
    else if (delta == 0) cout << -double(b) / (2 * a) << endl;
    else {
        double x1, x2;
        x1 = (-(double)b + sqrt(delta)) / (2 * a);
        x2 = (-(double)b - sqrt(delta)) / (2 * a);
        if (x1 > x2) swap(x1, x2);
        cout << x1 << ' ' << x2 << endl;
    }
}
 
int main() {
    string src;
    cin >> src;
    process(src);
    cout << fixed << setprecision(2);
    solve();
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    string src;
    getline(cin, src);
    const vector<string> tbl = {
        "`1234567890-=",
        "QWERTYUIOP[]\\",
        "ASDFGHJKL;\'",
        "ZXCVBNM,./",
    };
    for(int i = 0; i < src.size(); i++) {
        bool find = false;
        for(int j = 0; j < 4 && !find; j++) {
            auto t = tbl[j].find(src[i]);
            if(t == string::npos) continue;
            else {
                if(t > 0) src[i] = tbl[j][t - 1];
                find = true;
            }
        }
    }
    cout << src << endl;
    return 0;
}

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    set<int> S;
    while(n--) {
        int a;
        cin >> a;
        S.insert(a);
    }
    for(auto &it: S) cout << it << " ";
    cout << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {
    int n, x, y, z;
    while (cin >> n >> x >> y >> z) {
        int middle = x * 100 + y * 10 + z;
        bool not_found = true;
        for (int i = 9; i >= 1 && not_found; i--) {
            for (int j = 9; j >= 0; j--) {
                int total = middle * 10 + i * 10000 + j;
                if (total % n == 0) {
                    cout << i << ' ' << j << ' ' << total / n << endl;
                    not_found = false;
                    break;
                }
            }
        }
        if(not_found) cout << 0 << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
 
const int N = 31;
 
int fib[N];
 
int main() {
    fib[0] = 0, fib[1] = 1;
    int n;
    cin >> n;
    for(int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    cout << fib[n] << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
string dfs(int n) {
    if(n == 1) return "2(0)";
    if(n == 2) return "2";
    vector<int> division;
    for(int i = 0; i < 30; i++) {
        if(n & (1 << i)) division.emplace_back(i);
    }
    if(division.size() == 1) return "2(" + dfs(division.back()) + ")";
    string ans(dfs(1 << division.back()));
    for(int i = division.size() - 2; i >= 0; i--) {
        ans += "+" + dfs(1 << division[i]);
    }
    return ans;
}
 
int main(){
    int n;
    cin >> n;
    cout << dfs(n) << endl;
    return 0;
}

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

vector<string> split(const string src, char splitter) {
    vector<string> ans;
    string buffer;
    for (auto& c : src) {
        if (c == splitter) {
            if (buffer.size()) ans.push_back(buffer);
            buffer.clear();
        }
        else buffer.push_back(c);
    }
    if (buffer.size()) ans.push_back(buffer);
    return ans;
}

class tree {
private:
    struct node {
        string val;
        map<string, node*> children;
        node(const string init) : val(init) {}
    } *root;
    void delete_tree(node* root) {
        if (nullptr == root) return;
        for (auto& [key, ptr] : root->children) {
            delete_tree(ptr);
        }
        delete root;
        root = nullptr;
    }
    void _add_path_(node* root, const vector<string>& splitted_line, int cur_depth) {
        if (cur_depth == splitted_line.size()) return;
        auto exist = root->children.find(splitted_line[cur_depth]);
        if (exist != root->children.end()) {
            _add_path_((*exist).second, splitted_line, cur_depth + 1);
        }
        else {
            node* new_node = new node(splitted_line[cur_depth]);
            root->children.insert({ splitted_line[cur_depth], new_node });
            _add_path_(new_node, splitted_line, cur_depth + 1);
        }
    }
    void _print_tree_(node* root, int cur_depth) {
        if (nullptr == root) return;
        if (root->val.size()) { 
            cout << string(2 * (cur_depth - 1), ' ') << root->val << endl;
        }
        for (auto& [key, ptr] : root->children) {
            _print_tree_(ptr, cur_depth + 1);
        }
    }
public:
    tree() { root = new node(""); }
    ~tree() { delete_tree(root); }
    void add_path(const vector<string>& splitted_line) { 
        _add_path_(root, splitted_line, 0); 
    }
    void print_tree() { _print_tree_(root, 0); }
};

int main() {
    int n;
    while (cin >> n, n) {
        cin.get();
        string line;
        tree T;
        for (int i = 0; i < n; i++) {
            getline(cin, line);
            auto splitted_line = split(line, '\\');
            T.add_path(splitted_line);
        }
        T.print_tree();
        cout << endl;
    }
    return 0;
}

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

vector<int> primes;

bool is_prime(int n) {
    if (n == 2) return true;
    if (n == 1 || n % 2 == 0) return false;
    for (int i = 3; i <= n / i; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

void get_primes() {
    for (int i = 2; i <= 1000; i++) {
        if (is_prime(i)) primes.push_back(i);
    }
}

int main() {
    get_primes();
    int n, a;
    cin >> n >> a;
    unordered_map<int, int> ma, mn;
    for (int i = 2; i <= a / i; i++) {
        while (a % i == 0) {
            ma[i]++;
            a /= i;
        }
    }
    if (a > 1) ma[a]++;
    for (auto& prime : primes) {
        int nn = n;
        if (nn / prime) {
            while (nn) {
                mn[prime] += nn / prime;
                nn /= prime;
            }
        }
    }
    int k = 0;
    bool flag = true;
    while(flag) {
        for (auto& [x, y] : ma) {
            if (mn.find(x) == mn.end() || mn[x] < (k + 1) * y) {
                flag = false;
                break; 
            }
        }
        if (flag) k++;
    }
    cout << k << endl;
    return 0;
}

#include <stack>
#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<char, int> pri_level{ {'+', 1}, {'-', 1}, {'*', 2}, {'/', 2} };

void single_calaulation(stack<double>& operands, stack<char>& operators) {
    double a = operands.top(); operands.pop();
    double b = operands.top(); operands.pop();
    char op = operators.top(); operators.pop();
    switch (op) {
        case '+': operands.push(a + b); break;
        case '-': operands.push(b - a); break;
        case '*': operands.push(a * b); break;
        case '/': operands.push(b / a); break;
    }
}

int calculation(const string& src) {
    stack<double> operands;
    stack<char> operators;
    for (int i = 0; i < src.size(); i++) {
        if (isdigit(src[i])) {
            int num = 0, j = i;
            while (j < src.size() && isdigit(src[j])) {
                num = num * 10 + src[j] - '0';
                j++;
            }
            i = j - 1;
            operands.push(num);
        } else {
            while (!operators.empty() && pri_level[operators.top()] >= pri_level[src[i]]) {
                single_calaulation(operands, operators);
            }
            operators.push(src[i]);
        }
    }
    while (!operators.empty()) single_calaulation(operands, operators);
    return (int)operands.top();
}

int main() {
    string line;
    while (getline(cin, line), line.size()) {
        cout << calculation(line) << endl;
    }
    return 0;
}

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

constexpr int MAX_LEN = 105;

string s1, s2;
int f[MAX_LEN][MAX_LEN];

int dp(int ptr1, int ptr2) {
    if (ptr1 == s1.size() || ptr2 == s2.size()) return 0;
    if (~f[ptr1][ptr2]) return f[ptr1][ptr2];
    int ans = 0;
    if (s1[ptr1] == s2[ptr2]) ans = dp(ptr1 + 1, ptr2 + 1) + 1;
    else ans = max(dp(ptr1 + 1, ptr2), dp(ptr1, ptr2 + 1));
    return f[ptr1][ptr2] = ans;
}

int main() {
    cin >> s1 >> s2;
    memset(f, -1, sizeof f);
    cout << dp(0, 0) << endl;
    return 0;
}

#include <iostream>
using namespace std;
 
const int N = 1e2 + 10;
 
int a[N][N];
 
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
        }
    }
    int ans = 1e7;
    for (int x1 = 1; x1 <= n; x1++) {
        for (int y1 = 1; y1 <= m; y1++) {
            for (int x2 = x1; x2 <= n; x2++) {
                for (int y2 = y1; y2 <= m; y2++) {
                    int s = a[x2][y2] + a[x1 - 1][y1 - 1] - a[x2][y1 - 1] - a[x1 - 1][y2];
                    if (s >= k) {
                        ans = min(ans, (x2 - x1 + 1) * (y2 - y1 + 1));
                    }
                }
            }
        }
    }
    if (ans > 1e4) cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
 
const int N = 102, MOD = 1e5, INF = 0x3f3f3f3f;
 
int n, m;
int g[N][N], dist[N], p[N];
bool st[N];

int find(int x) {
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}
 
void dijkstra() {
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
    for(int i = 0; i < n; i++) {
        int t = -1;
        for(int j = 0; j < n; j++) {
            if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        st[t] = true;
        for(int j = 0; j < n; j++) {
            dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
}
 
int main() {
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) p[i] = i;
    int cost = 1;
    while(m--) {
        int a, b;
        cin >> a >> b;
        // 若城市之间已存在道路，则一定是选择代价小的道路（先输入的道路）
        if(find(a) != find(b)){
            p[find(a)] = find(b);
            g[a][b] = g[b][a] = cost;
        }
        cost = cost * 2 % MOD;
    }
    dijkstra();
    for(int i = 1; i < n; i++) {
        if(dist[i] > INF / 2) cout << -1 << endl;
        else cout << dist[i] % MOD << endl;
    }
    return 0;
}

#include <iostream>
#include <unordered_map>
using namespace std;
 
unordered_map<int, int> p;
 
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
 
void merge(int a, int b) {
    p[find(a)] = find(b);
}
 
int main() {
    int s, e;
    while (cin >> s >> e) {
        if (p.find(s) == p.end()) p[s] = s;
        if (p.find(e) == p.end()) p[e] = e;
        merge(s, e);
    }
    int ans = 0;
    for (auto& it : p) {
        int i = it.first;
        if (find(i) == i) ans++;
    }
    cout << ans << endl;
    return 0;
}

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

const vector<string> months{
    "January", "February", "March", "April", "May", "June", "July", "August",
    "September", "October", "November", "December"
};

const vector<string> weekdays{
    "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday",
    "Sunday"
};

int days_in_months[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

int get_month_from_str(const string src) {
    int i = 0;
    for (; i < months.size(); i++) {
        if (months[i] == src) return i + 1;
    }
    return -1;
}

bool is_leap(int year) {
    return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
}

int main() {
    int day, year;
    string month_str;
    while (cin >> day >> month_str >> year) {
        int month = get_month_from_str(month_str);
        int delta_day = 0;
        for (int i = 1000; i < year; i++) {
            delta_day += is_leap(i) + 365;
        }
        days_in_months[2] = is_leap(year)? 29: 28;
        for (int start_month = 1, start_day = 1; ;) {
            if (start_month != month) {
                delta_day += days_in_months[start_month];
                start_month++;
            } else {
                delta_day += day - 1;
                break;
            }
        }
        int res = (delta_day + 2) % 7;
        cout << weekdays[res] << endl;
    }
    return 0;
}

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

int days_in_months[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

struct date {
    int year, month, day;
};

date get_date(const string src) {
    int year = 0, month = 0, day = 0;
    for (int i = 0; i < 4; i++) {
        year = year * 10 + src[i] - '0';
    }
    for (int i = 4; i < 6; i++) {
        month = month * 10 + src[i] - '0';
    }
    for (int i = 6; i < 8; i++) {
        day = day * 10 + src[i] - '0';
    }
    return { year, month, day };
}

bool is_leap(int year) {
    return year % 400 == 0 || (year % 100 != 0 && year % 4 == 0);
}

int calculate(date date1, date date2) {
    int ans = 0;
    // 处理最后一个月的问题
    if (date1.day > date2.day) {
        ans += date2.day;
        date2.month--;
        if (date2.month == 0) {
            date2.year--;
            date2.month = 12;
        }
        days_in_months[2] = is_leap(date2.year) ? 29 : 28;
        date2.day = days_in_months[date2.month];
    }
    days_in_months[2] = is_leap(date2.year) ? 29 : 28;
    for (int i = date1.year; i < date2.year; i++) {
        ans += 365 + is_leap(i);
    }
    for (int month = date1.month, day = date1.day;;) {
        if (month < date2.month) {
            ans += days_in_months[month++];
        } else {
            ans += date2.day - date1.day + 1;
            break;
        }
    }
    return ans;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    date date1 = get_date(s1), date2 = get_date(s2);
    // 当date1与date2先后顺序不定时需要以下代码
    // //判断date1 & date2 哪个日期靠后，返回date1 < date2
    // auto cmp = [](const date& date1, const date& date2) {
    //     return date1.year < date2.year ||
    //            date1.year == date2.year && date1.month < date2.month ||
    //            date1.year == date2.year && date1.month == date2.month && date1.day < date2.day;
    // };
    // if (!cmp(date1, date2)) swap(date1, date2);
    cout << calculate(date1, date2) << endl;
    return 0;
}

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

const int N = 1e6 + 10;

int arr1[N], arr2[N], merged[N * 2], idx = 0;
int a, b, c, d;

int main() {
    int l1, l2;
    cin >> l1 >> l2;
    for (int i = 1; i <= l1; i++) cin >> arr1[i];
    for (int i = 1; i <= l2; i++) cin >> arr2[i];
    cin >> a >> b >> c >> d;
    for (int i = a; i <= b; i++) merged[idx++] = arr1[i];
    for (int i = c; i <= d; i++) merged[idx++] = arr2[i];
    // 如果有两个中间值，则取较小的
    cout << merged[(idx - 1) / 2] << endl;
    return 0;
}