muti多校-10

自用笔记算法

muti多校-10

HDU 6178

题目要求

给你一棵n节点的树，现在让你放k个猴子，可以删边，问最少可以剩余几条边，放k个猴子，满足任意一个猴
子至少与一只猴子相连

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>e[maxn];
int du[maxn];
int vis[maxn];
namespace IO {
    const int MT = 100 * 1024 * 1024;
    char IO_BUF[MT];
    int IO_PTR, IO_SZ;
    /// 要记得把这一行添加到main函数第一行！！！
    void begin() {
        IO_PTR = 0;
        IO_SZ = fread (IO_BUF, 1, MT, stdin);
    }
    template<typename T>
    inline bool scan_d (T & t) {
        while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != '-' && (IO_BUF[IO_PTR] < '0' || IO_BUF[IO_PTR] > '9'))
            IO_PTR ++;
        if (IO_PTR >= IO_SZ) return false;
        bool sgn = false;
        if (IO_BUF[IO_PTR] == '-') sgn = true, IO_PTR ++;
        for (t = 0; IO_PTR < IO_SZ && '0' <= IO_BUF[IO_PTR] && IO_BUF[IO_PTR] <= '9'; IO_PTR ++)
            t = t * 10 + IO_BUF[IO_PTR] - '0';
        if (sgn) t = -t;
        return true;
    }
    inline bool scan_s (char s[]) {
        while (IO_PTR < IO_SZ && (IO_BUF[IO_PTR] == ' ' || IO_BUF[IO_PTR] == '\n') ) IO_PTR ++;
        if (IO_PTR >= IO_SZ) return false;
        int len = 0;
        while (IO_PTR < IO_SZ && IO_BUF[IO_PTR] != ' ' && IO_BUF[IO_PTR] != '\n')
            s[len ++] = IO_BUF[IO_PTR], IO_PTR ++;
        s[len] = '\0';
        return true;
    }
    template<typename T>
    void print(T x) {
        static char s[33], *s1; s1 = s;
        if (!x) *s1++ = '0';
        if (x < 0) putchar('-'), x = -x;
        while(x) *s1++ = (x % 10 + '0'), x /= 10;
        while(s1-- != s) putchar(*s1);
    }
    template<typename T>
    void println(T x) {
        print(x); putchar('\n');
    }
};
using namespace IO;
int main(){
//    freopen("input.txt","r",stdin);
    begin();
    int t;
    scan_d(t);
    while(t--){
        int n,k;
        scan_d(n),scan_d(k);
        for(int i=0;i<=n;i++) e[i].clear();
        int ans=0;
        mm(du,0),mm(vis,0);
        for(int i=2;i<=n;i++){
            int x;
            scan_d(x);
            e[x].push_back(i);
            e[i].push_back(x);
            du[i]++,du[x]++;
        }
        queue<int>q;
        for(int i=1;i<=n;i++){
            if(du[i]==1) q.push(i);
        }
        while(!q.empty()){
            int x=q.front();
            q.pop();
            int len=e[x].size();
            for(int i=0;i<len;i++){
                int next=e[x][i];
                if(!vis[x] && !vis[next]){
                    vis[x]=1;
                    vis[next]=1;
                    ans++;
                }
                du[next]--;
                if(du[next]==1) q.push(next);
            }
        }
        if(ans*2>=k) ans=(k+1)/2;
        else ans+=k-ans*2;
        printf("%d\n",ans);
    }
    return 0;
}

思路

利用贪心的思维，显然我们应该先选择性价比最高的，即一条边连接两个点的情况。计算出这样的边的条数ans，如果ans*2>=k,结果就是(k+1)/2,
否则剩下来没有安排的猴子每一只需要多一条边，即结果为ans+k-2×ans。我的方法是用类拓扑排序的方法，找连接两个度数为1且没用被用过的点的边数，
每次找到一条边后注意更新度数。

HDU 6180

题目要求

已知一些商品制作的开始和结束时间，问在使用最少的机器的前提下机器工作的最少的总时间是多少

参考AC代码

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<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct node{
    int s,e;
}a[maxn];
multiset<int>st;
bool cmp(node a,node b){
    return a.s<b.s;
} 
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        st.clear();
        int n;
        scanf("%d",&n);
        for(int i=0;i<n;i++) scanf("%d%d",&a[i].s,&a[i].e);
        sort(a,a+n,cmp);
        LL ans=0;
        for(int i=0;i<n;i++){
            auto it=st.upper_bound(a[i].s);
            if(it==st.begin()){
                ans+=(LL)a[i].e-a[i].s;
                st.insert(a[i].e);
            }
            else{
                it--;
                ans+=(LL)a[i].e-*it;
                st.erase(it);
                st.insert(a[i].e);
            }
        }
        printf("%d %lld\n",st.size(),ans);
    }
    return 0;
}

思路

用multiset容器维护结束时间
按照区间左端点排序 第一个插入set后开始维护
若用upper_bound能找到合法的插入开始时间 删除原来的结束时间 更新成新的结束时间 更新总时间
若未找到合法的插入时间 新加入一个机器 插入结束时间 更新总时间

HDU 6181

题目要求

次短路裸题

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define P pair<LL,int>
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
const LL INF =(LL)1e18;
struct node{
    int to;
    LL w;
    node(int to,LL w):to(to),w(w){}
};
vector<node>G[maxn];
bool vis[maxn];
LL d[maxn],d1[maxn];
int n,m;
void solve(){
    priority_queue<P,vector<P>,greater<P> >que;
    fill(d+1,d+1+n,INF);
    fill(d1+1,d1+1+n,INF);
    d[1]=0;
    que.push(P(0,1));
    while(!que.empty()){
        P p=que.top();
        que.pop();
        int v=p.second;
        if(d1[v]<p.first) continue;
        int len=G[v].size();
        for(int i=0;i<len;i++){
            node &e=G[v][i];
            LL d2=p.first+e.w;
            if(d[e.to]>d2){
                swap(d[e.to],d2);
                que.push(P(d[e.to],e.to));
            }
            if(d1[e.to]>d2 && d[e.to]<d2){
                d1[e.to]=d2;
                que.push(P(d1[e.to],e.to));
            }
        }
    }    
    printf("%lld\n",d1[n]);
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<=n;i++) G[i].clear();
        for(int i=1;i<=m;i++){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(node(v,w));
            G[v].push_back(node(u,w));
        }
        solve();
    }
    return 0;
}

思路

次短路模版题

本文标题:muti多校-10

文章作者:Hippopmonkey

发布时间:2017-08-28, 02:05:24

最后更新:2017-08-28, 02:13:11

原始链接:http://xuboming8.github.io/2017/08/28/muti多校-10/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. muti多校-10
    1. 1.1. HDU 6178
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6180
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6181
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
|