ICPC 2018 青岛网络预赛 H Traveling on the Axis

【题目链接】

题目意思

每个案例给你一串01字符，0表示红灯，1表示绿灯，每一秒之后都会改变所有的灯的状态，1变0，0变1，只能通过绿灯，求任意两点距离的总和。

样例输入
3
101
011
11010
样例输出
12
15
43
Hint
For the first sample test case, it’s easy to calculate that t(0,1)=1, t(0,2)=2, t(0,3)=3, t(1,2)=2, t(1,3)=3 and t(2,3)=1, so the answer is 1+2+3+2+3+1=12.
For the second sample test case, it’s easy to calculate that t(0,1)=2, t(0,2)=3, t(0,3)=5, t(1,2)=1, t(1,3)=3 and t(2,3)=1, so the answer is 2+3+5+1+3+1=15.

解题思路

1.假设从0开始，那么遍历可以知道到达每一个点的时间
2.那么从第一个点开始到达每一个点的时间，只需要将第一个点的时间设为1，并将后面的每一个点减去(t[i]-1)，这样就得到了从第一个点开始到达每一个点的时间。
3.同理，第i个点。
4.然后就发现有问题了，针对于0的，起点应该是2，所以特判一下，如果当前是0，多加上n-i+1就好了。
5.树状数组维护前缀和。

AC代码

#include <iostream>
#include <string>
#include <cstring>
#define ll long long
using namespace std;
ll c[100005];
ll a[100005];
ll lowbit(ll k)
{
	return k & (-k);
}
void update(ll k, ll x)
{
	while (k < 100005)
	{
		c[k] += x;
		k += lowbit(k);
	}
}
ll query(ll k)
{
	ll ans = 0;
	while (k > 0)
	{
		ans += c[k];
		k -= lowbit(k);
	}
	return ans;
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(c, 0, sizeof c);
		ll ans = 0;
		string s;
		cin >> s;
		if (s[0] == '0')
			a[1] = 2;
		else
			a[1] = 1;
		for (int i = 2; i <= s.size(); i++)
			a[i] = a[i - 1] + (s[i - 1] == s[i - 2] ? 2 : 1);
		for (int i = 1; i <= s.size(); i++)
			update(i, a[i]);
		for (int i = 1; i <= s.size(); i++)
		{
			ans += (query(s.size()) - query(i - 1)) - (query(i) - query(i - 1) - 1)*(s.size() - i + 1);
			if (s[i - 1] == '0')
				ans += s.size() - i + 1;
		}
		printf("%lld\n", ans);
	}
}