QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#156888#7109. Traveling on the Axisucup-team061#AC ✓5ms5304kbC++20670b2023-09-02 14:33:542023-09-02 14:57:12

Judging History

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

  • [2023-09-02 14:57:12]
  • 评测
  • 测评结果:AC
  • 用时:5ms
  • 内存:5304kb
  • [2023-09-02 14:33:54]
  • 提交

answer

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

using ll = long long;
const int N = 1e5 + 5;

int n;
ll dp[N][2];
string s;

void solve() {
	cin >> s;
	n = (int)s.size();

	dp[n][0] = dp[n][1] = 0;
	for(int i = n - 1; i >= 0; i--) {
		ll tot = n - i;
		if(s[i] == '0') {
			dp[i][0] = dp[i + 1][0] + 2 * tot;
			dp[i][1] = dp[i + 1][0] + 1 * tot;
		} else {
			dp[i][0] = dp[i + 1][1] + 1 * tot;
			dp[i][1] = dp[i + 1][1] + 2 * tot;
		}
	}

	ll ans = 0;
	for(int i = 0; i < n; i++) {
		ans += dp[i][0];
	}

	cout << ans << "\n";
}

signed main()
{
	ios::sync_with_stdio(false),cin.tie(0);

	int t;
	cin >> t;
	while(t--)solve();
}

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

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3664kb

input:

3
101
011
11010

output:

12
15
43

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 5ms
memory: 5304kb

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