做电影网站,怎么修改wordpress后台地址,网站开发适合什么工作,国外域名注册哪个便宜朋友们我来了#xff0c;好久都没有更新了#xff0c;手实在痒痒#xff0c;不撸两道#xff0c;内心过意不去 文章目录A#xff1a;历史上的今天#xff08;history#xff09;题目题解代码实现B#xff1a; 勇者斗恶龙#xff08;dragon#xff09;题目描述题解代…朋友们我来了好久都没有更新了手实在痒痒不撸两道内心过意不去
文章目录A历史上的今天history题目题解代码实现B 勇者斗恶龙dragon题目描述题解代码实现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 时则视为被勇士打败此时它不能再恢复生命值了。 勇士想要知道他是否能打败这头龙如果能打败最少需要攻击多少次。
输入格式 第一行包含两个整数 nh,分别表示龙的头的数量和龙的生命值。 接下来 n 行每行两个整数atkidi含义见【题目描述】。 输出格式 第一行输出 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 解释】 只要最后一次攻击第一个头就能刚好击败恶龙。 数据范围与提示
题解
首先这道题很好想的就是贪心 按照atki-di从大到小排序这样越靠前的i对巨龙的伤害越高答案个数也就能越小 做到这就能85分了
然后就去枚举最后一击那么如果打其他头造成的攻击力为atki-di 因为其他攻击都打不死它 这里就可以找到一种贪心策略 首先将所有头按照atki-di从大到小排序 然后每次固定一个头后找出至少需要前面多少个头atki-di之和相加大于h-atkxx是你选中的最后一击, 时间复杂度n2
这样肯定是TLE于是我们考虑优化我们可以排序后统计 出atki-di的前缀和si那么我们只需要针对h-atki和sx-1大小关系分类讨论二分即可 时间复杂度nlogn
但是这里也只有95 还有你会发现这个时候处理出来的s数组并不具有单调性 二分很危险 其实atki ≤ di的情况是根本不需要的 它对于答案只会增加恶龙的生命值我们要把它排除掉i - -n - - 这个时候s数组就会具有单调性了
问题又来了很有可能最后一击atkx ≤ di 但是恶龙在被攻击后就生命值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;
}好了今天就先制作这两道吧几天后再完成后面两道 有任何问题欢迎指出也可以给我建议写博客的一些小细节。我们下期再见。。。
