2022杭电多校5(总结+补题)

总结

今天这把多校打的不是很好，开局跟队友2讨论了45分钟过了1010，队友1单做1012但是看错了题目wa1，然后队友2跟队友1一起做1012，我去开1003，一小时后他们做出了1012，我看着1003题目中1e6的点数，想到了之前队里图论大佬曾经说过多个点连边时可以用线段树优化建图，就跑去学线段树建图去了，找了半天博客虚了两个多小时写出了一发线段树优化建图的最短路但是t了，顿时怀疑人生，然后发现 $nlo{g}^{2}n$ 其实好像过不了这题，遂陷入自闭，最后半个小时队友又有了其他想法，交了二十多发终于在最后一分钟a了1003，三题结束。

题解

1003 - Slipper

题意：

给你一颗 $n$ 个点 $n-1$ 条无向边的树，树的根是 $1$ ，除了树边之外，深度差为 $k$ 的点可以两两以代价 $p$ 相互到达，问树上两点的最短路。

做法：

由于题目点数给到了 $1e6$ ，所以线段树优化建边的方法应该是不行的(多一个 $log$ 直接导致了代码 $tle$ )，所以我们考虑优化建图方法，我们可以新建树的层数个点，记为层主，让深度相同的点向层主建一条边权为 $0$ 的双向边，再让第 $i$ 层的层主向第 $i+k$ 层的所有点建一条有向边，再跑最短路即可。

(这里图片旋转不会调T_T)

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<ll,int>
#define f first
#define s second
using namespace std;
const ll inf = 0x3f3f3f3f;
int t;
int n,m;
int dis[2000010];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<vector<P>> g(n*2+1);
        for(int i=1;i<n;i++)
        {
            int u,v,w;
            cin>>u>>v>>w;
            g[u].emplace_back(v,w);
            g[v].emplace_back(u,w);
        }
        int k,p;
        cin>>k>>p;
        int ma=-1;
        vector<int> vis(n+1,0);
        function<void(int,int)> dfs = [&](int now,int idx)
        {
            vis[now]=vis[idx]+1;
            ma=max(ma,vis[now]);
            for(int i=0;i<g[now].size();i++)
            {
                int vv=g[now][i].f;
                if(vv!=idx)
                    dfs(vv,now);
            }
        };
        dfs(1,0);
        for(int i=1;i<=n;i++)
            g[n+vis[i]].emplace_back(i,0);
        for(int i=1;i<=n;i++)
        {
            if(vis[i]+k<=ma)
            {
                g[i].emplace_back(n+vis[i]+k,p);
                g[n+vis[i]+k].emplace_back(i,p);
            }
        }
        int st,end1;
        cin>>st>>end1;
        function<void()> dij = [&]()
        {
            memset(dis,0x7f,sizeof dis);
            dis[st]=0;
            priority_queue<P,vector<P>,greater<P> >q;
            q.emplace(0,st);
            int di,u,v,w;
            while(!q.empty())
            {
                tie(di,u)=q.top();
                q.pop();
                if(di>dis[u])
                    continue;
                for(int i=0;i<g[u].size();i++)
                {
                    tie(v,w)=g[u][i];
                    if(dis[v]>dis[u]+w)
                    {
                        dis[v]=dis[u]+w;
                        q.emplace(dis[v],v);
                    }
                }
            } 
            cout<<dis[end1]<<endl;
        };
        dij();
    }
    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

1010 - Bragging Dice

题意：

酒桌摇骰子游戏。

做法：

由于玩家 B 只能再玩家 A 断言后进行质疑（开盒）或继续断言，因此如果存在骰子点数为真的情况时，玩家 A 总是可以第一次就猜合理且最大的，导致玩家 B 无法继续断言，因此，只要二人的骰子不触发特殊规则 3 ，玩家 A 都是必胜的，所以我们只需要特判一下特殊规则三作为玩家 B 的必胜条件（其他情况都是玩家 A 必胜）即可。

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        vector<int> vis1(7,0),vis2(7,0);
        int m1=0,m2=0;
        for(int i=0;i<n;i++)
        {
            cin>>m;
            vis1[m]++;
            if(vis1[m]>1)
                m1=1;
        }
        for(int i=0;i<n;i++)
        {
            cin>>m;
            vis2[m]++;
            if(vis2[m]>1)
                m2=1;
        }
        if(m1||m2)
            cout<<"Win!"<<endl;
        else
            cout<<"Just a game of chance."<<endl;
    }
    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

1012 - Buy Figurines

题意：

有 n 个人去排队，每个人有一个到达时间 a_i 与一个买东西所需要的时间 s_i ，买东西的队伍有 m 个，第 i 个人到达后，会首先查看当前所有队伍，并选择人数最少的一个队伍排队（当多个队伍人数均为最小值时选择标号最小的一个队伍），问最后一个买完东西的人的结束时间。

做法：

我们考虑使用 $set$ 维护每个排队者的结束时间 $time$ 和所排的队列，当排队者的结束时间小于等于新来人的到达时间时，说明排队者已经结束购买，我们将它从 $set$ 里删除，再使用线段树+二分的方法确定新来人即将排的队列，新来人的结束时间即为 $max(该队伍中上一个人的结束时间，新来人的到达时间)+新来人的购买时间$ ，并用新来人的结束时间更新答案。迭代从第 $1$ 个人开始模拟到 $n$ 即可得到答案

代码：

/*
 author:wuzx
 */

#include
#define ll long long
#define int long long
#define endl "\n"
#define P pair<int,int>
#define f first
#define s second
using namespace std;
const int inf = 0x3f3f3f3f;
int t;
int n,m,k;
struct segtree{
    struct node{
        int l,r,tag;
        int val;
    };
    vector<node> tr;
    segtree(int n1):tr((n1+10)<<2){}
    void build(int root,int l,int r)//根节点为1，范围从1-n
    {
        tr[root].l=l;
        tr[root].r=r;
        tr[root].tag=0;//add的初始值为0
        if(l==r)
        {
            tr[root].val=0;//初始值
            return;
        }
        int mid=(l+r)>>1;
        build(root<<1,l,mid);
        build(root<<1|1,mid+1,r);
        tr[root].val=min(tr[root<<1].val,tr[root<<1|1].val);
    }
    void spread(int p)
    {
        if(tr[p].tag!=0)
        {
            tr[p<<1].val+=tr[p].tag;
            tr[p<<1|1].val+=tr[p].tag;
            tr[p<<1].tag+=tr[p].tag;
            tr[p<<1|1].tag+=tr[p].tag;
            tr[p].tag=0;
        }
    }
    void update(int root,int l,int r,int x)
    {
        if(l<=tr[root].l&&r>=tr[root].r)
        {
            tr[root].val+=x;
            tr[root].tag+=x;
            return;
        }
        spread(root);
        int mid=(tr[root].l+tr[root].r)>>1;
        if(l<=mid)
            update(root<<1,l,r,x);
        if(r>mid)
            update(root<<1|1,l,r,x);
        tr[root].val=min(tr[root<<1].val,tr[root<<1|1].val);
    }
    int getmin(int root,int l,int r)//单点更新下的
    {
        if(l<=tr[root].l&&r>=tr[root].r)
            return tr[root].val;
        spread(root);
        int mid=(tr[root].l+tr[root].r)>>1;
        int ans=inf*inf;
        if(l<=mid)
            ans=min(ans,getmin(root<<1,l,r));
        if(r>mid)
            ans=min(ans,getmin(root<<1|1,l,r));
        return ans;
    }
};
signed main()
{
    // freopen("1012.in", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        vector<P> a(n);
        for(int i=0;i<n;i++)
            cin>>a[i].f>>a[i].s;
        sort(a.begin(),a.end());
        multiset<P> st;
        segtree tr(m);
        tr.build(1,1,m);
        int l,r,mid;
        int ans=0;
        vector<int> time(m+1,1);
        for(int i=0;i<n;i++)
        {
            while(st.size())
            {
                P xx=*st.begin();
                if(xx.f<=a[i].f)
                {
                    tr.update(1,xx.s,xx.s,-1);
                    st.erase(st.begin());
                }
                else    
                    break;
            }
            l=1,r=m;
            int num=tr.getmin(1,1,m);
            while(l<r)
            {
                mid=(l+r)/2;
                if(tr.getmin(1,1,mid)>num)
                    l=mid+1;
                else
                    r=mid;
            }
            k=max(time[l],a[i].f)+a[i].s;
            time[l]=k;
            st.emplace(k,l);
            ans=max(ans,k);
            tr.update(1,l,l,1);
        }
        cout<<ans<<endl;
    }
    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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131