朋友們我來了，好久都沒有更新了，手實(shí)在癢癢，不擼兩道，內(nèi)心過意不去

文章目錄

• A：歷史上的今天（history）
• • 題目
  • 題解
  • 代碼實(shí)現(xiàn)
• B： 勇者斗惡龍（dragon）
• • 題目描述
  • 題解
  • 代碼實(shí)現(xiàn)

A：歷史上的今天（history）

題目

小 P 是一個(gè)普通的高中生。自從進(jìn)入高中以來，作業(yè)一天比一天多，每天都要熬夜趕作業(yè)。
而今天，他還需要多做一件事情——為明天歷史課準(zhǔn)備上課前三分鐘的《歷史上的今天》演講稿。
小 P 十分喜歡研究歷史，他的電腦里存了 個(gè)他最喜歡的歷史事件，每個(gè)歷史事件都由年,月,日以及事件名稱構(gòu)成。由于小 P 整理資料時(shí)有一些混亂，所以歷史事件中可能有未來（當(dāng)前時(shí)間點(diǎn)并沒有發(fā)生過）的事件。
現(xiàn)在，為了準(zhǔn)備演講稿，小 P 急需知道有多少歷史事件發(fā)生在歷史上的明天。然而他喜歡的歷史事件實(shí)在是太多了，以至于難以查找。 你能夠幫助他嗎?

一個(gè)事件發(fā)生在歷史上的當(dāng)天，當(dāng)且僅當(dāng)該事件發(fā)生在當(dāng)天或當(dāng)天之前，且除年份以外，月份和天數(shù)在數(shù)值上都相同。 你需要按照時(shí)間順序從小到大輸出這些歷史事件的名稱。數(shù)據(jù)保證不存在發(fā)生在同一天的兩個(gè)歷史事件,但可能存在兩個(gè)事件名稱相同。

輸入格式
第一行一個(gè)字符串 date0，表示今天的日期。
第二行一個(gè)整數(shù) n，表示小 P 喜歡的歷史事件的數(shù)量。
接下來 n 行，每行兩個(gè)字符串 datei, namei，分別表示第 i 個(gè)歷史事件發(fā)生的日期，以及該歷史事件的名稱。
字符串 datei (0 <= i <= n)的格式為 year.month.day 即三個(gè)數(shù) year, month, day 分別為年份，月份，天數(shù)的數(shù)值，中間用.隔開，且保證當(dāng)前日期一定合法。
為了讀入方便，我們規(guī)定 year, month, day 的位數(shù)分別嚴(yán)格為 4位,2位,2位，不足該位數(shù)的用 0 補(bǔ)齊。例如，2019年九月九日表示為2019.09.09,2020年七月二十四日表示為2020.07.24。
字符串namei (1 <= i <= n)保證只由數(shù)字(0-9)，小寫字母(a-z)，大寫字母(A-Z)，以及下劃線(_)構(gòu)成，長度不超過40。

輸出格式
第一行一個(gè)數(shù)字 k(1 <= k <= n) ，表示滿足條件的歷史事件的數(shù)量。
接下來 k 行，每行一個(gè)字符串 namei ，表示你認(rèn)為時(shí)間第 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
數(shù)據(jù)范圍與提示
【樣例 1 解釋】
只有第 3 個(gè)和第 5 個(gè)歷史事件滿足條件。
注意要按照時(shí)間順序從小到大輸出,未來的時(shí)間點(diǎn)應(yīng)該直接忽視掉。
【樣例 2 解釋】
綜上可以得出結(jié)論:歷史總是驚人的相似。

題解

這道題完全就是一個(gè)純粹的模擬，
處理出來所有日期是歷史上的明天的i，再判斷年份是不是已經(jīng)發(fā)生
丟到一個(gè)數(shù)組里面排序輸出就好了

唯一麻煩的就是處理一下明天的特殊性，
比如剛好是二月，剛好是閏年，剛好是一個(gè)月的最后一天，剛好是一年的最后一個(gè)月…
本來是一道簡單的模擬，硬生生掰成了手打if-else

送你一個(gè)小秘籍→

代碼實(shí)現(xiàn)

#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）

題目描述

現(xiàn)在有一條 n 頭龍，生命值為 h，勇士想要打敗這條作惡多端的龍。

勇士攻擊第 i 個(gè)頭會(huì)造成 min(h,atki) 點(diǎn)傷害，即龍的生命值減少 min(h,atki) 點(diǎn)；但龍的第 i 個(gè)頭受到傷害后會(huì)恢復(fù) di 點(diǎn)生命值，即生命值增加 di 。 勇士無法重復(fù)攻擊同一個(gè)頭，即他對(duì)于每個(gè)頭最多只能攻擊一次。當(dāng)龍的生命值為 o 時(shí)則視為被勇士打敗，此時(shí)它不能再恢復(fù)生命值了。 勇士想要知道他是否能打敗這頭龍，如果能打敗最少需要攻擊多少次。

輸入格式
第一行包含兩個(gè)整數(shù) n，h,分別表示龍的頭的數(shù)量和龍的生命值。
接下來 n 行，每行兩個(gè)整數(shù)atki，di，含義見【題目描述】。
輸出格式
第一行輸出 Yes 或 No，表示勇士是否能擊敗惡龍若能擊敗。
如果能打敗，在第二行輸出一個(gè)整數(shù)，表示打敗這頭龍所需的最小攻擊次數(shù)。

樣例
樣例1
3 5
2 3
2 0
1 0
樣例1
Yes
3
樣例2
3 6
2 3
2 0
1 0
樣例2
No
【樣例 1 解釋】 只要最后一次攻擊第一個(gè)頭，就能剛好擊敗惡龍。
數(shù)據(jù)范圍與提示

題解

首先這道題很好想的就是貪心
按照atk_i-d_i從大到小排序，這樣越靠前的i對(duì)巨龍的傷害越高，答案個(gè)數(shù)也就能越小
做到這就能85分了

然后就去枚舉最后一擊，那么如果打其他頭造成的攻擊力為atk_i-d_i
因?yàn)槠渌舳即虿凰浪?#xff0c;

這里就可以找到一種貪心策略
首先將所有頭按照atk_i-d_i從大到小排序，
然后每次固定一個(gè)頭后找出至少需要前面多少個(gè)頭atki-di之和相加大于h-atkx，x是你選中的最后一擊,
時(shí)間復(fù)雜度n²

這樣肯定是TLE，于是我們考慮優(yōu)化，我們可以排序后統(tǒng)計(jì)
出atk_i-d_i的前綴和s_i，那么我們只需要針對(duì)h-atk_i和s_x-1大小關(guān)系分類討論二分即可，
時(shí)間復(fù)雜度nlogn

但是這里也只有95
還有你會(huì)發(fā)現(xiàn)，這個(gè)時(shí)候處理出來的s數(shù)組并不具有單調(diào)性
二分很危險(xiǎn)！！！

其實(shí)atk_i ≤ d_i的情況是根本不需要的，
它對(duì)于答案只會(huì)增加惡龍的生命值，我們要把它排除掉，i - -，n - -
這個(gè)時(shí)候s數(shù)組就會(huì)具有單調(diào)性了

問題又來了，很有可能最后一擊atk_x ≤ d_i
但是惡龍?jiān)诒还艉缶蜕?了，題意說這個(gè)時(shí)候它無法回血，
這就意味著，這最后一擊很有可能在上面被我們自作聰明地排除掉

所以我們就不能i - -，n - -，直接在s數(shù)組上動(dòng)手腳就可以了

解決完這些問題后，注意到一組特判
看好h的數(shù)據(jù)范圍，有可能為0，
這意味著有可能剛一上場，惡龍就被嚇得尿尿了

你的答案就應(yīng)該是0而不是1

代碼實(shí)現(xiàn)

#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; }

好了，今天就先制作這兩道吧，幾天后再完成后面兩道
有任何問題歡迎指出，也可以給我建議寫博客的一些小細(xì)節(jié)。我們下期再見。。。

總結(jié)

以上是生活随笔為你收集整理的历史上的今天（history）+ 勇者斗恶龙（dragon）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。