文章

141

粉丝

68

获赞

400

访问

31.2k

头像
TAT的个数 题解:二分计数
P1646 同济大学机试题
发布于2025年3月11日 10:36
阅读数 8

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

int main() {
	string s;
	while(cin>>s){
	    long long ct=0;
	    for(auto x:s){
	        if(x=='T')ct++;
	    }
	    long long ans=0;
	    long long l=0;
	    for(auto x:s){
	        if(x=='T')l++;
	        if(x=='A')ans+=l*(ct-l);
	    }
	    cout<<ans<<endl;
	}
}

本题的核心是发现本质,本质上是找A,划分左右,左侧的T的数量和右侧T的数量的乘积就是该A能生成的TAT的数量,那么,我们只需要统计全部的,划分左右,即可计算出来结果

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发