3.18-3.24

2.天梯赛练习集-L2部分

L2-001 紧急救援

比较裸的一个迪杰斯特拉，更新的时候需要考虑更多的信息

当由 x 更新结点 y 时。

1. d[y]更新时，到达被y的路径条数变为 x 的路径条数，y人数随之更新
2. d[y] = d[x]+ dis[x][y]相等时，y结点路径条数增加，人数却要与之前的做比较，取一个最大值。

#include 
    
     using namespace std;const int N = 550,M = N*N;const int inf = 0x3f3f3f3f;int a[N],d[N],f[N],g[N],pa[N],n,m,s,e;int vis[N];int ver[M],edge[M],head[N],nxt[M],tot;void add(int x,int y,int z){    ver[++tot] = y;    edge[tot] = z;    nxt[tot] = head[x];    head[x] = tot;}void print(int now){    if(now==pa[now])printf("%d",now-1);    else{        print(pa[now]);        printf(" %d",now-1);    }}int main(){    cin>>n>>m>>s>>e;    s++;e++;    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        g[i] = a[i];    }    for(int i=1;i<=m;i++){        int x,y,z;        scanf("%d%d%d",&x,&y,&z);        x++;y++;        if(x==y)continue;        add(x,y,z);        add(y,x,z);    }    for(int i=1;i<=n;i++)d[i] = inf;    d[s] = 0;f[s] = 1;g[s] = a[s],pa[s] = s;    for(int i=0;i
     
      d[id]+edge[j]){                f[y] = f[id];                g[y] = a[y]+g[id];                d[y] = d[id]+edge[j];                pa[y] = id;            }        }    }    printf("%d %d\n",f[e],g[e]);    print(e);    puts("");    return 0;}
     
    

L2-007 家庭房产

• 一道挺恶心的并查集，匆匆过了

#include 
    
     using namespace std;const int N = 1010,M = 10010;int fa[M],vis[M];int find(int x){    return x==fa[x]?x:fa[x] = find(fa[x]);}vector
     
       g[M];struct node{    int num;    int id;    int cnt;    int flag;    double sum;    double ave;    double ave_num;}a[M],b[M];int n;void merge(int x,int y){    x = find(x);    y = find(y);    if(x>y)swap(x,y);    fa[y] = x;}bool cmp(node a,node b){    if(a.ave==b.ave){        return a.id
      
       b.ave;}int main(){    cin>>n;    for(int i=0;i<=10000;i++){        fa[i] = i;        a[i].cnt = 1;        a[i].id = i;    }    for(int i=1;i<=n;i++){        int id,father,mather,k;        cin>>id>>father>>mather>>k;        vis[id] = 1;        if(father!=-1){            merge(id,father);            vis[father] = 1;        }        if(mather!=-1){            merge(id,mather);            vis[mather] = 1;        }        for(int j=0;j
       
        >x;            merge(id,x);            vis[x] = 1;        }        cin>>a[id].num>>a[id].sum;    }    for(int i=0;i<10000;i++){        if(vis[i]){            int x = find(i);            b[x].sum += a[i].sum;            b[x].num += a[i].num;            b[x].cnt ++;            b[x].flag = 1;            b[x].id = x;        }    }    int res = 0;    for(int i=0;i<10000;i++){        if(b[i].flag){            if(b[i].num){                b[i].ave = b[i].sum/b[i].cnt;                b[i].ave_num = b[i].num/b[i].cnt;                b[i].ave = (double)round(b[i].ave*1000.0)/1000;            }            else{                b[i].ave = 0;                b[i].ave_num = 0;            }            res++;            //printf("%d %d %d %lf\n",i,b[i].id,b[i].num,b[i].ave);        }    }    sort(b,b+10000,cmp);    cout<
        
         <
        
       
      
     
    

L2-014

• 为了保证最后的出队序列是有序的，那么每个小队列也必须是有序的，最少的递减序列条数等于最长的单调不减序列的长度。所以直接求最长的单调不减序列长度即可。二分解法中每次覆盖之前的值，就可以理解为增加这一个位置纵向上的递减序列长度（比较抽象）

#include 
    
     using namespace std;const int N = 100010;int a[N],dp[N];int n;int main(){    cin>>n;    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    int len = 0;    for(int i=1;i<=n;i++){        int pos = lower_bound(dp,dp+len,a[i])-dp;        if(pos
    

L2-023 图着色问题

• 这个题很单纯，所用颜色必须为k个，多一个少一个都不行

#include 
    
     using namespace std;const int N = 1010;int a[N];int n,m,k,t;struct edge{    int x,y;}eg[N*N];bool check(){    for(int i=1;i<=m;i++){        if(a[eg[i].x]==a[eg[i].y])return false;    }    return true;}int main(){    cin>>n>>m>>k;    for(int i=1;i<=m;i++){        scanf("%d%d",&eg[i].x,&eg[i].y);    }    cin>>t;    set
     
       st;    while(t--){        st.clear();        for(int i=1;i<=n;i++){            scanf("%d",&a[i]);            st.insert(a[i]);        }        //cout<
      
       <
      
     
    

3. 天梯赛练习集-L3部分

L3-001 凑零钱

• 记忆路径的背包问题，因为要满足答案字典序最小，所以先从大的选，也可以理解为尽可能让小的有更多的选择，使得答案中字典序小的优先选取

#include 
    
     using namespace std;int dp[10004][102];int a[10004];int main() {    ios::sync_with_stdio(false);    int n, m;    cin >> n >> m;    for(int i = 1; i <= n; i++) {        cin >> a[i];    }    sort(a + 1, a + n + 1, greater
     
      ()); // 保证字典序最小    dp[0][0] = 1;    for(int i = 1; i <= n; i++) {        for(int j = 0; j <= m; j++) {            dp[i][j] = dp[i - 1][j];            if(j >= a[i])                dp[i][j] += dp[i - 1][j - a[i]];        }    }    if(dp[n][m] == 0) {        cout << "No Solution";    } else {        vector
      
        ans;        int i = n, j = m;        while(j > 0) {            if(j - a[i] >= 0 && dp[i - 1][j - a[i]]>0) {                ans.push_back(a[i]);                j -= a[i];            }            i--;        }        cout << ans[0];        for(int k = 1; k < ans.size(); k++) {            cout << " " << ans[k];        }    }}
      
     
    

L3-002 特殊堆栈

• 线段树
• 二分

#include 
    
     using namespace std;const int N = 100010;//maintain the number of values between the l and rstruct SegmentTree{    int l,r;    int dat;    #define L(x) t[x].l    #define R(x) t[x].r    #define MID(x) (t[x].l+t[x].r)/2}t[N*4];int n;void build(int p,int l,int r){    t[p].l = l;t[p].r = r;    t[p].dat = 0;    if(l==r)return;    build(p*2,l,MID(p));    build(p*2+1,MID(p)+1,r);    t[p].dat = t[p*2].dat+t[p*2+1].dat;}void change(int p,int x,int v){    if(L(p)==R(p)&&L(p)==x){        t[p].dat += v;        return ;    }    if(x<=MID(p)) change(p*2,x,v);    else change(p*2+1,x,v);    t[p].dat = t[p*2].dat+t[p*2+1].dat;}int query(int p,int x){    if(L(p)==R(p))return R(p);    if(x<=t[p*2].dat)return query(p*2,x);    else return query(p*2+1,x-t[p*2].dat);}int st[N];char op[15];int main(){    cin>>n;    int top = 0;    build(1,1,N-10);    while(n--){        scanf("%s",op);        if(op[1] == 'o'){            if(top==0)puts("Invalid");            else{                cout<
     
      <
     
    

#include 
    
     using namespace std;const int N = 100010;vector
     
       v;int st[N],top;int n,x;char op[15];int main(){    cin>>n;    while(n--){        scanf("%s",op);        if(op[1]=='o'){            if(top==0)puts("Invalid");            else{                printf("%d\n",st[--top]);                int p = lower_bound(v.begin(),v.end(),st[top])-v.begin();                v.erase(v.begin()+p);            }        }        else if(op[1]=='u'){            scanf("%d",&x);            st[top++] = x;            int p = lower_bound(v.begin(),v.end(),x)-v.begin();            v.insert(v.begin()+p,x);        }        else{            if(top==0)puts("Invalid");            else            printf("%d\n",v[(top-1)/2]);           }    }    return 0;}
     
    

L3-004 肿瘤诊断

• 三维BFS ，如果用DFS会爆栈

#include 
    
     using namespace std;int ma[1300][200][100];int vis[1300][200][100];int m,n,l,t;int dx[6] = {1,-1,0,0,0,0};int dy[6] = {0,0,1,-1,0,0};int dz[6] = {0,0,0,0,1,-1};bool check(int x,int y,int z){    if(x<1||x>m||y<1||y>n||z<1||z>l)return false;    if(vis[x][y][z]||ma[x][y][z]==0)return false;    return true;}struct node{    int x,y,z;};int bfs(int x,int y,int z){    queue
     
       q;    int res = 0;    q.push({x,y,z});vis[x][y][z] = 1;    while(!q.empty()){        node u = q.front();q.pop();        res++;        for(int i=0;i<6;i++){            int a = u.x+dx[i];            int b = u.y+dy[i];            int c = u.z+dz[i];            if(check(a,b,c)){                q.push({a,b,c});                vis[a][b][c] = 1;            }        }    }      return res;}int main(){    //memset(vis,0,sizeof vis);    scanf("%d%d%d%d",&m,&n,&l,&t);    for(int i=1;i<=l;i++){        for(int x=1;x<=m;x++){            for(int y=1;y<=n;y++){                vis[x][y][i]=0;                scanf("%d",&ma[x][y][i]);            }        }    }    int res = 0;    for(int z=1;z<=l;z++){        for(int x=1;x<=m;x++){            for(int y=1;y<=n;y++){                if(ma[x][y][z]==1&&vis[x][y][z]==0){                    int c = bfs(x,y,z);                    //cout<
      
       <
       
        =t)res+=c;                }            }        }    }    cout<
        
         <
        
       
      
     
    

L3-007 天梯地图

• 比较烦人的最短路，记录路径，比较路径，变量名上一定要细心

#include 
    
     using namespace std;const int N = 505;const int inf = 0x3f3f3f3f;int len[N][N],tim[N][N];int n,m;int d[N],t[N],g[N],vis[N],st,ed;vector
     
       t_res,d_res;void get_tim(int x){    if(x==st)t_res.push_back(x-1);    else {        get_tim(g[x]);        t_res.push_back(x-1);    }}void get_dis(int x){    if(x==st)d_res.push_back(x-1);    else{        get_dis(g[x]);        d_res.push_back(x-1);    }}bool check(){    if(d_res.size()!=t_res.size())return false;    for(int i=0;i
      
       >n>>m;    for(int i=1;i<=m;i++){        int x,y,one,l,t;        cin>>x>>y>>one>>l>>t;        x++;y++;        len[x][y] = l;        tim[x][y] = t;        if(one == 0){            len[y][x] = l;            tim[y][x] = t;        }    }    cin>>st>>ed;    st++;ed++;    for(int i=1;i<=n;i++)d[i] = inf,t[i] = inf,vis[i] = 0;    d[st] = 0;t[st] = 0;    priority_queue
       
        
          > q;    q.push(make_pair(0,st));    while(!q.empty()){        int x = q.top().second;q.pop();        if(vis[x])continue;        vis[x] = 1;        for(int i=1;i<=n;i++){            if(i==x)continue;            if(t[i] > t[x]+tim[x][i]){                t[i] = t[x]+tim[x][i];                d[i] = d[x]+len[x][i];                g[i] = x;                q.push(make_pair(-t[i],i));            }            else if(t[i]==t[x]+tim[x][i]&&d[i]>d[x]+len[x][i]){                d[i] = d[x]+len[x][i];                g[i] = x;                q.push(make_pair(-t[i],i));            }        }    }    printf("Time = %d",t[ed]);    get_tim(ed);    for(int i=1;i<=n;i++)d[i] = inf,t[i] = inf,vis[i] = 0;    d[st] = 0;t[st] = 1;    q.push(make_pair(0,st));    while(!q.empty()){        int x = q.top().second;q.pop();        if(vis[x])continue;        vis[x] = 1;        for(int i=1;i<=n;i++){            if(i==x)continue;            if(d[i] > d[x]+len[x][i]){                d[i] = d[x]+len[x][i];                t[i] = t[x]+1;                g[i] = x;                q.push(make_pair(-d[i],i));            }            else if(d[i] == d[x]+len[x][i]&&t[i] > t[x]+1){                t[i] = t[x]+1;                g[i] = x;                q.push(make_pair(-d[i],i));            }        }    }    get_dis(ed);    if(check()){        printf("; Distance = %d: %d",d[ed],d_res[0]);        for(int i=1;i
         
           %d",d_res[i]); } puts(""); } else{ printf(": %d",t_res[0]); for(int i=1;i
          
            %d",t_res[i]); puts(""); printf("Distance = %d: %d",d[ed],d_res[0]); for(int i=1;i
           
             %d",d_res[i]); } puts(""); } return 0;}
           
          
         
        
       
      
     
    

L3-016 二叉搜索树的结构

• BST 例题

#include 
    
     using namespace std;const int N = 110;struct node{    int l,r,data,fa;}t[N];map
     
       id;int a[N],n,m,d[N];void insert(int &p,int fa,int now,int x,int dp){    if(p==-1){        p = now;        t[p].data = x;        t[p].fa = fa;        id[x] = now;        d[now] = dp;        return;    }    if(t[p].data>x)        insert(t[p].l,p,now,x,dp+1);    else insert(t[p].r,p,now,x,dp+1);}int main(){    scanf("%d",&n);    int root = -1;    for(int i=1;i<=n;i++)t[i].data=t[i].l=t[i].r= -1;    for(int i=1;i<=n;i++){        scanf("%d",&a[i]);        insert(root,-1,i,a[i],1);    }      int q;cin>>q;    string st;int a,b;    while(q--){        cin>>a;        cin>>st;        if(st=="is"){            cin>>st>>st;            if(st=="root"){                if(!id.count(a)){                    puts("No");continue;                }                if(id[a]==1)puts("Yes");                else puts("No");            }            else if(st=="parent"){                cin>>st>>b;                if(!id.count(a)||!id.count(b)){                    puts("No");continue;                }                if(t[id[b]].fa == id[a])puts("Yes");                else puts("No");            }            else if(st=="left"){                cin>>st>>st>>b;                if(!id.count(a)||!id.count(b)){                    puts("No");continue;                }                if(t[id[b]].l == id[a])puts("Yes");                else puts("No");            }            else if(st=="right"){                cin>>st>>st>>b;                if(!id.count(a)||!id.count(b)){                    puts("No");continue;                }                if(t[id[b]].r==id[a])puts("Yes");                else puts("No");            }        }        else{            cin>>b;            cin>>st>>st;            if(st=="siblings"){                if(!id.count(a)||!id.count(b)||a==b){                    puts("No");continue;                }                if(t[id[a]].fa==t[id[b]].fa)puts("Yes");                else puts("No");            }            else {                cin>>st>>st>>st;                if(!id.count(a)||!id.count(b)){                    puts("No");continue;                }                if(d[id[a]] == d[id[b]])puts("Yes");                else puts("No");            }        }    }    return 0;}
     
    

L3-015 球队“食物链”

• 状压dp

#include 
    
     using namespace std;int n;char s[22][22];int d[1<<20][22];int g[22];bool check(int st){    int res = 0;    while(st&1)res++,st>>=1;    return res == n;}bool dp(int st,int fi,int now){    if(check(st)){        if(s[now][fi]=='W' || s[fi][now] == 'L'){            g[fi] = now;            return true;        }        else return false;    }    int flag = 0;    for(int i=0;i
     
      >i)&1)continue;        if(s[i][fi] == 'W'||s[fi][i] == 'L'){            flag = 1;break;        }    }    if(flag == 0)return false;    for(int i=0;i
      
       >i)&1)continue;        if(s[now][i]=='W' || s[i][now] == 'L'){            g[i] = now;            if(dp(st+(1<
      
     
    

L3-013 非常弹的球

• 很骚的一个题，有高中物理知识可以推导出，当角度为45度时，路程最远。

#include 
    
     int main() {    double w, p, v2, s = 0;    scanf("%lf%lf", &w, &p);    v2 = 2 * 1000 * 100 / w;    while (v2 > 0.000001) {        s += v2 / 9.8;        v2 *= (100 - p) * 0.01;    }    printf("%.3f", s);    return 0;}