QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#211634#6635. Strange KeyboardkkioCompile Error//C++202.6kb2023-10-12 19:36:542023-10-12 19:36:54

Judging History

你现在查看的是最新测评结果

  • [2023-10-12 19:36:54]
  • 评测
  • [2023-10-12 19:36:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxk=5005,maxn=1e6+10;
const ll inf=1e18;
int ch[maxn][26],tot,n,K;
vector<int> leaf[maxn];
string s[maxn],T;
vector<int> Len;
bool vis[maxk];
typedef long long ll;
ll dis[maxk],val[maxn];
int dep[maxn];
inline int getpre(int x)
{
    if(~val[x])return val[x];
    val[x]=inf;
    for(int v:leaf[x])
    {
        int len=dep[v]-dep[x];
        val[x]=min(val[x],dis[K-len%K]+(len+K-1)/K+1);
    }
    return val[x];
}
ll dp[maxn];
void solve()
{
    cin>>n>>K;
    Len.clear();
    for(int i=1;i<=n;i++)
        cin>>s[i],Len.push_back(s[i].size());
    cin>>T;
    sort(Len.begin(),Len.end());
    Len.resize(unique(Len.begin(),Len.end())-Len.begin());
    memset(dis,0x3f,sizeof dis);
    dis[K]=0;
    dis[0]=0;
    for(int l:Len)
    {
        if(l==0)continue;
        for(int i=0;i<K;i++)vis[i]=0;
        for(int i=0;i<K;i++)
            if(!vis[i])
            {
                vector<int> cy;
                int now=i;
                int z=l%K;
                do{
                    cy.push_back(now);
                    vis[now]=1;
                    now+=z;while(now>=K)now-=K;
                }while(now!=i);
                int len=cy.size();
                for(int i=0;i<len;i++)cy.push_back(cy[i]);
                for(int i=0;i<cy.size()-1;i++)dis[cy[i+1]]=min(dis[cy[i+1]],dis[cy[i]]+(cy[i]+l>=K?(cy[i]+l-cy[i+1])/K+1:1));
            }
    }
    tot=0;memset(ch[0],0,sizeof ch[0]);
    for(int i=1;i<=n;i++)
    {
        int now=0;
        vector<int> path;
        for(int j=0;j<s[i].size();j++)
        {
            int c=s[i][j]-'a';
            if(!ch[now][c])
            {
                ++tot;ch[now][c]=tot;
                dep[tot]=dep[now]+1;
                memset(ch[tot],0,sizeof ch[tot]);
                val[tot]=-1;
                leaf[tot].clear();
            }
            now=ch[now][c];
            path.push_back(now);
        }
        for(int v:path)leaf[v].push_back(now);
    }
    for(int i=1;i<=T.size();i++)dp[i]=inf;
    for(int i=0;i<T.size();i++)
    {
        int now=0;
        for(int j=i;j<T.size();j++)
        {
            int c=T[j]-'a';
            if(!ch[now][c])break;
            now=ch[now][c];
            dp[j+1]=min(dp[j+1],dp[i]+getpre(now));
        }
    }
    if(dp[(int)T.size()]!=inf)printf("%lld\n",dp[(int)T.size()]);
    else puts("-1");
}
int main()
{
	//freopen("data.in","r",stdin);
	//freopen("1.out","w",stdout);
    int T;scanf("%d",&T);
    while(T--)solve();
    return 0;
}
/*
1
5 4
cabd
bcca
ddab
dabd
cba
cbc
*/

详细

answer.code:4:7: error: ‘ll’ does not name a type
    4 | const ll inf=1e18;
      |       ^~
answer.code: In function ‘int getpre(int)’:
answer.code:16:12: error: ‘inf’ was not declared in this scope; did you mean ‘ynf’?
   16 |     val[x]=inf;
      |            ^~~
      |            ynf
answer.code: In function ‘void solve()’:
answer.code:78:39: error: ‘inf’ was not declared in this scope; did you mean ‘ynf’?
   78 |     for(int i=1;i<=T.size();i++)dp[i]=inf;
      |                                       ^~~
      |                                       ynf
answer.code:90:27: error: ‘inf’ was not declared in this scope; did you mean ‘ynf’?
   90 |     if(dp[(int)T.size()]!=inf)printf("%lld\n",dp[(int)T.size()]);
      |                           ^~~
      |                           ynf
answer.code: In function ‘int main()’:
answer.code:97:16: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   97 |     int T;scanf("%d",&T);
      |           ~~~~~^~~~~~~~~