程序员进阶之算法练习（五十五）
正文
题目1
题目链接 题目大意： 小明有一只猫，现在猫的饥饿值为H，并且每分钟会增加D； 他可以选择现在就买猫粮，1份猫粮价格为C，可以减少猫的饥饿值N；（猫粮只能一份一份购买） 他也可以选择晚上20点之后购买，商店会打8折；（当前的时间为hh时mm分） 问，小明最少需要花费多少，才能把猫的饥饿值降到0；
输入： 第一行，hh and mm (00 ≤ hh ≤ 23, 00 ≤ mm ≤ 59) 第二行，H, D, C and N (1 ≤ H ≤ 1e5, 1 ≤ D, C, N ≤ 1e2). 输出： 小明最少的花费，精确到小数点4位。
Examples input 19 00 255 1 100 1 output 25200.0000
题目解析： 从题目已经给出的条件我们可以判断，在没打折的时候，花费是(H+N-1)/N*C； 如果有打折，就要加上猫增加的饥饿值。 那么，我们容易得到一种方法：用max(0LL, 20 * 60 - hh * 60 - mm) * d计算猫增加的饥饿值，再统一计算价格； 再从cost1、cost2中选择一个较小值即可。
思考： 题目有个小trick，打折后的数字是浮点数。
int main(int argc, const char * argv[]) {
// insert code here...
lld hh, mm;
lld h, d, c, n;
cin >> hh >> mm;
cin >> h >> d >> c >> n;
lld cost1 = (h + n - 1) / n * c;
double cost2 = (max(0LL, 20 * 60 - hh * 60 - mm) * d + h + n - 1) / n * c * 0.8;
cout << min((double)cost1, cost2) << endl;
return 0;
}题目2
题目链接 题目大意： 我们认为一个字符串是好看，如果它满足： 1、由两种字符组成； 2、调整字符的顺序，可以使得相同字符是连续的； 比如说：ab、aba、abb、aaabbbb这样的字符是好看的，但abc、aa这样的字符是不好看的； 现在给出字符串s，问能否把s分成两个子序列，使得子序列都可以组成好看的字符串；
输入： 第一行，字符串s (1 ≤ |s| ≤ 1e5) 输出： 如果可以，输出Yes；否则输出No；
Examples input ababa output Yes input yeee output No
题目解析： 好看的字符串，其实就是要求字符串有且只有两种字符串。 题目的意思是把字符串s分成两个字符串，并且每个都有两种字符。 那么先统计字符串s中各个字符的数量，得到字符种数num，如果： num>4，无解； num=4，有解，直接分为2+2； num=3，必须有一个字符的数量>=2； num=2，两个字符数量都满足>=2； num=1，无解；
思考：
用a[i]表示字符串i的数量，然后对a进行从大到小的排序，可以简洁写完上面的判断
if ((count == 4) || (count == 3 && a[0] >= 2) || (count == 2 && a[1] >= 2)) cout << "Yes" << endl;
char str[N];
int a[N];
bool cmp(int a, int b) {
return a > b;
}
int main(int argc, const char * argv[]) {
// insert code here...
cin >> str;
long n = strlen(str);
int count = 0;
for (int i = 0; i < n; ++i) {
if (a[str[i] - 'a'] == 0) ++count;
a[str[i] - 'a']++;
}
sort(a, a + 26, cmp);
if ((count == 4) || (count == 3 && a[0] >= 2) || (count == 2 && a[1] >= 2)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}题目3
题目链接 题目大意： 小明邀请了n个朋友过来吃披萨，披萨只有一个且是圆形的； 现在需要把披萨分成形状完全相同的n+1块，问需要至少切多少刀？
输入： 第一行：n，表示朋友人数 ( 0 ≤ n ≤ 1e18 ) 输出： 至少需要切多少刀。
Examples input 3 output 2 样例解释： 两刀垂直切，得到4块。
题目解析： 由题目意思知道，一个圆切分成n+1块，那么每个扇形的弧度是2π/(n+1)； 那么按照这个弧度平分，不过圆心的切，(n+1)刀必定可以平分；
有另外一种情况，是过圆心切，比如样例的情况，两刀可以切成4块。 在这种切法情况下，切线经过的扇形，分成两部分。
即是说： 如果是分成奇数块，那么不能用过圆心的切法（因为每次都是切成偶数块）； 如果是分成偶数块，那么可以只用过圆心的切法；
于是有： (n+1)是奇数，ans=(n+1); (n+1)是偶数，ans=(n+1)/2;
思考： trick1：n很大，如果用int会爆； trick2：n=0的时候，ans=0；
int main(int argc, const char * argv[]) {
// insert code here...
lld n;
cin >> n;
if (n == 0) {
cout << 0 << endl;
return 0;
}
++n;
if (n % 2) {
cout << n << endl;
}
else {
cout << n / 2 << endl;
}
return 0;
}题目4
题目链接 题目大意： "Kuro", "Shiro" ， "Katie"三个人在玩游戏； 每个人一个字符串，长度相同； 游戏有n轮，每轮每个人都必须修改其中一个字符为其他任意字符； 字符串中的任意子串subStr，在字符串重复出现的次数，就是每个人的得分。 问游戏结束后，谁的分数最高；
输入： 第一行：n，游戏轮数 ( 0 ≤ n ≤ 1e9 ) 接下来3行字符串，分别表示"Kuro", "Shiro" ， "Katie"的字符串； 输出： 输出最高分的人，"Kuro", "Shiro" ， "Katie"； 如果有两个最高分，则输出'Draw'；
Examples input 3 Kuroo Shiro Katie output Kuro
题目解析： 任意子串的最大重复次数，其实就是某个字符的最大出现次数，因为： 如果ab是最大重复次数的子串，那么a出现的次数不会比ab少；
那么游戏转换为对字符串进行最多n次操作，使得某个字符出现最大次数。 容易知道，假如已经出现字符次数最大的字符是x，那么相当于把非x的字符改成x。 那么有sum=min(len, count+n)； sum是字符串的最大重复子串出现次数，len是字符串长度，count是相同字符出现最大次数； 接着分别判断三个人的得分即可。
思考： trick：字符串是全部相同的字符，且n=1的时候！ 此时最多是len-1
int main(int argc, const char * argv[]) {
// insert code here...
int n;
cin >> n;
string str[3];
cin >> str[0] >> str[1] >> str[2];
int sum[3];
for (int i = 0; i < 3; ++i) {
sum[i] = 0;
int count[1000]={0};
for (int j = 0; j < str[i].length(); ++j) {
count[str[i][j]]++;
sum[i] = max(sum[i], count[str[i][j]]);
}
if (sum[i] == str[i].length() && n == 1) {
sum[i] = str[i].length() - 1;
}
else {
sum[i] = min((int)str[i].length(), sum[i] + n);
}
}
int totalMax = max(sum[0], max(sum[1], sum[2]));
int size = 0, ans = 0;
for (int i = 0; i < 3; ++i) {
if (sum[i] == totalMax) {
++size;
ans = i;
}
}
if (size > 1) {
cout << "Draw" << endl;
}
else {
if (ans == 0) {
cout << "Kuro" << endl;
}
else if (ans == 1) {
cout << "Shiro" << endl;
}
else {
cout << "Katie" << endl;
}
}
return 0;
}题目5
题目链接 题目大意： Kuro生活在一个有n个小镇的国家，n个小镇由n-1条路相连，任意两个小镇都可以通过这些路相通。 n个小镇里面有两个特殊的小镇a和b，小镇a养了很多花，小镇b养了很多蜜蜂； 如果先经过小镇a，再经过小镇b，就会在小镇b吸引到很多蜜蜂，造成很严重的后果。 Kuro想定一条旅游路线（u，v）从小镇u到小镇v，每个小镇只能经过一次；（但不能先经过小镇a，再经过小镇b） 问，有多少条可能的路线？（u到v和v到u是不同的路线）
输入： 第一行：n , x and y，表示小镇数量和小镇a、b ( 1 ≤ n ≤ 3 * 1e5 , 1 ≤ x , y ≤ n , x ≠ y ) 接下来n-1行，每行两个数字u，v 表明u和v之间存在相通。
输出： 可能的路线数量。
Examples input 3 1 3 1 2 2 3 output 5
题目解析： 如果不考虑小镇a、b的影响，那么有n*(n-1)的路线；（因为题目给出来的是一棵树，并且小镇不能重复经过） 那么先经过小镇a，再经过小镇b的路线有哪些呢？ 小镇a到小镇b的路只有一条，这一条路把n个小镇分成两部分，小镇a部分（假设数量是sumA) 和 小镇b部分（假设数量是sumB）。 那么先经过a再经过b的路线有sumA*sumB。 那么ans=n*(n-1)-sumA*sumB。
vector<lld> g[N];
int vis[N];
lld cnt[N];
lld dfs(lld u) {
vis[u] = 1;
lld sum = 1;
for (int i = 0; i < g[u].size(); ++i) {
lld v = g[u][i];
if (!vis[v]) {
sum += dfs(v);
}
}
return cnt[u] = sum;
}
int main(int argc, const char * argv[]) {
// insert code here...
lld n, x, y;
cin >> n >> x >> y;
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
lld ans = n * 1LL * (n - 1);
vis[x] = 1;
for (int i = 0; i < g[x].size(); ++i) {
lld v = g[x][i];
dfs(v);
if (vis[y]) { // 这个子树包括y
lld sumA = n - cnt[v];
lld sumB = cnt[y];
ans -= sumA * sumB;
break;
}
}
cout << ans << endl;
return 0;
}总结
题目1，模拟题，注意到题目的隐藏条件，当时间延后的时候会增加饥饿值； 题目2，分类讨论，根据字符串中字符种数，再根据不同情况进行处理； 题目3，思考题，根据题目给出了重要线索“形状完全相同”和圆的特性，推演出来每一块的形状，自然可以根据奇、偶数量进行分类讨论； 题目4，模拟题，要特别注意trick，就是当n=1并且字符完全相同时；（这种也是不太喜欢的题目，容易踩坑） 题目5，逆向思考，题目看似很复杂，但是有一个隐含条件“任意两点之间只有一条路线”，这是由题目给出的条件退出来的，当我们发现求经过a再经过b的数量更好算时，就可以通过总数减去a经过b的数量来计算符合要求的路线数量。
腾讯云开发者
