19-07-25 计蒜客

2019-07-26

目录

A题

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
104
105
106
107
108
109
//优先级按照礼物大小和时间来定
#include<bits/stdc++.h>
using namespace std;
const int maxs = 200+10;
const int maxq = 100+10;
const int maxk = 150000+10;
const int inf =0x7fffffff;
int T,k,m,q;//k是朋友的数量,m是打开m次，q是q次查询
int t,p;//第l个朋友来的时候放进来p个人
string ans[maxk];//这样是很浪费时间的
int query[maxq];
struct node
{
    string name;
    int time;//时间戳
    int value;
    friend bool operator < (node a,node b)//这里要和自己所想的相反
    {
        if(a.value==b.value)
            return a.time > b.time;
        else
            return a.value < b.value;
    }
    node(){}
    node(string  name ,int time,int value)
        {
            this->name = name;
            this->value = value;
            this->time  = time;
        }
};
struct open_gate
{
    int time;
    int number;
};
priority_queue<node> que;
node data[maxk];//记录朋友
open_gate open[maxk];//记录打开的次数
bool cmp1(open_gate a, open_gate b)
{
    return a.time<b.time;
}
int main()
{
    cin.tie(0);
    std::ios::sync_with_stdio(false);
    cin>>T;
    while(T--)
    {
        while(!que.empty()) que.pop();
        string name;
        int value;
        int n;
        cin>>k>>m>>q;
        for(int i=1;i<=k;i++)
        {
            cin>>name>>value;
            data[i] = node(name,i,value);
        }
        for(int i=1;i<=m;i++)
        {
            cin>>t>>p;
            open[i].time =t;
            open[i].number = p;
        }
        for(int i=1;i<=q;i++)
        {
            cin>>n;
            query[i] = n;
        }
    sort(open+1,open+m+1,cmp1);//保证升序
    int it = 0;
    int order = 0;
    int time ,number ;
    for(int i=1;i<=m;i++)
    {
        time = open[i].time;
        number = open[i].number;
        while(it<time)
        {
            que.push(data[++it]);
        }
        while(number--)
        {
            if(que.empty())//太毒瘤了。。这。。
                break;
            ans[++order] = que.top().name;
            que.pop();
        }
    }
    while(it<k)
        que.push(data[++it]);
    while(!que.empty())
    {
        ans[++order] = que.top().name;
        que.pop();
    }
    for(int i=1;i<=q;i++)
    {
        cout<<ans[query[i]];
        if(i!=q)
            cout<<" ";
        else
            cout<<endl;
    }
    }
    return 0;
}

B题 暴力

DFS暴力一波，跟着题目走

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4+10;//边数
const int maxm = 1e5+10;//点数
vector<int> edge[maxn],connect_part;
int vis[maxn],vis1[maxn];//两个dfs
int t,n,m,u,v;
ll value[maxn];
void ini()//边不用clear
{
    memset(vis,false,sizeof(vis));
    memset(vis1,false,sizeof(vis1));
}
bool judge(int from)
{
    int ans =0;
    for (auto to : edge[from] )
    {
        if(!vis[to])//没有被销毁,应该与顺序无关
        {
            ans++;
        }
    }
    return ans<2;//less than
}
void dfs(int from)
{
    vis[from] = true;
    for(auto to : edge[from])
    {
        if(!vis[to]&&judge(to))
        {
            dfs(to);
        }
    }
}
void dfs1(int from)//计算数目
{
    vis1[from] = true;
    for(auto to :edge[from])
    {
        if(!vis[to]&&!vis1[to])
        {
            connect_part.push_back(to);
            dfs1(to);
        }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ini();
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&value[i]);
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&judge(i))//遍历每一个联通快
                dfs(i);
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i])
                continue;
            else if(!vis1[i])//联通块为奇数
                {
                    connect_part.clear();
                    connect_part.push_back(i);
                    dfs1(i);
                    if(connect_part.size()%2==0)
                    {
                        for(auto to : connect_part)//挺好玩的
                            vis1[to] = 2;
                    }
                }
        }
        ll res = 0;
        for(int i=1;i<=n;i++)
        {
            if(vis[i])//虽然肯定不会有
                continue;
            if(vis1[i]==1)
            {
                res += value[i];
            }
        }
        printf("%lld\n",res);
        for(int i=1;i<=n;i++)
            edge[i].clear();
    }

}

注意清空数组，注意数据范围long long

G题

RMQ板子

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 root 1,n,1
#define lson(x) x<<1
#define rson(x) x<<1|1
#define lroot l,mid,lson(p)
#define rroot mid+1,r,rson(p)
using namespace std;
const int maxn = 1e3+10;
const int inf =0x7fffffff;
int tree[(maxn<<2)+10];
int a[maxn];
int t,n,q,l,r;
void push_up(int p)
{
    tree[p] = max(tree[lson(p)],tree[rson(p)]);
    return ;
}
void build_tree(int l,int r,int p)
{
    if(l==r)
    {
        tree[p] = a[l];
        return ;//关键
    }
    int mid = l + ((r-l)>>1);
    build_tree(lroot);
    build_tree(rroot);
    push_up(p);
}
int query(int x,int y,int l,int r,int p)
{
    int res = -inf;
    if(x<=l&&y>=r)//子集
    {
        return tree[p];
    }
    int mid = l+((r-l)>>1);
    if(x<=mid) res = max(res,query(x,y,lroot));
    if(y>mid) res = max(res,query(x,y,rroot));
    return res;
}

int main()
{
    scanf(" %d",&t);
    while(t--)
    {
        scanf(" %d",&n);
        for(int i=1;i<=n;i++)
            scanf(" %d",&a[i]);
        build_tree(root);
        scanf(" %d",&q);
        for(int i=1;i<=q;i++)
        {
            scanf("%d %d",&l,&r);
            printf("%d\n",query(l,r,root));
        }
    }

}

E题 并查集建图

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
//并查集建立联同
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 20000+10;
const int maxm =100000+10;
const int maxq = 5000+10;
int f[maxn];
ll cnt[maxn];
int t,n,m,q,u,v,w;
struct EDGE
{
    int from,to,cost;
    bool friend operator<(EDGE a,EDGE b)
    {
        return a.cost<b.cost;
    }
};
EDGE edge[maxm];
struct query
{
    int time;
    ll res;
    int ques;
}ans[maxq];
void ini()
{
    for(int i=1;i<=n;i++)
        {
            f[i] = i;
            cnt[i] = 1;
        }

}
int getf(int x)
{
    return x==f[x]?x:f[x]=getf(f[x]);
}
void merge(int x,int y)
{
    int t1 = getf(x), t2=getf(y);
    if(t1==t2)
    {
        return ;
    }
    else//可以合并
    {
        f[t2]= t1;
        cnt[t1] += cnt[t2];
        cnt[t2] = 0;
        return ;
    }
}
bool cmp1(query a,query b)
{
    return a.ques<b.ques;
}
bool cmp2(query a,query b)
{
    return a.time<b.time;
}
ll get_ans(ll x)
{
    ll res = x*(x-1);//c(n,2)*2
    return res;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&q);
        ini();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            edge[i].from = u;
            edge[i].to = v;
            edge[i].cost = w;
        }
        sort(edge+1,edge+m+1);
        for(int i=1;i<=q;i++)
           {
                scanf("%d",&ans[i].ques);
                ans[i].time = i;
           }
        sort(ans+1,ans+q+1,cmp1);
        int limit=-1;//cnt记录联同集
        int it=1;//用于遍历边数组
        int from,to;
        for(int i=1;i<=q;i++)
        {
            ll res = 0;
            limit = ans[i].ques;
            while(it<=m&&edge[it].cost<=limit)
            {
                from = edge[it].from;
                to = edge[it].to;
                merge(from,to);
                it++;
            }
            for(int j=1;j<=n;j++)
            {
                if(cnt[j]<=1)
                    continue;
                if(f[j]==j)
                {
                    res+=get_ans(cnt[j]);//只找爸爸
                }
            }
            ans[i].res = res;
        }
        sort(ans+1,ans+q+1,cmp2);
        for(int i=1;i<=q;i++)
            printf("%lld\n",ans[i].res);
    }
}

I

多重背包+二进制优化（可以看背包九讲）

注意清空tot，两次多重背包，首先找到最小容量然后根据最小容量找到最小卡车花销。

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<bits/stdc++.h>
using namespace std;
const int inf = 0x7fffffff;
const int maxn = 2000+10;
const int maxm = 2000+10;
const int maxp = 50000;
const int maxcost = 50000;
int tot = 0;//用于第一个DP打包
int n,m,p;
int T;
int t,u,v;
int x,y,z;
int cost[maxn];//体积占比
int value[maxn];//提供能量占比
int dp[maxp+200];
int  pack1()//计算最小需要的容量
{
    for(int i=0;i<=p+100;i++)
        dp[i] = inf;
    dp[0] = 0;//可行解,传递闭包
    for(int i=1;i<=tot;i++)
    {
        for(int j=p+100;j>=value[i];j--)
            {
                if(dp[j-value[i]]==inf)
                    continue;
                dp[j] = min(dp[j],dp[j-value[i]]+cost[i]);
            }
    }
    //能得到需求能量的前提下的最小花销,内部能量外部花销
    int min_v = inf;
    for(int i=p;i<=p+100;i++)
    {
        min_v = min(dp[i],min_v);
    }
    return min_v;

}
int pack2(int min_v)//计算最小容量的最小花销，最小花销不能过大
{
    memset(dp,0,sizeof(dp));//可以不装满
    for(int i=1;i<=tot;i++)
    {
        for(int j=maxcost;j>=cost[i];j--)
        {
            dp[j] = max(dp[j],dp[j-cost[i]]+value[i]);
        }
    }
    //这里是满足容量下的最小花销，内部花销外部容量
    for(int i=1;i<=maxcost;i++)
        if(dp[i]>=min_v)
            return i;//最小花销
    return inf;

}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        tot = 0;//初始化操作
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&t,&u,&v);
            for(int k=1;v;k<<=1)
            {
                int num = min(k,v);
                cost[++tot] = num*u;
                value[tot] = num*t;
                v -= num;
            }
        }
        int min_v = pack1();//最小容量
        tot = 0;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&x,&y,&z);
            for(int k=1;z;k<<=1)
            {
                int num = min(k,z);
                cost[++tot] = num*y;//所需要的花销
                value[tot] = num*x;//能提供的体积
                z-= num;
            }
        }
        if(min_v==inf)
            {
                printf("TAT\n");
                continue;
            }
        int ans = pack2(min_v);
        if(ans==inf)
            {
               printf("TAT\n");
               continue;
            }
        else
            printf("%d\n",ans);

    }
    return 0;
}
© 2019 blog - Powered by Hexo - Theme Chan