2 Happig丶

尚未进行身份认证

我要认证

我的孤独,虽败犹荣

等级
TA的排名 1w+

2020ICPC·小米 网络选拔赛第一场

比赛链接前言第二场都快打了才补完题目发博客,最近事情真的太多了= =A - Intelligent Warehouse(DP+数论优化)

2020-10-30 09:16:39

HDU - 6514 Monitor(二维差分+二维前缀和)

传送门题目大意给出一个n∗mn*mn∗m的麦田(左下角为(1,1),(1,1),(1,1),右上角(n,m)(n,m)(n,m)),其中有ppp个矩形区域安装了监控,接下来有qqq个贼想偷某个矩形范围内的庄稼,问监控能否拍到贼。解题思路这时一道考验二维差分+二维前缀和的一道非常好的题目。首先我们需要将有监控的区域都置为111,也就是每个监控区域的所有元素都加一,这时不难想到二维差分,有的元素可能被多个监控重复覆盖,那么差分矩阵还原时需要将大于111的元素置为111。然后对还原的矩阵求前缀和,只需

2020-10-29 17:22:11

差分及二维差分

差分差分即相邻两个数的差,给定数组aaa我们能得到其差分数组d[i]=a[i]−a[i−1]d[i]=a[i]-a[i-1]d[i]=a[i]−a[i−1],那么不难得知a[i]=∑j=1id[j]a[i] = \sum_{j=1}^i d[j]a[i]=∑j=1i​d[j]。差分和前缀和的区别前缀和求的是sum[i]=∑j=1ia[j]sum[i] = \sum_{j=1}^i a[j]sum[i]=∑j=1i​a[j],如果使用前缀和表示某个位置的元素,那么a[i]=sum[i]−sum[i−1]

2020-10-29 10:48:02

第十一届蓝桥杯 H - 子串分值和:求字符串所有子串的不同字符个数和(思维/线段树)

题目大意解法一:标答这种解法应该就是标答了吧,在这里学到的,简单精炼而又高效,orz对于一个长度为nnn的字符串,若我们考虑所有子串的个数,可以考虑以下做法:考虑第iii个字符,它和前面字符加起来的长度为xxx,它和后面字符加起来的长度为yyy,那么包含字符iii的所有子串就有x×yx \times yx×y个例如对于字符串abcdabcdabcd,其子串的个数和为1×4+2×3+3×2+4×11 \times 4+ 2 \times 3 + 3 \times 2+4 \times 11×4+2

2020-10-28 19:18:58

Codeforces Raif Round 1 (Div. 1 + Div. 2) E. Carrots for Rabbits(贪心)

传送门题目大意给出nnn个萝卜,现在需要分成长度为正整数的若干个萝卜,定义每个长度为xxx的胡萝卜贡献为x2x^2x2,问最小的贡献是多少。解题思路手玩一下样例,还是不难得出对于一个胡萝卜若需要切成lll份,那么肯定是均摊才能是贡献最小。但是对于多个胡萝卜,并不容易得出每次切哪一根才能得到最优解。实际上无需考虑这一点,因为萝卜不能拼接,也就是如果最后的答案是将某些胡萝卜切成若干份,每份仍然是均摊的。这就启发我们,对于长度为xix_ixi​假设已经切了pip_ipi​刀的胡萝卜,那么考虑所有胡萝卜被

2020-10-26 21:07:24

Codeforces Raif Round 1 (Div. 1 + Div. 2) D. Bouncing Boomerangs(思维+构造)

传送门题目大意给出一个n∗mn*mn∗m的方格,保证每行每列最多只能有两个障碍,现在每列都会射出一个飞镖,飞镖碰到障碍物会向右旋转九十度继续直行,保证最多碰到三次障碍物。现在给出每列出发的飞镖最后弹射的次数,如果答案存在,需要我们还原一个合法含有若干障碍物的表格。解题思路这道题我感觉有以下两个难想的地方:首先是不能从左向右构造而需要从右向左构造,原因是弹射两次的飞镖,肯定需要右边弹射一次飞镖的列作为最后一次弹射,弹射三次的飞镖既可以利用右边弹射一次的列而且可以利用右边弹射两次及以上的列。而且

2020-10-26 20:48:30

HDU - 5950 Recursive sequence(非常规矩阵快速幂)

传送门题目大意给出一个如下的递推式,给出前两项求第nnn项:f(n)=f(n−1)+2f(n−2)+n4f(n)=f(n-1)+2f(n-2)+n^4f(n)=f(n−1)+2f(n−2)+n4解题思路对于n4n^4n4,实际上和f(n)f(n)f(n)并不是递推关系,一开始想的是将n4n^4n4和前面部分拆开来求,但是这样是错误的,不能拆开,因此考虑以下思路:n4=[(n−1)+1)4]=C40(n−1)4+C41(n−1)3+C42(n−1)2+C41(n−1)+1n^4=[(n-1)+1

2020-10-26 08:27:34

2018 ICPC 沈阳 Best ACMer Solves the Hardest Problem(暴力)

传送门题目大意在二维平面给出nnn个点,每个点都有一个权值,且横纵坐标是正整数且范围均是[1,6000][1,6000][1,6000],现在有四种操作:插入一个不存在的点删除一个已经存在的点输入一个点和长度kkk,权值www,距离该点欧几里得距离为k\sqrt{k}k​的所有点的权值都增加kkk输入一个点和长度kkk,求出距离该点欧几里得距离为k\sqrt{k}k​的所有点的权值和解题思路不难发现,该题的坐标范围很小,时间给了12s12s12s而且内存给的很大1024M1024M10

2020-10-25 19:47:22

Codeforces Round #677 (Div. 3) F. Zero Remainder Sum(dp好题)

传送门题目大意给出一个n∗mn*mn∗m的矩阵,每行最多选出⌊m2⌋\lfloor \frac{m}{2} \rfloor⌊2m​⌋个数(可以不选视贡献为零),给定kkk,问从矩阵中选出若干个数使其和为kkk的倍数,并输出最大结果。解题思路典型的类背包dpdpdp,常见的是序列的每个数选或者不选,然后同余转移。但是本题是一个加强版,也是考验dpdpdp功底的题目,因为范围很小,开一个范围内的四位数组绰绰有余,我们设d(i,j,cnt,res)d(i,j,cnt,res)d(i,j,cnt,res

2020-10-24 22:10:22

LightOJ - 1138 Trailing Zeroes (III)(n的阶乘结尾0的个数+二分)

传送门题目大意给出qqq,我们需要求出最小的nnn使得n!n!n!结尾有qqq个000题目大意考虑nnn的阶乘结尾000的个数,实际上就是看最后乘了多少个101010,也就是将n!n!n!质因数分解得出的2x5y2^x5^y2x5y,结尾000的个数就是min{x,y}min\{x,y\}min{x,y},手推前几个阶乘,不难发现x>yx >yx>y一定成立,因此我们只需考虑555的个数。对于n!n!n!内含有多少质数的乘积,这是一个比较巧妙的数论知识:首先看第一层,也就是只

2020-10-23 09:16:04

LightOJ - 1213 Fantasy of a Summation(找规律)

传送门题目大意给定长度为nnn的数组aaa,下面循环的深度为kkk,求sumsumsum:int n, sum = 0;int a[maxn];ll solve(){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { ... sum +=

2020-10-23 08:47:03

LightOJ - 1234 Harmonic Number(调和级数/分块打表)

传送门题目大意求f(n)=∑i=1n1if(n)=\sum_{i=1}^n \frac{1}{i}f(n)=∑i=1n​i1​解题思路方法一看到这个东西异常熟悉,不就是高数讲过的调和级数吗,但是忘记通项公式是什么了,去百度,有的地方说函数的极限是f(n)=ln(n+1)+γf(n)=ln(n+1)+ \gammaf(n)=ln(n+1)+γ,但是实际上这个是不精确的,正确的极限应该是ln(n)+γ+12nln(n)+ \gamma + \frac{1}{2n}ln(n)+γ+2n1​,测试时在1

2020-10-21 17:28:21

LightOJ - 1236 Pairs Forming LCM(质因数分解找规律+容斥)

传送门题目大意求∑i=1n∑j=in[lcm(i,j)==n],n≤1e14\sum_{i=1}^{n}\sum_{j=i}^{n}[lcm(i,j)==n],n\leq 1e^{14}∑i=1n​∑j=in​[lcm(i,j)==n],n≤1e14解题思路一开始以为是莫比乌斯反演,推了一下发现推不动了。尝试找下规律,对nnn质因数分解n=p1a1p2a2...pnann=p_1^{ a_1}p_2^{ a_2}...p_n^{ a_n}n=p1a1​​p2a2​​...pnan​​,然后考虑lc

2020-10-21 14:23:05

LightOJ - 1282 Leading and Trailing(求幂结果的前k位和后k位)

传送门题目大意求nk(n<231,k≤1e7)n^k(n < 2^{31},k \leq 1e7)nk(n<231,k≤1e7)的前333位和后333位解题思路对于后三位来说,只需要快速幂然后对100010001000取模,但是这个前三位怎么求我怎么也想不出来,后来看了题解才恍然大悟:nkn^knk用科学计数法表示为nk=a∗10bn^k = a*10^bnk=a∗10b,其中aaa是小数,将两边取对数,这样可以得到 klog10n=b+log10a~klog_{10

2020-10-20 21:20:14

LightOJ - 1336 Sigma Function(规律+数学思维)

传送门题目大意给出一个数nnn,设其唯一分解式为n=p1e1p2e2..pnenn=p_1^{e_1}p_2^{e2}..p_n^{e_n}n=p1e1​​p2e2​..pnen​​,给出σ(n)\sigma(n)σ(n)定义:σ(n)=p1e1−1−1p1−1∗p2e2+1−1p2−1∗...∗pnen+1−1pn−1\sigma(n)=\frac{p_1^{e_1-1}-1}{p_1-1}*\frac{p_2^{e_2+1}-1}{p_2-1}*...*\frac{p_n^{e_n+1}-1}{

2020-10-20 16:35:41

51Nod - 1165 整边直角三角形的数量(两种解法:本原直角三角形/求解方程的解数)

传送门题目大意给出直角三角形的周长nnn,求出有多少个不同的直角三角形满足a+b+c=na+b+c=na+b+c=n,且三边长均为整数。思路一关于本原直角三角形可以戳这里,不多解释了直接上代码(顺便吐槽一波这题内存怎么卡这么紧)//// Created by Happig on 2020/10/18//#include <bits/stdc++.h>#include <unordered_map>#include <unordered_set>u

2020-10-19 17:55:51

HDU - 1299 Diophantus of Alexandria(因数分解求方程整数解的个数)

传送门题目大意给定nnn,求出1x+1y=1n\frac{1}{x}+\frac{1}{y}=\frac{1}{n}x1​+y1​=n1​的正整数解的个数解题思路一开始我以为x,yx,yx,y其中有一个一定是nnn的倍数,但是后来才发现如果这样的话答案应该就是nnn的因子个数,但是第二个并不是这样的。又从其他地方下手找找,然鹅也没有找到正确解法正解是:不难发现x,yx,yx,y均大于nnn且一定有一个较大者。设x≤yx \leq yx≤y,令y=n+ky=n+ky=n+k,代入得到x=n2k+n

2020-10-19 17:35:05

本原直角三角形及应用

本原直角三角形本原直角三角形是指三边长均为整数且两两互素的直角三角形所有的直角三角形的三边长一定是某个本原直角三角形的对应倍数定义一对于互质的一对奇偶性相异的数m,n(m>n>0)m,n(m>n>0)m,n(m>n>0),得到唯一一组本原直角三角形,其三边长度分别为a=m2−n2,b=2nm,c=m∗m+n∗na=m^2-n^2,b=2nm,c=m*m+n*na=m2−n2,b=2nm,c=m∗m+n∗n定义二对于任意互质奇数p,q(p>q>0)p

2020-10-19 14:24:53

2020CCPC秦皇岛赛后总结

第一次打现场赛(虽然不能去现场),打铁了早上过去的有点晚,大概八点半过去了,上楼跑了两次拿东西。本以为东西都准备的差不多了,八点四十左右教练突然提醒准备证件,我们三人一头雾水,队友L的证件都在宿舍(不知所措中),我的学生证在楼上,匆匆跑去拿学生证。队友W在打印板子(没有提前准备好)。当我搞完所有事坐下时,已经八点五十多了,我们还没有开电脑?!匆匆打开电脑,然后加入监考系统,这时又出现的小岔子,搞得我很烦。八点五十九,队友W的板子终于打好了,教练打印题册还没回来。发现忘记开录屏了,接着又花几十秒看了操作手册

2020-10-18 22:47:13

Pohlig-Hellman算法

问题引入求ax≡b(mod  p),p≤1018a^x \equiv b(mod~~p),p\leq10^{18}ax≡b(mod  p),p≤1018的最小正整数解模板namespace PhoRho { //Phollard-Rho ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a % b); } ll fastpow(ll x, l

2020-10-14 17:51:56

查看更多

勋章 我的勋章
  • GitHub
    GitHub
    绑定GitHub第三方账户获取
  • 签到王者
    签到王者
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 1024勋章
    1024勋章
    #1024程序员节#活动勋章,当日发布原创博客即可获得
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 学习力
    学习力
    《原力计划【第二季】》第一期主题勋章 ,第一期活动已经结束啦,小伙伴们可以去参加第二期打卡挑战活动获取更多勋章哦。
  • 原力新人
    原力新人
    在《原力计划【第二季】》打卡挑战活动中,成功参与本活动并发布一篇原创文章的博主,即可获得此勋章。
  • 分享达人
    分享达人
    成功上传6个资源即可获取