30三
归类于心情日志
10 条评论
今天，我正式提交了退队的申请书，算是真正的离开了学校的集训队了。
虽然我的水平一直普普通通的，但是我很热爱这个比赛，因为很好玩，趣味很强。
当然acm的广告我就不打了，喜欢的人自然会喜欢，不喜欢的人我说到吐血也没用，我个人是感觉，如果你想快速学好编程，不管你喜欢不喜欢，这个绝对是一条很好的捷径。
这次的推出，我考虑了很久了。本来是打算等最后的选拔完成了再走的。但是后来想想，有想法就应该立刻实行，不能给自己拖拉的理由，所以就当下提交了退队申请，然后打算理清自己的思路，做自己喜欢做的事情了。
说个实话，这次去选拔，一开始还真挺功利的，就想骗点学分。。。谁知道比赛的途中发生各种事情，让我的感觉变化极大。因为一开始的失败，导致直接抹杀了自己那种功利性的感觉，然后继续比赛轻松了许多，却发现其乐无穷~然后，渐渐想起来自己一开始的想法，我当时就是因为觉得这种东西好玩才去编程，后来不断被各种东西蒙蔽了居然变成如此，不由汗颜不已。之后的比赛一直很享受，有好有差，但是找回那种感觉真的很好。也因为这样，我想，我可以毫无遗憾的离开去尝试更多的事情了。
我记得我刚刚上大学的时候，就希望自己能够尝试各种不同的生活，所以，我现在打算把大学生活告一个段落，然后尝试尝试新的生活，哈哈。
最后还是要感谢杭电acm集训队给我带来的知识和各种回忆，由衷的感谢。这个经历让我成长许多！
特别附上杭电acm网站以及教练blog：）
http://acm.hdu.edu.cn/
http://blog.sina.com.cn/liuyiding080513
至此，新的起点
210 views acm, 启航, 生活, 离开
13三
归类于心情日志
4 条评论
当然，这篇东西不是推荐LP的歌的。。。只是对自己生活的一个记录：）
今天参加了校赛也叫做省赛选拔赛。然后，选拔进去了，发挥正常，没有超常，没有过低水平发挥，完全和预想的一样。
然后就惊讶的看到。。。明天居然要开会，而且是临时定的。。。很不幸，明天我越好了教授，所以只能不去开会。于是我又看到一句很标志性的：无故缺席者视为放弃集训，当时头就大了。。。
好吧，还好，请假成功。不过明天就开始要训练了，以后的每个周末都是比赛，一般是4～5小时吧。也就是说，基本上我是没有周末下午了的。不过反正闲着也是闲着，无所谓了。
今天后，生活又会改变了，算是自己给自己加上了，自己本来应该达不到的目标吧。不过，不试试怎么知道机器性能呢～
好了，没时间说那么多了，本来想过个比较清闲的学期的，可惜最后居然比以往的都要忙，似乎从寒假之后，我就特别喜欢逆着自己的想法做事情，也许是自己故意给自己的磨练吧。谁知道呢，哈哈
明天又是崭新的一天。
C’est La Vie
ps：估计又是一个没的拍照，没的玩自己想做的程序，没法学自己想学的东西，没法泡妞，没法和朋友一起出去玩的学期，说实话，很讨厌，不过，我没的选择。
135 views acm, life, 学习, 安排, 忙, 生活, 竞赛
24一
归类于程序人生
2 条评论
今天开始学习学习哈夫曼树，于是就去找点题目做做，毕竟学数据结构这种东西还是让oj来验证你的想法最方便了。
google了一下，pku的3252貌似是个软柿子，捏之～
看了一些关于哈夫曼的介绍，大致有个想法了，打出来，wa。。。看来想错了。
于是再看资料，发现需要动态寻找最小的两个节点的，于是就写了一个比较暴力的，参考网上的资料。
6365627 zerob13 3253 Accepted 236K 250MS C++ 628B 2010-01-24 15:08:06
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<stdio.h>
#include<string.h>
#include<stdlib.h>
int lef[20001];
int n;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
int main (int argc, char * const argv[]) {
int i,j,k,l;
while(scanf("%d",&n)!=EOF){
for(i=0;i<n;i++)
{
scanf("%d",&lef[i]);
}
qsort(lef,n,sizeof(int),cmp);
long long int sum=0;
for(i=1;i<n;i++)
{
lef[i]+=lef[i-1];
sum+=lef[i];
k=lef[i];
for(j=i+1;j<n;j++)
{
if(k>lef[j])
{
lef[j-1]=lef[j];
}else {
break;
}
}
lef[j-1]=k;
}
printf("%lld\n",sum);
}
return 0;
} |
但是很不爽阿，感觉这种代码不是我的风格，于是打算用stl重新写一遍，于是我就开始用stl折腾了。。。
之后就出了一个效率好多了的stl版本。。。
6365653 zerob13 3253 Accepted 348K 32MS C++ 819B 2010-01-24 15:18:24
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| #include<stdio.h>
#include<string.h>
#include<queue>
#include<stdlib.h>
using namespace std;
int lef;
int n;
int cmp(const void *a,const void *b)
{
return *(int*)a-*(int*)b;
}
struct node{
int a;
friend bool operator< (node n1, node n2)
{
return n1.a > n2.a;
}
};
priority_queue<node>zerob;
int main (int argc, char * const argv[]) {
int i,j,k,l;
node kk;
while(scanf("%d",&n)!=EOF){
while(!zerob.empty()){
zerob.pop();
}
for(i=0;i<n;i++)
{
scanf("%d",&lef);
kk.a=lef;
zerob.push(kk);
}
long long int sum=0;
while(zerob.size()>1)
{
node a=zerob.top();
zerob.pop();
node b=zerob.top();
zerob.pop();
sum+=a.a+b.a;
kk.a=a.a+b.a;
zerob.push(kk);
}
printf("%lld\n",sum);
}
return 0;
} |
268 views acm, code, pku3252, 哈夫曼, 数据结构, 树, 算法, 编程
06十一
归类于程序人生
2 条评论
hdu的1251
上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
| import java.util.*;
/**
*
* @author yanglingfeng
*/
class TernaryTree {
private class Node {
char m_char;
Node left, right, middle;
boolean end;
int co;
public Node(char ch, boolean e) {
m_char = ch;
end = e;
co=0;
}
public Node(char ch, boolean e, Node leftc, Node rightc, Node middlec) {
m_char = ch;
end = e;
left = leftc;
right = rightc;
middle = middlec;
}
}
private Node root;
private int count;
/**
* 初始化三叉树
*/
public TernaryTree() {
clear();
}
/**
* 清除三叉树
*/
public final void clear() {
root = null;
count = 0;
}
/**
* 插入一个字符串
* @param s
*/
public void insert(String s) {
root = insert(root, s, 0);
}
/**
* 返回三叉树大小
* @return
*/
public int size() {
return count;
}
/**
* 返回是否能够找到字符串s
* @param s
* @return boolean
*/
public boolean contains(String s) {
return search(root, s, 0) != null;
}
public int count(String s) {
Node a= search(root, s, 0);
if(a!=null){
return a.co;
}else
return 0;
}
private Node search(Node ref, String s, int pos) {
if (ref == null) {
return null;
} else {
int cmp = s.charAt(pos) - ref.m_char;
if (cmp < 0) {
return search(ref.left, s, pos);
} else if (cmp > 0) {
return search(ref.right, s, pos);
} else {
if (1 + pos == s.length()) {
return ref;
}
return search(ref.middle, s, pos + 1);
}
}
}
private Node insert(Node ref, String s, int i) {
if (ref == null) {
count++;
ref = new Node(s.charAt(i), false);
}
int cmp = s.charAt(i) - ref.m_char;
if (cmp < 0) {
ref.left = insert(ref.left, s, i);
} else if (cmp > 0) {
ref.right = insert(ref.right, s, i);
} else {
if (i + 1 == s.length()) {
ref.end = true;
} else {
ref.middle = insert(ref.middle, s, i + 1);
}
ref.co++;
}
return ref;
}
}
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
// TODO code application logic here
TernaryTree dic=new TernaryTree();
Scanner inp=new Scanner(System.in);
String a=new String();
int mo=0;
while(inp.hasNextLine()){
a=inp.nextLine();
if(a.equals("")){
mo=1;
continue;
}
if(mo==0)
{
dic.insert(a);
}else
{
System.out.println(dic.count(a));
}
}
}
} |
341 views 1251, acm, hdu, java, oj, 三叉树, 数据结构
26八
归类于程序人生
参与评论
以前写的婚配模板，测试了多个题目，挺可靠的，于是发出来共享~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| //婚配问题 by 混沌的云Knight
//传入男人数n，女人数m
//男人对女人好感矩阵mtw，女人对男人好感矩阵wtm，匹配矩阵
//match1，match2 匹配成功返回1，否则返回0
//match1,match2返回一个成功婚姻匹配,未匹配顶点match值为-1
#include<string.h>
#define MAXN 502
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
char W[MAXN][MAXN];
int _O[MAXN];
int marry(int n,int m,int mtw[][MAXN],int wtm[][MAXN],int *match1,int *match2)
{
int i=0,j,h,M,t=-1,s1=n,s2=m;
memset(W,0,sizeof(W));
for(_clr(match1),_clr(match2);i<n;_O[++t]=i,i++);
while(t>=0)
{
h=_O[t--];
for(M=-1,i=0;i<m;i++)
if(!W[h][i]&&(M==-1||mtw[h][i]>mtw[h][M]))
M=i;
W[h][M]=1;
if(match2[M]==-1)
{
match1[h]=M;
match2[M]=h;
s1--;s2--;
}else if(wtm[M][h]>wtm[M][match2[M]])
{
match1[match2[M]]=-1;
_O[++t]=match2[M];
match1[h]=M;
match2[M]=h;
}else
_O[++t]=h;
}
return (!s1)||(!s2);
} |
331 views acm, C#, code, cpp, 匹配, 图论, 婚姻匹配, 模板, 稳定婚姻, 算法, 编程
25八
归类于心情日志
8 条评论
虽然早就知道结局，但是总还是有那么一些不舍的。。。
今年的区域赛是去不了了，明年再争取吧。。。
话说，自己的不努力的确是一个重要的原因，但是我们的失败其实在很久之前就已经表现出来了。
dragon如此看重结果和对个人能力的无比看重其实让我和ryb一直很不好受。。。
我们都知道，大牛们的确会很多算法，但是，不能因为这样，就要求我们两个什么都去学会。。我们，至少我，真的做不到。。。
就连回来的路上，我们说起下半年还练不练的问题的时候，dragon听到我说了一句：“我下半年还是会做自己喜欢的题目的。”而和我争吵起来。。。
dragon总是认为，个人必须什么都会，才能组队时做好，所以他一直反对我做我喜欢的题目，总觉得我不去做就是不对的。我承认我的确有些偏，而且不是很认真，但是我的确很喜欢这个活动。
我喜欢结构化的东西，当然我知道对于竞赛来说，这是远远不够的，的确dragon说的很对，他设想的都是最优的状态，但是，我真的做不到。。。
所以，我们队一直有这样那样的问题，就是因为大家的观点分歧太大了啊。。。
好吧，虽然我暑假没能拿到参赛机会，但是我并没有很大的失望。
真如某个友人傍晚的时候听说我的事情后问我：“你做这个的时候快乐过么？”
我回忆，虽然最后的日子挺压抑的，挺痛苦的，但是，很大的一段时间，虽然有抱怨，但是还是快乐的。
于是乎，值得了。
正如刘sir说的，这也是一种锻炼啊。。。
人生怎么可能一帆风顺呢，不管是什么原因导致的失败，只要再站起来就可以了，过去的就过去吧。
那么，暂别了acm，假如还有机会，我还是会用自己的方法努力一把的~
混沌的云Knight
记于2009年8月25日晚23：05分
185 views acm, lose, sadly, 兴趣, 心情日志, 日志, 日记
24八
归类于程序人生
参与评论
先献上java版八数码的代码，未使用启发式搜索，只是将所有状态预处理，然后直接读出罢了。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
| /*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
import java.util.*;
/**
*
* @author Zerob13
*/
class node{
int[][] state;
int pre,tem;
char dir;
node()
{
int i,j,k=1;
state=new int[3][3];
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
state[i][j]=k++;
}
}
pre=tem=dir=0;
}
int HASH()
{
int fac[]={1,1,2,6,24,120,720,5040,40320,362880};
int i,j,ret=0,num=0;
int[] b=new int[10];
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
b[ret++]=state[i][j];
}
ret=0;
for(i=0;i<9;i++)
{
num=0;
for(j=0;j<i;j++)
{
if(b[j]>b[i]) num++;
}
ret+=fac[i]*num;
}
tem=ret;
return ret;
}
}
public class Main {
static char output(int q)
{
if(q==1)
return 'u';
if(q==2)
return 'd';
if(q==3)
return 'r';
if(q==0)
return 'l';
return 0;
}
public static void main(String[] args) {
node[] queue=new node[362882];
byte[] hash=new byte[362882];
int[] sa=new int[362882];
int i,top,la,j,aaa,con;
for(i=0;i<362882;i++)hash[i]=0;
int[][] dir={{0,1},{1,0},{-1,0},{0,-1}};
top=la=0;
node head = new node(),p=new node();
aaa=1;
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
head.state[i][j]=aaa;
aaa++;
}
}
head.pre=-1;
head.HASH();
head.dir=0;
hash[head.tem]=1;
top=0;
la=1;
con=0;
queue[0]=new node();
for(i=0;i<3;i++)
{
for (j = 0; j < 3; j++) {
queue[0].state[i][j] = head.state[i][j];
}
}
queue[0].pre = head.pre;
queue[0].dir = head.dir;
queue[0].tem = head.tem;
while(top<la)
{
int ii,e,f,x,y,tem;
for(ii=0;ii<3;ii++)
{
for(j=0;j<3;j++)
{
head.state[ii][j]=queue[top].state[ii][j];
}
}
head.pre=queue[top].pre;
head.dir=queue[top].dir;
head.tem=queue[top].tem;
sa[head.tem]=top;
e=f=0;
for(ii=0;ii<3;ii++)
for(j=0;j<3;j++)
{
p.state[ii][j]=head.state[ii][j];
if(p.state[ii][j]==9)
{e=ii;f=j;}
}
for(i=0;i<4;i++)
{
x=dir[i][0]+e;
y=dir[i][1]+f;
if(x<0||y<0||x>=3||y>=3)
continue;
p.state[x][y]^=p.state[e][f];
p.state[e][f]^=p.state[x][y];
p.state[x][y]^=p.state[e][f];
tem=p.HASH();
if(hash[tem]==0)
{
p.pre=top;
p.tem=tem;
p.dir=output(i);
hash[tem]=1;
queue[la]=new node();
for(ii=0;ii<3;ii++)
{
for(j=0;j<3;j++)
{
queue[la].state[ii][j]=p.state[ii][j];
}
}
queue[la].pre=p.pre;
queue[la].dir=p.dir;
queue[la].tem=p.tem;
la++;
}
p.state[x][y]^=p.state[e][f];
p.state[e][f]^=p.state[x][y];
p.state[x][y]^=p.state[e][f];
}
top++;
}
Scanner in=new Scanner(System.in);
String kk;
while(in.hasNextLine())
{
kk=in.nextLine();
int[] s=new int[100];
int bbb=0;
aaa=0;
for(i=0;i<kk.length();i++)
{
if(kk.charAt(i)!=' ')
{
if(kk.charAt(i)=='x')
{
s[aaa++]=9;
}else
s[aaa++]=kk.charAt(i)-'0';
}
}
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
{
head.state[i][j]=s[bbb++];
}
}
aaa=head.HASH();
if(hash[aaa]!=0)
{
node star=queue[sa[aaa]];
while(star.pre!=-1)
{
System.out.print(star.dir);
star=queue[star.pre];
}
System.out.println("");
}else
{
System.out.println("unsolvable");
}
}
}
} |
151 views acm, eight, java, 广搜, 搜索, 预处理
23八
归类于程序人生
2 条评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
| #include <stdio.h>
#include <math.h>
#include<string.h>
const int maxn = 501;
const double eps = 1e-6;
struct TPoint
{
double x, y;
TPoint()
{
x=y=0;
}
TPoint operator-(TPoint &a)
{
TPoint p1;
p1.x = x - a.x;
p1.y = y - a.y;
return p1;
}
};
struct TCircle
{
double r;
TPoint centre;
TCircle()
{
r=0;
centre.x=centre.y=0;
}
};
struct TTriangle
{
TPoint t[3];
TTriangle()
{
int i;
for(i=0;i<3;i++)
{
t[i].x=t[i].y=0;
}
}
};
TCircle c;
TPoint a[maxn];
double distance(TPoint p1, TPoint p2)
{
TPoint p3;
p3.x = p2.x - p1.x;
p3.y = p2.y - p1.y;
return sqrt(p3.x * p3.x + p3.y * p3.y);
}
double triangleArea(TTriangle t)
{
TPoint p1, p2;
p1 = t.t[1] - t.t[0];
p2 = t.t[2] - t.t[0];
return fabs(p1.x * p2.y - p1.y * p2.x) / 2;
}
TCircle circumcircleOfTriangle(TTriangle t)
{
// 三角形的外接圆
TCircle tmp;
double a, b, c, c1, c2;
double xA, yA, xB, yB, xC, yC;
a = distance(t.t[0], t.t[1]);
b = distance(t.t[1], t.t[2]);
c = distance(t.t[2], t.t[0]);
//根据S = a * b * c / R / 4;求半径R
tmp.r = a * b * c / triangleArea(t) / 4;
xA = t.t[0].x; yA = t.t[0].y;
xB = t.t[1].x; yB = t.t[1].y;
xC = t.t[2].x; yC = t.t[2].y;
c1 = (xA * xA + yA * yA - xB * xB - yB * yB) / 2;
c2 = (xA * xA + yA * yA - xC * xC - yC * yC) / 2;
tmp.centre.x = (c1 * (yA - yC) - c2 * (yA - yB)) /
((xA - xB) * (yA - yC) - (xA - xC) * (yA - yB));
tmp.centre.y = (c1 * (xA - xC) - c2 * (xA - xB)) /
((yA - yB) * (xA - xC) - (yA - yC) * (xA - xB));
return tmp;
}
TCircle MinCircle2(int tce, TTriangle ce)
{
TCircle tmp;
if(tce == 0) tmp.r = -2;
else if(tce == 1)
{
tmp.centre = ce.t[0];
tmp.r = 0;
}
else if(tce == 2)
{
tmp.r = distance(ce.t[0], ce.t[1]) / 2;
tmp.centre.x = (ce.t[0].x + ce.t[1].x) / 2;
tmp.centre.y = (ce.t[0].y + ce.t[1].y) / 2;
}
else if(tce == 3) tmp = circumcircleOfTriangle(ce);
return tmp;
}
void MinCircle(int t, int tce, TTriangle ce)
{
int i, j;
TPoint tmp;
c = MinCircle2(tce, ce);
if(tce == 3) return;
for(i = 1;i <= t;i++)
{
if(distance(a[i], c.centre) > c.r)
{
ce.t[tce] = a[i];
MinCircle(i - 1, tce + 1, ce);
tmp = a[i];
for(j = i;j >= 2;j--)
{
a[j] = a[j - 1];
}
a[1] = tmp;
}
}
}
void run(int n)
{
TTriangle ce;
int i;
MinCircle(n, 0, ce);
printf("%.2lf\n", c.centre.x, c.centre.y, c.r);// 输出部分
}
int main()
{
int n;
while(scanf("%d", &n) != EOF && n)
{
for(int i = 1;i <= n;i++)
scanf("%lf %lf", &a[i].x, &a[i].y);// 输入
run(n);
}
return 0;
} |
246 views acm, code, cpp, 最小圆, 模板, 程序人生
