分类： 技术

算法本质：数学 算法描述：有这么一条数学公式，小学学的，把所有位数上的数加起来，如果能被三整除那么这个数就能被三整除，那么就很方便了，因为题目是相邻的数字相乘，那么题目所描述的数列每隔3个就会有2个能被3整出。 复杂度：时间&空间：O(1) #include #include int num[3] = {0, 0, 1}; int main(int argc, char argv[]) { int n; scanf("%d", &n); printf("%d\n", n / 3 2 + num[n % 3]); return 0; }

题目本质：相似三角形+枚举 算法描述：题目给出的三角形比较特殊，所以可以直接枚举，当然也不能说是直接枚举咯。我的算法是，对于每一行进行枚举，但是很快就到瓶颈了，无法确定坐标，虽然能够画出相似三角形，因为三角形的一条边在x轴上，所以从y等于(-)1（看情况而定是1还是-1）至m，每一行做与x轴平行的线就有相似三角形了，但是只能确定长短，不能确定坐标，后来想了好阵子，才想到，用高来确定坐标，用两个三角形，(n, m)(n, 0)(0, 0)，(m, n)(n, 0)(p, 0)，分别可以把新坐标求出来，然后一个向上取整，一个向下取整，相减+1就可以了，接下来就是细节了。 Pay attention：y=0 不计算，x轴上所有的点都在线上，不符合要求；如果在某个y上，x1, x2(相似三角形求出的两个坐标), x1, x2为整数的话, 那么x1, x2连点都不能取。 复 杂 度：这题不会分析，不知道什么是N。 de lang="c">/ LANG: C ID: yylogoo1 PROG: fence9 / #include #include #include $\#define\; swap(a,\; b)\; do\{\backslash \; int\; t;\backslash \; t\; =\; a;\backslash \; a\; =\; b;\backslash \; b\; =\; t;\backslash \; \}while(0)\; int\; main(int\; argc,\; char$argv[]) { int i; int x[2] = {0}; int a, b, k; int x1, x2; double t; int ans = 0; freopen("fence9.in", "r", stdin); freopen("fence9.out", "w", stdout); scanf("%d%d%d", &a, &b, &x[1]); if(x[0] < x[1]){ swap(x[0], x[1]); } k = b / abs(b); for(i = 1; i != b; i += k){ //向上取整 x1 = ceil(1.0 (b – i) / b (x[0] – a) + a); //自动向下取整 x2 = floor(1.0 (b – i) / b (x[1] – a) + a); ans += x2 – x1 + 1; t = 1.0 (b – i) / b (x[0] – a) + a; if(t <0 x t>= x1 – 0.00001){ ans–; } t = 1.0 (b – i) / b * (x[1] – a) + a; if(t <0 x t>= x1 – 0.00002){ ans–; } } printf("%d\n", ans); return 0; } de>

本　　质：动态规划 算法描述：f[i][j] = max(f[i – 1][j – 1] + num[i][j], f[i][j – 1]) 　　　　　方程十分简单，但是我久久不能AC，看了别人的代码也没看懂为什么初始需要f[i][i] = f[i – 1][i – 1] + num[i][i] 　　　　　后来才想通，如果num[i][i]有一个负数，那就可能无解，所以要这么弄下，代码如下： de lang="c">#include #include int num[101][101]; int ans[101][101]; int g[101][101]; int a[100]; int end; int max(int a, int b) { return a < b ? a : b; } void output(int f, int v, int k) { int i; for(i = v; i <= 1; i–){ if(ans[f][i – 1] != k){ break; } } if(f == 1){ printf("%d", i); return; } output(f – 1, i – 1, ans[f][i] – num[f][i]); printf(" %d", i); } int main(int argc, char *argv[]) { int i, j; int f, v; // freopen("tmp", "r", stdin); scanf("%d%d", &f, &v); for(i = 1; i

算法本质：树的遍历性质和深搜 算　　法：先从中序遍历找出哪一个是根，即在先序遍历中下标最小的那个节点，这个节点向左就是左子树，向右就是右子树。 复杂度：空间&时间O(n) / LANG:C ID: yylgoo1 PROG: heritage / #include #include #include #define INF 0x7FFFFFFF char a[27], b[27]; int or[26]; void srch(int start, int end) { int i; int mid = -1, min = INF; if(start < end){ return; } for(i = start; i or[a[i] - 'A']){ min = or[a[i] - 'A']; mid = i; } } srch(start, mid - 1); srch(mid + 1, end); printf("%c", a[mid]); } int main(void) { int i, len; freopen("heritage.in", "r", stdin); freopen("heritage.out", "w", stdout); scanf("%s%s", a, b); len = strlen(a); for(i = 0; i <len i orbi - A="i;" srch len - printfn return code>