题目链接：UVA-297 紫书p160 题意：用四分树来表示一个黑白图像：最大的图为根，然后按照图中的方式编号，从左到右对应4个子结点。如果某子结点对应的区域全黑或者全白，则直接用一个黑结点或者白结点表示；如果既有黑又有白，则用一个灰结点表示，并且为这个区域递归建树。 （以先序遍历输入） 思路：因为四分图比较特殊，只需给出先序遍历就可以确定整颗树。利用递归建树，遇见’p’就递归分别4个位置，每个位置记录左上角，再利用此次递归的边长得到方块的大小，边长每次缩小2倍。 当遇见’f’时从(r,c)到(r+w,c+w)累加没有加过位置的个数即为黑块大小。注意递归式中p也要引用，这样p++后才会改变p...

题目：Uva-806 Spatial Structures tag：递归建树，进制转换 题目大意： 一个n * n(n <= 64) 的正方形网格可以映射成一颗四叉树， 根节点对应整个区域。如果当前点对应的区域全为黑格子或者白色格子，就没有子节点，节点颜色即为格子颜色， （当然题目中黑色是1白色是0）， 有黑有白就是灰色并且有4个子节点分别对应4个边长一半的正方形区域，由此形成一颗四叉树，然后 每个从每个子节点出发回到根的路径（每个节点的4个4节点的边编号为1,2,3,4）， 看做一个5进制数。现在有两种输入， 1），给你一颗树，让你输出所有黑色子节点对应路径的5进制数转换十进制然后排序...

对于一个有n个元素的集合而言,其共有2^n个子集。其中空集和自身。 另外,非空子集个数为 2^n -1; 真子集个数为2^n -1; 非空真子集个数为 2^n -2.

//最小公倍数 = 两数的乘积 / 最大公约数

https://www.jisuanke.com/contest/7332/386137 思路：仔细观察，发现我们要做的就是将a与b匹配（就像括号一样）并允许c移到任何地方 #include <bits/stdc++.h> using namespace std; stack<char> mystack; bool fun(string s) { for(int i=0; i<s.size(); i++) { if(s[i]=='a') mystack.push('a'); else...

题目链接：http://sdnuoj.rainng.com/problem/show/1085 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3; const int mod = 1000000007; struct mat{ ll m[maxn][maxn]; }; mat mul(mat x, mat y, ll len) { mat tmp; for(int i=0; i<len; i++) { for(int...

A - Bi-shoe and Phi-shoe 欧拉函数讲解博客 欧拉函数快速筛法 欧拉函数：欧拉函数phi(x)代表小于等于x的数中和x互质（没有除1以外的公因子）的数的个数，比如说小于等于9的数中与9互质的有1，2，4，5，7，8，则phi(9)=6. 欧拉指出，以phi(x)表示小于等于x的数中与x互质的数的个数可以这样得到： phi(x) = x*(1-1/p1)*(1-1/p2)*(1-1/p3)...*(1-1/pn) 其中p1,p2,p3…pn是x的所有质因数，每个质因数只使用一次，使用上述公式，则phi(9)=9*(1-1/3)=6. 效仿素数筛法的欧拉筛。 欧拉...

C - Aladdin and the Flying Carpet 题目大意：给两个数a，b，求满足c*d==a且c>=b且d>=b的c,d二元组对数，(c,d)和(d,c)属于同一种情况； 题目分析：根据唯一分解定理，先将a唯一分解，则a的所有正约数的个数为num = (1 + a1) * (1 + a2) *…(1 + ai)，这里的ai是素因子的指数，见唯一分解定理，因为题目说了不会存在c==d的情况，因此num要除2，去掉重复情况，然后枚举小于b的a的约数，拿num减掉就可以了。 题目思路：根据唯一分解定理有: 1.每个数n都能被分解为：n=p1a1*p2a2*p3a...

题目地址 题目大意 输出n^k的前3位和后三位 题目解析：后三位可以直接使用快速幂对1000取模实现。难点在于如何求前三位 推导过程如下： n^k = 10^(lg n^k) = 10^(klg n) klgn = a(整数部分)+b(小数部分) 于是 10^(klg n) = 10^a * 10^b（0<=b<1） 便可以通过10^b看出前几位数字。 如何求b呢 modf( )函数 那么我们还要分析一下klgnk∗lgn是否会出现数据范围爆出的问题，double可控制的是16位，而k*lgn<=1e7∗lgn<1e9.所以可实现。 从本题的输出中学到的东西： 本题注意...

尼姆博弈：https://blog.csdn.net/BBHHTT/article/details/80199541 里面有个定理比较重要 题意，就是有一堆石子，一共有n个，把n个石子分成三堆，求有多少种分配的方式能够使得bob win？ 很容易就能够明白题目是让干什么的，这道题目就是一道尼姆博弈的题目，先来讲下尼姆博弈，其实很简单，有n堆石子，如果n堆石子的异或和是0，则先手必败，否则先手胜。尼姆博弈是利用二进制的思想，那么本题也可以利用二进制的思想，可知，如果要使得Alice输并且Alice为先手，只需要使得三堆石子异或等于0 即可，首先共有n个石子，把n转化成二进制来表示，假设其中有k...

题目： 情人节又到了，又到了一年一度发红包的时间。经大家研究决定，今年让奎奎自愿发红包。 俱乐部有n个人(0<n<100000)，每个人都有一个单身值v[i]与亲密度ti，单身值越大的人，在情人节的时候就越羡慕奎奎，奎奎就需要给他更大的红包来安慰他。 由于一个寒假没有见到奎奎，领红包的时候大家都想跟奎奎py，花费时间t[i]，先py后给红包噢。 大家都厌倦了等待，如果一个人等了时间t，那么奎奎发给他的红包大小就是v[i]·t。 但是奎奎还要和女朋友去快乐，想要花最少的钱来满足大家。 请你帮他计算最少需要发多少钱的红包。 输入 第一行一个整数n。接下来n行，每行两个数v[i]和t[i...

题意很简单，就是一个n<=1e7，n若可以被两个素数a,b(a<=b)所表示，问可以被多少组素数对表示。 1.bool类型占内存小，之前开的都是int数组，可以优化一下素数筛。（标记数组最好换成布尔类型的，节约时间和空间） 2.数组开的太大就会超时，尽量不要开这么大。 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e7+5; bool vis[maxn]; //bool类型占内存小，用int的话有可能memory exceed int pri...

题意：求f(n)=1/1+1/2+1/3+1/4…1/n (1 ≤ n ≤ 108).，精确到10-8 两种做法： 先介绍数论解法： 解法1.调和级数+欧拉常数 参考：https://www.cnblogs.com/shentr/p/5296462.html 知识点： 调和级数(即f(n))至今没有一个完全正确的公式，但欧拉给出过一个近似公式：(n很大时) f(n)≈ln(n)+C+1/2*n 欧拉常数值：C≈0.57721566490153286060651209 c++ math库中，log即为ln。 #include <bits/stdc++.h&...

挺有趣的一道题。 求出前sqrt(n)项和：即n/1+n/2+…+n/sqrt(n) 而（n/1-n/2)就是后面项中1.x的个数 (n/2-n/3)就是后面项中2.x的个数 依次类推。。。 举两个例子： n/1-n/2 = 5; 1.x n/2-n/3 = 2 2.x n/3-n/4 = 1 3.x <----- 重复，要减掉 n/1-n/2 = 10 1 n/2-n/3 = 4 2 n/3-n/4 = 1 3 n/4-n/5 = 1 4 由于n/sqrt(n) != sqrt(n) 故不存在重复的问题。 #include <bits/stdc++.h> usin...