文章

68

粉丝

691

获赞

24

访问

547.7k

头像
有点迷,前缀和数组不行吗?为啥一直50
P1646 同济大学机试题
发布于2020年6月1日 13:43
阅读数 8.0k

 

#define inf 0x3f3f3f3f
#define ll long long
#define vec vector<int,int>
#define P pair<int,int>
#define MAX 100005

int main() {
	string s;
	ll sumt[MAX];
	while (cin >> s) {
		ll res = 0;
		memset(sumt, 0, sizeof(sumt));
		sumt[0] = s[0] == 'T' ? 1 : 0;
		for (int i = 1; i < s.size(); i++) {
			if (s[i] == 'T')sumt[i] = sumt[i - 1] + 1;
			else sumt[i] = sumt[i - 1];
		}
		for (int i = 1; i < s.size(); i++) {
			if (s[i] == 'A') {
				res += sumt[i] * (sumt[s.size() - 1] - sumt[i]);
			}
		}
		cout << res << endl;
	}
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发