wudaoyunqi / wudaoyunqi.github.io_old Goto Github PK
View Code? Open in Web Editor NEW无聊搞的玩意儿;)
无聊搞的玩意儿;)
题目网址:https://vjudge.net/contest/299252#problem/C 思路啊,寒假训练做过这道题,也是第一次知道唯一分解定理这个东西。大意就是任何一个正整数都可以表示为若干个素数的乘积并且表示方法唯一,例如12=2^23,称之为标准分解式。有几个性质:1、如果N=P1^a1p2^a2…pm^am,那么它的正因数的个数为(1+a1)(1+a2)…(1+am)2、它的全体正
https://wudaoyunqi.com/2019/04/18/USACO-1-4-Dual-Palindromes/
思路和1.3思路一样,这一次只是多增加了判断是否有两个以上的进制表示是回文数字
https://wudaoyunqi.com/2018/10/16/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/#more
树状数组不太熟悉,所以下决心写出个教程来,断断续续花了三天(可太断断续续了),听说OI选手最喜欢写树状数组(线段树)了 前言我们将一个数组a[]树状化,每个节点的值C[i]记录了其叶子节点的权值之和,那么树状数组C[]就维护了这个数组a[]的前缀和S[i]=a[1]+a[2]+…+a[i],树状数组利用了二进制,使其可以在O(logn)时间内对这个数组a[]进行修改和求和(与O(n)比起来效率很高
https://wudaoyunqi.com/2019/05/01/%E6%B5%99%E6%B1%9F%E7%9C%81%E8%B5%9B19th-Thanks_TuSimple/
题目网址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4090 思路首先根据pi的值从小到大排序,同一个pi值按身高从低到高排序,然后线性匹配。
https://wudaoyunqi.com/2019/04/18/NEUOJ-2019-1Monthly-5/
Problem Description给你一个n个数的序列 已知这n个数为1,1/2,1/3….1/n 我们定义一个生成新序列的操作mjfgay: 每次将序列相邻两项相加并且取平均。并将新生成的序列代替原来的序列。 比如 对于序列 1 1/2 1/3 ,经过一次mjfgay操作后,我们可以得到一个新序列 3/4 5/12 显然,经过n-1次之后,这个序列只会剩一个数 每次给你序列的长度n,问经过n
https://wudaoyunqi.com/2019/05/05/NEUOJ-2019-1Monthly-2/
题目地址:https://oj.neu.edu.cn/problem/1460 思路任何一个整数都可以表示为n=p1^a1p2^a2…pn^an,则f(n,0)=a1a2…an,f(n,0)是积性函数(自己手推一下),对于f(x,y)是f(x,y-1)与自身进行狄利克雷卷积得到的结果,所以f(x,y)也是积性函数(这一点没有想通,等之后深挖狄利克雷卷积再填坑),所以f(x,y)也是积性函数。因此,
https://wudaoyunqi.com/2019/05/12/2017SWERC-Frosting-on-the-Cake/
题目网址:https://open.kattis.com/problems/frosting 思路n范围到1e5了,所以暴力不行啦,得把复杂度降低,目测大概O(n)左右。仔细观察每种颜色所处的Ai,Bj的i+j的关系,发现白色块(i%3+j)%3=2,黄色块(i%3+j)%3=0,红色块=1,那么答案就呼之欲出了。复杂度O(3n)。
https://wudaoyunqi.com/2019/05/12/2017SWERC-Ingredients/
题目网址:https://open.kattis.com/problems/ingredients 思路虽说是个拓扑排序,但不是广义上求顺序的,只要求把每一点的cost算出来就行,所以我用了dfs求cost和prestige,求的方法题目已经给出,取最小的cost,cost相同则取prestige最大的那个。求完之后用01背包算出答案。怎么看出是01背包的呢,首先它有要求的最大cost值,然后题目
https://wudaoyunqi.com/2019/05/05/NEUOJ-2019-2Monthly-2/
题目地址:https://oj.neu.edu.cn/problem/1466 思路通过找规律发现,只有素数或者质因子分解形式为两个质数(指数为1)的积的合数不符合题目条件。那么可以先预处理出1e6范围内的符合条件的结果,然后再用lower_bound查找n的位置就行。
https://wudaoyunqi.com/2019/05/05/%E6%B5%99%E6%B1%9F%E7%9C%81%E8%B5%9B19th-Robot-Cleaner-I/
题目地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5981 思路按照题意模拟即可,有三处剪枝,一是获得的字母数>字母总数时剪枝,二是给每个点对应一个哈希坐标,记录这个坐标是否在某几个x值循环(这一点比较难想,很容易t),三是只要处于do nothing状态就break
思路暴力是不能暴力的,此题是求任意区间乘积能否整除给出的一个数,那么我们不妨换个思路,对于一个数我们可以把它进行质因数分解,那么如果一个数可以整除另一个数,那么前者包含后者所有的质因数并且每个质因数个数都不小于后者。这道题先对ai进行质因数分解并记录,比如对于质数2,v[2]={1,2,2,4,4,4}表示第一个数有一个因数2,第二个数有两个,第三个数没有……,那么对于区间[l,r],查询d的一个
思路就是深搜(也是最直接的思路),结构体存每个人的性别,父母id,如果父母id是-1,就记为0(没有人的id是00000),先搜第一个人的祖先,最多搜到第五代就停止,将搜到的id做标记,然后搜第二个人的祖先,如果在第五代之内有第一个人的祖先,那么就输出no这道题和小字辈很相似,都是深搜的题。我遇到了两个坑点,一个是每个人的父母也要标明性别,另一个是输入id,性别的时候,如果是用cin连续输入的话,
https://wudaoyunqi.com/2019/05/01/%E6%B5%99%E6%B1%9F%E7%9C%81%E8%B5%9B19th-Postman/
题目网址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4096 思路首先将坐标分组排序,两边分别计算路径最后相加,比较左边和右边离原点最远的点,这个点就只走一次(最后一次),然后从最远的点开始往原点“跳”,每次跳k个点直到回到原点(如此能保证总路径是最短的)
思路期望就是走这条路的概率*这条路到达的时间,设期望为Ex,则Ex=(a1+a2+…+an+(b1+Ex)+(b2+Ex)+…+(bm+Ex))/(n+m),化简一下就是Ex=(a1+a2+…+an+b1+b2+…+bm)/n.式子的意思为,如果走可以到达终点的n条路的话,选取的概率就是1/(n+m),所花时间就是ai,如果走其他的m条路的话,选取的概率是1/(n+m),所花时间就是bi+Ex.期
前言寒假训练开始了,发现自己真是半灌水响叮当,自己关于割点的概念完全不知道,后来找了几篇不错的博客以及翻了翻白书,白书很适合理解概念,博客给的模板代码适合借鉴。 割点的概念在无向连通图中,如果将其中一个点以及这个点所连的所有的边都去掉,图不再连通,那么这个点成为割点(割顶/关节点)。 如何求割点暴力的方法: 依次删除每一个节点v DFS(BFS)判断是否连通 再把节点v加入图中 若用邻接表,需
十年饮冰,难凉热血。
https://wudaoyunqi.com/categories/
十年饮冰,难凉热血。
思路暴力是不能暴力的,此题是求任意区间乘积能否整除给出的一个数,那么我们不妨换个思路,对于一个数我们可以把它进行质因数分解,那么如果一个数可以整除另一个数,那么前者包含后者所有的质因数并且每个质因数个数都不小于后者。这道题先对ai进行质因数分解并记录,比如对于质数2,v[2]={1,2,2,4,4,4}表示第一个数有一个因数2,第二个数有两个,第三个数没有……,那么对于区间[l,r],查询d的一个
思路这是一棵树,但要把无根变为有根,题目中“只有一个出口”的条件便能确定这个树的根,由根去dfs就行了
思路堆(Heap)的概念清楚了这道题就不难,按照插入顺序建堆理解起来也不难,用map判断比较快。
这篇笔记看到哪写到哪,只是一些杂碎的知识汇总,以后有时间再重新整理一下 卷积神经网络结构一个简单的卷积神经网络是由各种层按照顺序排列组成,网络中的每个层使用一个可以微分的函数将激活数据从一个层传递到下一个层。卷积神经网络主要由三种类型的层构成:卷积层、池化层(Pooling)和全连接层。 1 卷积层卷积层的参数是由一些可学习的滤波器(filter)集合构成的。每个滤波器在空间上(宽度和高度)都比较
思路暴力是不能暴力的,此题是求任意区间乘积能否整除给出的一个数,那么我们不妨换个思路,对于一个数我们可以把它进行质因数分解,那么如果一个数可以整除另一个数,那么前者包含后者所有的质因数并且每个质因数个数都不小于后者。这道题先对ai进行质因数分解并记录,比如对于质数2,v[2]={1,2,2,4,4,4}表示第一个数有一个因数2,第二个数有两个,第三个数没有……,那么对于区间[l,r],查询d的一个
题目网址:https://vjudge.net/contest/299252#problem/E 思路n^k=(10^lgn)^k=10^klgn,求x的前三位方法:x=10^lgx,lgx=整数a+小数b,a描述x有几位,10^a=100…0,10^b修饰每一位的数字,所以x的前三位就是10^b*100。后三位很好求,在快速幂中取mod=1000即可。有个坑点是后三位可能有前导零,所以要注意格式
思路幸福数求法是如果不是幸福数,那么一定会出现循环,一种方法是标记每次得到的数,另一种*操作是判断20是否会出现(如果出现20,那么这个数就一定不是幸福数(小明某一次打表找到的规律而这道题还要判断是不是独立的,那么开个vector记录每次得到的数的前一个数,同时也记录每个幸福数要得到1需要经过几次转换,最后再判断是不是质数即可
https://wudaoyunqi.com/2019/05/05/NEUOJ-2019-2Monthly-3/
题目网址:https://oj.neu.edu.cn/problem/1467 思路求x出现了几次,当然是将所有编号踢入一个数组,然后用lower_bound和upper_bound寻找前后位置(目前二分很容易写错,stl大法好
思路蛮明显的二分,对[1,1e18]的数进行二分。这里有精度问题,所以要用到除法(某种角度很自然的想法?),精度问题可以用longdouble解决,c++写法一共有四种,当然直接上JAVA(窝不会耶
https://wudaoyunqi.com/2019/04/18/NEUOJ-2018%E6%96%B0%E7%94%9F%E8%B5%9B-2/
思路我们习惯将10进制转换为正进制,方法无非是取余n,其商再继续取余直至该数被除至0,依次得到的余数倒序即为该十进制的n进制表示。如果是-n进制,方法也基本一样,永远满足被除数=商除数+余数,这里注意余数>=0,当余数是负数时,将商++之后把余数变为正数(-=进制n)举个栗子:-1 = 1 (-2)^1 + 1 (-2)^0;① -1%(-2)=-1,-1/-2=0 ——> -1-
https://wudaoyunqi.com/2019/03/26/%E5%A4%A9%E6%A2%AF%E8%B5%9B-%E5%88%86%E8%80%8C%E5%86%B6%E4%B9%8B/
思路这道题也不难,不用想到什么无向图连通判断,只要对攻下的城市做记录,在跑一遍所有的边,看是否有一条边两个点都没被记录,这样的边就是孤立边给的时间是600ms,k是100,m是10000,复杂度就是km,完全不会超时(要学会对复杂度的预判呐
https://wudaoyunqi.com/2019/05/05/NEUOJ-2019-1Monthly-1/
题目地址:https://oj.neu.edu.cn/problem/1459 思路三种做法,1、三次lowbit 2、三次x=x&(x-1) 3、__builtin_popcountll(计算一个64位无符号整数的二进制有多少个位为1)
思路很简单很入门级的题,ACMer选手写这种题就是过家家,但是不知道最近我的脑袋是怎么了,这种题都会卡(卡nm?,这个脑子啊……,写个结构体然后排序不就好了嘛,充其量就是这个排名卡一下……哎,我居然在处理排名的时候又建了个数组然后非要用lower_bound来找分数一样的人有多少个然后在输出==,感觉我是被lower_boung带入歧途其实很简单的,用个com记录上一个排名,然后和当前的比较,如果
https://wudaoyunqi.com/2019/04/18/USACO-1-3-Palindromic-Squares/
思路N范围在【1,300】,暴搜一遍,借用一个数组存转换进制之后的digit,然后短除法取模即可。
前言上一篇博客我们讲到了快速幂(一般&&矩阵),现在我们要讲讲一个叫欧拉降幂的东西,为了得到欧拉降幂公式,我们需要回顾一下欧拉函数,再到欧拉定理以及拓展欧拉定理。 欧拉函数公式欧拉函数phi[x],表示[1,x-1]区间中与x互质的数的个数phi[x]=x(1-1/a1)(1-1/a2)…(1-1/an),其中ai是x的质因数那么就可以得到欧拉函数的一个性质,若p是质数,那么phi
https://wudaoyunqi.com/2019/04/18/%E4%B8%80%E4%BA%9B%E7%A2%8E%E7%A2%8E%E5%BF%B5/
之前去长白山的时候,我就说我发现自己一年过去了还是没有什么进步,cf分数还是那么低,每次都做不到四道题,每次都要思考很久,简单的思路不会,暴力有时候还会卡壳,算法的应用烂得跟个啥一样。没有进步,我觉得这个状态很可怕。数学系的课程我学不懂,我也没有精力把所有的时间都放在上面,想保研太难了(当然也许是我持有借口一说,但我不想深入)。自己搞ACM,不,我觉得不是在搞,而是不上心地散一点时间在上面。诚然我
前言被学弟带着过了我不会的05,02自己看错了(所以wa出翔,没进前250 01 PolynomialHDU 6668 数学/暴力判断题目大意:给出f(x)和g(x)多项式各个系数,求当x→∞时,f(x)/g(x)的值思路:无脑高数知识,高中爷也一定提前学到过。从最高位开始判断,当两个系数都为0时,判断下一位;如果f(x)系数不为0,g(x)系数为0,则趋于正无穷,反之趋于0;当两个
思路这道题就是求递减子列的个数,我的方法是开一个数组来记录当前每个递减子列的尾值,如果要插入的这个数大于所有尾值中最大的那一个,那么ans就+1,这个数就是新的递减子列的头(同时也是这个递减子列的尾,因为此时子列只有它一个元素),反之,用lower_bound找到最小的大于这个数的尾值,这个数就变为该递减子列的尾(更新尾值)。因为尾值数组始终保持递增(有序),所以可以用lower_bound来找。
https://wudaoyunqi.com/2019/05/05/%E6%B5%99%E6%B1%9F%E7%9C%81%E8%B5%9B19th-Potion/
题目地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4094 思路因为只能从rank高的(分给)rank低的,所以从n开始依次将bi置为ai,bi-1+=(bi-ai),如果bi<ai,那么输出No,否则输出Yes
https://wudaoyunqi.com/2019/05/12/2017SWERC-Cakey-McCakeFace/
题目网址:https://open.kattis.com/problems/cakeymccakeface 思路让你找出现次数最多的时间差,范围是[0,1e9],那么用map的key记录时间差,value记录出现次数,最后找出value最大的最小的key即可。因为map会自动对key排序(默认从小到大),那么比较大小的时候写成>max_n就行。
思路蛮明显的二分,对[1,1e18]的数进行二分。这里有精度问题,所以要用到除法(某种角度很自然的想法?),精度问题可以用longdouble解决,c++写法一共有四种,当然直接上JAVA(窝不会耶
https://wudaoyunqi.com/2019/05/12/2017SWERC-Blowing-Candles/
题目网址:https://open.kattis.com/problems/blowingcandles 思路旋转卡壳求凸包的宽度(ps:你需要一个靠谱的模板
https://wudaoyunqi.com/2018/10/10/Git%E6%93%8D%E4%BD%9C%E6%80%BB%E7%BB%93/
经久没有使用git(捂脸跑开),今天开会被czq小朋友教做人,所以欸真的需要再回顾一下git操作啊(:зゝ∠)。于是上git官网从头到尾仔仔细细看了一波(不能再废下去了啊喂(摇醒)。也相当于给自己做一个git笔记,以后有忘记的命令操作就来这里看啦。 前言Git是一种分布式版本控制系统,这与常被混淆的Github(只支持Git做版本控制的项目托管平台)是两种不同的概念。在Git中的绝大多数操作都只需
https://wudaoyunqi.com/2019/03/26/%E5%A4%A9%E6%A2%AF%E8%B5%9B-%E7%BA%A2%E8%89%B2%E8%AD%A6%E6%8A%A5/
思路第一种方法就是暴力,图我发现自己惯用vector来存,其实邻接矩阵也行,然后习惯用广搜,不习惯用深搜。比赛的时候想的巨复杂,其实还是因为自己做题太少,我居然想到用判断每个点所在连通块是否不连通来做(这也是我为什么想不到好的算法的原因吧,做题少脑子又木。用广搜算出连通块数量即可,也是很暴力的那种(似乎我现在对于暴力做很害怕?,注意的是攻占城市是一个一个攻占,已经被攻占的城市不涉及其他城市连通性,
题目网址:https://vjudge.net/contest/299252#problem/A 思路先预处理欧拉函数值,我习惯用线性筛了,然后将cost记忆化求值,这里注意phi[a]<a,所以从a+1开始遍历寻找phi=a的数,更新cost[a]
https://wudaoyunqi.com/2019/03/26/%E5%A4%A9%E6%A2%AF%E8%B5%9B-%E7%8C%9C%E6%95%B0%E5%AD%97/
思路猜数字:其实非常简单,但是就是不知道为啥我没做对,这一次是用的map,比赛用的是结构体,真是绝了。map的lower_bound方法是找出第一个大于等于key的迭代器指针
思路脑子头脑风暴一下,或者手推,就会发现这道题可以转换为26进制来做(0为a,25为z),倒数第1个字符串是zzz,即zzz-aaa,倒数第二个字符串是zzy,即zzz-aab,倒数第26个字符串是zza,即zzz-aaz,即把n-1转换为26进制,然后用zzz相减即可
前言其实整个系列弄下来是因为尝试做了小米OJ的二月月赛,结果被狠狠压在地上打(哭,看了评论有人给出的题解,有道题因为涉及到矩阵快速幂,所以干脆把快速幂重新再看一遍。 原理一般朴素的幂积算法计算$a^b$时间复杂度是O(n),而快速幂可以降到O(logn),实现的原理是将b二进制化,$b=2^a_{1}+2^a_{2}+…+2^a_{k}$ , $a^b=a^{2^a_{1}}a^{2^a_{2}}
思路二叉树的判断,如果是完全,则深度为h的树,除了第h层,其它层都是满的,这里用结构体来存二叉树,同时判断是否为完全。二叉树的空间定义为1<<20,其实用到的最大空间为1<<20-1,父节点为i,子节点就为i<<1,i<<1+1
https://wudaoyunqi.com/2019/03/26/%E5%A4%A9%E6%A2%AF%E8%B5%9B-%E5%B0%8F%E5%AD%97%E8%BE%88/
思路一道深搜题,不过要注意记忆化搜索,用maxx记录最小的那一辈(rank值最大),然后用vector存每一辈的下标,因为是顺序存的,所以输出也是递增的
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.