QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#149498#5460. Sum of NumbersinvernoTL 1ms9676kbC++141.8kb2023-08-24 18:44:002023-08-24 18:44:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-24 18:44:03]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:9676kb
  • [2023-08-24 18:44:00]
  • 提交

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

result: