40min AK

T1

Problem

给定一个长度为n的字符串，进行q次操作，每次操作修改其中一个字符，每次修改后输出极长连续字符的段数，如aabbaaa的段数是3。

Solution

set存连续段的（起点、终点、字符），每次修改字符的时候最多影响三个连续段，修改后输出set的大小即可。

T2

Problem

同一天内吃糖果的愉悦度为a1+max(0,a2-1)+max(0,a3-2)+...+max(0,ak-k+1)，现在有n个糖果a[]，问最少需要分几天来吃才能使得愉悦度之和大于等于x。

Solution

将a[]从大到小排序，二分天数，检验时贪心地将值更大的糖果放在每一天的最前面。

Code

bool check(vector<int>& a, int x, int m) {
    long long sum = 0;
    for (int i = 0; i < a.size(); ++i) {
        sum += max(0, a[i] - i / m);
    }
    return sum >= x;
}

int main() {
    int n, x; cin >> n >> x;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    sort(a.begin(), a.end(), greater<int>());
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(a, x, mid))r = mid - 1;
        else l = mid + 1;
    }
    cout << l;
}

T3

Problem

给了n个碎片，每个碎片有重量ai和特征值bi，现在进行q次操作，每次操作选择一个重量为xi的特征值最小的碎片j，将该碎片分成bj片，要求分的重量尽量平均，比如a=5,b=3就会分成[2,2,1]，最终输出碎片数量。

Solution

multiset直接模拟，每次最多增加9个碎片，所以multiset中总碎片数量不会很多。

T4

Problem

给了长度为n的数组a和长度为m的数组b，求在a、b中分别取一个数，他们的最小公倍数为k的方案数。

Solution

考虑将k的因数枚举出来，然后对a、b分别统计数组中每个k的因数的个数，最后只需要考察k的因数之间哪两个因数的最小公倍数是k，将对应的a、b数组中个数相乘，最后求和即可。由于k不超过1e9，其因数最多只有几百个，可以随便做。

Code

void getFactor(vector<int>& fact, int k) {
    for (int i = 1; i * i <= k; ++i) {
        if (k % i == 0) {
            fact.push_back(i);
            if (i * i != k) {
                fact.push_back(k / i);
            }
        }
    }
    sort(fact.begin(), fact.end());
}
int getLoc(vector<int>& v, int x) {
    int loc = lower_bound(v.begin(), v.end(), x) - v.begin();
    if (loc >= 0 && loc < v.size() && v[loc] == x) {
        return loc;
    }
    return -1;
}
int main() {
    int n, m, k; cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    vector<int> fact, cnt_a, cnt_b;
    getFactor(fact, k); // 获取k因数，存在fact中，并排序
    cnt_a.resize(fact.size(), 0);
    cnt_b.resize(fact.size(), 0);
    for (int i = 0; i < n; ++i) {
        int loc = getLoc(fact, a[i]); // 找到fact中a[i]的下标，不存在返回-1
        if (loc != -1) {
            cnt_a[loc]++;
        }
    }
    for (int i = 0; i < m; ++i) {
        int loc = getLoc(fact, b[i]); // 找到fact中a[i]的下标，不存在返回-1
        if (loc != -1) {
            cnt_b[loc]++;
        }
    }
    long long ans = 0;
    for (int i = 0; i < fact.size(); ++i) {
        for (int j = 0; j < fact.size(); ++j) {
            if (lcm(fact[i], fact[j]) == k) {
                ans += (long long)cnt_a[i] * cnt_b[j];
            }
        }
    }
    cout << ans;
}