正文
题目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的数量来计算符合要求的路线数量。
网友评论