nyoj38 布线问题(最小生成树)

最小生成树算法有两个比较出名的,就是prime算法和krakusl算法。
首先说下krakusl算法。这个算法就是三个步骤,
第一,把每个顶点看成一个集合,边集按照权值大小排序。
第二,从最小的 边集开始,如果边的加入没有使得生成树成为环(并查集),则把该边加入生成树,否则,判断下一条边。
第三,当所有的顶点都加入了生成树,则所有加入的边构成最小生成树。
更加详细的请查找百度百科。
下面是我写的此题的代码。

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
#include<stdio.h>  
#include<stdlib.h>
#include<limits.h>
#include<string.h>
#include<algorithm>
#define min(a,b) a>b?b:a
using namespace std;
int L[502];
int father[502];
struct P{
int val;
int v1,v2;
}a[130000];
void work();
int v,e;
int sum;
int comp(const void *a,const void *b)
{
P *c=(P *)a;
P *d=(P *)b;
return c->val-d->val;
}
int main()
{
int T;
int i;
scanf("%d",&T);
while(T--)
{
memset(father,0,sizeof(father));
scanf("%d%d",&v,&e);
for(i=0;i<e;i++)
scanf("%d %d %d",&a[i].v2,&a[i].v1,&a[i].val);
for(i=0;i<v;i++)
scanf("%d",&L[i]);
sum=0;
qsort(a,e,sizeof(a[0]),comp);
work();
printf("%d\n",sum+*min_element(L,L+v));

}
return 0;
}
int find(int x)//并查集函数
{
if(x!=father[x]) father[x]=find(father[x]);
return father[x];
}
void work()//kruskal算法
{
int i;
for(i=1;i<=v;i++)
father[i]=i;
for(i=0;i<e;i++)
{
int t=find(a[i].v1);
int tt=find(a[i].v2);
if(t!=tt)
{
sum+=a[i].val;
father[t]=tt;
}
}
}

这个算法也不是很理解,但是pime算法我也不太清楚,我写不出来,所以要想了解此算法,请移步此处

nyoj123 士兵杀敌-四(树状数组)

这题真的是出乎我的意料,我一直以为是线段树,没想到还是树状数组。我是在网上看的思路,然后自己编代码。

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
#include<stdio.h>  
int N;
int c[1000005];
int lowbit(int i)
{
return i&(-i);
}
void updata(int i,int num)
{
while(i<=N)
{
c[i]+=num;
i+=lowbit(i);
}

}
int S(int i)
{
int sum=0;
while(i>0)
{
sum+=c[i];
i-=lowbit(i);
}
return sum;
}

int main()
{
int T;
int i;
int num,b,e;
scanf("%d%d",&T,&N);
char s[10];
while(T--)
{
scanf("%s",s);
if(s[0]=='A')
{
scanf("%d%d%d",&b,&e,&num);
updata(b,num);
updata(e+1,-num);///////只有这里变一下,然后就和三一样了。太,,,,,,,,,,,,,
}
else
{
scanf("%d",&i);
printf("%d\n",S(i));
}
}
return 0;

}

这个就不多解释了,会树状数组就会懂。这题放了好多天,今天终于ac了。

nyoj290 动物统计

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
#include<stdio.h>  
#include<string.h>
struct Tire{
int count;
Tire *next[26];
};
Tire *root;
int Max;
char Maxs[11];
char ss[11];
void insert(char *s)
{
if(root==NULL || *s=='\0')
return ;
Tire *p=root;
int i;
int n;
while(*s!='\0')
{
n=*s-'a';
if(p->next[n]==NULL)
{
Tire *temp=new Tire;
for(i=0;i<26;i++)
temp->next[i]=NULL;
temp->count=0;
p->next[n]=temp;
}
p=p->next[n];
s++;
}
p->count++;
if(p->count>Max){ Max=p->count; strcpy(Maxs,ss);}
}
int main()
{
int N;
int i;
while(~scanf("%d",&N))
{
root=new Tire;
for(i=0;i<26;i++)
root->next[i]=NULL;
root->count=0;
Max=0;
while(N--)
{
scanf("%s",ss);
insert(ss);
}
printf("%s %d\n",Maxs,Max);
}
return 0;

}

我觉得这题应该可以用哈希表做,但是我没试验过,不知道可不可以过,不过你们可以试试。

nyoj685 查找字符串(字典树)

刚学的字典树就用上了。

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
#include<stdio.h>//685查找字符串  
struct Trie{
int count;
Trie *next[30];
};
Trie *root;;
int turn(char c)//把字符转换成数组序号
{
if(c>='a' && c<='z')
return c-'a';
else if(c=='@')
return 26;//@
else
return 27;// +
}
void insert(char *s)//插入一个字符串
{
if(root==NULL || *s=='\0')
return ;
int i;
Trie *p=root;
while(*s!='\0')
{
if(p->next[turn(*s)]==NULL)//字符串不存在,则创建
{
Trie *temp=new Trie;
for(i=0;i<30;i++)
temp->next[i]=NULL;
temp->count=0;//付初值0
p->next[turn(*s)]=temp;
}
p=p->next[turn(*s)];
s++;
}
p->count++;
}
int Tfind(char *s)
{
Trie *p=root;
while(p!=NULL && *s!='\0')
{
p=p->next[turn(*s)];
s++;
}
return p==NULL?0:p->count;//注意如果字符串不存在也是0;不存在时候p==NULL
}
void del(Trie *p)//删除,oj提交的时候建议不删除,因为这个也耗时间。系统自动会回收,但是自己写的时候要注意。
{
int i;
for(i=0;i<30;i++)
{
if(p->next[i]!=NULL)
del(p->next[i]);
}
delete p;
}
int main()
{
int T;
int n,m;
int i;
char s[20];
scanf("%d",&T);
getchar();
while(T--)
{
root=new Trie;
for(i=0;i<30;i++)
root->next[i]=NULL;
root->count=0;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{
scanf("%s",s);
insert(s);
}
while(m--)
{
scanf("%s",s);
printf("%d\n",Tfind(s));
}
del(root);
}
return 0;
}

线段树算法(数组和链表两种实现)

虽然oj上超时了吧,那是因为需要优化,暂时没想到怎么优化,但是我学会了线段树,值得纪念一下。

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
#include<stdio.h>  
#define N 1000005
struct Node{
int left,right;
int val;
}c[N*4+5];
int father[N+5];
int n;
void build(int i,int l,int r)//建立一个以i为祖先的线段树
{
c[i].left=l;
c[i].right=r;
c[i].val=0;
if(l==r)
{
father[l]=i;
return ;
}
else
{
build(i*2 , l , (l+r)/2 );
build(i*2+1, (l+r)/2+1, r );
}
}
void insert(int l,int r,int num,int i)
{
if(l<=c[i].left && c[i].right<=r)
c[i].val+=num;
if(c[i].left==c[i].right)
return ;
if(l<=(c[i].left+c[i].right)/2) insert(l,r,num,i*2);
if(r>(c[i].left+c[i].right)/2) insert(l,r,num,i*2+1);
}
int main()
{
int T,M;
int num,l,r;
scanf("%d%d",&T,&M);
build(1,1,M);
char s[15];
while(T--)
{
scanf("%s",s);
if(s[0]=='A')
{
scanf("%d %d %d",&l,&r,&num);
insert(l,r,num,1);
}
else
{
scanf("%d",&n);
printf("%d\n",c[father[n]].val);
}

}
return 0;
}

这是南阳oj上第123题,超时。大家不要抄啊,自己看看如何优化吧,。我也正在想。会了在发一篇博客讲解一下。

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
#include<cstdio>  
#include<iostream>
//#define N 1000002
using namespace std;
struct Node{
int left,right;
Node *leftchild,*rightchild;
int cover;
};
Node *Root;
int n;
Node* build(int l,int r)
{
Node *root=new Node;
root->left=l;
root->right=r;
root->leftchild=NULL;
root->rightchild=NULL;
root->cover=0;
if(l<r)
{
int mid=(r+l)>>1;
root->leftchild = build(l,mid);
root->rightchild= build(mid+1,r);
}
return root;
}
void insert(int l,int r,int num,Node *root)
{
if(root==NULL)
return ;
if(l<=root->left && root->right<=r)
root->cover+=num;
if(l<=(root->left+root->right)/2) insert(l,r,num,root->leftchild);
if(r>(root->left+root->right)/2) insert(l,r,num,root->rightchild);


}
int f(int l,int r,Node *root)
{
if(root->left==n && root->right==n)
return root->cover;
else
{
int mid=(l+r)>>1;
if(n<=mid) f(l,mid,root->leftchild);
else f(mid+1,r,root->rightchild);
}

}
/*
void print(Node *p)
{
if(p->leftchild==NULL)
{
printf("[%d %d]->[%d] \n",p->left,p->right,p->cover);

}
else{
print(p->leftchild);
print(p->rightchild);
}
}*/
int main()
{
int num,l,r;
int T,M;
char s[15];

scanf("%d %d",&T,&M);
Root=build(1,M+2);
while(T--)
{
scanf("%s",s);
if(s[0]=='A')
{
scanf("%d %d %d",&l,&r,&num);
insert(l,r,num,Root);
}
else
{
scanf("%d",&n);
printf("%d\n",f(1,M+2,Root));

}
}
//print(Root);

return 0;

}

上面是数组写的,这个是链表写的。很不好意思,这个也超时。不知道你们能不能看懂,我写仅仅是纪念。