分类目录归档：数据结构

洛谷/USACO 美国血统 American Heritage

洛谷题号：P1827
做过二百遍的二叉树重构了，老套路：

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

#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<list>
#include<cstring>
#include<cassert>
using namespace std;
char in[30],pre[30];
#define NULL 0
struct node{
char value;
node * left;
node * right;
node(){
value = '\0';
left = NULL;
right = NULL;
}
};
int find_in(int in_s, int in_e, char node){
for (int i = in_s; i <= in_e; i++){
if (in[i] == node)return i;
}
assert(0);
return -1;
}
void BuildTree(int in_s, int in_e, int pre_s, int pre_e, node * root){
if (in_s == in_e&&pre_s == pre_e){
root->value = pre[pre_s];
return;
}
if (in_s > in_e || pre_s > pre_e){
return;
}
root->value = pre[pre_s];
int pos_in = find_in(in_s, in_e, pre[pre_s]);
root->left = new node;
BuildTree(in_s, pos_in - 1, pre_s + 1, pre_s + pos_in - in_s, root->left);
root->right = new node;
BuildTree(pos_in + 1, in_e, pre_s + pos_in - in_s + 1, pre_e, root->right);
}
void postorder_traversal(node * ptr){
if (ptr->left != NULL)postorder_traversal(ptr->left);
if (ptr->right != NULL)postorder_traversal(ptr->right);
if (ptr->value != '\0')cout << ptr->value;
}
int main(){
ios::sync_with_stdio(false);
cin >> in+1 >> pre+1;
int len = 1;
while (in[len])len++;
len--;
node * root = new node;
BuildTree(1, len, 1, len, root);
postorder_traversal(root);
cout << endl;
}

洛谷/USACO 家的范围 Home on the Range

发表评论

洛谷题号：P2733
思路很简单，我是参考洛谷最大正方形这道题来写的，都是二维前缀和。

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

int n;
int arr[260][260];
int sum[260][260];
int cow[260];
inline int getSquareSum(int x, int y, int e){
x--; y--;
return sum[x + e][y + e] - sum[x + e][y] - sum[x][y + e] + sum[x][y];
}
int main(){
scanf("%d", &n);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
scanf("%1d", &arr[i][j]);
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + arr[i][j];
}
}
cow[1] = 1;
for (int e = 2; e <= 250 && cow[e - 1] > 0; e++){
for (int x = 1; x <= n - e + 1; x++){
for (int y = 1; y <= n - e + 1; y++){
if (getSquareSum(x, y, e) == e*e)
cow[e]++;
}
}
}
for (int i = 2; i <= 250 && cow[i] > 0; i++){
printf("%d %d\n", i, cow[i]);
}
}

洛谷/USACO 魔板 Magic Squares

发表评论

洛谷题号：P2730
THUOJ上也有这道题目，题目输入输出格式略微有不同，基本原理相同。但是THUOJ不能使用任何数据结构，全部都要自己写。

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

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
struct status{
int arr[9];
};
string s_result;
template <typename T> struct node{
T data;
node<T> * next;
};
template <typename T> struct list{
node<T> * head;
int _size;
list(){
_size = 0;
head = NULL;
}
~list(){
node <T> * current = head;
node <T> * next;
while (current != NULL){
next = current->next;
delete current;
current = next;
}
}
void insert(T & data){
_size++;
node<T> * ptr = new node<T>;
ptr->data = data;
ptr->next = head;
head = ptr;
}
bool search(T & target){
node<T> * ptr = head;
while (ptr != NULL){
if (ptr->data == target)return true;
ptr = ptr->next;
}
return false;
}
};
list<int> hashtable[50021];
inline int h(const int m){
return (2 * m + 29) % 50021;
}
inline int status2int(status m){
int t = 0;
for (int i = 1; i <= 8; i++){
t *= 10;
t += m.arr[i];
}
return t;
}
inline status int2status(int t){
status m;
for (int i = 8; i >= 1; i--){
m.arr[i] = t % 10;
t /= 10;
}
return m;
}
inline int change(int status_m, char type){
status m = int2status(status_m);
int t;
switch (type){
case 'A':
swap(m.arr[1], m.arr[8]);
swap(m.arr[2], m.arr[7]);
swap(m.arr[3], m.arr[6]);
swap(m.arr[4], m.arr[5]);
break;
case 'B':
t = m.arr[4];
for (int i = 4; i >= 2; i--)m.arr[i] = m.arr[i - 1];
m.arr[1] = t;
t = m.arr[5];
for (int i = 5; i <= 7; i++)m.arr[i] = m.arr[i + 1];
m.arr[8] = t;
break;
case 'C':
t = m.arr[2];
m.arr[2] = m.arr[7];
m.arr[7] = m.arr[6];
m.arr[6] = m.arr[3];
m.arr[3] = t;
break;
}
return status2int(m);
}
int BFS(int m){
queue<int> q;
queue<int> qi;
queue<string> qs;
q.push(12345678);
qi.push(0);
qs.push("");
while (!q.empty()){
int t = q.front();
q.pop();
int time = qi.front();
qi.pop();
string str = qs.front();
qs.pop();
if (t == m){
s_result = str;
return time;
}
else if (time > 30){
continue;
}
else{
int s = change(t, 'A');
if (!hashtable[h(s)].search(s)){
hashtable[h(s)].insert(s);
q.push(s); qi.push(time + 1); qs.push(str + 'A');
}
s = change(t, 'B');
if (!hashtable[h(s)].search(s)){
hashtable[h(s)].insert(s);
q.push(s); qi.push(time + 1); qs.push(str + 'B');
}
s = change(t, 'C');
if (!hashtable[h(s)].search(s)){
hashtable[h(s)].insert(s);
q.push(s); qi.push(time + 1); qs.push(str + 'C');
}
}
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
status m;
for (int i = 1; i <= 8; i++){
cin >> m.arr[i];
}
cout << BFS(status2int(m)) << endl;
cout << s_result << endl;

}

洛谷 A % B Problem

发表评论

题目编号：1865
用到的思想，一维前缀和，埃式素数筛

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

#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
bool prime[1000005];
int prefixsum[1000005];
int main(){
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
memset(prime,true,sizeof(prime));
prime[1]=false;
for(int i=2;i<=m;i++){
if(!prime[i])continue;
for(int j=2;i*j<=m;j++){
prime[i*j]=false;
}
}
for(int i=1;i<=m;i++){
prefixsum[i]=prefixsum[i-1]+prime[i];
}
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
if(l<1||r>m){
cout<<"Crossing the line"<<endl;
continue;
}
cout<<prefixsum[r]-prefixsum[l-1]<<endl;
}
}

洛谷最大正方形

发表评论

题号：1387
参考题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1387
作者: hychychyc 更新时间: 2017-06-06 11:25

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

#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#include<queue>
#include<cstdlib>
#include<cstring>
#include<map>
using namespace std;
int n, m;
int arr[105][105];
int sum[105][105];
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> arr[i][j];
}
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + arr[i][j]; //二维前缀和
}
}
int maxn = 1;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
for (int e = maxn; i + e <= n&&j + e <= m; e++){
int w = sum[i + e][j + e] - sum[i][j + e] - sum[i + e][j] + sum[i][j]; //这个用二维前缀和计算正方形和
if (e*e == w){
maxn = max(maxn, e);
}
else
break;
}
}
}
cout << maxn;
}

~~放上一张前缀和的图片，写的也很不清楚，也许有助于理解。~~

20180802更新：
上面代码都是错误的！！！！！！！！！
二维前缀和方程是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int arr[105][105];
int main(){
cin >> n >> m;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)cin >> arr[i][j];
for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + arr[i][j];
for (int k = min(n, m); k > 0; k--) {
for (int i = 1; i <= n - k + 1; i++) {
for (int j = 1; j <= m - k + 1; j++) {
if (k*k == arr[i + k - 1][j + k - 1] - arr[i - 1][j + k - 1] - arr[i + k - 1][j - 1] + arr[i - 1][j - 1]) { //参考这里
cout << k;
return 0;
}
}
}
}
}

动态规划做法：题解https://www.luogu.org/blog/user23035/solution-p1387

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
int arr[105][105];
int main() {
cin >> n >> m;
int ans = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
cin >> arr[i][j];
if(arr[i][j])arr[i][j] = min(min(arr[i - 1][j], arr[i][j - 1]), arr[i - 1][j - 1]) + 1;
ans = max(ans, arr[i][j]);
}
cout << ans;
}

洛谷银河英雄传说

发表评论

题号：P1196
参见题解：https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1196
结合源代码阅读才好……
推荐题解作者：作者: 超神火星人更新时间: 2017-04-29 09:14

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

#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<cstring>
#include<utility>
int father[30005],size[30005],front[30005];
using namespace std;
int sfind(int node){
if (father[node] == -1)return node;
int fn = sfind(father[node]);
front[node] += front[father[node]];
return father[node]=fn;
}
int main(){
for (int i = 1; i <= 30000; i++){
father[i] = -1;
size[i] = 1;
front[i] = 0;
}
ios::sync_with_stdio(false);
int n;
cin >> n;
while (n--){
char c;
int rf1, rf2;
cin >> c >> rf1 >> rf2;
int fa1 = sfind(rf1);
int fa2 = sfind(rf2);
switch (c){
case 'M':
front[fa1] += size[fa2];
father[fa1] = fa2;
size[fa2] += size[fa1];
size[fa1] = 0;
break;
case 'C':
if (fa1 != fa2)cout << "-1" << endl;
else cout << abs(front[rf1] - front[rf2])-1 << endl;
break;
}
}
}

20180815更新：
重做了这道题，还是看的这个人的题解。。。。

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

#include<iostream>
using namespace std;
int t;
int father[30005],front[30005],num[30005];
int _find(int node){
if(father[node]==0)return node;
int fn=_find(father[node]);
front[node]+=front[father[node]];
return father[node]=fn;
}
int main(){
ios::sync_with_stdio(false);
for(int i=1;i<=30000;i++)num[i]=1;
cin>>t;
while(t--){
char op;
int x,y;
cin>>op>>x>>y;
int fx=_find(x),fy=_find(y);
if(op=='M'){
front[fx]+=num[fy];
father[fx]=fy;
num[fy]+=num[fx];
num[fx]=0;
}else{
if(fx!=fy)cout<<-1<<endl;
else cout<<abs(front[x]-front[y])-1<<endl;
}
}
}

发现越到后面就越感觉是在抄题解怎么办，想也想不出来。

洛谷关押罪犯

发表评论

题号：1525
参见题解：作者: 超级范范更新时间: 2017-07-23 17:05
https://www.luogu.org/wiki/show?name=%E9%A2%98%E8%A7%A3+P1525

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

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int father[40005];
struct s{
int u, v, w;
bool operator < (s & s1){
return w>s1.w;
}
}arr[100005];
int _find(int node){
if (father[node] == -1)return node;
return father[node] = _find(father[node]);
}
void merge(int x, int y){
x = _find(x);
y = _find(y);
if (x != y)father[x] = y;
}
bool sameset(int x, int y){
return _find(x) == _find(y);
}
int main(){
memset(father, -1, sizeof(father));
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= m; i++){
cin >> arr[i].u >> arr[i].v >> arr[i].w;
}
sort(arr + 1, arr + m + 1);
int maxw = 0;
for (int i = 1; i <= m; i++){
if (sameset(arr[i].u, arr[i].v)){
if (arr[i].w > maxw){
cout << arr[i].w;
return 0;
}
}
else{
merge(arr[i].u, arr[i].v + n);
merge(arr[i].v, arr[i].u + n);
}
}
cout << 0;
}

20180814更新：除了并查集做法还有二分图做法，应该也很好做，不写了。
题解：https://www.luogu.org/blog/Kesdiael3/solution-p1525

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

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct p{
int a,b,c;
bool operator < (const p& p2) const{
return c>p2.c;
}
}ps[100005];
int father[40005];
int _find(int x){
if(father[x]==0)return x;
return father[x]=_find(father[x]);
}
bool _union(int x,int y){
if(_find(x)==_find(y))return false;
father[_find(x)]=_find(y);
return true;
}
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;i++)cin>>ps[i].a>>ps[i].b>>ps[i].c;
sort(ps+1,ps+m+1);
for(int i=1;i<=m;i++){
if(_find(ps[i].a)==_find(ps[i].b)){
cout<<ps[i].c;
return 0;
}else{
_union(ps[i].a,ps[i].b+n);
_union(ps[i].b,ps[i].a+n);
}
}
cout<<0;
}

计蒜客 NOIP模拟赛（一） D1T2

发表评论

原题：https://nanti.jisuanke.com/t/16446
北京市八十中的cjr说（特别感谢cjr提供思路，我进行了一下整理）：考虑每条边对答案的贡献：每条边肯定是一个父亲节点与一个儿子节点相连，该边对答案的贡献是 $size[i]*(n-size[i])*w$ ，其中 $i$ 为儿子节点， $size[i]$ 为该边的儿子节点所对应的子树大小（包括该儿子节点）， $w[i]$ 为边权， $n$ 为总节点数。可以这样做是利用了乘法原理。想象一下，假设一棵有根树，要计算从 $Node:n$ 到其它所有节点的最短距离：

该边必然要使用 $1*(n-1)$ 次，该边对答案的贡献就为 $1*(n-1)*w[i]$ 了。
子树大小由dfs算得即可，因为这是有根树。如果是图的话就不能这么干了，因为两个节点之间不仅仅又1条路径，这时候多源最短路只能用floyd做了。时间复杂度为 $O(n^3)$ 。
本题第一次计算任意两点间距离之和：初始化子树大小DFS复杂度 $O(n)$ ，算每条边的贡献 $O(n)$ ，更改边长复杂度 $O(1)$ 。

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

#include<iostream>
#include<list>
using namespace std;
int n,m;
long long father[100005],w[100005];
list<int> children[100005];
long long treesize[100005];
void dfs(int node){//获得子树大小
if(children[node].size()==0){
treesize[node]=1;
return;
}
long long tot=0;
for(list<int>::iterator i=children[node].begin();i!=children[node].end();i++){
dfs(*i);
tot+=treesize[*i];
}
treesize[node]=tot+1;
return;
}
int main(){
ios::sync_with_stdio(false);
cin>>n;
for(int i=2;i<=n;i++){
cin>>father[i]>>w[i];
children[father[i]].push_back(i);
}
dfs(1);
long long tot=0;
for(int i=2;i<=n;i++){
tot+=treesize[i]*(n-treesize[i])*w[i];
}
cout<<tot<<endl;
cin>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
long long change=treesize[a]*(n-treesize[a])*(b-w[a]);
tot+=change;
cout<<tot<<endl;
w[a]=b;
}
}

洛谷【模板】树状数组 1

发表评论

题号：3374

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<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
struct treearray{
const static int MAX=500005;
int C[MAX];
treearray(){
memset(C,0,sizeof(C));
}
int lowbit(int i){
return i&(-i);
}
void update(int i,int n){
while(i<=MAX){
C[i]+=n;
i+=lowbit(i);
}
}
int sum(int k){
int sum=0;
while(k>0){
sum+=C[k];
k-=lowbit(k);
}
return sum;
}
}ta;
int main(){
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
int t;
cin>>t;
ta.update(i,t);
}
for(int i=1;i<=m;i++){
int p1,p2,p3;
cin>>p1>>p2>>p3;
switch(p1){
case 1:
ta.update(p2,p3);
break;
case 2:
cout<<(ta.sum(p3)-ta.sum(p2-1))<<endl;
break;
}
}
}

数据结构邓俊辉 PA#3 重名剔除(Deduplicate)题解

发表评论

重名剔除(Deduplicate)

Description

Mr. Epicure is compiling an encyclopedia of food. He had collected a long list of candidates nominated by several belly-gods. As candidates in list are nominated by several people, duplication of name is inevitable. Mr. Epicure pay you a visit for help. He request you to remove all duplication, which is thought an easy task for you. So please hold this opportunity to be famous to all belly-gods.

Input

1 integer in fist line to denote the length of nomination list. In following n lines, each nomination is given in each line.

Output

All the duplicated nomination (only output once if duplication appears more multiple times), which is sorted in the order that duplication appears firstly.

Example

Input

10
brioche
camembert
cappelletti
savarin
cheddar
cappelletti
tortellni
croissant
brioche
mapotoufu

Output

cappelletti
brioche

Restrictions

1 < n < 6 * 10^5

All nominations are only in lowercase. No other character is included. Length of each item is not greater than 40.

Time: 2 sec

Memory: 256 MB

Hints

Hash

描述

Epicure先生正在编撰一本美食百科全书。为此，他已从众多的同好者那里搜集到了一份冗长的美食提名清单。既然源自多人之手，其中自然不乏重复的提名，故必须予以筛除。Epicure先生因此登门求助，并认定此事对你而言不过是“一碟小菜”，相信你不会错过在美食界扬名立万的这一良机

输入

第1行为1个整数n，表示提名清单的长度。以下n行各为一项提名

输出

所有出现重复的提名（多次重复的仅输出一次），且以其在原清单中首次出现重复（即第二次出现）的位置为序

样例

见英文题面

限制

1 < n < 6 * 10^5

提名均由小写字母组成，不含其它字符，且每项长度不超过40

时间：2 sec

空间：256 MB

提示

散列

继续阅读 →

杰克部落

梦想本不会发光，发光的是追梦的你

分类目录归档：数据结构

洛谷/USACO 美国血统 American Heritage

洛谷/USACO 家的范围 Home on the Range

洛谷/USACO 魔板 Magic Squares

洛谷 A % B Problem

洛谷最大正方形

洛谷银河英雄传说

洛谷关押罪犯

计蒜客 NOIP模拟赛（一） D1T2

洛谷【模板】树状数组 1

数据结构邓俊辉 PA#3 重名剔除(Deduplicate)题解

重名剔除(Deduplicate)

Description

Input

Output

Example

Restrictions

Hints

描述

输入

输出

样例

限制

提示

2024 年 5 月
一	二	三	四	五	六	日
		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