目录

B. 宝石手串

         D. 气球谜题

---

 

 

 

 

 

B. 宝石手串

        （1）两种扩容方式：
               

// 法一：直接加（通常用于拼接字符串）s += s// 法二：一个一个字符加（用于加单个字符）for (int i = len; i < 2 * len; i ++)s.push_back(s[i - len]);// 错误方法，s是一个容器，有大小，此方法会越界for (int i = len; i < 2 * len; i ++)s[i] = s[i - len];

        （2）每个字符记录上次出现位置，下次出现更新该字符最短间距 

        （3）dis数组值为 len - 1 时说明该字符只出现了一次，第二个是复制而来，该情况也要排除

#include<bits/stdc++.h>
#define LL long long
using namespace std;const int N = 2e5 + 5, INF = 0x3f3f3f3f;
int t, n, ans, h[30], vis[30], dis[30];
string s;int main()
{cin >> t;while (t --){cin >> n >> s;ans = INF;int len = s.length();s += s;memset(dis, 0x3f, sizeof(dis));memset(vis, 0, sizeof(vis));for (int i = 0; i < 2 * len; i ++){int x = s[i] - 'a';if (!vis[x]){h[x] = i;vis[x] = 1;}else{dis[x] = min(dis[x], i - h[x] - 1);h[x] = i;}}for (int i = 0; i < 30; i ++)if(dis[i] != len - 1)   	ans = min(ans, dis[i]);if (ans == INF)cout << "-1" << '\n';elsecout << ans << '\n';}return 0;
}

 

D. 气球谜题

        （1）memset无法赋 1e18，只能 for 循环赋值

        （2）dp[ i ][ j ] [ k ]：第 i 个气球颜色为 j ，出现过的颜色集合为 k

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5, INF = 1e18;
int n, ans, a[N], dp[N][5][10];
string s;signed main()
{cin >> n >> s;s = '0' + s;for(int i = 1; i <= n; i ++){for(int j = 0; j <= 2; j ++){for(int k = 1; k < 8; k ++){dp[i][j][k] = INF;}}}for (int i = 1; i <= n; i ++)cin >> a[i];for (int j = 0; j <= 2; j ++){if (s[1] - '0' == j)dp[1][j][1 << j] = 0;elsedp[1][j][1 << j] = a[1];}for (int i = 2; i <= n; i ++)			// 当前在第 i 个气球 for (int j = 0; j <= 2; j ++)		// 当前第 i 个气球的颜色 for (int k = 1; k < 8; k ++){//当前集合里面有 j  -->  j 已经出现过if (k >> j & 1){if (s[i] - '0' == j)dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k]);elsedp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] + a[i]);}//当前集合里面没有 j  -->  j 还未出现过, 现在要变成 j //					  -->  第 i - 1 个气球一定不是 j else{// 枚举第 i - 1 个气球的颜色for (int l = 0; l <= 2; l ++){		// k >> l & 1为真：前 i - 1 个气球的颜色集合里必须有 l，因为 i - 1 的颜色为 l // j != l 为真：当前第 i 个气球颜色肯定不能和第 i - 1 个气球颜色相等，若相等则违背集合没有颜色 j 的大条件// s[ i ] - '0' == j 和 != j ：分类当前第 i 个气球颜色是否为 j ，需不需要染成 j// 因为 k 和 j 都还在大循环里枚举，并不能保证第一个和第二个条件自然成立，因此需要加入 if 中判断if (k >> l & 1 && l != j && s[i] - '0' == j)dp[i][j][k | 1 << j] = min(dp[i][j][k | 1 << j], dp[i - 1][l][k]);if (k >> l & 1 && l != j && s[i] - '0' != j)dp[i][j][k | 1 << j] = min(dp[i][j][k | 1 << j], dp[i - 1][l][k] + a[i]);}}}ans = INF;for (int j = 0; j <= 2; j ++)for (int k = 1; k < 8; k ++)ans = min(ans, dp[n][j][k]);cout << ans;return 0;
}