ACM – UVA10308 – 无根树转有根树

比较莫名奇妙的题目,明明是搜索题目居然放在了数学分类,完全找不到数学的影子。。 利用vector,遍历树,找出最大的子树路径,然后与次大的子树路径相加即为答案。 因为图表示这方面太渣,基本上抄袭了别人的代码= = #include <bits/stdc++.h> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++) const double PI = acos(-1.0); #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << "

Read More

ACM – UVA10820 – 欧拉函数

给出一个Answer(x,y)函数,x,y属于[1,N],$Answer(k_x, k_y)$可以由Answer(x,y)得出,目的是求需要计算多少Answer(x,y)。 就是求1,N范围的欧拉函数的加和。欧拉函数的定义是与N互质的数的个数,所以需要如此计算。一开始没有发现就是求欧拉惭愧惭愧。 #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++) const double PI = acos(-1.

Read More

ACM – UVA11029 – 快速幂,快速前幂

后面的三位快速幂即可,但是前面三位不好求。经过分析,每一位都有可能牵扯到前三位的值,因此无法具体的作出判断。 如果使用模方法省去后面的部分,必定会造成误差,随着省略的部分增多,误差积累势必会越来越大。(错了一组数据) 最佳的方法还是数学分析(参考了题解): 分析n,$a = log_{10}^n$,则$n = a ^ {10}$。分解a = i + d,i为正数部分,d为小数部分。那么i影响的仅仅是位数,d影响的则是具体的数字。 这样得到的值是准确的。另外对浮点数取余 fmod(double, mod) #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define ll unsigned long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << "

Read More

ACM – UVA11121 – 进制

题意是由10进制转换成-2进制,但是明显我分析错了,所以写了调了接近一下午的bug。。。 有时间再写正常的题解。 题解: 如果当前数位和输入n符号相同,那么不做处理,如果不同且为1,那么下一位(即左边一位)做+1处理 — 因为下一位是上一位的2倍,就相当于做一个变号处理。

Read More

ACM – UVA571 – 模方程

一开始在扩展gcd上想了许久没有办法将得出的数字直接转换成为相应的输出,后来发现就是模方程。 因为不求最佳解,所以直接使用ca*x = n (mod cb)即可。这个方程的解可以覆盖全部的n,因为该方程如果有解,则n是gcd(ca, cb)的倍数。因为ca, cb互质 gcd (ca, cb) = 1,所以明显通过单纯的加满B,向A中倒,然后清空A就可以遍历所有n的解(尽管可能不是最佳解)。 不能是cb*x = n (mod ca),因为n可能大于ca. 如果求最佳解,显然是bfs。当然这到题目也可以dfs来做,不过明显要复杂很多。 #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << " "

Read More

ACM – UVa10006 – 快速幂

水题一发。无奈自己没有好好审清题意,另外快速幂居然写错了- = 快速幂在过程中修改a的值,但是我却计算成了在偶数时相乘,调试半天。看来还是咩有好好理解啊。 #include <iostream> #include <cstdio> #include <cstring> #include <set> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(b, -1, sizeof(b)) #define DEB(x, n) cout << (x) << " " << (n) << endl const double PI = acos(-1.0); #define CR printf("\n") // 调试用 template <class Type> void debug(Type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << "

Read More

ACM – UVa10023 – 开平方

本题目计算开根号数字,给出Y求X。X = sqrt(Y),主要问题在Y的超大数据。 时间限制是3s。我使用的大数模板中没有一个大数除大数的算法,因此直接借用Java来搞一搞。 利用公式$$(5/x+x)/2 = x$$递归逼近求解。这个公式比较好推,移项即可。 import java.util.*; import java.math.*; import java.util.HashSet; public class Main { static Set set; public static BigInteger cal(BigInteger a, BigInteger b) { BigInteger ans = (a.divide(b) .add(b)).divide(new BigInteger("2")); if(set.contains(ans)) return ans; else { set.add(ans); return cal(a, ans); } } public static void main(String [] args) { Scanner cin = new Scanner(System.in); BigInteger a; String s; int T = cin.nextInt(); while(T-- != ) { set = new HashSet(); s = cin.

Read More

ACM – UVa10791 – divide prime

谢天谢地终于过了。 就是求分解质因数后的和,如果是质数那么返回1+n本身。 一开始直接暴力求两个质因数的情况,铁定不对啊。。 第二次发现策略有问题,转为使用枚举质因数,然后发现仅仅是质因数LCM有问题啊。。 第三次没有考虑质数 第四次没有考虑Case 第五次不记得了。 第七次AC,哭了真是。。一定要先分析好题目啊。 #include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <map> #include <algorithm> #include <queue> #include <cmath> #include <bitset> using namespace std; // 大数,内存处理 #define inf 0x3f3f3f3f #define ll long long int #define mem(a) memset(a, 0, sizeof(a)) #define memm(a) memset(b, -1, sizeof(b)) #define deb(x, n) cout << (x) << " " << (n) << endl #define cr printf("\n") // 调试用 template <class type> void debug(type a[], int len) { for(int i = ; i < len ; i++) { cout << a[i] << "

Read More

ACM – UVa138 – 数学基础

这道题目其实就是推个公式,主要还是考验编程技巧。。 首先double的精度范围是15-16位,浮点数运算还是最快的,依据最后一个答案(总共10组),平方为16位刚好够用。 如果想要最精确的结果,当然还是使用long double或者long long来来保证精度问题。不过计算速度就会有所损失,采取二分的方法加速比较好。 利用double的代码: const double eps = 1e-10; for(double i = 8; i < maxn;i ++) { double res = i*(i+1)/2; ll ans = sqrt(res); if(res - ans*ans < eps) printf("%10lld %10lf\n", ans, i); } printf("done"); 利用long long的代码: for(ull i = 8; i < maxn;i ++) { ull res = i*(i+1)/2; ull l = i/2, r = i; ull mid, ans; bool find = ; // bsearch while(l <= r) { mid = (l+r)/2; ans = mid * mid; if(ans == res) { find = 1; break; } else if(ans > res) r = mid - 1; else l = mid + 1; } if(find) printf("

Read More

ACM – Uva10047 – 图论

隐式图搜索,多个状态然后减枝。。没看懂李大大所说可以承受是个啥意思。。 做起来实在太累了。。减枝的部分看了别人的代码,发现着实麻烦,不如用优先队列来的痛快=- =还有用优先队列做的= = 主要是$vis[x][y][p][c]$这组状态比较难搞,但是给了优先级(时间短的先出队),事情就好办了。 #include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define ll long long int #define MEM(a) memset(a, 0, sizeof(a)) #define MEMM(a) memset(a, -1, sizeof(a)) #define DEB(x, n) cout << (x) << " " << (n) << endl #define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++) #define CR printf("\n") const double PI = acos(-1.0); const int maxn = 30; char g[maxn][maxn]; // c, 0, 1, 2, 3, 4 // blue,w,g,black,r; struct Node { int x, y, c, p, t; Node(int x, int y, int c, int p, int t):x(x), y(y), c(c), p(p), t(t){} Node(){} bool operator < (const Node b) const { return t > b.

Read More