40min AKT1Problem给定一个长度为n的字符串,进行q次操作,每次操作修改其中一个字符,每次修改后输出极长连续字符的段数,如aabbaaa的段数是3。Solutionset存连续段的(起点、终点、字符),每次修改字符的时候最多影响三个连续段,修改后输出set的大小即可。T2Problem同一天内吃糖果的愉悦度为a1+max(0,a2-1)+max(0,a3-2)+...+max(0,ak-k+1),现在有n个糖果a[],问最少需要分几天来吃才能使得愉悦度之和大于等于x。Solution将a[]从大到小排序,二分天数,检验时贪心地将值更大的糖果放在每一天的最前面。Codebool 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;}T3Problem给了n个碎片,每个碎片有重量ai和特征值bi,现在进行q次操作,每次操作选择一个重量为xi的特征值最小的碎片j,将该碎片分成bj片,要求分的重量尽量平均,比如a=5,b=3就会分成[2,2,1],最终输出碎片数量。Solutionmultiset直接模拟,每次最多增加9个碎片,所以multiset中总碎片数量不会很多。T4Problem给了长度为n的数组a和长度为m的数组b,求在a、b中分别取一个数,他们的最小公倍数为k的方案数。Solution考虑将k的因数枚举出来,然后对a、b分别统计数组中每个k的因数的个数,最后只需要考察k的因数之间哪两个因数的最小公倍数是k,将对应的a、b数组中个数相乘,最后求和即可。由于k不超过1e9,其因数最多只有几百个,可以随便做。Codevoid 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;}