牛客周赛 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;
}