CodeVs天梯钻石Diamond题解
【摘要】
title: CodeVs天梯之Diamond date: 2017-12-28 tags:
天梯CodesVs categories: OI
CodeVs刷题攻略之Diamond
2...
title: CodeVs天梯之Diamond
date: 2017-12-28
tags:
- 天梯
- CodesVs
categories: OI
CodeVs刷题攻略之Diamond
2018.1.14 By gwj1139177410
0x01最短路
-
//1.计算几何求第四点坐标, 方法很多 //2.虚点，到A城市的四个机场边权都为0 //3.SPFA跑最短路 #include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<vector> #include<queue> using namespace std; //Timu double n, m, a, b; double x[500], y[500], t[110]; //Graph struct Edge{ int to; double w; Edge(int x, double y):to(x),w(y){} }; vector<Edge>G[500]; void insert(int u,int v,double w){ G[u].push_back(Edge(v,w)); } double distant(double nx,double ny,double mx,double my){ return sqrt((nx-mx)*(nx-mx)+(ny-my)*(ny-my)); } //spfa queue<int>q; int vis[500]; double dis[500]; void spfa(){ while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = 0; for(int i = 0; i < G[u].size(); i++){ int v = G[u][i].to; if(dis[u]+G[u][i].w<dis[v]){ dis[v] = dis[u]+G[u][i].w; if(!vis[v]){ q.push(v); vis[v] = 1; } } } } } int main(){ int T; cin>>T; while(T--){ //1.初始化 memset(x,0,sizeof x); memset(y,0,sizeof y); memset(t,0,sizeof t); memset(vis,0,sizeof vis); //2.datein cin>>n>>m>>a>>b; for(int i = 0; i < n; i++){ for(int j = 1; j < 4; j++) cin>>x[i*4+j]>>y[i*4+j]; cin>>t[i+1]; //point4, double l1=distant(x[i*4+1],y[i*4+1],x[i*4+2],y[i*4+2]); double l2=distant(x[i*4+1],y[i*4+1],x[i*4+3],y[i*4+3]); double l3=distant(x[i*4+2],y[i*4+2],x[i*4+3],y[i*4+3]); double l=max(l1,max(l2,l3));//三条里最常的就是对角线,然后中点坐标得到第4点 if(l1 == l)x[i*4+4]=(x[i*4+1]+x[i*4+2])-x[i*4+3], y[i*4+4]=(y[i*4+1]+y[i*4+2])-y[i*4+3]; if(l2 == l)x[i*4+4]=(x[i*4+1]+x[i*4+3])-x[i*4+2], y[i*4+4]=(y[i*4+1]+y[i*4+3])-y[i*4+2]; if(l3 == l)x[i*4+4]=(x[i*4+2]+x[i*4+3])-x[i*4+1], y[i*4+4]=(y[i*4+2]+y[i*4+3])-y[i*4+1]; } //3.预处理,建图(把所有机场连起来就好啦啦啦~) n *= 4; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(i == j)continue; int c1 = (i-1)/4+1, c2 = (j-1)/4+1; if(c1 == c2){ double w = distant(x[i],y[i],x[j],y[j])*t[c1]; insert(i,j,w); insert(j,i,w); }else{ double w = distant(x[i],y[i],x[j],y[j])*m; insert(i,j,w); insert(j,i,w); } } } //4.run for(int i = 1; i <= n; i++)dis[i] = 1e9+1; for(int i = (a-1)*4+1; i <= a*4; i++){ q.push(i); dis[i] = 0; vis[i] = 1; } spfa(); //5.dateout double ans = 1e9; for(int i = (b-1)*4+1; i <= 4*b; i++)ans = min(ans, dis[i]); printf("%.1lf\n",ans); } return 0; }- 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
-
//Floyd-wallshall模板 #include<iostream> using namespace std; int n, e[110][110]; int main(){ ios::sync_with_stdio(false); cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin>>e[i][j]; for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(e[i][k]+e[k][j]<e[i][j]) e[i][j] = e[i][k]+e[k][j]; int T; cin>>T; while(T--){ int a, b; cin>>a>>b; cout<<e[a][b]<<"\n"; } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
-
//数据太小, Floyd一番水 #include<iostream> #include<algorithm> using namespace std; int n = 60, m; int e[1010][1010], vis[1010]; int main(){ cin>>m; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) e[i][j] = i==j ? 0 : 0xffffff; for(int i = 0; i < m; i++){ char a, b; int w; cin>>a>>b>>w; int x = a-'A', y = b-'A'; if(x>=0 && x<25)vis[x] = 1; if(y>=0 && y<25)vis[y] = 1; //bugs数据可能有覆盖 e[x][y] = min(e[x][y], w); e[y][x] = min(e[y][x], w); } for(int k = 0; k < n; k++) for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) e[i][j] = min(e[i][j], e[i][k]+e[j][k]); int ans2 = 0xffffff, ans1; for(int i = 0; i < n; i++)if(vis[i] && e[i][(int)'Z'-'A']<ans2){ ans2 = e[i][(int)'Z'-'A']; ans1 = i; } cout<<(char)(ans1+'A')<<" "<<ans2; return 0; }- 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
//标程Dijkstra #include<iostream> #include<algorithm> #include<vector> using namespace std; //T int n = 60, m, vis[1010]; //Graph struct Edge{ int v, w; Edge(int v, int w):v(v),w(w){} }; vector<Edge>G[70]; //Dijkstra int dis[70], book[70], s = (int)'Z'-'A'; void Dijkstra(){ for(int i = 0; i < n; i++)dis[i] = 0xffffff; for(int i = 0; i < G[s].size(); i++)//bugs数据可能有覆盖 dis[G[s][i].v] = min(dis[G[s][i].v],G[s][i].w); dis[s] = 0; book[s] = 1; for(int i = 0; i < n; i++){ int v, w=0xffffff; for(int j = 0; j < n; j++) if(!book[j] && dis[j]<w) w = dis[v=j]; book[v] = 1; for(int j = 0; j < G[v].size(); j++) dis[G[v][j].v] = min(dis[G[v][j].v], w+G[v][j].w); } } int main(){ cin>>m; for(int i = 1; i <= m; i++){ char a, b; int w; cin>>a>>b>>w; int x = a-'A', y = b-'A'; if(x>=0 && x<25)vis[x] = 1; if(y>=0 && y<25)vis[y] = 1; G[x].push_back(Edge(y,w)); G[y].push_back(Edge(x,w)); } Dijkstra(); int v, w=0xffffff; for(int i = 0; i < n; i++) if(vis[i] && dis[i]<w) w = dis[v=i]; cout<<(char)(v+'A')<<" "<<w<<"\n"; return 0; }- 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
0x02启发式搜索
-
//(如果你玩数独会怎么填呢)......启发式:把能确定的(剩余少的)先填上 #include<iostream> using namespace std; const int score[10][10]={ {0,0,0,0,0,0,0,0,0,0}, {0,6,6,6,6,6,6,6,6,6}, {0,6,7,7,7,7,7,7,7,6}, {0,6,7,8,8,8,8,8,7,6}, {0,6,7,8,9,9,9,8,7,6}, {0,6,7,8,9,10,9,8,7,6}, {0,6,7,8,9,9,9,8,7,6}, {0,6,7,8,8,8,8,8,7,6}, {0,6,7,7,7,7,7,7,7,6}, {0,6,6,6,6,6,6,6,6,6} }; //r[i][j],第i行第j个数是否填过...row_cnt[i],第i行填了几个数 int a[11][11], row[11][11], col[11][11], area[11][11]; int row_cnt[11], col_cnt[11], cnt, ans=-1; //得到(r,c)是第几个区域的 inline int id(int r, int c){ return (r-1)/3*3+(c-1)/3+1; } //计算当前得分 inline int calc(){ int sum = 0; for(int i = 1; i <= 9; i++) for(int j = 1; j <= 9; j++) sum += score[i][j]*a[i][j]; return sum; } void dfs(int r, int c, int cc){ if(cc == 81){ ans = max(ans, calc()); return ; }else for(int i = 1; i <= 9; i++){//尝试每个填数 if(row[r][i]||col[c][i]||area[id(r,c)][i]) continue; row[r][i] = col[c][i] = area[id(r,c)][i] = 1; row_cnt[r]++; col_cnt[c]++; a[r][c] = i; //找没有填的最少的行和列 int tr, vr=-1, tc, vc=-1; for(int j = 1; j <= 9; j++) if(row_cnt[j]>vr && row_cnt[j]!=9) vr = row_cnt[tr=j]; for(int j = 1; j <= 9; j++) if(col_cnt[j]>vc && !a[tr][j])//(r,c)未填数 vc = col_cnt[tc=j]; dfs(tr,tc,cc+1); row[r][i] = col[c][i] = area[id(r,c)][i] = 0; row_cnt[r]--; col_cnt[c]--; a[r][c] = 0; } } int main(){ //datein for(int i = 1; i <= 9; i++){ for(int j = 1; j <= 9; j++){ cin>>a[i][j]; if(a[i][j]){ //更新初始数据 row[i][a[i][j]] = col[j][a[i][j]] = area[id(i,j)][a[i][j]] = 1; row_cnt[i]++; col_cnt[j]++; cnt++; } } } //找没有填的最少的行和列。 int tr, vr=-1, tc, vc=-1; for(int i = 1; i <= 9; i++) if(row_cnt[i]>vr && row_cnt[i]!=9) vr = row_cnt[tr=i]; for(int i = 1; i <= 9; i++) if(col_cnt[i]>vc && !a[tr][i]) vc = col_cnt[tc=i]; //dfs dfs(tr,tc,cnt); cout<<ans<<"\n"; return 0; }- 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
-
#include<iostream> #include<algorithm> #include<queue> #include<string> #include<map> using namespace std; const int dx[] = {0,0,-1,1}; const int dy[] = {1,-1,0,0}; string goal = "123804765", s; map<string,int>ma; int main(){ cin>>s; queue<string>q; q.push(s); while(!q.empty()){ string t = q.front(); q.pop(); if(t == goal)break; int z; for(z = 0; z < 9; z++) if(t[z]=='0')break; int x=z/3, y=z%3; for(int i = 0; i < 4; i++){ int nx=x+dx[i], ny=y+dy[i], nz=nx*3+ny; if(nx<0||nx>=3||ny<0||ny>=3)continue; string tt = t; swap(tt[z],tt[nz]); if(!ma.count(tt)){ q.push(tt); ma[tt] = ma[t]+1; } } } cout<<ma[goal]<<"\n"; return 0; }- 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
0x03线段树入门
-
#include<iostream> using namespace std; const int maxn = 100010; #define lch p<<1 #define rch p<<1|1 struct node{ int val, addmark; }sgt[maxn<<2]; void pushdown(int p, int l, int r){ if(!sgt[p].addmark)return; int t = sgt[p].addmark, m=l+r>>1; sgt[lch].addmark += t; sgt[rch].addmark += t; sgt[lch].val += t*(m-l+1); sgt[rch].val += t*(r-m); sgt[p].addmark = 0; } void update(int p, int l, int r, int ql, int qr, int v){ if(l>qr || r<ql)return ; if(ql<=l && r<=qr){ sgt[p].val += v*(r-l+1); sgt[p].addmark += v; return ; } int m = l+r>>1; if(ql<=m)update(lch,l,m,ql,qr,v); if(qr>m)update(rch,m+1,r,ql,qr,v); sgt[p].val = sgt[lch].val+sgt[rch].val; } int query(int p, int l, int r, int ql, int qr){ if(ql<=l && r<=qr)return sgt[p].val; pushdown(p,l,r); int m = l+r>>1, ans = 0; if(ql<=m)ans += query(lch,l,m,ql,qr); if(qr>m)ans += query(rch,m+1,r,ql,qr); return ans; } int main(){ int n, m; cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; update(1,1,n,i,i,x); } cin>>m; for(int i = 1; i <= m; i++){ int op, x, y; cin>>op>>x>>y; if(op == 1){ update(1,1,n,x,x,y); }else{ cout<<query(1,1,n,x,y)<<"\n"; } } return 0; }- 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<iostream> using namespace std; const int maxn = 100010; #define lch p<<1 #define rch p<<1|1 struct node{ int val, addmark; }sgt[maxn<<2]; void pushdown(int p, int l, int r){ if(!sgt[p].addmark)return; int t = sgt[p].addmark, m=l+r>>1; sgt[lch].addmark += t; sgt[rch].addmark += t; sgt[lch].val += t*(m-l+1); sgt[rch].val += t*(r-m); sgt[p].addmark = 0; } void update(int p, int l, int r, int ql, int qr, int v){ if(l>qr || r<ql)return ; if(ql<=l && r<=qr){ sgt[p].val += v*(r-l+1); sgt[p].addmark += v; return ; } int m = l+r>>1; if(ql<=m)update(lch,l,m,ql,qr,v); if(qr>m)update(rch,m+1,r,ql,qr,v); sgt[p].val = sgt[lch].val+sgt[rch].val; } int query(int p, int l, int r, int ql, int qr){ if(ql<=l && r<=qr)return sgt[p].val; pushdown(p,l,r); int m = l+r>>1, ans = 0; if(ql<=m)ans += query(lch,l,m,ql,qr); if(qr>m)ans += query(rch,m+1,r,ql,qr); return ans; } int main(){ int n, m; cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; update(1,1,n,i,i,x); } cin>>m; for(int i = 1; i <= m; i++){ int op, x, y, k; cin>>op; if(op == 1){ cin>>x>>y>>k; update(1,1,n,x,y,k); }else{ cin>>x; cout<<query(1,1,n,x,x)<<"\n"; } } return 0; }- 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<iostream> using namespace std; int n, m, a[30010], r, p; int main(){ cin>>n>>m; for(int i = 1; i <= n; i++)a[i]=i; r = n; p = 1; while(r>1){ p = (p+m-1)%r; if(p==0)p=r; cout<<a[p]<<" "; for(int i = p; i <= r-1; i++)a[i]=a[i+1]; r--; } cout<<a[1]<<"\n"; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
0x04并查集
-
//类MST,对于每条边把他作为_max且作为常数，然后枚举所有比他小的边直到联通，维护全局最大值 #include<iostream> #include<algorithm> using namespace std; const int inf = 0xfffffff; int n, m, st, ed, _max=inf, _min=1; int gcd(int a, int b){ return !b?a:gcd(b,a%b);} //graph struct edge{ int u, v, w;}e[5010]; bool cmp(edge a, edge b){ return a.w<b.w; } //UnionFindSet int fa[510]; void init(int n){ for(int i = 1; i <= n; i++) fa[i]=i; } int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]);} void merge(int x, int y){ if(find(x)==find(y))return ; fa[find(x)]=find(y); } //main int main(){ cin>>n>>m; for(int i = 1; i <= m; i++) cin>>e[i].u>>e[i].v>>e[i].w; cin>>st>>ed; sort(e+1,e+m+1, cmp); for(int i = 1; i <= m; i++){ init(n); for(int j = i; j >= 1; j--){ merge(e[j].u, e[j].v); if(find(st)==find(ed)){ if((e[i].w*1.0/e[j].w) < (_max*1.0/_min)){ _max = e[i].w; _min = e[j].w; } break; } } } if(_max==inf && _min==1){ cout<<"IMPOSSIBLE\n"; return 0;} int r = gcd(_max, _min); _max /= r; _min /= r; if(_min == 1)cout<<_max<<"\n"; else cout<<_max<<"/"<<_min<<"\n"; return 0; }- 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
-
//并查集及补集 //凡是与i+n节点在同一个集合里的，都是不能与i在同一个集合里的。 #include<iostream> #include<algorithm> using namespace std; struct Edge{ int u, v, w; }e[100010]; bool cmp(Edge a, Edge b){ return a.w>b.w; } int fa[20010<<1]; void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; } int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void merge(int x, int y){ x=find(x);y=find(y);if(x!=y)fa[x]=y;} int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= m; i++) cin>>e[i].u>>e[i].v>>e[i].w; sort(e+1,e+m+1,cmp); init(n<<1); for(int i = 1; i <= m; i++){ int u = e[i].u, v = e[i].v; if(find(u) == find(v)){ cout<<e[i].w<<"\n"; return 0; } merge(u+n, v); merge(v+n, u); } cout<<0<<"\n";//.... return 0; }- 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
-
//并查集模板 #include<iostream> using namespace std; int fa[5010]; void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;} int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void merge(int x, int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;} int main(){ int n, m, p; cin>>n>>m>>p; init(n); for(int i = 1; i <= m; i++){ int a, b; cin>>a>>b; merge(a,b); } for(int i = 1; i <= p; i++){ int a, b; cin>>a>>b; if(find(a)==find(b))cout<<"Yes\n"; else cout<<"No\n"; } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
-
//本题思路：把x作为a,b,c三种动物分别加入，维护三个集合的关系。 //并查集及补集 //其中i用来连接与i同类的，i+n用来连接能吃i的，i+2*n用来连接i能吃的。 //具体来说，凡是与i+n节点在同一个集合里的，都是被i吃的动物。 #include<iostream> #include<algorithm> using namespace std; int ans = 0; int fa[50010*3]; void init(int n){ for(int i = 1; i <= n; i++)fa[i]=i; } int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void merge(int x, int y){ x=find(x);y=find(y);if(x!=y)fa[x]=y;} int some(int x, int y){ return find(x)==find(y); } int main(){ int n, m; cin>>n>>m; init(n*3); for(int i = 1; i <= m; i++){ int op, x, y; cin>>op>>x>>y; if(x>n||y>n){ans++;continue;}//2)当前的话中X或Y比N大，就是假话 if(op==2&&x==y){ans++;continue;}//3)当前的话表示X吃X，就是假话 if(op==1){ if(some(x,y+n)||some(y,x+n))ans++;//如果x吃y或者y吃x，就不是同类 else{ merge(x,y);//x和y是同类 merge(x+n,y+n);//能吃x和y的也是同类 merge(x+n*2,y+n*2);//x和y能吃的也是同类 } }else{ if(some(x,y)||some(y,x+n))ans++;//如果x和y是同类或者y吃x else{ merge(x,y+n);//x和吃y的连起来 merge(x+n,y+n*2);//能吃x的和被y吃的连起来(三种动物之间的关系啊) merge(x+n*2,y);//x能吃的和y连起来 } } } cout<<ans<<"\n"; return 0; }- 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
0x05堆
-
//贪心：优先打价值最大的(如果能打的话) #include<iostream> #include<algorithm> using namespace std; struct d{ int t, w; }a[110]; bool cmp(d a, d b){ return a.w>=b.w; } int n, book[110], ans; int main(){ cin>>n; for(int i = 0; i < n; i++)cin>>a[i].t; for(int i = 0; i < n; i++)cin>>a[i].w; sort(a, a+n, cmp); for(int i = 0; i < n; i++) for(int j = a[i].t; j >= 1; j--) if(!book[j]){ ans += a[i].w; book[j] = 1; break; } cout<<ans; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
-
//STL默认大根堆 #include<iostream> #include<queue> using namespace std; int n, ans; priority_queue<int,vector<int>,greater<int> >q; int main(){ cin>>n; for(int i = 1; i <= n; i++){ int x; cin>>x; q.push(x); } while(q.size()!=1){ int a = q.top(); q.pop(); int b = q.top(); q.pop(); ans += a+b; q.push(a+b); } cout<<ans<<"\n"; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
-
//动态维护大根堆,贪心减少入队元素个数 //以及,拓展参见刘汝佳蓝书P189,K路归并 #include<iostream> #include<algorithm> #include<queue> using namespace std; const int maxn = 100010; int n, a[maxn], b[maxn]; //q为答案的n个元素。 priority_queue<int>q; //递归输出 void print(){ if(q.empty())return ; int t = q.top(); q.pop(); print(); cout<<t<<" "; } int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>a[i]; for(int i = 1; i <= n; i++)cin>>b[i]; //step1:排序,让序列单调，后面用单调性减少状态数 sort(a+1,a+n+1); sort(b+1,b+n+1); //step2:随便加n个元素作为初始值 for(int i = 1; i <= n; i++){ q.push(a[1]+b[i]); } for(int i = 2; i <= n; i++){ if(a[i]+b[1]>=q.top())break;//step3因为单调,所以后面的a[i]+b[1]只会更大。 for(int j = 1; j <= n; j++){ if(a[i]+b[j]>=q.top())break;//step4:因为单调,所以后面的肯定会更大。 //step5:如果没有break,则当前元素比答案中的最大值要大，更新答案。 q.pop(); q.push(a[i]+b[j]); } } //step6:此时队列中剩下的n各元素就是最小值 print(); return 0; }- 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
0x06高精度++
-
//高精除高精,模板 //思路:模拟减法，a每次减去b的10^n倍可以提高效率 #include<iostream> #include<algorithm> #include<string> #include<cstring> using namespace std; const int maxn = 510; int a[maxn], b[maxn], c[maxn], t[maxn]; //比较x和y的大小,x>y时返回1,x==y返回0,x<y返回-1 int compare(int x[], int y[]){ if(x[0] < y[0])return -1; if(x[0] > y[0])return 1; for(int i = x[0]; i > 0; i--){ //越后面的位越大啊 if(x[i] < y[i])return -1; if(x[i] > y[i])return 1; } return 0; } //y=x*(10^k) void times(int x[], int y[], int k){ for(int i = 1; i <= x[0]; i++)y[i+k-1] = x[i]; y[0] = x[0]+k-1; } int main(){ string s1, s2; cin>>s1>>s2; a[0] = s1.size(); b[0] = s2.size(); //bugs:a比b小的情况,就是...如果只剩0的话这个商的长度的也会变成0 错误数据:0 100 if(a[0]<b[0]||(a[0]==b[0]&&s1<s2)){ cout<<"0\n"; return 0; } for(int i = 1; i <= a[0]; i++)a[i] = s1[a[0]-i]-'0'; for(int i = 1; i <= b[0]; i++)b[i] = s2[b[0]-i]-'0'; c[0] = a[0]-b[0]+1; for(int i = c[0]; i > 0; i--){ memset(t,0,sizeof(t)); times(b,t,i); while(compare(a,t)>=0){ c[i]++; //高精减,a=a-t for(int j = 1; j <= a[0]; j++){ if(a[j] < t[j]){ a[j+1]--; a[j] += 10; } a[j] -= t[j]; } while(!a[a[0]] && a[0]>1)a[0]--; } } while(!c[c[0]] && c[0]>1)c[0]--; for(int i = c[0]; i > 0; i--)cout<<c[i]; return 0; }- 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<iostream> #include<string> #include<cstring> using namespace std; const int maxn = 1010; int a[maxn], l[maxn], r[maxn], m[maxn], t[maxn]; //m=l+r>>1 void mid(){ //m = l; memcpy(m,l,sizeof(l)); //m += r; m[0] = r[0]+1; for(int i = 1; i <= r[0]; i++){ m[i] += r[i]; if(m[i]>=10){ m[i] %= 10; m[i+1]++; } } while(m[0]>1 && m[m[0]]==0)m[0]--; //m /= 2; for(int i = m[0]; i >= 1; i--){ if(i > 1)m[i-1]+=m[i]%2*10; m[i] /= 2; } while(m[0]>1 && m[m[0]]==0)m[0]--; } //return m*m>a; bool C(){ //t = 0; memset(t,0,sizeof(t)); //t = m*m; for(int i = 1; i <= m[0]; i++) for(int j = 1; j <= m[0]; j++) t[i+j-1] += m[i]*m[j]; t[0] = m[0]*2; for(int i = 1; i <= t[0]; i++){//处理进位 t[i+1] += t[i]/10; t[i] %= 10; } while(t[0]>1 && t[t[0]]==0)t[0]--; //return t>a; if(t[0] != a[0])return t[0]>a[0]; for(int i = t[0]; i >= 1; i--) if(t[i]!=a[i])return t[i]>a[i]; return 0; } int main(){ //输入 string s; cin>>s; a[0] = s.size(); for(int i = 1; i <= a[0]; i++)a[i] = s[a[0]-i]-'0'; //二分 l[0] = 1; r[0] = a[0]/2+2; r[r[0]] = 1; for(int i = 1; i <= 2000; i++){ mid(); //m=l+r>>1; if(C())memcpy(r,m,sizeof(m));//r=m; else memcpy(l,m,sizeof(m));//l=m; } //输出 for(int i = l[0]; i >= 1; i--)cout<<l[i]; return 0; }- 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
0x07哈希表
-
#include<iostream> #include<set> using namespace std; set<int>s; int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= n; i++){ int x; cin>>x; s.insert(x); } for(int i = 1; i <= m; i++){ int x; cin>>x; if(s.count(x))cout<<"YES\n"; else cout<<"NO\n"; } return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
-
/* 贪心 1.找出不互质的数的集合，就是把互斥的数删去. 2.那么当有两个互斥的数时，如果删掉前面(小)的，这个数后面的与它互斥的数也会入选，所以删掉后面的更优。 3.因为每个数都是不同的。 */ #include<iostream> #include<algorithm> #include<map> using namespace std; const int maxn = 1e5+10; int n, p, a[maxn], ans; map<int,int>ma; int main(){ cin>>n>>p; for(int i = 1; i <= n; i++)cin>>a[i]; sort(a+1,a+n+1); //枚举每个数，如果当前数没有被删，那么集合元素+1，然后把与他互斥的数删了。 for(int i = 1; i <= n; i++) if(!ma[a[i]]){ ma[a[i]*p]=1; ans++; } cout<<ans<<"\n"; return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
-
//Meet in the Middle #include<iostream> #include<algorithm> #include<map> using namespace std; int n, mass, ans(666), f[233]; map<int, int>ma; //能称出的质量->需要的砝码 //k:当前用的砝码个数,cur:从哪个砝码开始选,sum:当前称出的质量 void dfs1(int k, int cur, int sum){ if(sum>mass || cur>n/2)return ; ma[sum] = k; dfs1(k+1,cur+1,sum+f[cur]);//选当前砝码 dfs1(k,cur+1,sum);//不选当前砝码 } void dfs2(int k, int cur, int sum){ if(sum>mass || cur>n)return ; if(ma.find(mass-sum) != ma.end()){//如果能跟前半段的结果组成目标质量 ans = min(ans,k+ma[mass-sum]);//更新答案 return; } dfs2(k+1,cur+1,sum+f[cur]); dfs2(k,cur+1,sum); } int main(){ cin>>n>>mass; for(int i = 0; i < n; i++) cin>>f[i]; dfs1(0,0,0);//先搜前半段 dfs2(0,n/2,0);//再搜后半段 cout<<ans<<"\n"; return 0; }- 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
0x08树型动态规划
-
/* 1.将博物馆的结构抽象成一棵二叉树，每条边都有对应的权值（走过这条边花费的时间） 2.只在叶子节点有藏画，要求你在有限的时间内偷到尽可能多的藏画。 3.点的信息按照深度优先顺序给出（前序遍历），建立一颗二叉树； 4.然后从根节点开始深搜，每走过一条走廊到达下一个点， 5.剩余的时间remain要减去2倍这条走廊的花费，相当于一去一回； */ //f[i,j]:来到第i个走廊（还未走过这条走廊）还剩下j时间，能拿到最大的画的数量。 //f[i,j]=max{f[i,j],f[lch,k]+f[rch,j-2*t[i]-k]| 0<=k<=j-2*t[i]}; #include<iostream> #include<algorithm> using namespace std; const int maxn = 1010; //堆式建树 int tree[maxn<<1][2], f[maxn][maxn]; void init(int root){ //tree[i][0]:走过第i条走廊的时间，tree[i][1]:第i条走廊某端的藏画 cin>>tree[root][0]>>tree[root][1]; tree[root][0] *= 2; if(!tree[root][1]){ init(root<<1); init(root<<1|1); } } int dp(int i, int j){ if(f[i][j] || j==0)return f[i][j];//搜过了或者没有时间了就返回 if(tree[i][1])return f[i][j]=min(tree[i][1],(j-tree[i][0])/5);//有藏画的叶子节点 for(int k = 0; k <= j-tree[i][0]; k++) f[i][j]=max(f[i][j],dp(i<<1,k)+dp(i<<1|1,j-tree[i][0]-k)); return f[i][j]; } int main(){ int tot; cin>>tot; init(1); cout<<dp(1,tot)<<"\n"; return 0; }- 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
-
//用f[x][0],f[x][1] 分别表示x没去和去了的最大价值。 //f[x][0] = sigmar:max(f[y][0],f[y][1]); //f[x][1] = sigmar:f[y][0]; #include<iostream> #include<algorithm> #include<vector> const int maxn = 6000<<1; using namespace std; int n, r[maxn], f[maxn][2], in[maxn]; vector<int>G[maxn]; int dp(int x, int q){ if(f[x][q])return f[x][q]; if(q)f[x][q] = r[x]; for(int i = 0; i < G[x].size(); i++){ int y = G[x][i]; if(q)f[x][q] += dp(y,0); else f[x][q] += max(dp(y,0),dp(y,1)); } return f[x][q]; } int main(){ cin>>n; for(int i = 1; i <= n; i++)cin>>r[i]; for(int i = 1; i <= n; i++){ int a, b; cin>>a>>b; G[b].push_back(a); in[a]++; } int head = 0; //找树根,即入度为0的结点 for(int i = 1; i <= n; i++) if(in[i]==0){ head = i; break; } cout<<max(dp(head,1),dp(head,0))<<"\n"; return 0; }- 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
0x09最小生成树
-
//MST-Prim-贪心 #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int maxn = 110; //Graph int e[maxn][maxn]; //Prim int dis[maxn], book[maxn]; //main int main(){ ios::sync_with_stdio(false); int n; cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin>>e[i][j]; //将1号顶点加入生成树 book[1] = 1; for(int i = 1; i <= n; i++)dis[i]=e[1][i]; //将剩余的n-1个点加入生成树 for(int i = 2; i <= n; i++){ //找到所有点里面到生成树距离最短的 int v, w=0xffffff; for(int j = 1; j <= n; j++) if(!book[j] && dis[j]<w) w = dis[v=j]; //将该点加入生成树 book[v] = 1; //用该点的出边松弛其他非生成树点到生成树的距离 for(int j = 1; j <= n; j++) if(!book[j] && dis[j]>e[v][j]) dis[j] = e[v][j]; } LL ans = 0; for(int i = 1; i <= n; i++)ans += dis[i]; cout<<ans<<"\n"; return 0; }- 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
//MST-Prim-贪心-堆优化 #include<iostream> #include<algorithm> #include<queue> using namespace std; const int maxn = 110; //Graph int e[maxn][maxn],ans; //Prim struct node{ int v, w; node(int v=0, int w=0):v(v),w(w){} bool operator < (node b)const{return w>b.w;} }; priority_queue<node>q;//保存所有可以抵达生成树的边 int book[maxn]; //main int main(){ ios::sync_with_stdio(false); int n; cin>>n; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) cin>>e[i][j]; //将1号顶点加入生成树 book[1] = 1; for(int i = 1; i <= n; i++) if(e[1][i])q.push(node(i,e[1][i])); //将剩余的n-1个点加入生成树 for(int i = 2; i <= n; i++){ //找到所有(与生成树相连的)点里面到生成树距离最短的 node t = q.top(); q.pop(); while(book[t.v]){//只有不在生成树里的点才可以加到生成树里面，这里避免重复。 t = q.top(); q.pop(); } //将该点加入生成树 book[t.v] = 1; ans += t.w; //用该点的出边松弛其他非生成树点到生成树的距离 for(int j = 1; j <= n; j++) if(!book[j] && e[t.v][j])//当前加入生成树的点可以扩充出的边指向的节点 q.push(node(j,e[t.v][j])); } cout<<ans<<"\n"; return 0; }- 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
-
//MST-Kruskal-排序贪心+并查集 //题中N=M,(M小于N^2的)稀疏图。 #include<iostream> #include<algorithm> using namespace std; typedef long long LL; const int maxn = 100010; //Graph struct Edge{ int u, v, w; }e[maxn]; bool cmp(Edge a, Edge b){return a.w<b.w;} //UnionFindSet int fa[maxn]; void init(int n){for(int i=1;i<=n;i++)fa[i]=i;} int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void merge(int x,int y){x=find(x);y=find(y);if(x!=y)fa[x]=y;} //main int main(){ int n, m; cin>>n>>m; for(int i = 1; i <= m; i++) cin>>e[i].u>>e[i].v>>e[i].w; sort(e+1,e+m+1,cmp); LL ans = 0; init(n); for(int i = 1; i <= m; i++){ int u = e[i].u, v = e[i].v; if(find(u) != find(v)){ merge(u,v); ans += e[i].w; } } cout<<ans<<"\n"; return 0; }- 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
文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。
原文链接：gwj1314.blog.csdn.net/article/details/79059173
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）