首页 > 其他分享 >ABC343 G Compress Strings 题解

ABC343 G Compress Strings 题解

时间:2024-03-03 17:47:47浏览次数:29  
标签:cnt int 题解 LL Compress ABC343 字符串 size mod

Question

ABC343 G Compress Strings

给定 \(N\) 个字符串 \(S_1,S_2,\cdots, S_N\)

找到一个包含所有这些字符串作为子字符串的最小长度的字符串

一个字符串 \(S\) 包含一个字符串 \(T\) 作为子字符串是指:

如果 \(T\) 可以通过从 \(S\) 的开头删除零个或多个字符以及从末尾删除 \(0\) 个或多个字符而获得

Solution

先观察如果一个字符串的前缀等于另外一个字符串的后缀,那么就可以共用一些字符

用哈希算出两个字符串可以共用的字符数量 \(p[i][j]\),特别得,如果 \(j\) 是 \(i\) 的子串,\(p[i][j]\) 就是 \(j\) 的长度

求出 \(p[i][j]\) 后用状压 DP 来确定字符串的顺序

Code

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;


struct Hash {
    int p, mod;
    Hash(int p, int mod) : p(p), mod(mod) {}

    LL pow(LL a, LL b) {
        LL ans = 1;
        for (; b; b >>= 1, a = a * a % mod) if (b & 1) ans = ans * a % mod;
        return ans;
    }

    vector<LL> get_hash(string &s) {
        int n = s.size();
        vector<LL> h(n + 1, 0);
        h[0] = s[0] - 'a' + 1;
        for (int i = 1; i < n; i++) {
            h[i] = (h[i - 1] * p + s[i] - 'a' + 1) % mod;
        }
        return h;
    }

    LL get_sub_hash(vector<LL> &h, int l, int r) {
        if (l == 0) return h[r];
        return (h[r] - h[l - 1] * pow(p, r - l + 1) % mod + mod) % mod;
    }
};

LL dp[21][1 << 20];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    Hash hsh1(37, 1e9 + 7);
    vector<string> s(n + 1);
    vector<vector<LL> > h(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> s[i], h[i] = hsh1.get_hash(s[i]);
    


    vector<vector<int> > p(n + 1, vector<int>(n + 1, 0));
    
    for (int i = 1; i <= n; i++)  // s[i] 在前 s[j] 在后
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;

            int flg = 0;
            if (s[i].size() >= s[j].size()) {
                for (int k = 0; k + s[j].size() - 1 < s[i].size(); k++ )
                    if (hsh1.get_sub_hash(h[i], k, k + s[j].size() - 1) == h[j][s[j].size() - 1]) {
                        p[i][j] = s[j].size();
                        flg = 1;
                        break;
                    }
            }
            if (flg) continue;

            int cnt;
            for (cnt = min(s[i].size(), s[j].size()) - 1; cnt >= 0; cnt--) {
                LL A = hsh1.get_sub_hash(h[i], s[i].size() - 1 - cnt , s[i].size() - 1);
                LL B = hsh1.get_sub_hash(h[j], 0, cnt);
                if (A == B)
                    break;
            }
            p[i][j] = cnt + 1;
        }

    // for (int i = 1; i <= n; i++)
    //     for (int j = 1; j <= n; j++) {
    //         printf("%d%c", p[i][j], " \n"[j == n]);
    //     }

    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++)
        dp[i][1 << (i - 1)] = s[i].size();

    for (int S = 0; S < (1<<n); S++) {
        for (int i = 1; i <= n; i++) {
            if ((S >> (i - 1) & 1) == 0) continue;
            for (int j = 1; j <= n; j++) {
                if (S >> (j - 1) & 1) continue;
                if (p[i][j] == s[j].size()) 
                    dp[i][S | (1 << (j - 1))] = min(dp[i][S | (1 << (j - 1))], dp[i][S]);
                else 
                    dp[j][S | (1 << (j - 1))] = min(dp[j][S | (1 << (j - 1))], (LL)(dp[i][S] + s[j].size() - p[i][j]));
            }
        }
    }

    LL ans = INF;
    for (int i = 1; i <= n; i++) ans = min(ans, dp[i][(1 << n) - 1]);
    cout << ans << '\n';
    return 0;
}

标签:cnt,int,题解,LL,Compress,ABC343,字符串,size,mod
From: https://www.cnblogs.com/martian148/p/18050346

相关文章

  • AT_abc184_f [ABC184F] Programming Contest 题解
    题目传送门前置知识Meetinthemiddle解法非正解当成超大背包来做,暴力枚举每个数是否进行相加。时间复杂度为\(O(2^{n})\)。llp[50],ans=0;voiddfs(llx,lln,llm,llworth){ if(x==n+1) { if(worth<=m) { ans=max(ans,worth); } } else { if(wo......
  • P2532 [AHOI2012] 树屋阶梯 题解
    P2532[AHOI2012]树屋阶梯题解容易发现答案是卡特兰数,那么考虑证明这一点。考虑从左下角到右上角填满格子。利用动态规划的思想,回忆一下某道\(IOI\)的题目[数字三角形],每个格子的方案都只能由其左边或下边转移而来。可以结合图理解一下。好,刚才这个定义显然很符合卡特兰......
  • CF1931G One-Dimensional Puzzle 题解
    CF1931GOne-DimensionalPuzzle题解题意传送门思路考虑一下怎么入手,发现一个拼图只能接一些拼图(废话但是有用),所以我们可以简单地画出一个链接关系的图,\(u\tov\)表示编号为\(u\)的拼图后面能够接编号为\(v\)的拼图。然后我们发现问题转换为:......
  • AT_joig2021_d 展覧会 2 (Exhibition 2) 题解
    题目传送门前置知识二分答案解法最小值最大,考虑二分答案。关于check函数的书写,比luoguP1182数列分段SectionII多了个对位置的判定,注意对当前是第一次展出时进行特判。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineullunsigne......
  • ABC343
    T1:WrongAnswer模拟代码实现a,b=map(int,input().split())c=a+bifc==0:print(1)else:print(0)T2:AdjacencyMatrix模拟代码实现n=int(input())a=[list(map(int,input().split()))foriinrange(n)]foriinrange(n):print(*[j+1f......
  • 牛客练习赛122题解A-D
    牛客练习赛122A.黑白配代码:#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e5+7;constintINF=0x3f3f3f3f;typedeflonglongll;#defineendl"\n"voidsolve(){ intt,n;cin>>t>>n;inta[n+1];while(t--)......
  • CF1934题解
    题解首先拜谢波叔呀,一眼看上去没思路,直到看见了四重循环,大彻大悟。Solution没什么好说的,暴力四重题意大意就是给你一个数,在1,3,6,10,15中取数,使取出的数等于输入的数,求出至少需要用多少个数。求数代码: for(longlongi=0;i<=2;i++){ for(longlongj=0;j<=1;j++){ for(lo......
  • AT_abc169_f Knapsack for All Subsets题解
    如果我们定义\(dp[i][j]\)表示对于前i个字符而言,其子集满足条件的个数。那4么对于一个位置i而言,要么选择它贡献要么不选择,所以\(dp[i][j]=dp[i-1][j-a[i]](j>=a[i])+dp[i-1][j]\),这是每一个\(f(i)\)的函数。然后我们加上所有的\(dp[i][k](i:1到n)ans+=dp[i][k......
  • CF1383A String Transformation 1 题解
    若某一位\(i\)上\(A_i>B_i\),则显然无解。否则,建立并查集,然后遍历字符串,若\(A_i,B_i\)不在一个集合就合并\(A_i\)与\(B_i\),直到只剩下一个集合,此时的合并总次数即为答案。为什么呢?因为将\(A_i,B_i\)合并的操作可以视为等价于将以\(A_i\)开头的连续若干个相同字符均改......
  • 「TFOI R1」Unknown Graph 题解
    这里是出题人题解。\(\text{SolutionOfProblemC:UnknownGraph.}\)题意还是很清晰的,这里就不再赘述题意了。首先如果没有\(q\)的限制,显然有一种贪心思想就是每个点每次选剩余入度最多的与之连边。但是因为限制,就无法保证贪心的正确性。那该怎么办呢?一个大提示:这题是......