偶尔刷刷题

分类

题解(32)

/ 注册

全部文章（共32篇）

牛客OI周赛11-普及组-B-GameWithNumbers

题目大意：判断2到m有多少个数字是合法的。对于给定的n个数，是合法的；其他数字若是合法，那么必须存在2到n-1的约数，且这些约数都是合法的。暴力求解：从小到大枚举2到m，如果约数都合法，标记该数字合法；如果遇到一个不合法的约数，则不标记合法。需要从小到大确定是否合法，保证用到的约数都是更小的、...

模拟筛法约数筛选法数学枚举时间复杂度

2019-08-23

0 723

牛客OI周赛11-普及组-A多项式

题目大意：给定一个多项式各校的系数和次幂，输出化简后的非零项数目。排序，将次幂相同的排在一起；合并同类型，次幂相同累加系数，非零则统计。（次幂非常大，不能用桶排序；需要哈希或者使用map；排序去重统计更方便。） #include <bits/stdc++.h> using names...

排序空间复杂度统计

2019-08-23

0 729

牛客NOIP暑期七天营-普及组4-D火龙果画

题目大意：输入n个直角三角形，被第i个三角形覆盖，美观度增加，请问所有被覆盖的点中，最大美观度是多少？暴力70分，但不开long long就只有20了。数据很水，开了long long，边加美味度边统计最大值都有70（23行放到16行之后）！暴力做法，不需要多想：对于每个三角形，包含在里面的点全...

差分标记差分模拟时间复杂度思维前缀和几何

2019-08-22

2 964

牛客NOIP暑期七天营-普及组4-C火龙果田

题目大意：n*m矩阵，某些位置已经有一个数字，其他位置如何填，才能使数字之和最大？要求相邻两个数字之差不超过d。要数字之和最大，填的数字越大越好。对于一个空格，到底填多少呢？一时很难确定。对于最小的数字a，周围填的数字越大越好，那就填a+d吧！填下去之后，如果与周围有冲突，那就填不了了： 1、...

堆广搜单调队列贪心思维优先队列

2019-08-22

2 887

牛客NOIP暑期七天营-普及组4-B火龙果图

题目大意：已知一个由立方体搭建的长宽高都不超过n的图像每个位置立方体的数量，输出三视图，看到立方体输出*，否则输出. 正视图：第一列的*数量，取决于第一列的最大立方体数量，第2-n列以此类推。左视图：第一列的*数量，取决于第一行的最大立方体数量，第2-n列于对应的2-n行的最大值相关。俯视图：有...

二维数组模拟字符

2019-08-22

0 829

牛客NOIP暑期七天营-普及组4-A火龙果树

题目大意：一棵树，第一年只有祖先0；每一年，0可以分支出1个1，0可以分支出1个0和1个1，n年后共有多少个结点？ f[i][j]表示第i年数字j的数量： f[i][0] = f[i-1][1]，因为只有1能得到0； f[i][1] = f[i-1][0]+f[i-1][1]，因为0和1都能够得...

预处理状态规律递推

2019-08-22

0 865

牛客NOIP暑期七天营-普及组3-D子段和

题目大意：对于一个永不超过250个数的序列，可以删除末尾数，可以在末尾增加一个数，中途询问是否有一个区间的和等于x，有就输出Yes，否则输出No。判断是否有连续一段的和（区间和）等于m，可以用前缀和+哈希表判断：对于每一个区间，必有起点l和终点r，元素之和为s[r] - s[l-1]，其中s记录...

区间平移二分单调性单调单调递增前缀和 map 哈希

2019-08-21

0 831

牛客NOIP暑期七天营-普及组3-C区间中最多的数

题目大意：给定n个数，q次询问，每次问区间[l, r]直接出现最多的数字是什么？并列的话输出较大数。从数据范围看，O(qn)超时，O(qa)不超时。空间限制128M，开一个100*200000的数组刚好不超时。预处理每种数字出现的前缀和，对于每个循环，分别O(1)求出每种数字的数量，记录最优值...

模拟时间复杂度空间复杂度前缀和

2019-08-21

0 817

牛客NOIP暑期七天营-普及组3-B填数

题目大意：填n个数，对于每个位置，遇到0随便填正整数，遇到1不比前面小，遇到2比前面大，填数之和能不超过m吗？要想数字之和不超过m，那么填的数字尽量小！从左往右，下标从小到大填，任意填必填最小值1，不比前面小就填前面的那个数，比前面大就只大1。细节1：第一个数必填1，虽然数据保证b[1]是0，...

模拟细节贪心

2019-08-21

0 737

牛客NOIP暑期七天营-普及组3-A-X操作

题目大意：一个整数x，每次操作能加1或者减1，m次操作后能变成y吗？（多组数据） m次操作，每次操作必须改变。如果x和y相差超过m，显然不行。如果x变成y后，还剩下偶数次，那么可以每两次变回自己，否则剩下奇数次，无论怎样都变不回自己。注意数据范围，需要开long long。 #include &...

分类讨论思维

2019-08-21

0 799