2019年ccpc秦皇岛赛区（I题）

87 阅读 0 评论 58 点赞

我是靠谱客的博主默默机器猫，最近开发中收集的这篇文章主要介绍2019年ccpc秦皇岛赛区（I题），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意就是题目里面给你了一些字母，然后每个字母是由三个字符代表的，这三个字符的顺序是无序，然后现在给你一个字符串，问可以构成这个字符串的最短子串是多长，实测AC。

类似暴力的dp，自己的dp水平还是不行。代码能力也有待提高。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    string A[10];
    int AA[10];
} E[20];
map<char,int>MAP;
char B[100000+10];
#define inf 0x3f3f3f3f
int main()
{
    
    cout<<!1<<endl;

    MAP.clear();
    E[1].A[0]="QQQ";
    E[2].A[0]="QQW";
    E[3].A[0]="QQE";
    E[4].A[0]="WWW";
    E[5].A[0]="QWW";
    E[6].A[0]="WWE";
    E[7].A[0]="EEE";
    E[8].A[0]="QEE";
    E[9].A[0]="WEE";
    E[10].A[0]="QWE";
    for(int i=1; i<=10; i++)
    {
        char W[10];
        sort(E[i].A[0].begin(),E[i].A[0].end());
        for(int j=0; j<3; j++)
            W[j]=E[i].A[0][j];
        int j=0;
        do
        {
            E[i].A[j]="";
            for(int jj=0; jj<3; jj++)
                E[i].A[j]+=W[jj];
            j++;
        }
        while(next_permutation(W,W+3));
    }
    MAP['Y']=1;
    MAP['V']=2;
    MAP['G']=3;
    MAP['C']=4;
    MAP['X']=5;
    MAP['Z']=6;
    MAP['T']=7;
    MAP['F']=8;
    MAP['D']=9;
    MAP['B']=10;
    scanf("%s",B);
    int s=strlen(B);
    node C[3];
    for(int i=0; i<s; i++)
    {
        if(i==0)
        {
            int d=i%2;
            C[d]=E[MAP[B[i]]];
//            int s=(int)C[d].size();
            for(int j=0; j<6; j++)
            {
                C[d].AA[j]=3;
            }
        }
        else
        {
            int d=i%2;
            C[d]=E[MAP[B[i]]];
//            int s=(int)C[d].size();
//            int ss=(int)C[!d].size();
            for(int j=0; j<6; j++)
            {
                if(C[d].A[j].size()<3)
                    continue;
                cout<<C[d].A[j]<<endl;
                C[d].AA[j]=inf;
                for(int jj=0; jj<6; jj++)
                {
                    if(C[!d].A[jj].size()<3)
                        continue;
//                    cout<<"dadafd"<<C[!d].A[jj]<<endl;

                    C[d].AA[j]=min( C[!d].AA[jj]+3,C[d].AA[j]);

                    for(int k=0; k<=2; k++)
                    {
                        int flag=0;
                        int l=0;
                        for(int kk=k; kk<3; kk++)
                        {
                            if(C[d].A[j][l++]!=C[!d].A[jj][kk])
                            {
                                flag=1;
                                break;
                            }
                        }
                        if(flag==0)
                        {
                            C[d].AA[j]=min( C[!d].AA[jj]+3-(3-k),C[d].AA[j]);
                        }
                    }
//                    cout<<"dsbhfd213214fdf"<<C[d].AA[j]<<endl;

                }
//                cout<<"3131413^^^"<<C[d].AA[j]<<endl;
            }
        }
    }
    int t=inf;
    for(int i=0; i<6; i++)
    {
        if(C[(s-1)%2].AA[i])
            t=min(t,C[(s-1)%2].AA[i]);
    }
//    printf("%dn",t);

    printf("%dn",t+strlen(B));
}
/*
XDTBVV
*/