QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149498 | #5460. Sum of Numbers | inverno | TL | 1ms | 9676kb | C++14 | 1.8kb | 2023-08-24 18:44:00 | 2023-08-24 18:44:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 200020;
struct big{
int n;
int a[N];
}ans, nw;
bool inti = 1;
int n, k;
string st;
big operator + (big a, big b) {
int m = max(a.n, b.n);
a.n = m;
a.a[a.n + 1] = 0;
for (int i = 1;i <= m;++ i) {
a.a[i] += b.a[i];
if (a.a[i] > 9) {
a.a[i] -= 10;
a.a[i+1] += 1;
}
}
if (a.a[m + 1] != 0) ++ a.n;
return a;
}
bool operator < (big a, big b) {
if (a.n != b.n) {
return a.n < b.n;
}
for (int i = a.n;i >= 1;-- i) {
if (a.a[i] != b.a[i])
return (a.a[i] < b.a[i]);
}
return false;
}
big cp(int x, int y) {
big c;
c.n = 0;
for (int i = y;i >= x;-- i) {
c.a[++c.n] = st[i - 1] - '0';
}
return c;
}
void dfs(int d, int j, big nw, int len) {
if (d == k) {
if (abs(n - j + 1 - len) > 1) return;
big nw2 = cp(j, n);
nw = nw + nw2;
if (inti || nw < ans) {
ans = nw;
inti = false;
}
return ;
}
if (j > n) return;
for (int h = -1;h <= 1;++ h){
int i = h + len;
if (i <= 0) continue;
if (j + i <= n + 1)
dfs(d + 1, j + i, nw + cp(j,j + i - 1), i);
}
return;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
int tcase = 0;
cin >> tcase;
while (tcase --) {
inti = 1;
cin >> n >> k;
++ k;
cin >> st;
int L = max((int)((double)2 * n / k - (k - 1))/2,1);
int R = min(L + k - 1, n);
for (int i = L;i <= R;++ i)
dfs(2, i + 1, nw = cp(1,i), i);
for (int i = ans.n;i >= 1;-- i) cout << ans.a[i];
cout << endl;
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 9676kb
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:
14784831118837406178836926889338534686282673568766236634755656937882215287385462955156050909263591777812338848367066791388114052424030336665834540855829898074119794503307802569172408047861