`
249326109
  • 浏览: 56258 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论
文章列表
链接:http://pat.zju.edu.cn/contests/pat-a-practise/1001   概述:计算a+b的值,并且将和按照每三位一个逗号分隔的方式输出。   注意点:负数和零的处理。   #include<stdio.h> int main() { int a, b, c; scanf("%d%d", &a, &b); c = a + b; if (c == 0) { printf("0\n"); return 0; } int flag = 0; ...

uva 10341 - Solve It

    博客分类:
  • acm
根据一些数学知识可知,整个函数是单调递减的,所以根据二分法找零点。 需要注意 浮点类型数字的比较方法。   #include<stdio.h> #include<math.h> #include<float.h> int p, q, r, s, t, u; double calcu(double x) { return p * exp(-x) + q * sin(x) + r * cos(x) + s * tan(x) + t * pow(x, 2) + u; } int main() { while ( ...

uva 270 - Lining Up

    博客分类:
  • acm
题目中特别说明注意高效,估计简单的O(n^3)枚举法要超时,试了下果然。 不过这个题目以前在上普林斯顿的algorithms里有个大程跟这个95%相似的问题,所以我一下子就想到了优化的解法,复杂度是O( (n^2)logn )。 优化解法:对于每个点,按照其他点相对于这个点的斜率排序,在排序的序列中找寻最长的斜率相同的子串长度,其中最费时的是排序,所以总体的复杂度就是n 乘以 nlogn。     #include<stdio.h> #include<stdlib.h> #include<float.h> #include<strin ...
基本思路:先按照长度排序,总长度等于第一个子串加上最后一个子串,然后从最后开始枚举子串与子串file[0]相加,也从后开始找到另一个子串与子串file[1]相加,并交换相加顺序,直到两个先加的串相等。 注意考虑所有子串都相等的特殊情况。   #include<stdio.h> #include<string.h> #include<stdlib.h> #define MAX_LEN 256*8+5 #define MAX_LINE 300 char file[MAX_LINE][MAX_LEN]; int cmp(const v ...
我的想法是都存到一个数组里,录入的时候将如果后面一个数字小,就交换下位置,然后按照两个数字依次排序,排序之后正常情况应该是依次两个两个相等,否则就有问题。 有人是from和to分别放到两个数组,依次排序后一对一比较,但是这种情况有bug,比如A到B,B到C,C到A理论上应该No,这种解法确是YES(虽然据说好像没有这种case,也能AC...)。   #include<stdio.h> #include<stdlib.h> #define MAX 2*500000+5 typedef struct Exchange { int from; int ...

uva 10905 Children's Game

    博客分类:
  • acm
贪婪法,先排序。数字好像超过了一般整数的大小,数组稍微开大点。     #include<stdio.h> #include<stdlib.h> #include<string.h> char num[55][200]; int cmp(const void *a, const void* b) { char *aa = (char*) a; char *bb = (char*) b; char m[400] = { 0 }; char n[400] = { 0 }; strcat(m, aa); strcat( ...

uva 10123 - No Tipping

    博客分类:
  • acm
  略蛋疼的一道题目,研究了好久,最开始简单的枚举回溯法,果断超时。网上看到了好多人的优化,最后选择了一种线性的解法,只需扫描一遍即可。 基本思路:将问题转化为依次往板上放包裹,为了让板尽可能的平衡,一定是先放扭矩小的上去,所以先将包裹分类,左支点左边的一波,中间的一波,右支点右边的一波,分别排序,把中间的一波先放上去,这样可以增加系统的稳定性,然后左右两边依次往上放直到一边失去平衡,换另一边上,如果两边都不能放还有剩余的话,就是没有解了。   思路参考: http://www.ngszone.com/blog/archives/250   0.019s AC: #includ ...
回溯法,注意回溯回来之后状态要恢复,冲突判断是从当前点向四周辐射,直到出界或者遇到墙,如果有遇到其他车,说明冲突。   #include<stdio.h> int n; int board[5][5]; int maxNum; int isConflicted(int i, int j) { int o, p; for (o = i; o >= 0 && board[o][j] != 0; o--) { if (board[o][j] == -1) return 1; } for (o = i; o < ...

uva 216 - Getting in Line

    博客分类:
  • acm
开始还以为最小生成树,结果最多8个节点,明显是要暴力枚举。 先递归生成每种排列,计算距离总和,记录下最小的,最后输出。   #include<stdio.h> #include<math.h> #include<string.h> typedef struct Point { int x; int y; } Point; Point point[8]; int n; double minLen; int minPerm[8]; int perm[8]; void permu(int cur) { if (cu ...
太简单了没啥好说的,排下序然后搜索下,看不出要怎么用回溯法。     #include<stdio.h> #include<stdlib.h> #define MAX 10005 int marbles[MAX]; int cmp( const void*a, const void*b) { return *(int*) a - *(int*) b; } int search(int n, int q) { int i; for (i = 0; i < n; i++) if (marbles[i] == q) ...
暴力枚举所有的子集列,比较在每种情况下每行是否唯一,我把每行数据当成2进制转化为10进制之后比较的。这里枚举子集是用的位向量法,产生的子集序列 子集大小变化是不规则的,但是一旦有小的子集可以区分所有行,子集大的情况就不用计算了,直接可以忽略。     #include<stdio.h> #include<math.h> #include<stdlib.h> int led[105][20]; int flag[20]; int p, n; int minNum; void judge() { int arr[105]; i ...

uva 10167 - Birthday Cake

    博客分类:
  • acm
简单枚举法不解释。   #include<stdio.h> #define MAX 105 int cherry[MAX][2]; int n; void search() { int i, j, k; int oneHalf; int theOther; int error; for (i = -500; i <= 500; i++) for (j = -500; j <= 500; j++) { oneHalf = theOther = 0; error = 0; for (k = 0; k ...

uva 532 - Dungeon Master

    博客分类:
  • acm
bfs在三维空间的扩展,仔细一点问题不大。   #include<stdio.h> #include<string.h> typedef struct Point { int x; int y; int z; int len; } Point; typedef Point* Ptr; char dungeon[40][40][40]; int l, r, c; int dir[6][3] = { { 1, 0, 0 }, { -1, 0, 0 }, { 0, 1, 0 }, { 0, -1, 0 }, { 0, 0, ...

uva 439 - Knight Moves

    博客分类:
  • acm
先研究下国际象棋中马是怎么走的,然后bfs就哦了。   #include<stdio.h> #include<string.h> #include<stdlib.h> int map[10][10]; typedef struct Point { int x; int y; int dis; } Point; typedef Point* Ptr; Point queue[5000]; int dir[8][2] = { { -2, 1 }, { -2, -1 }, { -1, 2 }, { 1, 2 }, ...

uva 705 - Slash Maze

    博客分类:
  • acm
开始无从下手,后来参考了别人的思路 http://blog.csdn.net/shuangde800/article/details/7726620 有了思路后不知道怎么求环,后来发现题目说了没岔路。。   #include<stdio.h> #include<string.h> #define MAX 200 int w, h; char maze[MAX][MAX]; int cases = 1; int isCircle; int num; int circleCount; int maxLen; int hasCircle; ...
Global site tag (gtag.js) - Google Analytics