比赛链接：https://pintia.cn/market/item/1302816969611366400

7-1 多二了一点 (15分)

模拟。

#include
using namespace std;

int sum(string s) {
int res = 0;
for (char c : s) res += c - '0';
return res;
}

int main() {
string s;
cin >> s;
if (s.size() & 1) {
cout << "Error: " << s.size() << " digit(s)" << "\n";
} else {
string s_x = s.substr(s.size() / 2);
string s_y = s.substr(0, s.size() / 2);
if (sum(s_x) - sum(s_y) == 2)
cout << "Yes: " << s_x << " - " << s_y << " = 2" << "\n";
else
cout << "No: " << s_x << " - " << s_y << " != 2" << "\n";
}
}

7-2 数字之王 (20分)

模拟。

#include
using namespace std;

int func(int n) {
if (n == 0) return 0;
int mul = 1;
while (n) {
int x = n % 10;
mul *= x * x * x;
n /= 10;
}
int res = 0;
while (mul) {
res += mul % 10;
mul /= 10;
}
return res;
}

int main() {
int N1, N2;
cin >> N1 >> N2;
vector a(N2 - N1 + 1);
iota(a.begin(), a.end(), N1);
while (any_of(a.begin(), a.end(), [](int x) { return x >= 10; })) {
for (auto &x : a)
x = func(x);
}
int mx = 0;
map cnt;
for (auto x : a) {
if (++cnt[x] > mx)
mx = cnt[x];
}
vector ans;
for (auto i : cnt) {
if (i.second == mx)
ans.push_back(i.first);
}
sort(ans.begin(), ans.end());
cout << mx << "\n";
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " \n"[i == ans.size() - 1];
}

7-3 如需挪车请致电 (20分)

有点麻烦的模拟。

#include
using namespace std;

map mp{
{"ling", 0},
{"yi", 1},
{"er", 2},
{"san", 3},
{"si", 4},
{"wu", 5},
{"liu", 6},
{"qi", 7},
{"ba", 8},
{"jiu", 9}
};

int to_int(string s) {
if (mp.count(s)) {
return mp[s];
} else {
int res = 0;
for (int i = 0; i < int(s.size()); i++)
res = res * 10 + s[i] - '0';
return res;
}
}

int func(string s) {
if (s.find("sqrt") != string::npos) {
return sqrt(to_int(s.substr(4)));
}
for (char oper : string("+-*/%^")) {
int oper_pos = s.find(oper);
if (oper_pos != string::npos) {
int a = to_int(s.substr(0, oper_pos));
int b = to_int(s.substr(oper_pos + 1));
if (oper == '+') return a + b;
if (oper == '-') return a - b;
if (oper == '*') return a * b;
if (oper == '/') return a / b;
if (oper == '%') return a % b;
if (oper == '^') return pow(a, b);
}
}
return to_int(s);
}

int main() {
for (int i = 0; i < 11; i++) { string s; cin >> s;
cout << func(s);
}
}

7-4 胖达与盆盆奶 (20分)

将熊猫的编号视作横坐标，体重视作纵坐标，将纵坐标相连即得一条凹凸的曲线，每次从曲线的凹处向两边延伸，两个凹处的相接点取较大值。

#include
using namespace std;
int main() {
int n;
cin >> n;
vector a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int x, int y) {
return a[x] < a[y]; }); vector milk(n);
vector vis(n);
for (auto i : p) {
if (vis[i]) continue;
milk[i] = 200;
vis[i] = true;
for (int j = i - 1; j >= 0 and a[j] >= a[j + 1]; j--) {
milk[j] = max(milk[j], milk[j + 1] + (a[j] > a[j + 1] ? 100 : 0));
vis[j] = true;
}
for (int j = i + 1; j < n and a[j] >= a[j - 1]; j++) {
milk[j] = max(milk[j], milk[j - 1] + (a[j] > a[j - 1] ? 100 : 0));
vis[j] = true;
}
}
cout << accumulate(milk.begin(), milk.end(), 0) << "\n";
}

7-5 买地攻略 (25分)

$O_{(n^2)}$，枚举区间的左右端点，但理论上来讲应该过不了。

#include
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += a[j];
if (sum <= m) ++ans;
}
}
cout << ans << "\n";
}

$O_{(nlog_n)}$，枚举区间左端点，利用前缀和二分查找右端点。

#include
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector a(n);
for (int i = 0; i < n; i++) cin >> a[i];
vector pre(n);
for (int i = 0; i < n; i++) {
if (i == 0) pre[i] = a[i];
else pre[i] = pre[i - 1] + a[i];
}
int ans = 0;
for (int i = 0; i < n; i++) {
int j = upper_bound(pre.begin(), pre.end(), (i == 0 ? 0 : pre[i - 1]) + m) - pre.begin();
ans += j - i;
}
cout << ans << "\n";
}