孤独的照片-创新互联
题目链接:4261. 孤独的照片 - AcWing题库
10年积累的网站设计制作、网站建设经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先建设网站后付款的网站建设流程,更有延平免费网站建设让你可以放心的选择与我们合作。分析:思维题ps:一开始以为是字符串问题,然后就是一阵WA...
题解:读完题,你会发现。一张照片里面至少存在3头牛。
错误思想:直接每三头牛为一组照片,判断是否合理。
解释:
1:一张照片里面说的是至少三头牛。GHHH也是符合条件的
2:三个一组,会TLE的
正解:那么如何才能进行思维转化呢?
我们发现,只要照片里面存在一只孤独的牛,那么就会对答案产生贡献。
我们列组样例进行解释:GGHHHGGG
先说思路:我们把每一个相同字符连续的段看为一个贡献者。这个贡献者可能会贡献,也可能不会贡献。
因为只有孤独的牛才会对答案产生贡献。
所以,我们每次只需要在连续的段里面选择一个字符,看他能否在他的左边/右边组成符合条件的照片。
图解:
这里还存在一种情况:夹心(GHG)--->(GGG...H...GGG)
然而这种情况的贡献值:H左边牛的个数*H右边牛的个数(举个夹心情况算一下就会明白哦)
最后再处理一下两端贡献者的贡献就行啦
具体看代码:
#include#define int long long
using namespace std;
const int N=2e6+10;
inline void solve(){
int n;string s;cin>>n>>s;
vectorve;//这里用vector存每段贡献者的长度
for(int i=0,j;i1) ans+=(ve[1]-1)+(ve[(int)ve.size()-2]-1);//最后处理一下两端
cout<
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网站题目:孤独的照片-创新互联
当前链接:http://myzitong.com/article/ecohs.html