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

ACM – Uva10054 – 欧拉回路

问能不能拼接一条项链,条件是首尾相同构成环。 这个题的坑在: 虽然保证连通,但是不一定每个颜色都有,所以单纯的暴力euler(1)是很愚蠢的。 题目本身是要求顺序输出的,也就是dfs不能回溯,如果回溯,为了保证准确性,需要交换uv的位置来保证。 通过统计出度入度判断是否满足欧拉回路。 #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); int n; const int maxn = 1000+10; int g[60][60]; void euler(int u) { for(int v = 1; v <= 50; v++) if(g[u][v]) { g[u][v]--, g[v][u]--; euler(v); printf("

Read More

ACM – Uva10105 – 组合数

基本上是组合数裸题。。 给出$(x_1+x_2+x_3….x_k)^n$,要求计算$x_1^{n_1}x_2^{n_2}…x_k^{n_k}$的系数。 思想就是从一个算式中取出$n_k$,即$C_n^{n_k}$,然后减去$n_k$,如果直接相乘则会重复。 #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 – Uva10294 – 置换

项链和手镯。 项链的问题在于不可以翻转,因此少了一种置换,而手镯则可以反转。然后我们计算旋转的置换。 旋转的步长可以是0,i,2i…然后我们可以得出循环一共有n/gcd(i,n)个元素,因此,我们可以计算出一共有gcd(i,n)个循环。则不定点的个数为 $a = \Sigma t^{gcd(i,n)}$。 翻转。翻转奇数情况和偶数情况是不一样的,因为奇数情况会多一个不定点,这个不定点就是在轴上的点。剩余的不定点的个数就是$n/2$,总共不定点的个数就是$nt^{(n+1)/2}$。偶数的情况下,如果正好切在两个珠子上,那么循环长度为2的点有$n/2-1$个,长度为1的循环有2个,所以总共$n/2+1$个。如果没有切在珠子上,不定点的个数为$n/2$,和为$b = n/2*(t^{n/2+1} + t^{n/2})$。 然后我们可以计算出项链的个数$a/n$,手镯的个数$(a+b)/2n$ 列出式子以后代码就方便了。记得求pow的时候可以顺手打表 /*============================================================================= # # Author: svtter - svtter@qq.com # # QQ : 57180160 # # Last modified: 2015-05-03 18:48 # # Filename: 10294.cpp # # Description: # =============================================================================*/ #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) << "

Read More

ACM – Uva10375 – 组合数公式

有些匪夷所思的题目。。注释部分加上就WA,不加就AC。。 推公式,因为$$C(n,k) = C(n,k-1) * (n-k+1)/k$$ 所以$$ans = \frac{C(n, k)}{C(r, s)}\qquad$$改成递推即可。 #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 – Uva106 – 勾股定理

從維基百科的勾股數條目參考來的通解: 給一個任意數對(X,Y),用以下公式代替 $A = X^2 – Y^2$ $B = 2XY$ $C = X^2 + Y^2$ 得出的A,B,C就是一組勾股數。 若 (X,Y) 恰好互質而且一奇一偶,那麼會得到一組(A,B,C)互質的勾股數。 知道通解後,雙層迴圈跑 (X,Y) 就能找出所有互質勾股數。 按照台湾同胞的题解。 — 勾股数公式也是很神奇的啊。。。 此外还学习了bitset,因为是按位存储,所以比一般的bool来的更加迅速,也更加节省时间。 #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) << "

Read More

ACM – Uva10673 – 扩展gcd

水题一发。。直接使用floor和ceil函数,然后暴力即可。。。 如果使用快速的方法,就是扩展gcd。其中d的初始值没有关系,最后返回的是gcd(a,b). 暴力算法 #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 #define FOR(i, s, e) for(int (i) = (s); (i) < (e); (i)++) const double PI = acos(-1.

Read More

ACM – Uva10717 – lcm+dfs

今天不适合刷题。。。 题意:一个桌子4条腿,每条腿由一种硬币构成,四条腿必须一样长,请问如何最接近给出的标准桌子高度,输出两个最接近的值。 更新两个值的时候错误的判断如果lcm大于h就不再更新了,却没有想到高于h的部分依然可以更新,只是不能更新小于h的部分了。 #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