CodeVs刷题攻略之Diamond

CodeVs刷题攻略之Diamond

2018.1.14 By gwj1139177410

0x01最短路

  1. Car的旅行路线

    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
    //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;
    }
  2. 多源最短路

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    //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;
    }
  3. 回家

    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
    //数据太小, 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
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    //标程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;
    }

0x02启发式搜索

  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
    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
    //(如果你玩数独会怎么填呢)......启发式:把能确定的(剩余少的)先填上
    #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;
    }
  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
    #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;
    }

0x03线段树入门

  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
    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;
    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;
    }
  2. 线段树练习 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
    #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;
    }
  3. 约瑟夫问题

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //好玩么
    #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;
    }

0x04并查集

  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
    //类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;
    }
  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
    //并查集及补集
    //凡是与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;
    }
  3. 家族

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    //并查集模板
    #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;
    }
  4. 食物链

    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
    //本题思路:把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;
    }

0x05堆

  1. 地鼠游戏

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    //贪心:优先打价值最大的(如果能打的话)
    #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;
    }
  2. 合并果子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    //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;
    }
  3. 最小的N个和

    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
    //动态维护大根堆,贪心减少入队元素个数
    //以及,拓展参见刘汝佳蓝书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;
    }

0x06高精度++

  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
    44
    45
    46
    47
    48
    49
    50
    51
    52
    //高精除高精,模板
    //思路:模拟减法,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;
    }
  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
    //二分答案
    #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;
    }

0x07哈希表

  1. 元素查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    #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;
    }
  2. 互斥的数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /*
    贪心
    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;
    }
  3. 砝码称重 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
    //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;
    }

0x08树型动态规划

  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
    /*
    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;
    }
  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
    //用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;
    }

0x09最小生成树

  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
    //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
    40
    41
    42
    43
    44
    //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;
    }
  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
    //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;
    }