首先是A题,看错题目了,本来应该计算大于50,结果算了小于等于50的。
下面是正解代码:
#include <bits/stdc++.h>
using namespace std;
int mon2day(int y, int m) {
if (m & 1 && m < 8)return 31;
if (!(m & 1) && m >= 8)return 31;
if (m == 2)
return (y % 4 == 0) ? 29 : 28;
else
return 30;
}
int ch2num[10] = {13, 1, 2, 3, 5, 4, 4, 2, 2, 2};
struct Date {
int year, mon, day;
auto operator++() {
day++;
if (day > mon2day(year, mon))
day = 1, mon++;
if (mon > 12)
mon = 1, year++;
return *this;
}
int flatten() const {
return year * 10000 + mon * 100 + day;
}
int getSum() const {
int date = flatten();
int sum = 0;
while (date) {
sum += ch2num[date % 10];
// cout << date % 10 << " " << sum << endl;
date /= 10;
}
return sum;
}
auto operator<=>(const Date&b) const {
return flatten() <=> b.flatten();
}
};
int main() {
int ans = 0;
for (auto d = Date{2000, 1, 1}; d <= Date{2024, 4, 13}; ++d) {
int sum = d.getSum();
cout << d.flatten() << " " << sum << endl;
if (sum > 50) ans++;
}
cout << ans << endl;
return 0;
}
接下来C题,二分没什么问题。(由于比较菜,写不好二分,所以直接用STL了)
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 1e6 + 5;
int n, S;
int p[N], c[N];
// cost的缓存
int cost[N];
// 与第gnum次组团训练相当的代价
int getCost(int gnum) {
if (cost[gnum] != 0) return cost[gnum];
int sum = 0;
for (int i = 1; i <= n; i++) {
if (c[i] >= gnum )sum += p[i];
}
return cost[gnum] = sum;
}
// 进行ss次组团训练的情况,用来排序
// 存的数据是ss,排序指标是getCost(ss)
struct Case {
int ss;
auto operator<(auto b) const {
return getCost(ss) > getCost(b.ss);
}
auto operator==(auto b) const {
return getCost(ss) == getCost(b.ss);
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> S;
int max_c = 0;
for (int i = 1; i <= n; i++) {
cin >> p[i] >> c[i];
max_c = max(max_c, c[i]);
}
vector<Case> vec;
for (int i = 1; i <= max_c; i++) {
vec.push_back({i});
// cout << "S_num=" << i << ", S_cost=" << getCost(i) << endl;
}
auto target = Case{0};
cost[0] = S;
auto l = lower_bound(vec.begin(), vec.end(), target);
int group_num = max_c;
if (l != vec.end())
group_num = l->ss - 1;
int ans = S * group_num;
for (int i = 1; i <= n; i++) {
c[i] = max(0LL, c[i] - group_num);
ans += c[i] * p[i];
}
cout << "ans = " << ans << endl;
return 0;
}