阿里研发岗0407编程题题解

这场考试感觉码量比较大，做完选择题，还剩一个小时出头，还以为写不完。
最后还剩5分钟写完了，挺刺激的。。。

进制转换

写个函数，对p进制处理一下
如果p进制不行，就是字符串中有个字符大于等于p，就返回-1

wa了几发，发现题目还有相同结果，保留一个
吐了

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mod = 7 + 1e9;

string s;
vector<int> a;
vector<int> b;

int calc(int p) {
    LL ans = 0;
    for (auto &i : a) {
        if (i >= p) return -1;
        ans = ans * p + i;
        ans %= mod;
    }
    return ans;
}

int main() {
    cin >> s;

    auto f = [](char v) {
        if (isdigit(v)) return v - '0';
        return v - 'A' + 10;
    };
    for (auto & i : s) {
        a.push_back(f(i));
    }

    for (int i = 2; i <= 16; ++i) {
        int val = calc(i);
        if (val < 0) continue;
        b.push_back(val);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (auto &i : b) cout << i << endl;
    return 0;
}

小红的账单

读到题，发现要自己处理数字，什么毒瘤出题人

发现带冒号的字符串，都是冒号左边是没啥用的字符串，右边是小数
写成一个函数，先找到冒号这个分界，再用substr和atof（字符串转double）处理一下就好了

#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;
const int N = 503;

string month[] = {"", "January", "February", "March",  "April", "May", "June", "July", "August", "September", "October", "November", "December"};

pair<string, double> get() {
    string s;
    cin >> s;
    int p = 0;
    while (s[p] != ':')
        ++p;
    return {s.substr(0, p), atof(s.substr(p + 1).c_str())};
}

int main() {
    double a = 1e9, b = -1e9;
    int pa = 0, pb = 0;
    for (int i = 1; i <= 12; ++i) {
        auto g = get();
        // cout << "*** " << g.first << ' ' << g.second << endl;
        double in = 0, out = 0;
        for (int j = 1; j <= g.second; ++j) {
            auto c = get();
            // cout << "*** **" << c.first << ' ' << c.second << endl;
            if (c.second > 0)
                in += c.second;
            else
                out += c.second;
        }
        if (a > out) {
            a = out;
            pa = i;
        }
        if (b < in) {
            b = in;
            pb = i;
        }
        printf("%s:%s%.2f\n", month[i].c_str(), in + out >= 0 ? "+" : "", in + out);
    }
    cout << month[pa] << ' ' << month[pb] << endl;
    return 0;
}

小红的子串删除

(感觉双指针出烂了，但是他这是删除，又绕了几下，调了好久...)

枚举左端点
找到不合法的右端点
now表示删除这个区间后，字符的种类

当挪到时，（这个和前面那个不太一样）就是合法的区间
所以ans加上
因为边界问题，右端点也可能合法，需要特判

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 3 + 2e5;

int n, k;
char s[N];
int cnt[26], now;

int main() {
    cin >> n >> k;
    cin >> s + 1;
    // 这个循环结束后，now就是整个字符串的字符种类数
    for (int i = 1; i <= n; ++i) {
        now += !cnt[s[i] - 'a']++;
    }
    LL ans = 0;
    for (int i = 1, j = 1; j <= n; ++j) {
        while (i <= n && now >= k) {
            now -= !--cnt[s[i] - 'a'];
            ++i;
        }
        ans += i - j - 1;
        if (now >= k) ++ans; // 特判
        now += !cnt[s[j] - 'a']++;
    }
    cout << ans << endl;
    return 0;
}