头像


访客:2617

离线:6小时前




15天前

题目来源于《挑战程序设计竞赛》,题目涉及的算法只对应相关章节 (不一定是最优解的,思路写的有点简陋)


例题1 编辑距离 传送门

题意:
编辑距离,是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

思路:
dp[i][j]:所有将a中的前i个字母变成 b中前j个字母的集合的操作次数
对a中的第i个字母操作,分为以下四种操作
1. 在该字母之后添加: dp[i][j] = dp[i][j-1] + 1
2. 删除该字母: dp[i][j] = dp[i-1][j] + 1
3. 替换该字母: dp[i][j] = dp[i-1][j-1] + 1
4. 啥也不做(对应结尾字母相同): dp[i][j] = dp[i-1][j-1]

代码:

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

const int N = 1e3 + 10;
char s1[N], s2[N];
int dp[N][N];

int edit_distance(char s1[], char s2[], int n, int m)
{
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int i = 1; i <= m; i++) dp[0][i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
        }
    return dp[n][m];
}

int main()
{
    cin >> s1 + 1;
    cin >> s2 + 1;
    int n = strlen(s1 + 1);
    int m = strlen(s2 + 1);

    cout << edit_distance(s1, s2, n, m);
}

例题2 禁止字符串

题意:
考虑只由’A’,’G’,’C’,’T’四种字符组成的DNA字符串。给定一个长度为K的字符串S。请计算长度恰好为n 且不包含 S的宇符串的个数。输出个数 mod 10009 后的结果。

思路:
trans[i][j]:在S[1…i]添加字符cho[j]后(新串T), 满足 T的后缀 和 S的前缀 相等的最大长度
dp[i][j]:当前构造字符串P长度为i,满足𝑃[𝑖 −𝑗+1…𝑖]=𝑆[1…𝑖]的方案数

可得到如下转移方程:
设 ne = trans[i][j], 若 ne 合法(即 ne != k, k = |S|) dp[i+1][ne] += dp[i][j]

代码:

//禁止字符串 
#include <bits/stdc++.h>

using namespace std;

const int K = 110;
const int N = 10010;
const int C = 5;
const int mod = 10009;

int n, k;
string cho = "AGCT", s;

//trans[i][j]:当前已经匹配i个字符,添加字符cho[j]后,匹配的字符个数
int trans[K][C];
//dp[i][j]:当当前字符串长度为i,状态j结尾的方案数
int dp[N][K];

int main()
{
    cin >> n >> k;
    cin >> s;

    //预处理trans
    memset(trans, 0, sizeof trans);
    for (int i = 0; i < k; i++)
    {
        string tmp = s.substr(0, i);
        for (int j = 0; j < 4; j++)
        {
            string cur = tmp + cho[j];
            while (s.substr(0, cur.length()) != cur)
                cur = cur.substr(1);
            trans[i][j] = cur.length();
        }
    }

    //计算dp
    memset(dp, 0, sizeof dp);
    dp[0][0] = 1;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < k; j++)
            for (int c = 0; c < 4; c++)
            {
                int ne = trans[j][c];
                if (ne == k) continue;
                dp[i + 1][ne] = (dp[i + 1][ne] + dp[i][j]) % mod;
            }

    //计算总方案数
    int tot = 0;
    for (int i = 0; i < k; i++) 
        tot = (tot + dp[n][i]) % mod;
    cout << tot << endl;

    return 0;
}

例题3 DNA repair 传送门

题意:
考虑只由’A’,’G’,’C’,’T’四种字符组成的DNA字符串。给定一个原字符串s,和n个禁止模式字符串P1,P2…Pn。请修改宇符串s,使得其中不包含任何禁止模式。每次修改操作只能将S中的某个字符修改为其他字符。如果不存在这样的修改,请输出-1,否则,输出所需的最少修改回数。

思路:
考虑从左向右修改,以修改到的位置和对应的后缀状态进行动态规划

后缀状态表示方法:
先求出𝑃[1]…𝑃[𝑁]所有字符串的前缀串
以样例2为例,前缀串Q[1…K]为{“A”, “"T” ,”𝑇𝐺”}
为了避免重复,去重,每个前缀串的下标作为对应的后缀状态
对每个Q[i],判断Q[i]的后缀中是否含有禁止串

状态转移数组trans[i][j] :
与例题2的做法类似,添加字符后,反复删除第一个字符, 直到等于某个状态的字符串,即为转移到的状态

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 55;
const int S = 1010;

int n, cas;
string s, p[N], cho = " AGCT";
bool flag[S];
int trans[S][5], dp[S][S];

int main()
{
    ios::sync_with_stdio(false);

    while (cin >> n && n)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> p[i];
            p[i] = " " + p[i];
        }
        cin >> s; s = " " + s;

        vector<string>pre;
        pre.push_back(" ");
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < p[i].length(); j++)
            pre.push_back(" " + p[i].substr(1, j));
        stable_sort(pre.begin(), pre.end());
        pre.erase(unique(pre.begin(), pre.end()), pre.end());
        int m = (int)pre.size() - 1;

        for (int i = 0; i <= m; i++) flag[i] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                int lens = pre[i].length(), lent = p[j].length();
                if (lens >= lent && pre[i].substr(lens - lent + 1) == p[j].substr(1))
                {
                    flag[i] = 0;
                    break;
                }
            }

        for (int i = 0; i <= m; i++)
            for (int j = 1; j <= 4; j++)
            {
                string ne = pre[i] + cho[j];
                while (true)
                {
                    int pos = lower_bound(pre.begin(), pre.end(), ne) - pre.begin();
                    if (pos <= m && pre[pos] == ne)
                    {
                        trans[i][j] = pos;
                        break;
                    }
                    ne = " " + ne.substr(2);
                }
            }

        int lens = (int)s.length() - 1;
        for (int i = 0; i <= lens; i++)
            for (int j = 0; j <= m; j++)
            dp[i][j] = 0x3f3f3f3f;
        dp[0][0] = 0;
        for (int i = 0; i < lens; i++)
        {
            for (int j = 0; j <= m; j++)
            {
                if (dp[i][j] == 0x3f3f3f3f) continue;
                for (int k = 1; k <= 4; k++)
                {
                   int st = trans[j][k];
                   if (flag[st] == 0) continue;

                   if (s[i + 1] == cho[k]) dp[i + 1][st] = min(dp[i + 1][st], dp[i][j]);
                   else dp[i + 1][st] = min(dp[i + 1][st], dp[i][j] + 1);
                }
            }
        }

        int mi = 0x3f3f3f3f;
        for (int i = 0; i <= m; i++) mi = min(mi, dp[lens][i]);
        if (mi == 0x3f3f3f3f) mi = -1;
        printf("Case %d: %d\n", ++cas, mi);
    }

    return 0;
}

习题1 Easy Problem 传送门

题意:
给你一个字符串s,每个位置的字符都有一个删除的代价。现在可以删除一定量的字符使得新字符串不包含子序列”hard”(可以不连续),求最小代价。

思路:
dp[i][j]:当前处理位置为i, 包含t.subtr(1, i)子序列的最大权值和

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, fare[N];
char s[N], t[10] = " hard";
//dp[i][j]:当前处理位置为i, 包含t.subtr(1, i)子序列的最大权值和
ll dp[N][5];

int main()
{
    scanf("%d", &n);
    scanf("%s", s + 1);
    for (int i = 1; i <= n; i++) scanf("%d", &fare[i]);

    ll sum = 0;
    for (int i = 1; i <= n; i++) sum += fare[i];

    for (int i = 1; i <= n; i++)
    {
        if (s[i] == 'h')
        {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0]) + fare[i];
            dp[i][2] = dp[i - 1][2] + fare[i];
            dp[i][3] = dp[i - 1][3] + fare[i];
        }
        else if (s[i] == 'a')
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1];
            dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + fare[i];
            dp[i][3] = dp[i - 1][3] + fare[i];
        }
        else if (s[i] == 'r')
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1] + fare[i];
            dp[i][2] = dp[i - 1][2];
            dp[i][3] = max(dp[i - 1][2], dp[i - 1][3]) + fare[i];
        }
        else if (s[i] == 'd')
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1] + fare[i];
            dp[i][2] = dp[i - 1][2] + fare[i];
            dp[i][3] = dp[i - 1][3];
        }
        else
        {
            dp[i][0] = dp[i - 1][0] + fare[i];
            dp[i][1] = dp[i - 1][1] + fare[i];
            dp[i][2] = dp[i - 1][2] + fare[i];
            dp[i][3] = dp[i - 1][3] + fare[i];
        }
    }

    ll ma = 0;
    for (int i = 0; i < 4; i++) ma = max(ma, dp[n][i]);
    printf("%lld\n", sum - ma);

    return 0;
}


本人不太会写博客,若有错误,敬请指出,有点丑见谅





15天前

题目来源于《挑战程序设计竞赛》,题目涉及的算法只对应相关章节 (不一定是最优解的,思路写的有点简陋)


例题1 Sequence 传送门

题意:
给定N个数字组成的序列,保证A1比其他数字都大。先要将这个序列分成三段,并将每段分别反转,求能得到的字典序最小的序列的什么?要求每段都不为空。

思路:
首先,确定第一段的位置。题中限制𝐴_1大于其他任何数字,那么确定第一段的分割位置只需考虑第一段就足够了。只需将数组A反转,求一遍后缀数组,答案为满足条件的字典序最小的方案。(注意限制每段不能为空)

然后,将剩余部分分割成两段,由于没有第一段的条件约束,这两段要综合考虑。将序列分割成两段再分别反转得到的序列,可以看作是将两个原序列拼接得到的新序列中的某个子串反转得到的序列。

例如:原串 S=ABCDEFGH
以D右侧为分割线,将原串分割成 S1=ABCD, S2=EFGH,反转S1、S2拼接后为DCBAHGFE
令 T = S + S,即 T=ABCDEFGHABCDEFGH,标黑处子串的反转后为上述串

因此,可以将剩余部分扩倍,反转后,求一遍后缀数组,即可得到答案。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 4e5 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(int s[], int n, int m)
{
    int i, p, w;
    memset(cnt, 0, sizeof cnt);
    //for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        memset(cnt, 0, sizeof(cnt));
        //for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        memcpy(oldrk, rk, sizeof(rk));
        //for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

int n, s[N], val[N], tmp1[N], tmp2[N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);

    vector<int>v;
    for (int i = 1; i <= n; i++) v.push_back(s[i]);
    stable_sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int len = v.size();
    for (int i = 1; i <= n; i++) 
        val[i] = lower_bound(v.begin(), v.end(), s[i]) - v.begin() + 1;

    reverse(val + 1, val + n + 1);
    reverse(s + 1, s + n + 1);

    get_sa(val, n, len);

    vector<int>ans;
    //取第一段
    int p = 0;
    for (int i = 1; i <= n; i++)
        if (sa[i] > 2)
        {
            p = sa[i];
            break;
        }
    for (int i = p; i <= n; i++) ans.push_back(s[i]);
    reverse(val + 1, val + n + 1);
    reverse(s + 1, s + n + 1);

    //取第二、三段
    int tot = 0;
    for (int i = n - p + 2; i <= n; i++) 
        tmp1[++tot] = s[i], tmp2[tot] = val[i];
    int cnt = tot;
    for (int i = 1; i <= cnt; i++) 
        tmp1[++tot] = tmp1[i], tmp2[tot] = tmp2[i];
    reverse(tmp1 + 1, tmp1 + tot + 1);
    reverse(tmp2 + 1, tmp2 + tot + 1);

    get_sa(tmp2, tot, len);

    for (int i = 1; i <= tot; i++)
        if (sa[i] <= tot / 2 && sa[i] > 1)
        {
            p = sa[i];
            break;
        }
    for (int i = p, j = 1; j <= tot / 2; i++, j++)
        ans.push_back(tmp1[i]);

    for (int i = 0; i < ans.size(); i++) printf("%d\n", ans[i]);

    return 0;
}

例题2 Secretary 传送门

题意:
给定两个字符串S和T。请计算两个字符串最长的公共字符串子串的长度。

思路:
首先,考虑一个简化的问题,计算一个字符串中至少出现两次的最长子串。答案一定会在后缀数组中相邻两个后缀的公共前缀之中,所以只要考虑它们就好了。这是因为子串的开始位置在后缀数组中相距越远,其公共前缀的长度也就越短。因此,高度数组的最大值其实就是答案。

再考虑原问题的解法。因为对于两个字符串,不好直接运用后缀数组,因此我们可以将S和T,通过在中间插入一个不会出现的字符(’#’)拼成一个新串P。之后计算方法和上述相同。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e4 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];
// px[i] = rk[id[i]](用于排序的数组所以叫 px)

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
    int i, m = 300, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

void get_height(char s[], int n)
{
    for (int i = 1, k = 0; i <= n; ++i) 
    {
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        ht[rk[i]] = k;
    }
}

int T, n, m;
char s[N], t[N];

int main()
{
    scanf("%d", &T);
    getchar();
    while (T--)
    {
        cin.getline(s + 1, N);
        cin.getline(t + 1, N);

        n = strlen(s + 1);
        m = strlen(t + 1);

        s[n + 1] = '#';
        strcpy(s + n + 2, t + 1);

        get_sa(s, n + m + 1);
        get_height(s, n + m + 1);

        int ma = 0;
        for (int i = 2; i <= n + m + 1; i++)
        {
            int pos1 = sa[i - 1], pos2 = sa[i];
            if ((pos1 <= n && pos2 <= n) || 
                    (pos1 >= n + 2 && pos2 >= n + 2))
                continue;
            ma = max(ma, ht[i]);
        }
        printf("Nejdelsi spolecny retezec ma delku %d.\n", ma);
    }

    return 0;
}

例题3 最长回文子串 传送门

题意:
输入一个字符串Str,输出Str里最长回文子串的长度。

思路:
与例题2类似,令 S 的反串为 T
将原串 S 和 T 利用间隔符 ’#’ 拼接起来
对奇偶两种情况分类讨论,求对应位置的lcp,将其转化为回文串长度,取最大值。
注意两侧的边界。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 220050;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];
// px[i] = rk[id[i]](用于排序的数组所以叫 px)

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
    int i, m = 300, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

void get_height(char s[], int n)
{
    for (int i = 1, k = 0; i <= n; ++i) 
    {
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        ht[rk[i]] = k;
    }
}

int Log[N], f[N][23];
void RMQ_pre(int n)
{
    Log[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        if (!(i & (i - 1))) Log[i] = Log[i - 1] + 1;
        else Log[i] = Log[i - 1];
        f[i][0] = ht[i];
    }
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int RMQ_min(int l, int r)
{
    int d = Log[r - l + 1];
    return min(f[l][d], f[r - (1 << d) + 1][d]);
}

char s[N], t[N];

int main()
{
    while (~scanf("%s", s + 1))
    {
        int tot = 0, n = strlen(s + 1);
        for (int i = 1; i <= n; i++) t[++tot] = s[i];
        t[++tot] = '#';
        for (int i = n; i >= 1; i--) t[++tot] = s[i];

        get_sa(t, tot);
        get_height(t, tot);
        RMQ_pre(tot);

        int ma = 0;
        for (int i = 1; i <= n; i++)
        {
            int x = i, y = n * 2 + 2 - i;
            //奇数长度
            int rkx = rk[x], rky = rk[y];
            if (rkx > rky) swap(rkx, rky);
            ma = max(ma, RMQ_min(rkx + 1, rky) * 2 - 1);
            //偶数长度
            if (i == 1) continue;
            x = i; y = n * 2 + 3 - i;
            rkx = rk[x], rky = rk[y];
            if (rkx > rky) swap(rkx, rky);
            ma = max(ma, RMQ_min(rkx + 1, rky) * 2);
        }
        printf("%d\n", ma);
    }

    return 0;
}

习题1 Glass Beads 传送门

题意:
求所给字符串同构的字典序最小的字符串的起始位置。

思路:
令原字符串为S, len = |S|, 构造字符串T = S + ‘}’ + S
求一遍后缀数组,取满足sa[i] <= len的最小的sa[i]

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e4 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N];

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
    int i, m = 300, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

int t;
char s[N];

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%s", s + 1);

        int n = strlen(s + 1);
        for (int i = 1; i <= n; i++) s[n + i] = s[i];
        s[n * 2 + 1] = '{';
        get_sa(s, n * 2 + 1);

        int ans = 0;
        for (int i = 1; i <= 2 * n; i++)
        {
            if (sa[i] <= n)
            {
                ans = sa[i];
                break;
            }
        }
        printf("%d\n", ans);
    }

    return 0;
}

习题2 Common Substrings 传送门

题意:
求两个串长度大于等于k的公共子串的个数。

思路:
后缀数组+单调栈+差分
图片1.png
对于每两条相邻的绿线,作为一个整体计算,设当前计算横向区间为[l,r], 纵向区间为[L,R], cnt1为属于第一个串的个数,cnt2为属于第二个串的个数,那么对[l, r]所有点的贡献均为cnt1 * cnt2, 可用差分数组维护。
L = 左侧最近比height[i]小的下标 + 1, R = 右侧最近比height[i]小的下标 + 1, 可用单调栈维护
直接求大于k的也可以,此方法可求所有长度的解

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;

typedef long long ll;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
    int i, m = 300, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

void get_height(char s[], int n)
{
    for (int i = 1, k = 0; i <= n; ++i) 
    {
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        ht[rk[i]] = k;
    }
}

int l[N], r[N], qu[N], tot;
void get_array_lr(int n)
{
    ht[0] = ht[n + 1] = -1;
    tot = 0; qu[++tot] = 0;
    for (int i = 1; i <= n; i++)
    {
        while (tot && ht[i] <= ht[qu[tot]]) tot--;
        l[i] = qu[tot] + 1;
        qu[++tot] = i;
    }

    tot = 0; qu[++tot] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        while (tot && ht[i] <= ht[qu[tot]]) tot--;
        r[i] = qu[tot] - 1;
        qu[++tot] = i;
    }

    ht[0] = ht[n + 1] = 0;
}

int k;
char s[N], t[N];
vector<int>v[N];
ll sum[N];

int main()
{
    while (~scanf("%d", &k) && k)
    {
        scanf("%s", s + 1);
        scanf("%s", t + 1);

        int lens = strlen(s + 1);
        int lent = strlen(t + 1);

        s[lens + 1] = '#';
        for (int i = 1; i <= lent; i++) s[lens + 1 + i] = t[i];
        int n = lens + lent + 1;

        get_sa(s, n);
        get_height(s, n);
        get_array_lr(n);

        for (int i = 1; i <= n; i++) v[i].clear();
        for (int i = 1; i <= n; i++) v[ht[i]].push_back(i);
        for (int i = 0; i <= n; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++)
        {
            if (sa[i] <= lens) cnt[i] = 1;
            else cnt[i] = 0;
            cnt[i] += cnt[i - 1];
        }

        for (int i = 0; i <= n + 1; i++) sum[i] = 0;

        for (int i = n; i >= 1; i--)
        {
            int rborder = 0;
            for (int j = 0; j < v[i].size(); j++)
            {
                if (r[v[i][j]] <= rborder) continue;
                rborder = r[v[i][j]];
                int le = l[v[i][j]] - 1, ri = r[v[i][j]];
                int cnt1 = cnt[ri] - cnt[le - 1];
                int cnt2 = ri - le + 1 - cnt1;
                ll val = 1LL * cnt1 * cnt2;
                int mi = max(ht[le], ht[ri + 1]) + 1;
                sum[mi] += val; sum[i + 1] -=val;
            }
        }

        for (int i = 1; i <= n; i++) sum[i] += sum[i - 1];
        for (int i = n; i >= 1; i--) sum[i] += sum[i + 1];
        printf("%lld\n", sum[k]);
    }

    return 0;
}

习题3 Facer’s string 传送门

题意:
给你a、b串,让你求a串中有多少后缀与b串的所有后缀的公共前缀的长度最大值等于k。

思路:
恰好等于k的方案数可以转化为 大于等于k+1的方案数S1 减去 大于等于k的方案数S2
将a、b串用一个间隔符(此题可采用较大的数)拼起来,求一遍后缀数组,求得S1、S2, 两者作差即为答案

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;

typedef long long ll;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(int s[], int n, int m)
{
    int i, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

void get_height(int s[], int n)
{
    for (int i = 1, k = 0; i <= n; ++i) 
    {
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        ht[rk[i]] = k;
    }
}

int pre[N];
int cal_least_k(int n, int k)
{
    int l = 0, r = 0, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (ht[i] < k)
        {
            if (l != 0 && pre[r] - pre[l - 1] != r - l + 1) ans += pre[r] - pre[l - 1];
            l = r = 0;
            continue;
        }
        if (l == 0) l = i - 1;
        r = i;
    }
    if (l != 0 && r != 0) ans += pre[r] - pre[l - 1];

    return ans;
}

int n, m, k;
int a[N], b[N];

int main()
{
    while (~scanf("%d %d %d", &n, &m, &k))
    {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i]++;
        for (int i = 1; i <= m; i++) scanf("%d", &b[i]), b[i]++;

        a[n + 1] = 10005;
        for (int i = 1; i <= m; i++) a[n + 1 + i] = b[i];

        int tot = n + m + 1;
        get_sa(a, tot, 10005);
        get_height(a, tot);

        for (int i = 0; i <= tot; i++) pre[i] = 0;
        for (int i = 1; i <= tot; i++)
        {
            if (sa[i] <= n) pre[i] = 1;
            pre[i] += pre[i - 1];
        }

        int ans = cal_least_k(tot, k) - cal_least_k(tot, k + 1);
        printf("%d\n", ans);
    }

    return 0;
}

习题4 Common Palindromes 传送门

题意:
给定两个字符串S,T,询问(i,j,k,l)这样的四元组个数
满足S[i,j],T[k,l]都是回文串并且S[i,j]=T[k,l]

思路:
先预处理出后缀数组、高度数组和回文半径数组。
在每遇到一个长clen公共子串c的过程中,都遍历长度plen大于clen的公共回文子串p,将p的个数加到区间[clen, plen]中的每一个元素上去(因为两个字符串的lcp最大为clen,之前大于clen的公共回文子串无法传递)。
每出现一次长plen的公共回文子串p,都代表出现了一次plen-1,plen-2, …clen的公共回文子串,此过程可用树状数组维护。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;
typedef map<int, ll>::iterator IT;

const int N = 4e5 + 50;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
    int i, m = 300, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

void get_height(char s[], int n)
{
    for (int i = 0; i <= n; i++) ht[i] = 0;
    for (int i = 1, k = 0; i <= n; ++i) 
    {
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        ht[rk[i]] = k;
    }
}

int Log[N], f[N][21];
void RMQ_pre(int n)
{
    Log[0] = -1;
    for (int i = 1; i <= n; i++)
    {
        if (!(i & (i - 1))) Log[i] = Log[i - 1] + 1;
        else Log[i] = Log[i - 1];
        f[i][0] = ht[i];
    }
    for (int j = 1; (1 << j) <= n; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
        f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}
int RMQ_min(int l, int r)
{
    int d = Log[r - l + 1];
    return min(f[l][d], f[r - (1 << d) + 1][d]);
}

char s[N], t[N], p[N];
int rad[N], flag[N], pre[N];

void get_rad(char p[], int pos, int lens)
{
    int prepos = pos;
    p[++pos] = '&';
    for (int i = prepos; i >= 1; i--) p[++pos] = p[i];

    get_sa(p, pos);
    get_height(p, pos);
    RMQ_pre(pos);

    for (int i = 1; i <= prepos; i++)
    {
        int x = i, y = pos - i + 1;
        int rkx = rk[x], rky = rk[y];
        if (rkx > rky) swap(rkx, rky);
        rad[i] = RMQ_min(rkx + 1, rky) / 2;
        if (x > lens) rad[i] = min(rad[i], x - lens - 1);
    }
}

struct BIT_tree{
    int treemax;
    ll tree[N];
    void init() //初始化 
    {
        memset(tree, 0, sizeof tree);
        treemax = 100010;
    }
    inline int lowbit(int x){ return x & (-x); }
    void modify(int i, ll x) //单点更新 
    {
        i++;
        while(i <= treemax)
        {
            tree[i] += x;
            i += lowbit(i);
        }
    }
    ll query(int i)//前缀和查询 
    {
        i++;
        ll s = 0;
        while(i > 0)
        {
            s += tree[i];
            i -= lowbit(i);
        }
        return s;
    }
}lencnt[2], addsum[2];

ll get_ans(int pos)
{
    ll ans = 0;
    map<int, ll>mp[2];
    for (int i = 0; i < 2; i++) lencnt[i].init(), addsum[i].init(), mp[i].clear();
    for (int i = 1; i <= pos; i++)
    {
        int lcplen = ht[i];
        lcplen -= pre[min(pos, sa[i] + ht[i] - 1)] - pre[sa[i] - 1];
        for (int j = 0; j < 2; j++)
        {
            IT it = mp[j].upper_bound(lcplen);
            while (it != mp[j].end())
            {
                int x = it->first;
                ll y = it->second;
                lencnt[j].modify(x, -y);
                addsum[j].modify(x, -1LL * x * y);
                lencnt[j].modify(lcplen, y);
                addsum[j].modify(lcplen, 1LL * lcplen * y);
                mp[j][lcplen] += y;
                mp[j].erase(it++);
            }
        }
        int rlen = rad[sa[i]], cho = 1 - flag[i];
        ans += addsum[cho].query(rlen); //先统计小于等于rlen的答案 
        ans += 1LL * rlen * (lencnt[cho].query(100005) - lencnt[cho].query(rlen));
        lencnt[flag[i]].modify(rlen, 1);
        addsum[flag[i]].modify(rlen, rlen);
        mp[flag[i]][rlen] += 1;
    }
    return ans;
}

int main()
{
    scanf("%s", s + 1);
    scanf("%s", t + 1);

    int lens = strlen(s + 1), lent = strlen(t + 1);

    int pos = 0;
    for (int i = 1; i <= lens; i++) p[++pos] = '#', p[++pos] = s[i];
    p[++pos] = '#'; p[++pos] = '*';
    for (int i = 1; i <= lent; i++) p[++pos] = '#', p[++pos] = t[i];
    p[++pos] = '#';
    lens = lens << 1 | 1; 
    lent = lent << 1 | 1;

    get_rad(p, pos, lens);

    p[pos + 1] = '\0';
    get_sa(p, pos);
    get_height(p, pos);
    for (int i = 1; i <= pos; i++)
    {
        if (sa[i] <= lens) flag[i] = 0;
        else flag[i] = 1;
        if (p[i] == '#') pre[i] = 1;
        pre[i] += pre[i - 1];
    }

    ll ans = get_ans(pos);
    printf("%lld\n", ans);

    return 0;
}

习题5 String 传送门

题意:
给你一个串,求所有不同字串的贡献和,每种字串的贡献,k*(k+1)/2,k为该子串出现的次数

思路:
后缀数组 + 单调栈
1. 对出现大于等于2次的计算,处理方法类似习题2, 利用单调栈和height分类求解即可
2. 对只出现1次的计算,枚举每个串S[i], len = |S[i]|, 则有 len - max(height[i], height[i + 1]) 个串只出现了一次

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int sa[N], rk[N], oldrk[N << 1], id[N], px[N], cnt[N], ht[N];

bool cmp(int x, int y, int w) 
{
  return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void get_sa(char s[], int n)
{
    int i, m = 300, p, w;
    for (int i = 1; i <= m; i++) cnt[i] = 0;
    for (i = 1; i <= n; ++i) ++cnt[rk[i] = s[i]];
    for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (i = n; i >= 1; --i) sa[cnt[rk[i]]--] = i;

    for (w = 1; w < n; w <<= 1, m = p) 
    {  // m=p 就是优化计数排序值域
        for (p = 0, i = n; i > n - w; --i) id[++p] = i;
        for (i = 1; i <= n; ++i)
            if (sa[i] > w) id[++p] = sa[i] - w;

        for (int i = 0; i <= m; i++) cnt[i] = 0;
        for (i = 1; i <= n; ++i) ++cnt[px[i] = rk[id[i]]];
        for (i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
        for (i = n; i >= 1; --i) sa[cnt[px[i]]--] = id[i];

        for (int i = 0; i <= n; i++) oldrk[i] = rk[i];
        for (p = 0, i = 1; i <= n; ++i)
            rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    }
}

void get_height(char s[], int n)
{
    for (int i = 1, k = 0; i <= n; ++i) 
    {
        if (k) --k;
        while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
        ht[rk[i]] = k;
    }
}

int l[N], r[N], qu[N], tot;
void get_array_lr(int n)
{
    ht[0] = ht[n + 1] = -1;

    qu[++tot] = 0;
    for (int i = 1; i <= n; i++)
    {
        while (tot && ht[i] <= ht[qu[tot]]) tot--;
        l[i] = qu[tot] + 1;
        qu[++tot] = i;
    }

    tot = 0;
    qu[++tot] = n + 1;
    for (int i = n; i >= 1; i--)
    {
        while (tot && ht[i] <= ht[qu[tot]]) tot--;
        r[i] = qu[tot] - 1;
        qu[++tot] = i;
    }

    ht[0] = ht[n + 1] = 0;
}

char s[N];
vector<int>v[N];
int sum[N];

int main()
{
    scanf("%s", s + 1);

    int len = strlen(s + 1);

    get_sa(s, len);
    get_height(s, len);
    get_array_lr(len);

    ll ans = 0;
    for (int i = 1; i <= len; i++) v[ht[i]].push_back(i);
    for (int i = len; i >= 1; i--)
    {
        int rborder = 0;
        for (int j = 0; j < v[i].size(); j++)
        {
            int le = l[v[i][j]], ri = r[v[i][j]];
            if (ri <= rborder) continue;
            rborder = ri;
            int down = max(ht[le - 1], ht[ri + 1]) + 1;
            int cs = ri - le + 2;
            ans += 1LL * cs * (cs + 1) / 2 * (i + 1 - down);
        }
    }

    for (int i = 1; i <= len; i++)
    {
        int ma = max(ht[i], ht[i + 1]);
        ans += len - sa[i] + 1 - ma;
    }

    printf("%lld\n", ans);

    return 0;
}


本人不太会写博客,若有错误,敬请指出,有点丑见谅





15天前

题目来源于《挑战程序设计竞赛》,题目涉及的算法只对应相关章节 (不一定是最优解的,思路写的有点简陋)


例题1 Constellations 传送门

题意:
给1个n行m列的大01矩阵 和 t个p行q列的小01矩阵,求这t个小矩阵有多少个在大矩阵中。

思路:
二维hash。算出整个矩阵的所有的P*Q小矩阵的hash值,存在set中,同时求出目标矩阵的hash值,判断该值是否出现即可。若出现,将该hash值从set中删除。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

typedef unsigned int UI;

const int N = 1010;
const int M = 60;

int n, m, t, x, y;
char mp[N][N], s[M][M];

const UI p0 = 1413;
UI p[N * N], hash1[N][N], hash2[N];
multiset<UI>se;

//计算大01矩阵 
void pre(int n, int m, int x, int y)
{
    p[0] = 1;
    for (int i = 1; i <= n * m; i++) p[i] = p[i - 1] * p0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        hash1[i][j] = hash1[i][j - 1] * p[1] + mp[i][j];

    for (int i = y; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        hash2[j] = hash1[j][i] - hash1[j][i - y] * p[y];
        for (int j = 1; j <= n; j++)
        hash2[j] = hash2[j - 1] * p[y] + hash2[j];
        for (int j = x; j <= n; j++)
        se.erase(hash2[j] - hash2[j - x] * p[x * y]);
    }
}

int main()
{
    int cas = 0;
    while (~scanf("%d %d %d %d %d", &n, &m, &t, &x, &y))
    {
        if (n + m + t + x + y == 0) break;
        se.clear();

        for (int i = 1; i <= n; i++)
            scanf("%s", mp[i] + 1);

        for (int T = 1; T <= t; T++)
        {
            for (int i = 1; i <= x; i++)
                scanf("%s", s[i] + 1);

            //计算小01矩阵 
            UI ans = 0;
            for (int i = 1; i<= x; i++)
                for (int j = 1; j <= y; j++)
                ans = ans * p0 + s[i][j];
            se.insert(ans);
        }

        pre(n, m, x, y); 

        int cnt = t - se.size();
        printf("Case %d: %d\n", ++cas, cnt);
    }

    return 0;
}

习题1 Constellations 传送门

题意:
给定3个字符串 s1, s2, s3,试求一个字符串 S
使 s1, s2, s3 都是这个字符串的子串,问这个字符串的最短长度。

思路:
先考虑简单情况,合并两个字符串t1, t2, (t1在t2的左侧)
有以下两种情况:
1. t1包含t2, 则合并结果为t1
2. t1不包含t2, 设 len 为 t1的后缀串 和 t2的前缀串 的最长公共子串T, 则合并时去掉T即可

利用以上方法,枚举3个字符串的全排列,根据顺序依次合并s1, s2, s3, 最后对结果取最小值即可

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned long long ULL;

const int N = 3e5 + 10;

string s[5];
int num[N], tot;
ULL p[N], hash1[N], hash2[N];

void init(int n)
{
    p[0] = 1;
    for (int i = 1; i <= n; i++) p[i] = p[i - 1] * 131;
}

string merge(string a, string b)
{
    a = " " + a; b = " " + b;
    int lena = a.length() - 1, lenb = b.length() - 1;
    for (int i = 1; i <= lena; i++) hash1[i] = hash1[i - 1] * 131 + a[i] - '0';
    for (int i = 1; i <= lenb; i++) hash2[i] = hash2[i - 1] * 131 + b[i] - '0';

    for (int i = 1; i <= lena - lenb + 1; i++)
        if (hash1[i + lenb - 1] - hash1[i - 1] * p[lenb] == hash2[lenb]) 
            return a.substr(1);
    for (int i = max(1, lena - lenb + 2); i <= lena; i++)
    {
        int len = lena - i + 1;
        if (hash1[lena] - hash1[i - 1] * p[len] == hash2[len]) 
            return a.substr(1) + b.substr(len + 1);
    }
    return a.substr(1) + b.substr(1);

}

string merge(string a, string b, string c)
{
    return merge(merge(a, b), c);
}

int main()
{
    init(300005);

    for (int i = 1; i <= 3; i++) cin >> s[i];

    for (int i = 1; i <= 3; i++) num[i] = i;

    int mi = N;
    do{
        string ans = merge(s[num[1]], s[num[2]], s[num[3]]);
        mi = min(mi, (int)ans.length());
    }while (next_permutation(num + 1, num + 4));
    printf("%d\n", mi);

    return 0;
}


习题2 Where’s Wally 传送门

题意:
从w行h列的大图中找出p行p列的小图,旋转翻转皆可,共8种。问大图中共有多少个小图。

思路:
直接对大图不好处理,可采取对小图进行旋转翻转8种操作对应hash值的计算,将其存入set中。
遍历大图,对每个p*p的块,求出对应的hash值,判断是否在set中即可。

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

typedef unsigned long long ULL;

const int N = 1e3 + 10;
const int M = 1e2 + 10;

int w, h, p;
char s[N][N], t[N][N];
char ns[N][N], nt[N][N], backup[N][N];

int get_val(char c)
{
    if (c >= 'A' && c <= 'Z') return c - 'A';
    if (c >= 'a' && c <= 'z') return 26 + c - 'a';
    if (c >= '0' && c <= '9') return 52 + c - '0';
    if (c == '+') return 62;
    if (c == '/') return 63;
}

void change_matrix(int n, int m, char (&s)[N][N], char (&e)[N][N])
{
    for (int i = 1; i <= n; i++)
    {
        int tot = 0;
        for (int j = 1; s[i][j]; j++)
        {
            int val = get_val(s[i][j]);
            for (int k = 5; k >= 0; k--)
                if (val & (1 << k)) e[i][++tot] = '1';
                else e[i][++tot] = '0';
        }
    }
}

ULL P[N * N], ha[N][N];
void init(int n)
{
    P[0] = 1;
    for (int i = 1; i <= n; i++) P[i] = P[i - 1] * 131;
}

int main()
{
    init(1000005);

    while (~scanf("%d %d %d", &w, &h, &p))
    {
        if (w + h + p == 0) break;

        for (int i = 1; i <= h; i++) scanf("%s", s[i] + 1);
        for (int i = 1; i <= p; i++) scanf("%s", t[i] + 1);

        change_matrix(h, w, s, ns);
        change_matrix(p, p, t, nt);

        for (int i = 1; i <= h; i++)
            for (int j = 1; j <= w; j++)
            ha[i][j] = ha[i][j - 1] * 131 + ns[i][j] - '0';

        set<ULL>se; 

        for (int t = 1; t <= 8; t++)
        {
            if (t == 5)
            {
                memcpy(backup, nt, sizeof nt);
                for (int i = 1; i <= p; i++)
                    for (int j = 1; j <= p; j++)
                    nt[i][p - j + 1] = backup[i][j];
            }

            ULL val = 0;
            for (int i = 1; i <= p; i++)
                for (int j = 1; j <= p; j++)
                val = val * 131 + nt[i][j] - '0';
            se.insert(val);

            memcpy(backup, nt, sizeof nt);
            for (int i = 1; i <= p; i++)
                for (int j = 1; j <= p; j++)
                nt[p - j + 1][i] = backup[i][j];
        }

        int cnt = 0;
        for (int i = 1; i + p - 1 <= h; i++)
            for (int j = 1; j + p - 1 <= w; j++)
            {
                ULL val = 0;
                for (int k = i; k <= i + p - 1; k++)
                    val = val * P[p] + ha[k][j + p - 1] - ha[k][j - 1] * P[p];
                if (se.find(val) != se.end()) cnt++;
            }
        printf("%d\n", cnt);
    }

    return 0;
}

习题3 The Oculus 传送门

题意:
数字可以被唯一分解成为一系列斐波那契数的加和的形式。
现在给定两个这样的 数字a 和 数字b 将他们的乘积 c 也表示成为斐波那契数的加和的形式。
随后将 c 其中非首位的一个1改成0,题目要求哪一位是被修改的一位。

思路:
将题目转换一下,记X=A×B−C,判断X是斐波那契数列的第几项。
对每个斐波那契数都取个模数,可采取自然溢出、双哈希等等来避免冲突
由于杭电OJ,RE报WA,导致我的代码里是三哈希,事实上只要自然溢出即可
求出A×B的值后,枚举答案,判断修改位置

代码:

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ULL;

const int N = 2e6 + 10;
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;

ll f1[N], f2[N];
ULL f3[N];

int t;
int alen, a[N];
int blen, b[N];
int clen, c[N];

set<pair<ll,ll> >se;

int main()
{
    f1[1] = 1; f1[2] = 2;
    f2[1] = 1; f2[2] = 2;
    f3[1] = 1; f3[2] = 2;
    for (int i = 3; i <= 2000005; i++)
    {
        f1[i] = (f1[i - 1] + f1[i - 2]) % mod1;
        f2[i] = (f2[i - 1] + f2[i - 2]) % mod2;
        f3[i] = f3[i - 1] + f3[i - 2];
    }

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &alen);
        for (int i = 1; i <= alen; i++)
            scanf("%d", &a[i]);
        scanf("%d", &blen);
        for (int i = 1; i <= blen; i++)
            scanf("%d", &b[i]);
        scanf("%d", &clen);
        for (int i = 1; i <= clen; i++)
            scanf("%d", &c[i]);

        ll aval1 = 0, bval1 = 0;
        ll aval2 = 0, bval2 = 0;
        ULL aval3 = 0, bval3 = 0;
        for (int i = 1; i <= alen; i++)
            if (a[i])
            {
                aval1 = (aval1 + f1[i]) % mod1;
                aval2 = (aval2 + f2[i]) % mod2;
                aval3 += f3[i];
            }
        for (int i = 1; i <= blen; i++)
            if (b[i])
            {
                bval1 = (bval1 + f1[i]) % mod1;
                bval2 = (bval2 + f2[i]) % mod2;
                bval3 += f3[i];
            }

        ll res1 = aval1 * bval1 % mod1;
        ll res2 = aval2 * bval2 % mod2;
        ULL res3 = aval3 *bval3;

        ll cval1 = 0, cval2 = 0;
        ULL cval3 = 0;
        for (int i = 1; i <= clen; i++)
            if (c[i])
            {
                cval1 = (cval1 + f1[i]) % mod1;
                cval2 = (cval2 + f2[i]) % mod2;
                cval3 += f3[i];
            }
        int ans = 0;
        for (int i = 1; i <= clen; i++)
        {
            if (c[i]) continue;
            ll tmp1 = (cval1 + f1[i]) % mod1;
            ll tmp2 = (cval2 + f2[i]) % mod2;
            ULL tmp3 = cval3 + f3[i];
            if (tmp1 == res1 && tmp2 == res2 && tmp3 == res3)
            {
                ans = i;
                break;
            }
        }

        printf("%d\n", ans);
    }

    return 0;
}


本人不太会写博客,若有错误,敬请指出,有点丑见谅





22天前

题目描述

1.png
2.png
3.png

样例

4.png ·

问题分析

由题意可知,要构造 gcd(x,y)>1 ,显然与1无关,故不考虑1.
设 S(p) 为 2~n 所有最小质因子为p的数的集合
由上述定义,可将 2~n 中的所有整数划分到对应的集合中

例如 n = 10
S(2) = {2, 4, 6, 8, 10}
S(3) = {3, 9}
S(5) = {5}
S(7) = {7}

情况一:S(p).size() % 2 == 0

对于 ∀p, ∀x,y∈S(p), gcd(x,y) >= p && p > 1
那么,在同一个集合中即可任选两个数匹配进行构造,即可解决的 S(p).size() % 2 == 0 情况

情况二:S(p).size() % 2 == 1

若集合 S(p).size() % 2 == 1 时,要考虑到两个集合进行构造
设p1,p2,满足 S(p1).size() % 2 == 1 && S(p2).size() % 2 == 1 && p1 < p2
那么,可以选择 x = p1 * p2, y = p2,这样就能解决此问题
但是还是存有漏洞,万一 p1 > sqrt(n) 则 p1 * p2 > n,显然会出错
我们可以将所有 p ≤ sqrt(n) 的集合用上述方法处理,所有 p > sqrt(n) 的集合选择 x = p, y = 2 * p 处理
(当然你得判断y合法,)

实现方法

先用线性筛预处理出每个数的最小质因子,然后放入对应的集合 divv 中
优先构造 p > sqrt(n) 的情况
再处理 S(p).size() % 2 == 1的情况
最后将所有集合里的元素匹配即可

C++ 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 10;

int p[N], tot, d[N], st[N];
void init(int n)//用线性筛预处理出每个数的最小质因子
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i]) p[++tot] = i, d[i] = i;
        for (int j = 1; j <= tot && i * p[j] <= n; j++)
        {
            st[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                d[i * p[j]] = d[i];
                break;
            }
            else d[i * p[j]] = p[j];
        }
    }
}

int t, n;
set<int>divv[N];

int main()
{
    init(200005);

    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);

        //放入对应的集合 divv 
        for (int i = 1; i <= n; i++) divv[i].clear();
        for (int i = 1; i <= n; i++) divv[d[i]].insert(i);

        //记录答案
        vector<int>a, b;
        a.clear(); b.clear();

        //优先构造 p > sqrt(n) 的情况
        int sqn = sqrt(n);
        int pos = upper_bound(p + 1, p + tot + 1, sqn) - p;
        for (int i = pos; p[i] <= n; i++)
        {
            int val1 = p[i], val2 = 2 * p[i];
            if (val2 > n) continue;
            a.push_back(val2);
            b.push_back(val1);
            divv[2].erase(val2);
            divv[p[i]].erase(val1);
        }

        //处理 S(p).size() % 2 == 1的情况
        vector<int>v;
        for (int i = 1; p[i] <= n; i++)
        {
            int sz = divv[p[i]].size();
            if (sz & 1) v.push_back(p[i]);
        }
        for (int i = 0; i + 1 < v.size(); i += 2)
        {
            int val1 = v[i], val2 = v[i + 1];
            if (1LL * val1 * val2 > n) continue;
            a.push_back(val1 * val2);
            b.push_back(val2);
            divv[val1].erase(val1 * val2);
            divv[val2].erase(val2);
        }

        //若存在奇数个元素的集合,直接删一个,以便后续处理
        for (int i = 1; p[i] <= n; i++)
        {
            if (divv[p[i]].size() % 2 == 1)
                divv[p[i]].erase(p[i]);
        }

        //最后将所有集合里的元素匹配
        for (int i = 1; p[i] <= n; i++)
        {
            for (auto it = divv[p[i]].begin(); it != divv[p[i]].end(); it++)
            {
                a.push_back(*it);
                it++;
                b.push_back(*it);
            }
        }

        printf("%d\n", a.size());
        for (int i = 0; i < a.size(); i++)
            printf("%d %d\n", a[i], b[i]);
    }
}

本人不太会写博客,若有错误,敬请指出,有点丑见谅



分享 KMP


1个月前

KMP:

定义:Knuth-Morris-Pratt字符串查找算法,简称为“KMP算法”,常用于在一个文本串S内查找一个模式串P的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。

注:以下字符串起始下标均为1

引入概念:

  • 前缀:指的是字符串的子串中从原串最前面开始的子串
    如abcdef的前缀有:a,ab,abc,abcd,abcde

  • 后缀:指的是字符串的子串中在原串结尾处结尾的子串
    如abcdef的后缀有:f,ef,def,cdef,bcdef

  • Next[i]:满足 以1开始的前缀以i结尾的后缀 相等条件的最大长度(长度<i)

Next数组求解:
求解Next数组,只涉及模式串P,要将模式串作为文本串(即S=P)

  • 边界:Next[1]=0;(由定义即可得到)

  • 匹配状态:j + 1表示当前P要匹配的下标,i表示当前S串要匹配的下标
    若P[j+1]=S[i],直接匹配成功,则Next[j]=Next[j-1]+1;
    若P[j+1]≠S[i],匹配失败,需要根据Next[j]不断向前跳j,直到匹配成功或者j=0;

Image

void get_Next(char S[], char P[])//S:文本串 P:模式串(此时S = P)
{
    int n = strlen(S + 1);
    int m = strlen(P + 1);

    Next[1] = 0;
    for (int i = 2, j = 0; i <= n; i++)
    {
        while (j && S[i] != P[j + 1]) j = Next[j];
        if (S[i] == P[j + 1]) j++;
        Next[i] = j;
    }
}

Next数组运用:
过程和求解基本一致,直接用原文本串即可。

//例:获取文本串S 中 模式串P 的个数
int get_count(char S[], char P[])
{
    int n = strlen(S + 1);
    int m = strlen(P + 1);

    int cnt = 0; //统计个数

    for (int i = 1, j = 0; i <= n; i++)
    {
        while (j && S[i] != P[j + 1]) j = Next[j];
        if (S[i] == P[j + 1]) j++;
        if (j == m) //找到匹配成功项
            cnt++, j = Next[j];
    }

    return cnt;
}

时间复杂度: O(N + M)

相关性质(周期性):

  • 若模式串P中 j / (j - Next[j]) == 0, 则P中必存在最小循环节(P[1~j-Next[j]),且循环次数为 j / (j - Next[j])
    证明方法可通过切割移项法证“循环节”成立,通过反证法证“最小”成立
  • 若模式串P中 j / (j - Next[j]) ≠ 0, 则P中必存在最小循环节(P[1~j-Next[j]),且循环次数为 j / (j - Next[j]),余项为P[1 ~ j % Next[j]]
    证明方法如上

不知道理解得对不对,请大佬指教



活动打卡代码 AcWing 175. 电路维修


3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 510;
typedef pair<int,int> PII;

int t, n, m;
char mp[N][N];
int dist[N][N], st[N][N];

string ops = "\\//\\";
int dir1[4][2] = {-1, -1, -1, 1, 1, -1, 1, 1};
int dir2[4][2] = {0, 0, 0, 1, 1, 0, 1, 1};

bool check(int x, int y)
{
    return x >= 0 && x <= n && y >= 0 && y <= m;
}

int bfs()
{
    deque<PII>qu;

    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    dist[0][0] = 0;
    qu.push_back({0, 0});

    while (!qu.empty())
    {
        PII cur = qu.front(); qu.pop_front();
        int x = cur.first, y = cur.second;
        if (st[x][y]) continue;
        st[x][y] = 1;

        for (int i = 0; i < 4; i++)
        {
            int nex = x + dir1[i][0], ney = y + dir1[i][1];
            int j = x + dir2[i][0], k = y + dir2[i][1];

            if (!check(nex, ney) || st[nex][ney]) continue;
            int w = 0;
            if (mp[j][k] != ops[i]) w = 1;
            if (dist[nex][ney] > dist[x][y] + w)
            {
                dist[nex][ney] = dist[x][y] + w;
                if (w == 1) qu.push_back({nex, ney});
                else qu.push_front({nex, ney});
            }
        }
    }

    return dist[n][m];
}

int main()
{
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

        int ans = bfs();
        if (ans == 0x3f3f3f3f) printf("NO SOLUTION\n");
        else printf("%d\n", ans);
    }

    return 0;
}


活动打卡代码 AcWing 174. 推箱子


3个月前
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 25;

int t, n, m;
char mp[N][N];//mp: 存地图
string ops = "nswe";//ops:上下左右
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};//下上右左

struct node{
    int x, y, dir;
};

bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != '#';
}

int vis[N][N], pre_man[N][N];
int bfs_man(PII sta, PII en, PII box, string& seq)
{
    memset(vis, 0, sizeof vis);
    memset(pre_man, -1, sizeof pre_man);

    queue<PII>qu;
    vis[sta.first][sta.second] = 1;
    vis[box.first][box.second] = 1;
    qu.push(sta);

    int flag = -1;
    while (!qu.empty())
    {
        PII cur = qu.front(); qu.pop();
        int x = cur.first, y = cur.second;
        if (cur == en)
        {
            while (pre_man[x][y] != -1)
            {
                int d = pre_man[x][y];
                seq.push_back(ops[d]);
                x = x + dir[d][0];
                y = y + dir[d][1];
            }
            flag = seq.length();
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int nex = x - dir[i][0], ney = y - dir[i][1];//(nex,ney):人的位置
            if (check(nex, ney) == 0 || vis[nex][ney]) continue;
            vis[nex][ney] = 1;
            qu.push({nex, ney});
            pre_man[nex][ney] = i;
        }
    }
    return flag;
}

node pre[N][N][4];//pre(i,j,k):当前箱子在(i,j),上一个在(i+dir[k][0],j+dir[k][1])的状态
string path[N][N][4];//path(i,j,k):走到推(i,j,k)这个状态的位置的行走路程
PII dist[N][N][4];//dist(i,j,k):从初始状态到达(i,j,k)状态的箱子最短路程和人最短路程
bool st[N][N][4];
bool bfs_box(PII man, PII box, node& end)
{
    memset(st, 0, sizeof st);

    queue<node>qu;

    for (int i = 0; i < 4; i++)
    {
        int x = box.first, y = box.second;
        int a = x + dir[i][0], b = y + dir[i][1];//(a,b):人的位置
        int j = x - dir[i][0], k = y - dir[i][1];//(j,k):箱子的位置

        if (check(a, b) == 0 || check(j, k) == 0) continue;
        string seq;
        int distance = bfs_man(man, {a, b}, box, seq);
        if (distance == -1) continue;
        st[j][k][i] = 1;
        qu.push({j, k, i});
        pre[j][k][i] = {x, y, -1};
        path[j][k][i] = seq;
        dist[j][k][i] = {1, distance};
    }

    bool flag = false;
    PII mi = {1e9, 1e9};

    while (!qu.empty())
    {
        node cur = qu.front(); qu.pop();
        int x = cur.x, y = cur.y, d = cur.dir;
        if (mp[x][y] == 'T')
        {
            flag = true;
            if (dist[x][y][d] < mi) mi = dist[x][y][d], end = cur;
            continue;
        }
        for (int i = 0; i < 4; i++)
        {
            int a = x + dir[i][0], b = y + dir[i][1];//(a,b):人的位置
            int j = x - dir[i][0], k = y - dir[i][1];//(j,k):箱子的位置

            if (check(a, b) == 0 || check(j, k) == 0) continue;
            string seq;
            int distance = bfs_man({x + dir[d][0], y + dir[d][1]}, {a, b}, {x, y}, seq);
            if (distance == -1) continue;
            PII now_dist = {dist[x][y][d].first + 1, dist[x][y][d].second + distance};
            if (!st[j][k][i])
            {
                st[j][k][i] = 1;
                qu.push({j, k, i});
                pre[j][k][i] = cur;
                path[j][k][i] = seq;
                dist[j][k][i] = now_dist;
            }
            else if (dist[j][k][i] > now_dist)
            {
                pre[j][k][i] = cur;
                path[j][k][i] = seq;
                dist[j][k][i] = now_dist;
            }
        }
    }

    return flag;
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        if (n == 0 && m == 0) break;

        for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

        PII man, box;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                if (mp[i][j] == 'B') box = {i, j};
                if (mp[i][j] == 'S') man = {i, j};
            }

        printf("Maze #%d\n", ++t);
        node end;
        if (bfs_box(man, box, end))
        {
            string ans;
            while (end.dir != -1)
            {
                ans.push_back((char)(ops[end.dir] - 32));
                ans.append(path[end.x][end.y][end.dir]);
                end = pre[end.x][end.y][end.dir];
            }
            reverse(ans.begin(), ans.end());
            cout << ans << endl;
        }
        else printf("Impossible.\n");
        printf("\n");
    }

    return 0;
}


活动打卡代码 AcWing 173. 矩阵距离


3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e3 + 10;
int n, m, dist[N][N];
char mp[N][N];

struct node{
    int x, y;
};
int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m && dist[x][y] == -1;
}

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);

    memset(dist, -1, sizeof dist);
    queue<node>qu;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        if (mp[i][j] == '1') qu.push({i, j}), dist[i][j] = 0;

    while (!qu.empty())
    {
        node cur = qu.front(); qu.pop();
        for (int i = 0; i < 4; i++)
        {
            int nex = cur.x + dir[i][0];
            int ney = cur.y + dir[i][1];
            if (!check(nex, ney)) continue;
            dist[nex][ney] = dist[cur.x][cur.y] + 1;
            qu.push({nex, ney});
        }
    }

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

    return 0;
}


活动打卡代码 AcWing 172. 立体推箱子


3个月前
#include <bits/stdc++.h>
using namespace std;

const int N = 5e2 + 10;
int n, m, dist[5][N][N];
char mp[N][N];

struct node{
  int x, y, sta;  
};
//sta: 0->立着 1->横着躺 2->竖着躺
int dir[3][4][3] = {
    -2, 0, 2, 1, 0, 2, 0, -2, 1, 0, 1, 1, // sta = 0
    -1, 0, 1, 1, 0, 1, 0, -1, 0, 0, 2, 0, // sta = 1
    -1, 0, 0, 2, 0, 0, 0, -1, 2, 0, 1, 2  // sta = 2
};

bool check(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m && mp[x][y] != '#';
}

int bfs(node sta, node en)
{
    queue<node>qu;
    while (!qu.empty()) qu.pop();
    qu.push(sta);
    dist[sta.sta][sta.x][sta.y] = 0;

    while (!qu.empty())
    {
        node cur = qu.front(); qu.pop();
        int x = cur.x, y = cur.y, sta = cur.sta;
        if (x == en.x && y == en.y && sta == en.sta) return dist[sta][x][y];

        for (int i = 0; i < 4; i++)
        {
            int nex = x + dir[sta][i][0];
            int ney = y + dir[sta][i][1];
            int nesta = dir[sta][i][2];

            if (!check(nex, ney)) continue;
            if (nesta == 0 && mp[nex][ney] == 'E') continue;
            if (nesta == 1 && !check(nex, ney + 1)) continue;
            if (nesta == 2 && !check(nex + 1, ney)) continue;
            if (dist[nesta][nex][ney] != -1) continue;

            node ne = {nex, ney, nesta};
            dist[nesta][nex][ney] = dist[sta][x][y] + 1;
            qu.push(ne);
        }
    }

    return -1;
}

int main()
{
    ios::sync_with_stdio(false);

    while (cin >> n >> m)
    {
        if (n == 0 && m == 0) break;
        memset(dist, -1, sizeof dist);
        for (int i = 1; i <= n; i++) cin >> mp[i] + 1;

        node sta = {0, 0, 0}, en;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
            {
                if (mp[i][j] == 'X' && sta.x == 0)
                {
                    if (mp[i][j + 1] == 'X') sta = {i, j, 1};
                    else if (mp[i + 1][j] == 'X') sta = {i, j, 2};
                    else sta = {i, j, 0};
                }
                if (mp[i][j] == 'O') en = {i, j, 0};
            }

        int ans = bfs(sta, en);
        if (ans == -1) cout << "Impossible" << endl;
        else cout << ans << endl;
    }

    return 0;
}


活动打卡代码 AcWing 171. 送礼物


3个月前
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 50;
const int M = 25;
int n, w, g[N];
int w1[1 << M], tot, k;
int ans;

void dfs1(int pos, int val)
{
    if (pos == k)
    {
        w1[++tot] = val;
        return;
    }

    ll sum = 1LL * val + g[pos + 1];
    if (sum <= w) dfs1(pos + 1, sum);
    dfs1(pos + 1, val);
}

void dfs2(int pos, int val)
{
    if (pos == n)
    {
        int l = 1, r = tot;
        while (l < r)
        {
            int mid = (l + r + 1) >> 1;
            if (1LL * w1[mid] + val <= w) l = mid;
            else r = mid - 1;
        }
        ans = max(ans, val + w1[l]);
        return;
    }

    ll sum = 1LL * val + g[pos + 1];
    if (sum <= w) dfs2(pos + 1, sum);
    dfs2(pos + 1, val);
}

int main()
{
    scanf("%d %d", &w, &n);
    for (int i = 1; i <= n; i++) scanf("%d", &g[i]);

    k = n / 2 + 2;
    sort(g + 1, g + n + 1);
    reverse(g + 1, g + n + 1);

    dfs1(0, 0);

    sort(w1 + 1, w1 + tot + 1);
    tot = unique(w1 + 1, w1 + tot + 1) - w1 - 1;

    dfs2(k, 0);

    printf("%d\n", ans);

    return 0;
}