牛客周赛 Round 72 题解
本次牛客最后一个线段树之前我也没碰到过，等后续复习到线段树再把那个题当例题发出来
小红的01串（一）
思路：正常模拟，从前往后遍历一遍去统计即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int a[4];
signed main()
{
cin>>s;
int ans=0;
for(int i=1;i<s.size();i++)
{
if(s[i-1]=='0'&&s[i]=='1')
{
ans++;;
}
if(s[i-1]=='1'&&s[i]=='0')
{
ans++;;
}
}
cout<<ans;
}小红的01串（二）
思路：我们找一下规律，我们发现长度为2的只有1个，长度为3的可以有3个，长度为4的会有6个，所以规律就是长度为n的01交替序列，能产生的值为(1+n-1)*n/2;
然后直接去统计即可
#include <iostream>
#include <string>
using namespace std;
#define int long long
signed main() {
string s;
cin >> s;
int n = s.size();
int result = 0;
int length = 1;
for (int i = 1; i < n; ++i)
{
if (s[i] != s[i - 1])
{
length++;
}
else
{
if (length >= 2)
{
result += (length - 1) * length / 2;
}
length = 1;
}
}
if (length>=2)
{
result += (length - 1) * length / 2;
}
cout << result << endl;
return 0;
}小红的01串（三）
思路：我们首先来分析一下什么时候会是不可能存在的，最大的相邻01子串应当为2*min(a,b)前提是大的要比小的至少多1
然后剩下的就是看k的奇偶性，如果是奇数，那么a,b用的一样多，否则就是大的比小的多用一个
但是呢注意特判，因为有可能为0，如果为0的话，只有a,b同时都不为0，那就是不可能构造出来的，看代码吧
#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int a,b,k;
void solve()
{
cin>>a>>b>>k;
if(k==0&&a!=0&&b!=0)
{
cout<<"-1\n";
return ;
}
if(2*min(a,b)<k)
{
cout<<"-1\n";
return ;
}
else
{
if(k%2==1)
{
int x=(k+1)/2;
a-=x;
b-=x;
for(int i=1; i<=a; i++)
{
cout<<0;
}
for(int i=1; i<=x; i++)
{
cout<<"01";
}
for(int i=1; i<=b; i++)
{
cout<<1;
}
cout<<"\n";
}
else
{
k-=1;
int x=(k+1)/2;
a-=x;
b-=x;
if(a>b)
{
a-=1;
if(a<0)
{
cout<<-1<<"\n";
return ;
}
for(int i=1; i<=a; i++)
{
cout<<0;
}
for(int i=1; i<=x; i++)
{
cout<<"01";
}
for(int i=1; i<=b; i++)
{
cout<<1;
}
cout<<"0";
cout<<"\n";
}
else
{
b-=1;
if(b<0)
{
cout<<-1<<"\n";
return ;
}
cout<<"1";
for(int i=1; i<=a; i++)
{
cout<<0;
}
for(int i=1; i<=x; i++)
{
cout<<"01";
}
for(int i=1; i<=b; i++)
{
cout<<1;
}
cout<<"\n";
}
}
}
}
signed main()
{
cin>>t;
while(t--)
{
solve();
}
return 0;
}
小红的01串（四）
思路：我们可以先去找到右边和当前元素相同和不同的位置，然后跑dp，dp[i]表示到i位置所花的最小花费是多少
ps：dp数组初始化大一点，因为开的太小了，所以导致赛时没过
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,x,y;
string s;
int a[100005];
int same[100005];
int differ[100005];
int dp[100005];
signed main()
{
cin>>n>>x>>y;
cin>>s;
s=' '+s;
for(int i=1;i<=n;i++)
{
same[i]=-1;
differ[i]=-1;
}
memset(dp,0x3f,sizeof(dp));
dp[1]=0;
int num[2]={-1,-1};
for(int i=n;i>=1;i--)
{
if(s[i]=='1')
{
same[i]=num[1];
differ[i]=num[0];
}
else
{
same[i]=num[0];
differ[i]=num[1];
}
num[s[i]-'0']=i;
}
for(int i=1;i<=n;i++)
{
if(same[i]!=-1)
{
dp[same[i]]=min(dp[same[i]],dp[i]+x);
}
if(differ[i]!=-1)
{
dp[differ[i]]=min(dp[differ[i]],dp[i]+y);
}
}
cout<<dp[n];
return 0;
}小红的01串（五）
思路：dp[i][j]表示，选完前i个位置，取模13余j的个数，那么我们就可以发现找到dp转移公式，假设此次后面加上add这个数，那么整题值变化为整体值*10+add
因此dp转移方程为
dp[i+1][(j*10+add)%13]=(dp[i+1][(j*10+add)%13]+dp[i][j])%mod;
#include<bits/stdc++.h>
using namespace std;
#define int long long
string s;
int dp[200005][13];
int mod=1000000007;
signed main()
{
cin>>s;
int n=s.size();
dp[0][0]=1;
for(int i=0;i<n;i++)
{
for(int j=0;j<13;j++)
{
if(dp[i][j]==0)
{
continue;
}
if(s[i]=='0'||s[i]=='1')
{
int add=s[i]-'0';
dp[i+1][(j*10+add)%13]=(dp[i+1][(j*10+add)%13]+dp[i][j])%mod;
}
else
{
for(int add=0;add<=1;add++)
{
dp[i+1][(j*10+add)%13]=(dp[i+1][(j*10+add)%13]+dp[i][j])%mod;
}
}
}
}
cout<<dp[n][0];
return 0;
}