AC了,但不明白为什么
  • 板块P1666 前缀单词
  • 楼主houmy
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/6/15 16:01
  • 上次更新2024/6/15 17:51:34
查看原帖
AC了,但不明白为什么
555809
houmy楼主2024/6/15 16:01

如题,把排序改成字典序之后就过了(之前用的是以长度为第一关键字)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll dp[55];
string a[55];
ll ans;
inline bool cmp(const string& a,const string& b){
    // if(a.size()!=b.size())return a.size()<b.size();
    return a<b;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        dp[i]=1;
        for(int j=1;j<i;j++){
            bool ok;
            int sz1=a[i].size(),sz2=a[j].size();
            if(sz1==sz2)ok=(a[i]!=a[j]);
            else if(sz1>sz2)ok=(a[i].substr(0,sz2)!=a[j]);
            else if(sz1<sz2)ok=(a[j].substr(0,sz1)!=a[i]);
            // cout<<a[i]<<" "<<a[j]<<" "<<ok<<endl;
            if(ok)dp[i]+=dp[j];
        }
        ans+=dp[i];
    }
    cout<<ans+1;
}
2024/6/15 16:01
加载中...