牛客比赛第4场 k
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/884/K
牛客第四场 k题
怎么说，有类似的题，是找3的倍数，然后这个就是有了300，也就是在找两个0，然后把0前面的算，在和0的个数-1相乘，再加上累计0的个数到1的时候的和加起来，这个算出最后的总数，遇到1个0的时候就++，自己错了很多遍，然后超时，不知道为啥，最后各种if else飘过，但是自己测试的数据有的不对，但是牛客的测题机器过了，不得不说，还是nb，然后稍微吧最后的情况改掉，就对了，可能就是自己太菜，很多想法题都想不到，如果用暴力肯定会超时，但是你要是用组合数学的话，一般就是n的复杂度
因为能被3整除的数字串的和一定是3的倍数，一开始的思路是记录前缀和，再对每一个前缀和遍历之后的前缀和用后面的前缀和减去前面的前缀和如果差值为3的倍数则ans++ ，但是会t
所以如果是前缀和是一样的，那么就是说这段区间里面的都是可以的，然后在加上组合数学就完全ok
一定记住这个规律，再求任何数k的时候可以直接套用公式，简单易懂，关键是跑得快
然后感谢一位博主https://blog.csdn.net/qq_21433411/article/details/81807960的讲解
自己的菜鸡代码
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef long long ll;
using namespace std;
char s[100005];
int a[100005],b[100005][4];
int main()
{
int i,j;
while(scanf("%s",s+1)!=EOF)
{
ll len=strlen(s+1),ans=0;
int sum=0,flag=0,x=0,y=0,num=0;
a[len+1]=0;
for(i=len;i>0;i--)
{
a[i]=a[i+1]+s[i]-'0';
a[i]%=3;
}
for(i=1;i<=len;i++)
{
if(a[i]==0)
{
b[i][0]=b[i-1][0]+1;
b[i][1]=b[i-1][1];
b[i][2]=b[i-1][2];
}
else if(a[i]==1)
{
b[i][0]=b[i-1][0];
b[i][1]=b[i-1][1]+1;
b[i][2]=b[i-1][2];
}
else if(a[i]==2)
{
b[i][0]=b[i-1][0];
b[i][1]=b[i-1][1];
b[i][2]=b[i-1][2]+1;
}
//xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
if(s[i]=='0'&&flag==0)
{
sum=b[i-1][a[i]];
//cout<<sum<<endl;
flag++;
if(i==len)
ans+=flag;
}
else if(s[i]=='0'&&flag!=0)
{
flag++;
//cout<<"xxx"<<sum<<' '<<flag<<endl;
}
if(s[i]!='0'&&flag<2)
{
ans+=flag;
flag=0;
sum=0;
}
if((s[i]!='0'||i==len)&&flag>=2)
{
ans+=(flag-1)*sum;
for(j=1;j<=flag;j++)
ans+=j;
flag=0;sum=0;
//cout<<"ans="<<ans<<endl;
}
}
cout<<ans<<endl;
}
}
int a[100005],b[100005][4];
int main()
{
int i,j;
while(scanf("%s",s+1)!=EOF)
{
ll len=strlen(s+1),ans=0;
int sum=0,flag=0,x=0,y=0,num=0;
a[len+1]=0;
for(i=len;i>0;i--)
{
a[i]=a[i+1]+s[i]-'0';
a[i]%=3;
}
for(i=1;i<=len;i++)
{
if(a[i]==0)
{
b[i][0]=b[i-1][0]+1;
b[i][1]=b[i-1][1];
b[i][2]=b[i-1][2];
}
else if(a[i]==1)
{
b[i][0]=b[i-1][0];
b[i][1]=b[i-1][1]+1;
b[i][2]=b[i-1][2];
}
else if(a[i]==2)
{
b[i][0]=b[i-1][0];
b[i][1]=b[i-1][1];
b[i][2]=b[i-1][2]+1;
}
//xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
if(s[i]=='0'&&flag==0)
{
sum=b[i-1][a[i]];
//cout<<sum<<endl;
flag++;
if(i==len)
ans+=flag;
}
else if(s[i]=='0'&&flag!=0)
{
flag++;
//cout<<"xxx"<<sum<<' '<<flag<<endl;
}
if(s[i]!='0'&&flag<2)
{
ans+=flag;
flag=0;
sum=0;
}
if((s[i]!='0'||i==len)&&flag>=2)
{
ans+=(flag-1)*sum;
for(j=1;j<=flag;j++)
ans+=j;
flag=0;sum=0;
//cout<<"ans="<<ans<<endl;
}
}
cout<<ans<<endl;
}
}
查看4道真题和解析
