- 浏览: 56059 次
- 性别:
- 来自: 杭州
最新评论
-
huntfor:
csdn链接多少啊!
将博客搬博客园 -
huntfor:
把多线程考虑在内重写一遍吧
工厂模式总结 -
249326109:
huntfor 写道比我写的简单多了。。。。。。慢慢练习吧,我 ...
pat 1005. Spell It Right (20) -
huntfor:
比我写的简单多了。。。。。。
pat 1005. Spell It Right (20) -
huntfor:
好长啊。。。。看了之后对字符编码了解更清楚了一点,本来还以为是 ...
字符编码编码
文章列表
链接: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;
...