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

ACM – hdu5104-water

这个题目的总结就是不作不会死- -好端端的暴力我非要用个bfs。

看见自己wrong了还以为是哈希的问题- =

题意

  • p1+p2+p3 = n,$p1 <= p2 <= p3$
  • 输出符合条件的组数

输入输出

  • 给100组n,输出组数

分析

  • 只有3个数,暴力解就可以,注意循环终止条件。

Read More