E. Subsequences (easy version)

 

 

本题和H题唯一的不同点是数据范围。

 

你有一个长度为nn的字符串。你可以选择它的任意一个子序列。子序列定义为可以将这个字符串删去若干个字符得到。特别的，空串也是一个子序列。

 

对于一个长度为mm的子序列，选出它的花费是n-mn−m，也就是你需要删掉的字符数量。

 

你的任务是选出来kk个本质不同的子序列，使得总花费最小。输出这个最小花费。

 

如果选不出kk个，输出-1−1。

 

思路：

因为本题的数据量比较小，所以我们可以采取BFS去模拟整个的过程。

利用bfs与set结合，队列存储当前字符串，每次删除一个字符，若set不存在，更新队列与set。

bfs先从删除少的字符串开始，保证了代价最小效率最优。

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <set>
 6 #include <queue>
 7  
 8 #define LL long long
 9 using namespace std;
10 const int MAXN = 200005;
11  
12 int n,k;
13 set<string> st;
14 queue<string> q;
15 string s;
16  
17 int main()
18 {
19     scanf("%d%d",&n,&k);
20     cin >> s;
21     int cnt = 0;
22     q.push(s);
23     st.insert(s);
24     while (!q.empty() && st.size()<k)
25     {
26         string v = q.front();
27         q.pop();
28         for (int i=0;i<v.size();i++)
29         {
30             string nv = v;
31             nv.erase(i,1);
32             if (!st.count(nv) && st.size()+1<=k)
33             {
34                 q.push(nv);
35                 st.insert(nv);
36                 cnt += (n-nv.size());
37             }
38         }
39     }
40     if (st.size()<k)
41         printf("-1\n");
42     else
43        printf("%d\n",cnt);
44     return 0;
45 }
Ackerman

 

 

F. Topforces Strikes Back

 

从n个数中选出来最多3个数，使得这三个数中不存在任意一个数是另一个数的倍数，同时使得这三个数的和最大。

 

这道题的贪心的想法非常巧妙，看了大佬的博客才知道怎么去贪。 Orz

我们根据我们选出的个数进行讨论：

一、

如果我们只选出了一个数，那么肯定就直接选最大的

二、

如果我们选出了两个数，我们讨论下是不是还一定要选最大的数a呢？答案是肯定的

证明如下：

1、如果有一个数不是a的因数，那么直接用a替换这个数。

2、如果两个数都是a的因数，那么这两个数的和最大是 a/2+a/3 < a，也就是说我们在步骤一中就已经得到最优解了。

所以对于这一种情况，我们只需要选出来最大的数，然后从剩下的数中找到一个不是它的因数的最大的数即可。

三、

如果选出三个数，我们同样还是来看是否一定要选a

可以发现，如果选出来的三个数中有一个或两个数不是a的因数，那么就可以由情况二进行证明，一定要选出来a。

而如果三个数都是a的因数，我们会发现唯一一种特殊情况 a/2 + a/3 + a/5 > a ，我们只要对这种情况进行一次特判就可以了。特判完后就选出最大的a然后一样用第二种情况的方法进行判断

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <set>
 6 #include <queue>
 7  
 8 #define LL long long
 9 using namespace std;
10 int t,n,a[200005];
11 int main() {
12    // freopen("../in.txt","r",stdin);
13     scanf("%d", &t);
14     while (t--) {
15         scanf("%d", &n);
16         int ans = 0;
17         for (int i = 1; i <= n; i++) {
18             scanf("%d", &a[i]);
19             ans = max(ans, a[i]);
20         }
21         sort(a + 1, a + n + 1);
22         int an = a[n];
23         bool flag1 = 0, flag2 = 0, flag3 = 0;
24         for (int i = 1; i <= n; i++) {
25             if (a[i] * 2 == an)flag1 = 1;
26             if (a[i] * 3 == an)flag2 = 1;
27             if (a[i] * 5 == an)flag3 = 1;
28         }
29         if (flag1 && flag2 && flag3)ans = max(ans, an / 2 + an / 3 + an / 5);
30         for (int i=1;i<=n;i++){
31             if (a[n]%a[i] == 0){
32                 a[i] = 2000000000;
33             }
34         }
35        sort(a+1,a+n+1);
36         while (a[n] == 2000000000){
37             n--;
38         }
39         ans = max(ans,an+a[n]);
40         for (int i=1;i<=n;i++){
41             if (a[n]%a[i] != 0){
42                 ans = max(ans,an+a[n]+a[i]);
43             }
44         }
45         printf("%d\n",ans);
46     }
47     return 0;
48 }
Ackerman

 

H. Subsequences (hard version)

本题和E题唯一的不同点是数据范围。

你有一个长度为n的字符串。你可以选择它的任意一个子序列。子序列定义为可以将这个字符串删去若干个字符得到。特别的，空串也是一个子序列。

对于一个长度为m的子序列，选出它的花费是n−m，也就是你需要删掉的字符数量。

你的任务是选出来kk个本质不同的子序列，使得总花费最小。输出这个最小花费。

如果选不出k个，输出-1。

 

思路：

这道题的数据范围比E题高了许多，所以如果跟E一样去搜索的话会超时。

这题是个dp题

确定状态：我们不妨设 dp[i][j] 的含义是前 i 个 长度为 j 的字符串的子序列的个数

确定状态转移方程：

第一、如果字符str[i] 第一次出现  dp[i][j] = dp[i-1][j-1] + dp[i-1][j]

　　　　　　　　　　　　　　　　　　　　（取str[i]）   （不取str[i]）

 

第二、如果字符str[i] 不是第一次出现  那么我们就找它前面出现的时候 vis[str[i]-'a']

 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j] - dp[str[i]-'a'-1][j-1]   （减去重复的就好了）

 

我的代码采取了一个优化，就是如果此时序列已经大于k了我就直接取k就好了

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <set>
 6 #include <queue>
 7  
 8 #define ll long long
 9 using namespace std;
10 const int MAXN = 105;
11  
12 ll n,k;
13 char s[110];
14 ll dp[MAXN][MAXN];
15 int vis[28];
16 int main()
17 {
18     scanf("%lld%lld",&n,&k);
19     scanf("%s",s+1);
20     dp[0][0]=1;
21     for(int i=1;i<=n;i++)
22     {
23         int alp=s[i]-'a';
24         dp[i][0]=1;
25         for(int j=1;j<=i;j++)
26         {
27             dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
28             if(vis[alp])
29             {
30                 dp[i][j]-=dp[vis[alp]-1][j-1];
31             }
32             dp[i][j]=min(dp[i][j],k);
33         }
34         vis[alp]=i;
35     }
36     ll cost=0;
37     for(int i=n;i>=0;i--)
38     {
39         cost+=min(dp[n][i],k)*(n-i);
40         k-=min(dp[n][i],k);
41         if(k==0) break;
42     }
43     if(k>0) printf("-1\n");
44     else printf("%lld\n",cost);
45     return 0;
46 }
47
Ackerman