CDE题

C题：构造

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

void put0(int x)
{
    while(x>0)cout<<0,x--;
}

void put1(int x)
{
    while(x>0)cout<<1,x--;
}

void put01(int x)
{
    while(x>0)cout<<0<<1,x--;
}

void solved()
{
    int a,b,k;cin>>a>>b>>k;
    
    if(k==0)
    {
        if(a && b)cout<<-1;
        else put0(a),put1(b);
    }
    else
    {
        if(a==b && k>min(a,b)*2-1)cout<<-1;
        else if(a!=b && k>min(a,b)*2)cout<<-1;
        else
        {
            if(k&1)//奇数
            {
                int d=(k+1)/2;
                put0(a-d),put01(d),put1(b-d);
            }
            else//偶数
            {
                int d=k/2;
                if(a>=b)put0(a-d-1),put01(d),put1(b-d),put0(1);
                else put1(1),put0(a-d),put01(d),put1(b-d-1);
            }
        }
    }
    cout<<'\n';
}

int main()
{
    int t;
    cin>>t;
    while(t--)solved();
	return 0;
}

D题法一：dp，直接顺推就行

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

void solved()
{
    int n,x,y;cin>>n>>x>>y;
    string s;cin>>s;s=" "+s;
    vector<int> f(n+1,1e18),ne0(n+1),ne1(n+1);
    
    //ne0[i],ne1[i]分别表示i位置右边最近的0和1的位置
    int p0=0,p1=0;
    for(int i=n;i>=1;i--)//预处理ne0[i],ne1[i]
    {
        ne0[i]=p0,ne1[i]=p1;
        s[i]=='1'?p1=i:p0=i;
    }
    
    f[1]=0;
    for(int i=1;i<=n;i++)//顺序递推即可
    {
        if(ne1[i])f[ne1[i]]=min(f[ne1[i]],f[i]+(s[i]=='1'?x:y));
        if(ne0[i])f[ne0[i]]=min(f[ne0[i]],f[i]+(s[i]=='0'?x:y));
    }
    cout<<f[n];
}

signed main()
{
    solved();
	return 0;
}

D题法二：Dijkstra求单源最短路

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

using PII=pair<int,int>;

void solved()
{
    int n,x,y;cin>>n>>x>>y;
    string s;cin>>s;s=" "+s;
    
    vector<int> ne0(n+1),ne1(n+1);
    //ne0[i],ne1[i]分别表示i位置右边最近的0和1的位置
    int p0=0,p1=0;
    for(int i=n;i>=1;i--)//预处理ne0[i],ne1[i]
    {
        ne0[i]=p0,ne1[i]=p1;
        s[i]=='1'?p1=i:p0=i;
    }
    
    //Dijkstra求单源最短路
    vector<int> f(n+1,1e18),vis(n+1,0);
    priority_queue<PII,vector<PII>,greater<PII>> q;
    q.push({0,1});f[1]=0;
    
    while(q.size())
    {
        auto[cost,t]=q.top();q.pop();
        
        if(vis[t])continue;
        vis[t]=1;
        
        int x0=ne0[t],x1=ne1[t];
        if(x0)
        {
            int d=(s[t]=='0'?x:y);
            if(cost+d<f[x0])
            {
                f[x0]=cost+d;
                q.push({f[x0],x0});
            }
        }
        if(x1)
        {
            int d=(s[t]=='1'?x:y);
            if(cost+d<f[x1])
            {
                f[x1]=cost+d;
                q.push({f[x1],x1});
            }
        }
    }
    cout<<f[n];
}

signed main()
{
    solved();
	return 0;
}

E题：dp，跟D题一样直接顺推就行

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

const int mod=1e9+7;

void solved()
{
	string s;cin>>s;
	int n=s.size();s=" "+s;
	
	//f[i][j]:前i个组成的整数模13余j的方案数 
	vector<vector<int>> f(n+1,vector<int> (13));
	
	f[0][0]=1;//初值 
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='?')
		{
			for(int j=0;j<13;j++)//?有两种情况：即可能是1也可能是0 
			{
				f[i][(j*10)%13]+=f[i-1][j]; 
				f[i][(j*10)%13]%=mod;
				f[i][(j*10+1)%13]+=f[i-1][j]; 
				f[i][(j*10+1)%13]%=mod;
			}
		}
		else
		{
			for(int j=0;j<13;j++)
			{
				f[i][(j*10+s[i]-'0')%13]+=f[i-1][j]; 
				f[i][(j*10+s[i]-'0')%13]%=mod;
			}
		}
	}
	cout<<f[n][0];//答案：前n个数组成的整数%13等于0的方案数 
}

signed main()
{
    solved();
	return 0;
}