A：历史上的今天（history）

题目

小 P 是一个普通的高中生。自从进入高中以来，作业一天比一天多，每天都要熬夜赶作业。
而今天，他还需要多做一件事情——为明天历史课准备上课前三分钟的《历史上的今天》演讲稿。
小 P 十分喜欢研究历史，他的电脑里存了个他最喜欢的历史事件，每个历史事件都由年,月,日以及事件名称构成。由于小 P 整理资料时有一些混乱，所以历史事件中可能有未来（当前时间点并没有发生过）的事件。
现在，为了准备演讲稿，小 P 急需知道有多少历史事件发生在历史上的明天。然而他喜欢的历史事件实在是太多了，以至于难以查找。你能够帮助他吗?

一个事件发生在历史上的当天，当且仅当该事件发生在当天或当天之前，且除年份以外，月份和天数在数值上都相同。你需要按照时间顺序从小到大输出这些历史事件的名称。数据保证不存在发生在同一天的两个历史事件,但可能存在两个事件名称相同。

输入格式
第一行一个字符串 date0，表示今天的日期。
第二行一个整数 n，表示小 P 喜欢的历史事件的数量。
接下来 n 行，每行两个字符串 datei, namei，分别表示第 i 个历史事件发生的日期，以及该历史事件的名称。
字符串 datei (0 <= i <= n)的格式为 year.month.day 即三个数 year, month, day 分别为年份，月份，天数的数值，中间用.隔开，且保证当前日期一定合法。
为了读入方便，我们规定 year, month, day 的位数分别严格为 4位,2位,2位，不足该位数的用 0 补齐。例如，2019年九月九日表示为2019.09.09,2020年七月二十四日表示为2020.07.24。
字符串namei (1 <= i <= n)保证只由数字(0-9)，小写字母(a-z)，大写字母(A-Z)，以及下划线(_)构成，长度不超过40。

输出格式
第一行一个数字 k(1 <= k <= n) ，表示满足条件的历史事件的数量。
接下来 k 行，每行一个字符串 namei ，表示你认为时间第 i 小的符合上述条件的历史事件的名称。
如果没有任何满足要求的历史事件，输出第一行即可。

样例
样例1
2019.09.09
5
2019.10.07 Double_Ninth_Festival
2020.07.24 The_2020_Tokyo_Olympic_Games
2019.09.10 35th_Teachers_day
2022.02.04 The_2022_Beijing_Olympic_Winter_Games
1985.09.10 Chinese_Teachers_day
样例1
2
Chinese_Teachers_day
35th_Teachers_day
样例2
2019.11.16
7
2017.11.16 Tiw_AK_NOIP2017
2018.11.16 Tiw_AK_NOIP2018_day1
2018.11.17 Tiw_AK_NOIP2018_day2
2019.11.17 Tiw_AK_CSP2019_day2
2019.11.16 Tiw_AK_CSP2019_day1
2020.11.17 Tiw_AK_CSP2020_day2
2020.11.16 Tiw_AK_CSP2020_day1
样例2
2
Tiw_AK_NOIP2018_day2
Tiw_AK_CSP2019_day2
样例3
2024.10.31
20
0401.11.01 history
1539.11.01 history
0259.11.01 history
1955.11.01 history
0663.11.01 history
0372.11.01 history
0270.11.01 history
0047.11.01 history
0465.11.01 history
0036.11.01 history
1188.11.01 history
1367.11.01 history
1142.11.01 history
1820.11.01 history
0058.11.01 history
0153.11.01 history
0557.11.01 history
1959.11.01 history
1074.11.01 history
0152.11.01 history
样例3
20
history
history
history
history
history
history
history
history
history
history
history
history
history
history
history
history
history
history
history
history
数据范围与提示
【样例 1 解释】
只有第 3 个和第 5 个历史事件满足条件。
注意要按照时间顺序从小到大输出,未来的时间点应该直接忽视掉。
【样例 2 解释】
综上可以得出结论:历史总是惊人的相似。
在这里插入图片描述

题解

这道题完全就是一个纯粹的模拟，
处理出来所有日期是历史上的明天的i，再判断年份是不是已经发生
丢到一个数组里面排序输出就好了

唯一麻烦的就是处理一下明天的特殊性，
比如刚好是二月，刚好是闰年，刚好是一个月的最后一天，刚好是一年的最后一个月…
本来是一道简单的模拟，硬生生掰成了手打if-else
在这里插入图片描述
送你一个小秘籍→

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 10005
struct node {int year, num;
}result[MAXN];
int n, tot, year, month, day;
string opt;
string name[MAXN], date[MAXN];bool run ( int a ) {if ( ( a % 4 == 0 && a % 100 != 0 ) || ( a % 400 == 0 && a % 3200 != 0 ) )return 1;return 0; 
}void init () {day ++;if ( month == 2 ) {if ( run ( year ) ) {if ( day == 30 ) {month = 3;day = 1;}}else {if ( day == 29 ) {month = 3;day = 1;}}}else {if ( month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12 ) {if ( day == 32 ) {month ++;day = 1;}}else {if ( day == 31 ) {month ++;day = 1;}}}if ( month == 13 ) {month = 1;year ++;}
}bool cmp ( node x, node y ) {return x.year < y.year;
}int main() {cin >> opt;int len = opt.length();for ( int i = 0;i < len;i ++ ) {if ( i < 4 )year = year * 10 + ( opt[i] - '0' );if ( i >= 5 && i <= 6 )month = month * 10 + ( opt[i] - '0' );if ( i >= 8 && i <= 9 )day = day * 10 + ( opt[i] - '0' );}init ();scanf ( "%d\n", &n );for ( int i = 1;i <= n;i ++ ) {cin >> date[i] >> name[i];int y = 0, m = 0, d = 0;for ( int j = 0;j < len;j ++ ) {if ( j < 4 )y = y * 10 + ( date[i][j] - '0' );if ( j >= 5 && j <= 6 )m = m * 10 + ( date[i][j] - '0' );if ( j >= 8 && j <= 9 )d = d * 10 + ( date[i][j] - '0' );}if ( m == month && d == day && y <= year ) {result[++ tot].year = y;result[tot].num = i;}}sort ( result + 1, result + tot + 1, cmp );printf ( "%d\n", tot );for ( int i = 1;i <= tot;i ++ )cout << name[result[i].num] << endl;return 0;
}

B：勇者斗恶龙（dragon）

题目描述

现在有一条 n 头龙，生命值为 h，勇士想要打败这条作恶多端的龙。
在这里插入图片描述
勇士攻击第 i 个头会造成 min(h,atki) 点伤害，即龙的生命值减少 min(h,atki) 点；但龙的第 i 个头受到伤害后会恢复 di 点生命值，即生命值增加 di 。勇士无法重复攻击同一个头，即他对于每个头最多只能攻击一次。当龙的生命值为 o 时则视为被勇士打败，此时它不能再恢复生命值了。勇士想要知道他是否能打败这头龙，如果能打败最少需要攻击多少次。

输入格式
第一行包含两个整数 n，h,分别表示龙的头的数量和龙的生命值。
接下来 n 行，每行两个整数atki，di，含义见【题目描述】。
输出格式
第一行输出 Yes 或 No，表示勇士是否能击败恶龙若能击败。
如果能打败，在第二行输出一个整数，表示打败这头龙所需的最小攻击次数。

样例
样例1
3 5
2 3
2 0
1 0
样例1
Yes
3
样例2
3 6
2 3
2 0
1 0
样例2
No
【样例 1 解释】只要最后一次攻击第一个头，就能刚好击败恶龙。
数据范围与提示
在这里插入图片描述

题解

首先这道题很好想的就是贪心
按照atk_i-d_i从大到小排序，这样越靠前的i对巨龙的伤害越高，答案个数也就能越小
做到这就能85分了

然后就去枚举最后一击，那么如果打其他头造成的攻击力为atk_i-d_i
因为其他攻击都打不死它，
在这里插入图片描述
这里就可以找到一种贪心策略
首先将所有头按照atk_i-d_i从大到小排序，
然后每次固定一个头后找出至少需要前面多少个头atki-di之和相加大于h-atkx，x是你选中的最后一击,
时间复杂度n²

这样肯定是TLE，于是我们考虑优化，我们可以排序后统计
出atk_i-d_i的前缀和s_i，那么我们只需要针对h-atk_i和s_x-1大小关系分类讨论二分即可，
时间复杂度nlogn

但是这里也只有95
还有你会发现，这个时候处理出来的s数组并不具有单调性
二分很危险！！！
在这里插入图片描述
其实atk_i ≤ d_i的情况是根本不需要的，
它对于答案只会增加恶龙的生命值，我们要把它排除掉，i - -，n - -
这个时候s数组就会具有单调性了

问题又来了，很有可能最后一击atk_x ≤ d_i
但是恶龙在被攻击后就生命值0了，题意说这个时候它无法回血，
这就意味着，这最后一击很有可能在上面被我们自作聪明地排除掉

所以我们就不能i - -，n - -，直接在s数组上动手脚就可以了

解决完这些问题后，注意到一组特判
看好h的数据范围，有可能为0，
这意味着有可能刚一上场，恶龙就被吓得尿尿了
在这里插入图片描述
你的答案就应该是0而不是1

代码实现

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 300005
#define LL long long
#define INF 0x7f7f7f7f
int n, h, result = INF, inter;
LL s[MAXN];struct node {LL atk, d;
}a[MAXN];bool cmp ( node x, node y ) {return x.atk - x.d > y.atk - y.d;
}void solve ( int l, int r, LL val ) {if ( l > r ) return;int mid = ( l + r ) >> 1;if ( s[mid] >= val ) {inter = min ( inter, mid );if ( l == mid ) return;solve ( l, mid, val );}else solve ( mid + 1, r, val );
}int main() {scanf ( "%d %d", &n, &h );for ( int i = 1;i <= n;i ++ )scanf ( "%lld %lld", &a[i].atk, &a[i].d );if ( h == 0 ) return ! printf ( "Yes\n0" );sort ( a + 1, a + n + 1, cmp );for ( int i = 1;i <= n;i ++ )if ( a[i].atk <= a[i].d ) s[i] = s[i - 1];else s[i] = s[i - 1] + a[i].atk - a[i].d;for ( int i = 1;i <= n;i ++ ) { inter = INF;if ( h <= a[i].atk ) return ! printf ( "Yes\n1" );solve ( 1, i - 1, h - a[i].atk );result = min ( result, inter + 1 );}if ( result == INF )printf ( "No" );elseprintf ( "Yes\n%d", result );return 0;
}