牛客编程巅峰赛S2第6场
A-StringⅡ
题目
题目描述
给出一个仅包含小写字母的字符串s，你最多可以操作k次，使得任意一个小写字母变为与其相邻的小写字母（ASCII码差值的绝对值为1），请你求出可能的最长相等子序列（即求这个字符串修改至多k次后的的一个最长子序列，且需要保证这个子序列中每个字母相等）。
子序列：从原字符串中取任意多个字母按照先后顺序构成的新的字符串。
示例1
输入
2,"abcde"
返回值
3
示例2
输入
10,"acesxd"
返回值
4
备注:
数据满足：(1leq |s|leq 2^{10}, 1leq k leq3000)，其中(|s|)表示字符串的长度。
思路
找到所有字符串中所有字符到每个字母的距离，排序。
找每个字母所能得到的最大长度。
代码
class Solution {
public:
/**
*
* @param k int整型 表示最多的操作次数
* @param s string字符串 表示一个仅包含小写字母的字符串
* @return int整型
*/
int string2(int k, string s) {
// write code here
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);
}
//cout << sums << " " << p << endl;
//if(p == n) return n;
}
return ans;
}
};
B-Bang Bang
题目
题目描述
音游狂热爱好者牛牛接到了一个新的任务，那就是给一张乐谱设计重音符。每当玩家敲击重音符的时候就会发出"bang"的美妙声音!!
每一张乐谱都有(n)个音符从左到右一字排开，现在牛牛的任务就是选出其中(m)个音符将其标记为重音符，同时任意两个重音符之间都必须隔着至少(k)k个音符。
一个有意思的问题诞生了，请求出这样合法的设计方案种数，并输出答案对(1000000007)取模的结果。
示例1
输入
3,2,1
返回值
1
备注:
数据范围 (3≤n≤1000，m(0≤m≤n)，k(0≤k≤n))
思路
动态规划
一个位置只有两种可能：放重音符和不放重音符。
那么用(dp[i][j])代表前(j)个字符中放了(i)个重音符可能的情况总数。
代码
const int mod = 1e9+7;
#define ll long long
class Solution {
public:
/**
*
* @param n int整型 乐谱总音符数
* @param m int整型 重音符数
* @param k int整型 重音符之间至少的间隔
* @return long长整型
*/
long long solve_bangbang(int n, int m, int k) {
// write code here
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-天花板
题目
题目描述
牛牛想知道(sum_{i=1}^n left lceil frac{n}{i} ight ceil)的值是多少(式子中(left lceil frac{n}{i} ight ceil)表示向上取整)，现在牛牛给你(mathit n)，请你告诉牛牛和是多少。
示例1
输入
10
返回值
33
备注:
(1leq nleq 10^9)
思路
比赛中一直在oeis中找公式，害，大意了啊
分块
模拟一遍样例：
1 2 3 4 5 6 7 8 9 10
10 5 4 3 2 2 2 2 2 1
可以得到(left lceil frac{n}{i} ight ceil)的值在一段区间里是不变的，那么只要找到区间的左右端点就行了。
左端点是很容易得到的。
右端点计算方法如下：
- 二分查找右边界
- 直接计算右边界
统计即为答案。
代码
#define ll long long
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型
* @return long长整型
*/
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;
}
/*
** 1 2 3 4 5 6 7 8 9 10
** 10 5 4 3 2 2 2 2 2 1
*/
long long Sum(int n) {
// write code here
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);
// j = find(n, i);
sums += ceil(1.0 * n / i) * (j-i+1);
}
return sums;
}
};