Rikkar - 个人主页动态 - 牛客网

发布(209) 评论刷题收藏

2021-12-18 16:05

苏州大学 Java

D. Domino for Young （黑白染色）

题目 运用黑白染色，求出的最少颜色的棋子就是答案。因为当把棋盘用黑和白染色后，每放一个格子必然会占掉黑格和白格各一个，看能最多占掉多少个相邻的黑白格。 Code: #include<iostream> using namespace std; typedef long long ll; int main() {  int t;cin >> t; ll f = 1, h = 0, b = 0; while (t--) {  int n;cin >> n; if (t%2==1) {  h += (n + 1) / 2; b += n / 2; } else {...

0 点赞评论收藏

分享

2021-12-18 16:04

苏州大学 Java

C. Division （质因数分解）

题目 思路：首先如果a%b!=0,那答案直接为a。如果a%b==0，我们只需给a除以一个最小的数让a%b!=0即可。 将a b质因数分解 a=a1^n1 * a2^n2 * a3^n3 * a4^n4 …an^nn b=b1^n1 * b2^n2 * b3^n3 * b4^n4 …bn^nn 可知当a不包含b全部的质因数组成即可使a%b!=0，即假设a1=b1,那么a的n1=b的n1-1可满足条件，只需将b的所有质因数求出，将a相应得质因数变为组成b得该质因数次方-1即可，然后比较得出除以的那个最小的数，用a除以即为答案。 #include<iostream> #include&l...

0 点赞评论收藏

分享

2021-12-18 16:04

已编辑

苏州大学 Java

D. Divide and Sum (组合数、思维)

添加链接描述 对于任意分组可以发现其实差值是一样的，将绝对值拆开，会发现都是后面n个大的-前面n的小的。 看例子 a1 a2 a3 a4 a5 b1 b2 b3 b4 b5 （已按大小排序） 假设对于第一组 取了前面3个，后面2个，然后其从很小到大排序，后面一组只可能是取前面2个，后面3个，从大到小排序。那么对于第一组的前3个（顺序）与后面一组的前3个（逆序），必然是第一组的前三个都是a，后面一组的前三个都是b,然后对于第一组后两个，和后一组后两个，第一组后两个必然是b,后一组后两个必然是a。将绝对值去掉一组的差值就等于b1+b2+b3+b4+b5-a1-a2-a3-a4-a5，所有情况都是如...

0 点赞评论收藏

分享

2021-12-18 16:04

苏州大学 Java

D. Santa‘s Bot (概率、逆元)

题目 首先每个礼物被抽到的概率不是均等的，是先从n个人里等概率选出一个人，再从k个礼物等概率选出一个礼物，第1个人每个礼物选中概率1/(nk1) 第二人 1/(nk2)。对于一个礼物c产生的贡献= (1/(nki))【其被选中的概率】(num[c]/n)【正确给到孩子的概率】，需要先记录出每个礼物对应几个孩子，即该礼物的数量。把分母用逆元算即可。 Code: #include<iostream> #include<algorithm> #include<cmath> #include<iomanip> #include<map> #i...

0 点赞评论收藏

分享

2021-12-18 16:03

苏州大学 Java

B. Verse For Santa (模拟、细节)

题目 当能直接唱完就输出0。 当不能时从开始遍历相加直到sum>s,取前面最大值的那个下标，因为减去最大才更有利于后面唱的片段最多。 但要注意下范围：跳过片段该遍历到哪？跳过之后若想能比不跳过多，则需至少到达s+2（无跳过时s是最大不超出的片段数），因为跳过一个则需到s+1才和原来的片段相等，要大于需s+2。所以我们要找到从1—s+1中的最大数下标。 Code: #include<iostream> #include<algorithm> #include<cmath> #include<iomanip> #include<map&g...

0 点赞评论收藏

分享

2021-12-18 16:03

苏州大学 Java

B - Catch Overflow! (范围处理)

题目 很容易想到用堆处理，但会有操作使得数值远大于long long.此时灵活将范围缩小，细节见代码。 #include<iostream> #include<stack> using namespace std; typedef long long ll; const ll Max = pow(2, 32) - 1; stack<ll> sta; int main() {  ll a = 0; int t;cin >> t; ll sum = 1; ll ans = 0; int f = 0; sta.push(1); while (t--) ...

0 点赞评论收藏

分享

2021-12-18 16:03

苏州大学 Java

A. Deadline （不等式、分块整除）

题目 分块整除⌈x+d/（x+1）⌉=⌊x+(d+x)/(x+1)⌋=1+⌊x+(d−1)/(x+1)⌋ Code: #include<iostream> #include<cmath> using namespace std; typedef long long ll; const int Max = 1e6 + 5; const int Mod = 1e9 + 7; int main() {  int t;cin >> t; while (t--) {  int n, d;cin >> n >> d; int f = 0; ...

0 点赞评论收藏

分享

2021-12-18 16:02

已编辑

苏州大学 Java

B. Yet Another Meme Problem (math)

题目 a * b+a+b=a * 10^n+b a * b+a=a*10^n b+1=10^n 故b=9 99 999 9999… 都满足情况，答案为a的个数乘1 —B中满足条件的b的数目 #include<iostream> #include<cmath> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll a[Max], b[Max], lst[Max]; int main() {  int t;cin >> t; while (t--) {  ll a, d;ci...

0 点赞评论收藏

分享

2021-12-18 16:02

苏州大学 Java

C. Two Arrays (dp、思维)

题目 a[i][j] 表示前i个数字中第i个数字为j的所有情况的非递减序列的数目 b[i][j] 表示前i个数字中第i个数字为j的所有情况的非递增序列的数目 对于非递减数列aa，和非递增数列bb，只要第一个元素满足aa[1]>=bb[1]整个数列就满足aa中个元素>=bb中对应元素了。那么只需枚举a中第一个元素所有可能与之相对应满足条件的b中第一个元素即可。 另：递增序列第一个数字为j的所有情况=递减序列最后一个数字为j的所有情况 ，递减序列同理 Code #include<iostream> #include<cmath> using namespace ...

0 点赞评论收藏

分享

2021-12-18 16:02

苏州大学 Java

Cable master POJ - 1064 (二分精度)

题目 思路：二分每条绳子的长度，循环100次即可。 判断条件：每一段向下取整求最大可以裁剪的数量，如果所有数量大于等于k则满足l=mid,小于则不满足r=mid。使用流输出还需注意cout规定小数精度后是四舍五入的，但printf是只截取前多少位。 #include<iostream> #include<cmath> #include<iomanip> using namespace std; typedef long long ll; const int Max = 1e6 + 5; double lst[Max]; int n, k; int c(dou...

0 点赞评论收藏

分享

2021-12-18 16:01

已编辑

苏州大学 Java

Aggressive cows POJ - 2456 (二分---最小化最大值)

题目 二分距离 判断条件就是从一开始每发现一个>=d时放一头牛，如果能全部放完l=mid,否r=mid-1,mid=(l+r+1)/2。  #include<iostream> #include<cmath> #include<iomanip> #include<algorithm> using namespace std; typedef long long ll; const int Max = 1e6 + 5; double lst[Max]; int n, m, x; int check(int d) {  int last = 1...

0 点赞评论收藏

分享

2021-12-18 16:01

已编辑

苏州大学 Java

D. TediousLee （找规律、推导）

题目 一层层推导下去很容易发现规律，a[i]=2*a[i-2]+a[i-1]，看下面这张图，标着的序号代表以这个顶点为根的整颗子树所对应的阶次。6由两个4一个5组成，5由两个3一个4组成。那涂色得到的答案不就是上方的公式吗？但答案去是不对的，这还忽略了一个claw树，当达到6阶层时按照如下涂红色的去取会发现还多了一个claw，就是最上面的那个4个点，那么我们现在只要找到什么时候还要给答案加一个claw即可，当我们要求第i阶层时会发现只有当i-1 与 i-2最上面的点都是不取时可以多构成一个claw，然后相应的第i第阶层最上面的点变成取用状态，那我们只需额外去记录前两个的阶层最上面点是空还是不空...

0 点赞评论收藏

分享

2021-12-18 16:01

已编辑

苏州大学 Java

B. Light It Up （前缀和、模拟）

题目 预先做好一个所有偶数与前一个数差值和3以后奇数a[i]和前一个数差值的前缀和b[i]（代表插入数后的情况），然后遍历插入到所有数后面的情况，假设插入到第i个数那么前i个数的贡献用a[i-1]表示，插入中间的贡献用lst[i]-lst[i-1]-1表示，后面的贡献用b[n+2]-b[i]表示，算出最大贡献即可。 Code: #include<iostream> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll a[Max], b[Max], lst[Max]; int main() { ...

0 点赞评论收藏

分享

2021-12-18 16:00

已编辑

苏州大学 Java

C. Covered Points Count (线段问题---差分、排序)

题目 两种解法： 1.用差分思想，l—r所有点加1用map[l]+1,mdp[r+1]-1表示，前缀和即是当前点所对应覆盖线段数。 Code: #include<iostream> #include<stack> #include<map> #include<string> #include<algorithm> using namespace std; typedef long long ll; const int Max = 1e6 + 5; ll a[Max], b[Max]; pair<ll, ll> lst[Ma...

0 点赞评论收藏

分享

2021-12-18 16:00

苏州大学 Java

B. Planet Lapituletti（模拟）

题目 思路：直接暴力从给出的时间一分钟一分钟加到第二天，判断条件为：如果之前时间有3,4,6,7,9直接排除（倒转后改时间无效），如果倒转后时间大于给出的时间范围也无效（倒转中单个数字变化为2->5 5->2 1,0,8不变，再让全部数字倒置一下），如果有满足条件则输出，没有则输出00：00. Code: #include<iostream> #include<cmath> #include<iomanip> #include<algorithm> #include<map> using namespace std; ty...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客网在线编程
牛客网题解
牛客企业服务