QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#768098 | #5460. Sum of Numbers | wxhtzdy | TL | 0ms | 3512kb | C++20 | 2.1kb | 2024-11-21 00:33:50 | 2024-11-21 00:33:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
k += 1;
string s;
cin >> s;
vector<int> g;
for (int i = 0; i < k; i++) {
g.push_back(n / k);
}
auto Add = [&](string s, string t) {
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
int carry = 0;
int ptr = 0;
string res = "";
while (ptr < int(s.size()) || ptr < int(t.size()) || carry != 0) {
int ds = (ptr < int(s.size()) ? int(s[ptr] - '0') : 0);
int dt = (ptr < int(t.size()) ? int(t[ptr] - '0') : 0);
int d = (ds + dt + carry) % 10;
res += char('0' + d);
carry = (ds + dt + carry) / 10;
ptr += 1;
}
reverse(res.begin(), res.end());
return res;
};
int c = (n / k) * k;
string res = "";
int pw = 1;
for (int i = 0; i < k; i++) {
pw *= 4;
}
for (int t = 0; t < pw; t++) {
int x = t;
vector<int> f;
for (int i = 0; i < k; i++) {
f.push_back(x % 4);
x /= 4;
}
int len = c;
for (int i = 0; i < k; i++) {
len += (f[i] - 1);
}
if (len != n) {
continue;
}
for (int i = 0; i < k; i++) {
g[i] += (f[i] - 1);
}
if (*min_element(g.begin(), g.end()) > 0) {
int ptr = 0;
string sum = "0";
for (int i = 0; i < k; i++) {
string cur = "";
for (int j = 0; j < g[i]; j++) {
cur += s[ptr];
ptr += 1;
}
sum = Add(sum, cur);
}
if (res.empty()) {
res = sum;
} else {
if (int(res.size()) > int(sum.size())) {
res = sum;
} else if (int(res.size()) == int(sum.size())) {
res = min(res, sum);
}
}
}
for (int i = 0; i < k; i++) {
g[i] -= (f[i] - 1);
}
}
cout << res << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3512kb
input:
2 8 1 45455151 2 1 42
output:
9696 6
result:
ok 2 lines
Test #2:
score: -100
Time Limit Exceeded
input:
10 1301 6 56328399613959594774559774218276494124991536454496431869449134772679831477279356599352619469813771742358572734317965823527349354276551857226632977613336815474383422853946661428822284645652423563864641261338984158269966469425994769486371736593879954275146732544891889693921182364554588732946...
output:
2861837555106640794797067737879913860686764066159587941287350938727749577629356630565034353414526438507603808735990935008225192080065174423508575377930722196909797866802717925250679901255 1330897896655974774035586406544907434842835048336411271110427836483063457950873824562288934364096546537492367401...