youralmight - 个人主页动态

2019-08-11 14:21

已编辑

1. 思想:  指数循环节-欧拉函数的性质-数论 题目:Graph Games 链接:https://ac.nowcoder.com/acm/contest/883/D 大意:求有多少个(i,j)满足i∈[1,n],j∈[1,m](n∈[1,1e9],m∈[1,1e9]),A(i^j)=0modp(p是质数,p∈[1,1e9]),其中A(x)表示 一个十进制数字，由x个'1'组成 分析:A(i^j)=0(mod p)    (10^(i^j)-1)/9= 0(mod p) 10^(i^j) = 1 mod(9*p) 因为p是质数, 所以若p==2||p==5,10^(i^j)对...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

牛客多校第二场

A:暴力打表找规律 概率问题总是会遇到状态的概率相互依赖的,如:dp[i]=Kj * dp[j]+balabala dp[j]= Ki *dp[i]+balabala 暴力都不好暴力怎么打表? 这次问了蓝心老师这种问题怎么搞，原来说是可以撒点. 撒点？好像有道理，这好像是一种打表找概率的一个不错的方法。特别是在随机决策的时候 https://ac.nowcoder.com/acm/contest/882/A 题目大意:有N个位置[0,N-1]，0和N-1的位置相连形成一个环，玩家初始在0,访问了0, 每次随机前进一步或后退一步，问当玩家访问完了每一个点的时候，最后在M点的概率 ...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

dp-线段树进阶-几何转dp-点集划分

https://ac.nowcoder.com/acm/contest/881/I 大意:给n(1e5)个点给定每个点的x坐标,y坐标,a属性,b属性，求:让你将所有点划分到2个点集A,B(其中一个可以为空) ,划分要求为:不存在点C∈A,点D∈B,xC>=xD&&yC<=yD,划分的权值为A内所有点的a属性和B内所有点的b属性之和 分析: 这他喵?????怎么写?? 一看，完全没有任何思路 直到看到题解:用一条非递减的折线穿过点集,折线下的全部划为B，折线上的点全部划为A，这样的划分肯定是合法的( 猜一猜，好像是这样没错).   然后下面就是一个非...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

dp-缩小维度-限制条件-牛客多校第一场-ABBA

https://ac.nowcoder.com/acm/contest/881/E 题目大意: 让你构造一个字符串(长度2n+2m,全部由'A'和’B'构成),字符串可以拆分为n个"AB"串,m个"BA"串， 问这样的串有多少种. 比赛的时候完全没想到怎么搞，只想到可以用想类似括号序列的方法:每个A代表1,B代表-1, 于是一个AB串就具有一个前缀和 dp[i]代表串的前缀和为i的方法数 没想太明白，其实这样也可以搞，但是要加一维:dp[i][j]代表前缀和为[i]使用了[j]个A的前缀方案数     其实跟题解差不多: 这道题说起...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

贪心-牛客多校第一场

https://ac.nowcoder.com/acm/contest/881/C 貌似只把问题带到了数列上就会变简单一点？？？？ 先把原题读一遍，再看下面的解释   有一个长度为n(1e4)的序列a:每个元素的范围是[1,1e3] 你需要构造一个序列b:b中的每个元素要大于等于0，sum：b[1,n]要等于m 求min    于是，类似于你可以花费b[i]的和来减少某个a[i]的值:如何是的a[i]的平方和最小 方法当然是:每次使用eps个花费,都放在最大的a[i]身上   于是，贪就完了: /////////////////////////////////////...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

单调栈-笛卡尔树-序列-2019牛客多校第一场A

https://ac.nowcoder.com/acm/contest/881/A 题意:给定两个长度为n(1e5)的排列a,b,求最大的m 使a,b的前缀[1,m]的所有子区间的最小值的下标相同 分析:对a,b来说，每个区间都对应着一个确定的下标，相反地，每个下标都对应着一些区间，这些区间 是可以求出来的,利用单调栈求出min(le),max(ri)使 a[le,ri]>=a[i],这样对应的区间就是{[k1,k2]|le<=k1<=i<=k2<=ri} 既然题目说前缀中每个区间对应的下标是要相同地，那么反过来，每个下标对应的m以内的区间要全部相同。 ...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

寻找解题方向-猜系数-配凑法-2019牛客暑假多校第一场

首先给个D神的博客的传送门:https://www.cnblogs.com/Dillonh/p/11209476.html 题目链接:https://ac.nowcoder.com/acm/contest/881/B (背景好评!) 这题呢:我想了想，我里出题还有2点差距: 1.要相信题都是可解的: "这TM不是废话吗，但是我太菜了我不会呀！我我咋知道怎么写"看到这个第一点，不用说是这个想法。 但是我要说的是，由于肯定是可解的，你要知道，一定有某条途径，使得这个本不可求的积分，变成 一个可求的积分，这是什么意思呢？ 想一想，像这种很多项相乘的，在高数里，你会...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

最小树形图-hdu4966

https://vjudge.net/contest/311526#problem/G 大意:给定n(50)门属性，每门属性有a[i](500)个级别,同时有M(2000)门课程,参加j号课程需要c属性达到d ,这样就可以把你的e属性提升成f,同时花费g元钱,问要把属性升满要多少钱 分析:第一眼看到这题，有种网络流的感觉，于是欻欻欻开始写，还好隔壁xmk大佬的提示“你可以试试网络， 流，然后就开始自闭了，这题是最小树形图“，于是就开始写最小树形图，但最小树形图不是所有点都必须可到达吗 但这题可以使属性i达到a[i]，但不一定要经过a[i]-1呀，于是这题我开始迷糊了，感觉像是自己遇到...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

暴力-n*sqrt(n)

https://vjudge.net/contest/311526#problem/B 其实题目很简单，给一个数列a,求每一个元素它左右两边最近的j使a[j]是a[i]的倍数, 怎么说呢,暴力,完了 因为n∈[1,1e5],a[i]∈[1,1e5] 最后这样做复杂度就是n*sqrt(n) 写这篇博客是因为我不够自信，总是觉得这样的复杂度过不了，然而其实是过的了的 说不定我应该更加莽才对

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

Colorful Tree-树形dp-树上连通块-树上路径统计

http://acm.hdu.edu.cn/showproblem.php?pid=6035 题意:有n(2e5)个结点的一棵树，每一个结点上都有一个颜色c[i],设一条路径的value为这天路径上点的颜色 的种类数，求树上所有路径的value和。 分析:树上所有路径，那显而易见是要算贡献的，那怎么算每个颜色/每个点对ans的贡献呢？首先看，要算每个点 对ans的贡献和很难算的,因为路径上还可以有同颜色的别的点呀，并且同颜色的点的个数还是不确定的，你想先算起来 再除也没有办法。于是可以算每个颜色对ans的贡献，因为不知道不包含某个颜色的路径有多少条，但是->->->...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

区间dp-拓扑排序种类数

https://vjudge.net/contest/311202#problem/L 之前在CF上做过类似的题，所以这次就被这种思维带过去了 后来看题解知道这题可以用到区间dp 一个排列，对每个元素给定le[i]和ri[i],表示[le[i],ri[i]]内的元素都大于等于p[i],而le[i]-1和ri[i]+1的元素都小于 p[i] 这有点像之前的CF上的线段树的题，但是可以用到区间dp,因为在区间[le,ri]内最小的元素的两边界就是le[i],ri[i] 然后就可以把一部分的元素丢到左边 得到dp[le,ri]=dp[le,minpos-1]*dp[minpos+1,r...

0 点赞评论收藏

2019-08-11 14:22

已编辑

北京航空航天大学算法工程师

贪心-暴力-CF

https://codeforces.com/contest/1190/problem/C 题目不长 一种思想: 因为可以模仿对手的行为，如果如果之前对手走了一步，自己可以不动 所以如果不是第一走的，那就肯定不会输   所以对于先手者，有几种情况 1.可一步到位，那就直接赢了 2.不可一步到位，这种情况下再看后手者，如果他不可以一步到位，那他肯定不会输，因为他可以模仿，但是无论他怎么做，对手也不会输，对手也可以模仿，所以如果后手者不能一步到位，那肯定会是平手；但如果后手者可以一步到位，那就是后手者赢   可以O(n)看出是不是属于1，剩下是不是后手者赢，其实是也可以Onlog...

0 点赞评论收藏

2019-08-11 14:23

已编辑

北京航空航天大学算法工程师

HDU-6222 2017长春找规律

设t=2*k发现S=t*sqrt(3*k*k-3) 打表,得到数列(前4项为2,4,14,52)，我和cyy找了半天一直找出来，最后当等比数列算的，居然过了 然后写下我对找规律类题目的看法 这类规律有哪些(我现在遇到了哪些) A.多项式:这个应该不用说了，其实大家都很熟悉就是f(n)是关于n的一个多项式，一般这种问题的多项式次数不会超过4,因为次数太高就不好出题了，为了鉴定一个通项公式是一个多项式,可以用多层求差的办法,就是先把就是g(i)=f(i+1)-f(i),h(i)=g(i+1)-g(i),如果是一个多项式,只要次数够多，肯定能找到的 B.指数级:其实这个也不是很难找,今天这...

0 点赞评论收藏

2019-08-11 14:25

已编辑

北京航空航天大学算法工程师

ZOJ-1309-圆的切线

题意:给一个点，多个圆，求多个圆在某条直线上的投影的并 典型的求切线的题目 旋转向量法:求出切线向量在坐标轴中的角A(三角函数求) 再算出切线与中心连线之间的夹角B,两个切线的角就是A+B和A-B 但是呵，几何题 我遇到了如下坑点: 1.用反三角函数求角度，要用asin或者acos，用这两个就能A，用atan就会WA 2.这题最后算结果有两种做法,一种是乘tan，一种是除tan，用乘就会A，用除就会WA 3.不要把PI自己定义成3.1415926,每次都使用acos(-1)就可以了，速度快，精度高 4.不能滥用+eps，什么时候用可以参考https://blog.csdn.n...

0 点赞评论收藏

2019-08-11 14:24

已编辑

北京航空航天大学算法工程师

hdu-4821 String

一道水题，做不出来是我菜了 不熟悉字符串Hash hash主要有两个用处 1.建立字符串到int的映射 2.特异化(确定)一个字符串 本题属于下一种 https://vjudge.net/problem/HDU-4821 写这篇主要是为了让自己记住教训 附：代码 /////////////////////////////////////////Info///////////////////////////////////////////////// //Problem: //Date: //Skill: //Bug: ////////////////////////////...

0 点赞评论收藏

关注他的用户也关注了：