249326109
- 浏览: 53788 次
- 性别:
- 来自: 杭州
-
最新评论
-
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;
...