[综合] 紫书 习题 10-2 UVa 808（建立坐标+找规律）

这次是我遇见过最迷的一次 我写的程序uDebug全过 和ac程序对拍也过，求出来的坐标是一模一样的，最后结果输出的方式也是一样的 交上去就是错的 迷 第一次遇到这种情况 大佬在哪里 #include<cstdio> #include<cmath> #defineREP(i,a...

[综合] 紫书 习题 10-4 UVa 1644（素数筛）

素数筛没什么好说的 #include<cstdio> #include<vector> #include<cstring> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constint...

[综合] 紫书 习题 10-5 UVa 1213（01背包变形）

这里就是01背包多了一维物品个数罢了 记得不能重复所以有一层循环顺序要倒着来 边界f[0][0]=1 #include<cstdio> #include<vector> #include<cstring> #defineREP(i,a,b)for(inti=(a)...

[综合] 紫书 习题 10-6 UVa 1210（前缀和）

素数筛然后前缀和 看代码 #include<cstdio> #include<vector> #include<cstring> #include<map> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usi...

[综合] 紫书 习题 10-8 UVa 10622（gcd）

把这个数质因数分解然后求因子个数的gcd就ok了。 一些细节 （1）这道题的质因数不需要存下来，每一次做完取一次gcd就ok了 （2）判断奇偶用ans&1的时候要加括号，位运算要注意括号 （3）这道题在32位带符号整数范围内，也就是说用int可以了 （3）注意ans最后的处理，看代码 #in...

[综合] 紫书 习题 10-3 UVa 1643（计算几何 叉乘）

直观感觉对角线重合的时候面积最大 然后可以根据方程和割补算出阴影部分的面积 注意知道两点坐标，可以求出与原点形成的三角形的面积 用叉乘，叉乘的几何意义以这两个向量为边的平行四边形的面积 所以用叉乘除以2就可以 （x1,y1）,(x2,y2),叉乘为x1y2-y1x2 #include<cstd...

[综合] 紫书 习题 10-9 UVa 294（正约数个数）

一个数的正约数个数等于这个数的质因数分解后 每一项幂+1的积 因为每个质因数的幂可以为0，1，2……（注意可以为0） 所以就每个质因数配一个幂任意组合就可得一个正因数，根据乘法原理可得正约数个数。 另外质因数分解可以不用素数筛（但可能会稍微慢一点） #include<cstdio> #d...

[综合] 紫书 习题 10-10 UVa 1645（递推）

除了根节点以外，有n-1个节点，然后就看n-1的因数有那些，所有因数加起来（递推）就好了。 #include<cstdio> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnamespacestd;constintMOD=1e9+7; ...

[综合] 紫书 习题 10-11 UVa 1646（斐波那契+高精度）

自己用手算一下可以发现是斐波那契数列，然后因为数字很大，用高精度 以后做题的时候记得算几个数据找规律 #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #def...

[综合] 紫书 习题 10-12 UVa 557（概率计算）

开始的时候我没有考虑1/2的概率，直接一波组合数，然后WA 后来去看题解发现我们可以反过来想，求最后两个人不一样的情况 这个时候肯定会抛到最后的 所以每一种可能就是（0.5）^(n-2),然后一共有C（n-2，n/2-1）种 乘起来就ok了。 但是这样会超时而且结果太大 所以我们可以尝试递推 通过计...

[综合] 紫书 习题 10-13 UVa 11526（打表找规律+分步枚举）

首先看这道题目，我预感商数肯定是有规律的排列的，于是我打表找一下规律 100/1=100 100/2=50 100/3=33 100/4=25 100/5=20 100/6=16 100/7=14 100/8=12 100/9=11 100/10=10 100/11=9 100/12=8 100/1...

[综合] 紫书 习题 10-14 UVa 10886（暴力+数据范围）

开始的时候一看这题感觉很难，觉得肯定有什么很快的办法 不能暴力做（受了上一题10-13的影响） 然后一看那个函数感觉无从下手。 然后看了博客发现，原来这道题就是直接暴力…… 因为n的范围为10的7次方啊，不会超时 自己以后要注意数据范围 #include<cstdio> #include...

[综合] 紫书 习题 10-16 UVa 1647 (高精度+递推）

这道题我已经推出00和1过两步变成00了，可我没有继续做下去…… 后来看了博客发现自己已经做了90%了…… 可惜了，以后不要轻易放弃。 1的个数有个规律，就是每次都乘以2，因为0和1下一步都会变出1 然后因为0和1个个数是一样的，所以1的变出1，0的也变出1 最后1的个数就乘以2了 第i次1的个数为...

[综合] 紫书 习题 10-17 UVa 11105 (筛法）

类似于素数筛的思想去做，不然暴力会超时而且还要判重 #include<cstdio> #include<cstring> #include<vector> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingnames...

[综合] 紫书 习题 10-18 UVa 10837 (欧拉函数变形）

这道题很巧妙，要把式子变一下 phi(n)=n*(1-1/p1)*(1-1/p2)……(1-1/pr) =n*((p1-1)/p1)*((p1-2)/p2)……((pr-2)/pr) =p1^k1*p2^k2……pr^kr*((p1-1)/p1)*((p1-2)/p2)……((pr-2)/pr) =...

[综合] 紫书 习题 10-19 UVa 10868 (物理动能定理）

这道题看起来很长，而实际上就是考物理 可以用动能定理来算出末速度。 同时注意要特判绳子比桥还长的情况。 #include<cstdio> #include<cmath> #defineREP(i,a,b)for(inti=(a);i<(b);i++) usingname...

[综合] 紫书 习题 10-21 UVa 1649 (组合数）

C(n,k)=m，固定k，枚举k 这里用到了组合数的一个性质 当k固定的时候，C(2*k,k)最小 C（m，k）最大（对于这道题而言是这样，因为大于m就最终答案不可能为m了） 所以就二分去枚举2*k到m之间了。 最后注意算组合数的时候超过m可以直接返回，同时比较时候可能会超出longlong 有小技...

[综合] 紫书 习题 10-22 UVa 10479 (找规律）

自己一直在纠结这个串的构造方法 而没有观察串本身的规律…… 2的63次方用unsignedlonglong 然后可以发现串是递归构造的。 将串分成1，1，2，4，8，16，然后会发现s串里面1个s-2串，2个s-3串，3个s-4串最后加上s 如第三个串1003 是由1个1串（1），2个0串（0）最...

[综合] 紫书 习题 10-32 UVa 1414 ( 迷之规律）

看了其他人博客，貌似i个盘子的方案数满足f[i]=f[i-1]*x+y ？？？？？？？ 神来之笔 貌似没有找到严格的证明…… 牛逼…… 如果这样的话暴力求出x和y然后递推完事 #include<cstdio> #include<stack> #defineREP(i,a,b...

[综合] 2018 NOIP备战计划

2018NOIP目标 （1）刷完紫书数论习题 （2）听51nod讲座和习题，根据其知识结构来备战。 （3）刷完紫书动规 （4）初赛前两个星期左右开始复习 刷紫书动规的时候感觉偏难，进步缓慢。应该自己调低难度 两个大任务 （1）51nod讲座 （2）按照《算法竞赛进阶指南》中动规的分类来刷（线性动...