QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156668#7109. Traveling on the Axisucup-team133#AC ✓27ms8952kbC++23855b2023-09-02 14:00:142023-09-02 14:37:22

Judging History

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

  • [2023-09-02 14:37:22]
  • 评测
  • 测评结果:AC
  • 用时:27ms
  • 内存:8952kb
  • [2023-09-02 14:00:14]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    string S;
    cin >> S;

    int n = S.size();
    vector dp(n + 1,
              vector<ll>(2));  // i から j (mod 2) にスタートしたときに以降の地点に到達するまでにかかる時間の総和
    dp[n][0] = dp[n][1] = 0;
    ll ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        int x = S[i] - '0';
        for (int j = 0; j < 2; j++) {
            int y = x ^ j;
            if (y == 1)
                dp[i][j] = dp[i + 1][j ^ 1] + (n - i);
            else
                dp[i][j] = dp[i + 1][j] + (n - i) * 2;
        }
        ans += dp[i][0];
    }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    for (; T--;) solve();
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 3576kb

input:

3
101
011
11010

output:

12
15
43

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 27ms
memory: 8952kb

input:

6107
1010101
010110100110101
1010
1010101010010101010
101011
0101101011010101010
0101101011
11011010101
010
1011010
10110101010101010100
010101010110101
10101010101011
0101010101010101011
00101010011000
1010101010010110110
01010101001010101010
101010101010101
100100101010101010
01
011
0101010100101
...

output:

96
889
24
1515
69
1567
279
345
14
106
1702
791
621
1447
764
1615
1755
736
1333
6
15
542
44
1689
1515
140
833
497
596
24
1640
694
462
30
425
14
1041
1446
96
504
124
75
560
970
771
945
6
1
321
137
786
720
206
769
46
103
225
74
554
2
100
529
260
207
197
2
197
1041
140
857
207
1
74
1604
41
343
1041
14
1...

result:

ok 6107 lines

Extra Test:

score: 0
Extra Test Passed