2019.2.17集训

课程表

上午
  • 平衡树
下午
  • 树链剖分

笔记(本人太菜了,上了一天课没听懂,暂时咕咕咕)

  1. 平衡树
  2. 树链剖分

2019.2.16实验集训

课程表

上午
  • 线段树
下午
  • 树状数组
晚上
  • 考试:线段树$and$树状数组(但是我不用考,哈哈哈哈哈哈

笔记

  1. 线段树

    • 概述:一种二叉树,类似区间树,主要用于解决连续区间的动态查询问题(单点/区间修改、区间最值/求和等等)

    • 建树:很显然,线段树是个完全二叉树,所以可以直接使用数组在储存这个树,连边都不用存了。
    1
    int SegTree[N];

洛谷1194 买礼物

  • 图论的最后这道题竟然这么简单,只有建图的问题,其他就是非常基础最小生成树了。
  • 优惠就是图中的一条边,不要建边两次,最小生成树我用的是$Kruskal$。
  • Code:
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
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int u,v,w;
}e[250005];
int A,B,cnt,tot=1,ans,f[505];
bool cmp(node x,node y){
return x.w<y.w;
}
int find(int x){
if(f[x]==x) return x;
return f[x]=find(f[x]);
}
void Update(int a,int b){
int x=find(a);
int y=find(b);
if(x!=y) f[x]=y;
return;
}
void addEdge(int a,int b,int c){
cnt++;
e[cnt].u=a;
e[cnt].v=b;
e[cnt].w=c;
return;
}
void kruskal(){
int i=1;
while (i<=cnt&&tot<=B){
if (find(e[i].u)!=find(e[i].v)){
tot++;
ans+=e[i].w;
Update(e[i].u,e[i].v);
}
i++;
}
return;
}
int main(){
scanf("%d%d",&A,&B);
for(int i=1;i<=B;i++)
for(int j=1;j<=B;j++){
int w;
scanf("%d",&w);
if(i<j&&w!=0) addEdge(i,j,w);//0的情况要特判!
}
for(int i=1;i<=B;i++) addEdge(0,i,A);
for(int i=0;i<=B;i++) f[i]=i;
sort(e+1,e+cnt+1,cmp);
kruskal();
printf("%d\n",ans);
return 0;
}

洛谷1144 最短路计数

  • 本来写了个和一些题解比较相像的什么$SPFA$、$Dijkstra$之类的,后面出$bug$懒得弄了,就看了眼题解,第一篇$dalao$用$bfs$做,做法十分清爽,不得不orz。但是为什么很多$dalao$写的题解都比较简略呢。。。。看来我太菜了吧QAQ

  • 所以我就写了一篇$dalao​$代码较详细的解释。因为边的权值都为1,所以这道题才能用$bfs​$,$dalao​$说的:

    一个点最短路一定经过了一个层数比它少一的结点(否则不是最短路)。

    所以用每个相邻且层数比当前结点层数少一的点更新当前点的路径跳数即可。

    有一些人看不懂,这中间的层数就是离源点(顶点1)的距离,或者说是$bfs$搜索树的深度。所以这个最短路一定是沿着从深度比它少1的结点来的,不然它就不算最短路,这个跳数应该就是把最短路数量从旁边的点转移过来。

  • Code:更多解释请看代码

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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 1<<30
#define Mod 100003
using namespace std;
vector<int> G[1000005];//注意这是2维数组,用来存每一个点所连的边,而题目中有10^6个点,所以是10^6+5
queue<int>Q;//bfs所需要的队列
int dep[1000005],cnt[1000005];//dep是每个点对于源点的深度,cnt储存答案,即到点i的最短路个数
bool vis[1000005];//判断点是否使用
int main(){
int N,M;
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++){
int x,y;scanf("%d%d",&x,&y);
G[x].push_back(y);//存边,无向图存有向边两次
G[y].push_back(x);
}
dep[1]=0;
vis[1]=1;
Q.push(1);
cnt[1]=1;
while(!Q.empty()){//bfs核心代码
int x=Q.front();
Q.pop();
for(int i=0;i<G[x].size();i++){//遍历点所连的每一条边
int t=G[x][i];
if(!vis[t]){
vis[t]=1;
dep[t]=dep[x]+1;//深度+1
Q.push(t);
}
if(dep[t]==dep[x]+1)//dalao说的最后一句话,这个点直接从旁边深度-1的结点添加最短路数量
cnt[t]=(cnt[t]+cnt[x])%Mod;//不要忘记要%Mod
}
}
for(int i=1;i<=N;i++)
printf("%d\n",cnt[i]);
return 0;
}
  • %%%GGN_2015
  • 本人个人Blog,欢迎$dalao​$进来拍砖,交换友链什么的^ _ ^

洛谷1074 靶形数组

  • emm,需要一些剪枝的一道题(废话),要从0的个数最少的行开始搜,很显然这样搜出去的分支就会少很多。
  • 因为我太菜了,所以我这题抄了下题解……
  • Code:
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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=10;
int a[N][N],ans[N][N],vis[3][N][N],b[82],maxn,flag;
struct Row{
int h,zero_cnt;
}row[N];
int cmp(Row row1,Row row2){
return row1.zero_cnt<row2.zero_cnt;
}
int getGrid(int x,int y){//获取在哪个小格子
if(x>=1&&x<=3){
if(y>=1&&y<=3) return 1;
else if(y>=4&&y<=6) return 2;
else return 3;
}
if(x>=4&&x<=6){
if(y>=1&&y<=3) return 4;
else if(y>=4&&y<=6) return 5;
else return 6;
}
if(x>=7&&x<=9){
if(y>=1&&y<=3) return 7;
else if(y>=4&&y<=6) return 8;
else return 9;
}
}
int getScore(int x,int y){//获取搜索完后的得分
if(x==1||y==1||x==9||y==9) return 6;
else if(x==2||y==2||x==8||y==8) return 7;
else if(x==3||y==3||x==7||y==7) return 8;
else if(x==4||y==4||x==6||y==6) return 9;
else return 10;
}
int cal(){
int sum=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++)
sum+=ans[i][j]*getScore(i,j);
return sum;
}
void dfs(int xh){
if(xh>81){
flag=1;
maxn=max(maxn,cal());
return;
}
int x=b[xh]/9+1;
int y=b[xh]%9;
if(y==0)
x=b[xh]/9,y=9;
if(!a[x][y]){
for(int j=1;j<=9;j++){
int g=getGrid(x,y);
if(!vis[0][x][j]&&!vis[1][y][j]&&!vis[2][g][j]){
ans[x][y]=j;
vis[0][x][j]=1,vis[1][y][j]=1,vis[2][g][j]=1;
dfs(xh+1);
vis[0][x][j]=0,vis[1][y][j]=0,vis[2][g][j]=0;
}
}
}
else dfs(xh+1);
return;
}
void Init(){
for(int i=1;i<=9;i++){
int cnt=0;
for(int j=1;j<=9;j++){
cin>>a[i][j];
if(a[i][j]==0)
cnt++;
else{
int v=a[i][j];
int g=getGrid(i,j);
ans[i][j]=v;
vis[0][i][v]=1,vis[1][j][v]=1,vis[2][g][v]=1;
}
}
row[i].h=i;
row[i].zero_cnt=cnt;
}
sort(row+1,row+9+1,cmp);
int num=0;
for(int i=1;i<=9;i++)
for(int j=1;j<=9;j++){
int x=row[i].h,y=j;
num++;
b[num]=(x-1)*9+y;
}
return;
}
int main(){
Init();
dfs(1);
if(flag)
cout<<maxn<<endl;
else
cout<<-1<<endl;
return 0;
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×