牛客编程巅峰赛S2第6场
A-StringⅡ
题目
题目描述
给出一个仅包含小写字母的字符串s,你最多可以操作k次,使得任意一个小写字母变为与其相邻的小写字母(ASCII码差值的绝对值为1),请你求出可能的最长相等子序列(即求这个字符串修改至多k次后的的一个最长子序列,且需要保证这个子序列中每个字母相等)。
子序列:从原字符串中取任意多个字母按照先后顺序构成的新的字符串。
示例1
输入
2,"abcde"
返回值
3
示例2
输入
10,"acesxd"
返回值
4
备注:
数据满足:
1
≤
∣
s
∣
≤
2
10
,
1
≤
k
≤
3000
1\leq |s|\leq 2^{10}, 1\leq k \leq3000
1≤∣s∣≤210,1≤k≤3000,其中
∣
s
∣
|s|
∣s∣表示字符串的长度。
思路
找到所有字符串中所有字符到每个字母的距离,排序。
找每个字母所能得到的最大长度。
代码
class Solution {
public:
int string2(int k, string s) {
sort(s.begin(), s.end());
int n = s.size();
vector<vector<int> > dist(26);
for(int i = 0; i < 26; i++){
for(int j = 0; j < n; j++){
dist[i].push_back(abs(i+'a'-s[j]));
}
}
for(int i = 0; i < 26; i++) sort(dist[i].begin(), dist[i].end());
int ans = 1;
for(int i = 0; i < 26; i++){
int sums = 0, p = 0;
while(p < n){
sums += dist[i][p++];
if(sums > k) break;
ans = max(ans, p);
}
}
return ans;
}
};
B-Bang Bang
题目
题目描述
音游狂热爱好者牛牛接到了一个新的任务,那就是给一张乐谱设计重音符。每当玩家敲击重音符的时候就会发出"bang"的美妙声音!!
每一张乐谱都有
n
n
n个音符从左到右一字排开,现在牛牛的任务就是选出其中
m
m
m个音符将其标记为重音符,同时任意两个重音符之间都必须隔着至少
k
k
kk个音符。
一个有意思的问题诞生了,请求出这样合法的设计方案种数,并输出答案对
1000000007
1000000007
1000000007取模的结果。
示例1
输入
3,2,1
返回值
1
备注:
数据范围
3
≤
n
≤
1000
,
m
(
0
≤
m
≤
n
)
,
k
(
0
≤
k
≤
n
)
3≤n≤1000,m(0≤m≤n),k(0≤k≤n)
3≤n≤1000,m(0≤m≤n),k(0≤k≤n)
思路
动态规划
一个位置只有两种可能:放重音符和不放重音符。
那么用
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]代表前
j
j
j个字符中放了
i
i
i个重音符可能的情况总数。
代码
const int mod = 1e9+7;
#define ll long long
class Solution {
public:
long long solve_bangbang(int n, int m, int k) {
if(m == 0) return 1;
vector<vector<int> > dp(1010, vector<int>(1010, 0));
dp[0][0] = 1;
for(int i = 0; i <= n; i++) dp[1][i] = 1;
for(int i = 2; i <= m; i++){
for(int j = k + 2; j <= n; j++){
dp[i][j] = (dp[i][j-1] + dp[i-1][j-k-1]) % mod;
}
}
long long res = 0;
for(int i = 1; i <= n; i++){
res = (res + dp[m][i]) % mod;
}
return res;
}
};
C-天花板
题目
题目描述
牛牛想知道
∑
i
=
1
n
⌈
n
i
⌉
\sum_{i=1}^n \left \lceil \frac{n}{i} \right \rceil
∑i=1n⌈in⌉的值是多少(式子中
⌈
n
i
⌉
\left \lceil \frac{n}{i} \right \rceil
⌈in⌉表示向上取整),现在牛牛给你
n
\mathit n
n,请你告诉牛牛和是多少。
示例1
输入
10
返回值
33
备注:
1
≤
n
≤
1
0
9
1\leq n\leq 10^9
1≤n≤109
思路
比赛中一直在oeis中找公式,害,大意了啊
分块
模拟一遍样例:
1 2 3 4 5 6 7 8 9 10
10 5 4 3 2 2 2 2 2 1
可以得到
⌈
n
i
⌉
\left \lceil \frac{n}{i} \right \rceil
⌈in⌉的值在一段区间里是不变的,那么只要找到区间的左右端点就行了。
左端点是很容易得到的。
右端点计算方法如下:
统计即为答案。
代码
#define ll long long
class Solution {
public:
ll findr(ll n, ll i){
ll l = i, r = n;
ll ans = l;
while(l <= r){
ll mid = (l+r)/2;
int x = ceil(1.0 * n / i), y = ceil(1.0 * n / mid);
if(x <= y) {
l = mid + 1;
ans = mid;
}
else r = mid - 1;
}
return ans;
}
long long Sum(int n) {
ll sums = 0;
ll j;
for(ll i = 1; i <= n; i = j + 1){
if(i == n) j = n;
else j = (n - 1) / ((n - 1) / i);
sums += ceil(1.0 * n / i) * (j-i+1);
}
return sums;
}
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)