暑假集训系列题解（九）

暑假集训系列题解（九）¶

题目1¶

题目链接¶

题目描述¶

Takahashi Kingdom has N towns, called Town 1 through N. There are N−1 roads in this kingdom. The i-th road connects Town ui and Town vi bidirectionally. For any two towns a and b, it is possible to get from Town a to Town b by traversing some roads. Takahashi, the king, wants to spread some information all over the kingdom. Since he is busy, he can directly transmit this information to at most K towns. Assume that Takahashi finishes transmitting the information at time 0. Then, for each t=1,2,3,⋯, the following happens: For towns a and b directly connected by a road, if a has already received the information at time t−0.5 but b has not, b receives it at time t. Takahashi wants to choose the K towns to transmit the information to minimize the time taken until every town receives it. Find the minimum time this takes.

Constraints All values in input are integers. 1≤K<N≤ $2×10^5$ 1≤ui,vi≤N For any two towns a and b, it is possible to get from Town a to Town b by traversing some roads.

输入¶

Input is given from Standard Input in the following format: N K u1 v1 u2 v2 ⋮ uN−1 vN−1

输出¶

Print the answer.

样例输入¶

样例输出¶

【样例1】
1
【样例2】
2
【样例3】
3

题解¶

树上DP，详细见代码注释。

参考链接：

https://blog.csdn.net/qq_48099121/article/details/115670878

代码¶

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
    int to,next;
};
node edge[400500]= {0};
int head[200500]= {0};
int cnt=0,num=0;
void add_edge(int from,int to)
{
    edge[++cnt]= {to,head[from]};
    head[from]=cnt;
}
int f[200500]= {0}; ///f代表以u为根节点的子树中距离u最近的特殊点
int g[200500]= {0}; ///g代表以u为根节点的子树中未被覆盖到的最远的点
int dfs(int now,int fa,int mid)
{
    f[now]=inf,g[now]=0;
    for(int i=head[now]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa)
            continue;
        dfs(to,now,mid);
        f[now]=min(f[now],f[to]+1);
        g[now]=max(g[now],g[to]+1);
    }
    if(g[now]+f[now]<=mid)
        g[now]=-inf;
    else if(g[now]==mid)
        g[now]=-inf,f[now]=0,num++;
}
int check(int mid)
{
    num=0;
    dfs(1,-1,mid);
    if(g[1]>=0)   ///还有未被覆盖到的点
        num++;
    return num;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n-1; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add_edge(x,y);
        add_edge(y,x);
    }
    int l=0,r=n;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid)<=m)
            r=mid;
        else
            l=mid+1;
    }
    cout<<l<<endl;
}

题目2¶

题目链接¶

http://icpc.upc.edu.cn/problem.php?cid=2889&pid=5

题目描述¶

Farmer John has just received a new shipment of N (1 <= N <= 20) bales of hay, where bale i has size S_i (1 <= S_i <= 100). He wants to divide the bales between his three barns as fairly as possible.

After some careful thought, FJ decides that a "fair" division of the hay bales should make the largest share as small as possible. That is, if B_1, B_2, and B_3 are the total sizes of all the bales placed in barns 1, 2, and 3, respectively (where B_1 >= B_2 >= B_3), then FJ wants to make B_1 as small as possible.

For example, if there are 8 bales in these sizes: 2 4 5 8 9 14 15 20

A fair solution is Barn 1: 2 9 15 B_1 = 26 Barn 2: 4 8 14 B_2 = 26 Barn 3: 5 20 B_3 = 25

Please help FJ determine the value of B_1 for a fair division of the hay bales.

输入¶

* Line 1: The number of bales, N. * Lines 2..1+N: Line i+1 contains S_i, the size of the ith bale.

输出¶

* Line 1: Please output the value of B_1 in a fair division of the hay bales.

样例输入¶

样例输出¶

题解¶

三维动态规划转移，代码如下：

代码¶

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
ll a[25]= {0};
bool dp[2][2005][2005]= {0};
int main()
{
    ll n,sum=0;
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
    {
        scanf("%lld",&a[i]);
        sum+=a[i];
    }
    dp[1][0][0]=true;
    ll last=1,now=0;
    ll ans=sum;
    for(ll i=1; i<=n; i++)
    {
        for(ll j=0; j<2005; j++)
        {
            for(ll k=0; k<2005; k++)
            {
                if(dp[i&1][j][k]==1)
                {
                    dp[(i+1)&1][j][k]=true;
                    if(k+a[i]<2005)
                        dp[(i+1)&1][j][k+a[i]]=true;
                    if(j+a[i]<2005)
                        dp[(i+1)&1][j+a[i]][k]=true;
                }
            }
        }
    }
    for(ll j=0; j<2005; j++)
    {
        for(ll k=0; k<2005; k++)
        {
            if(dp[n&1][j][k])
            {
                ans=min(ans,max(sum-j-k,max(j,k)));
            }
        }
    }
    cout<<ans<<endl;
}

题目3¶

题目链接¶

http://icpc.upc.edu.cn/problem.php?cid=2889&pid=7

题目描述¶

Given are two sequences of length N each: A=(A1,A2,A3,…,AN) and B=(B1,B2,B3,…,BN). Determine whether it is possible to make A equal B by repeatedly doing the operation below (possibly zero times). If it is possible, find the minimum number of operations required to do so.

Choose an integer i such that 1≤i<N, and do the following in order: swap Ai and Ai+1; add 1 to Ai; subtract 1 from Ai+1. Constraints 2≤N≤ $2×10^5$ 0≤Ai≤ $10^9$ 0≤Bi≤ $10^9$ All values in input are integers.

输入¶

Input is given from Standard Input in the following format: N A1 A2 A3 … AN B1 B2 B3 … BN

输出¶

If it is impossible to make A equal B, print -1. Otherwise, print the minimum number of operations required to do so.

样例输入¶

【样例1】
3
3 1 4
6 2 0
【样例2】
3
1 1 1
1 1 2
【样例3】
5
5 4 1 3 2
5 4 1 3 2
【样例4】
6
8 5 4 7 4 5
10 5 6 7 4 1

样例输出¶

【样例1】
2
【样例2】
-1
【样例3】
0
【样例4】
7

提示¶

样例1解释： We can match A with B in two operations, as follows: First, do the operation with i=2, making A=(3,5,0). Next, do the operation with i=1, making A=(6,2,0). We cannot meet our objective in one or fewer operations. 样例2解释： In this case, it is impossible to match A with B. 样例3解释： A may equal B before doing any operation.

题解¶

对一个数组进行如上的三次操作之后 $i+a[i]$ 的值保持不变，所以只要把a数组 $i+a[i]$ 转变为b数组中 $j+b[j]$ 即可，又因为为相邻交换，所以只需要求出逆序对即可。

参考链接：

https://blog.csdn.net/weixin_45483201/article/details/117699573

https://www.cnblogs.com/spnooyseed/p/14810702.html

代码¶

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3."Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
const ll maxn=400000;
ll tree[400500]={0};
ll a[200500]={0};
ll b[200500]={0};
unordered_map<int,vector<int> >mpa,mpb;
ll lowbit(ll x)
{
    return x&(-x);
}
void add(ll pos,ll val)
{
    for(ll i=pos;i<=400000;i+=lowbit(i))
        tree[i]+=val;
}
ll query(ll pos)
{
    ll ans=0;
    for(ll i=pos;i>=1;i-=lowbit(i))
        ans+=tree[i];
    return ans;
}
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=i;
        mpa[a[i]].push_back(i);
    }


    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&b[i]);
        b[i]+=i;
        mpb[b[i]].push_back(i);
    }

    for(auto v:mpa)
    {
        if(v.second.size()!=mpb[v.first].size())
            return 0*puts("-1");
        auto v2=mpb[v.first];
        for(int i=0;i<v.second.size();i++)
            a[v.second[i]]=v2[i];
    }

    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        add(a[i],1);
        ans+=i-query(a[i]);
    }
    cout<<ans<<endl;
}

题目4¶

题目链接¶

http://icpc.upc.edu.cn/problem.php?cid=2890&pid=3

题目描述¶

Farmer John has discovered that his cows produce higher quality milk when they are subject to strenuous exercise. He therefore decides to send his N cows (1 <= N <= 25,000) to climb up and then back down a nearby mountain!

Cow i takes U(i) time to climb up the mountain and then D(i) time to climb down the mountain. Being domesticated cows, each cow needs the help of a farmer for each leg of the climb, but due to the poor economy, there are only two farmers available, Farmer John and his cousin Farmer Don. FJ plans to guide cows for the upward climb, and FD will then guide the cows for the downward climb. Since every cow needs a guide, and there is only one farmer for each part of the voyage, at most one cow may be climbing upward at any point in time (assisted by FJ), and at most one cow may be climbing down at any point in time (assisted by FD). A group of cows may temporarily accumulate at the top of the mountain if they climb up and then need to wait for FD's assistance before climbing down. Cows may climb down in a different order than they climbed up.

Please determine the least possible amount of time for all N cows to make the entire journey.

输入¶

Line 1: The number of cows, N.
Lines 2..1+N: Line i+1 contains two space-separated integers: U(i) and D(i). (1 <= U(i), D(i) <= 50,000).

输出¶

Line 1: A single integer representing the least amount of time for all the cows to cross the mountain.

样例输入¶

样例输出¶

题解¶

贪心，详细见代码注释。

代码¶

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
struct node
{
    ll u,d,sum,sum1;
};
bool cmp(node a,node b)
{
    if(a.d>a.u&&b.d<=b.u)        ///下山比上山慢的的优先上
        return 1;
    else if(a.d<=a.u&&b.d>b.u)
        return 0;
    else if(a.d>a.u)            ///先上的优先让上山快的上，加速时间
        return a.u<b.u;
    else
        return a.d>b.d;         ///后上的优先让下山的慢的上，尽可能拖延时间
}
node a[25500]={0};
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)
        scanf("%lld%lld",&a[i].u,&a[i].d);
    sort(a+1,a+n+1,cmp);
    ll ans=0;
    for(ll i=1;i<=n;i++)
        a[i].sum=a[i-1].sum+a[i].u;
    for(ll i=1;i<=n;i++)
    {
        a[i].sum1=max(a[i].sum,a[i-1].sum1)+a[i].d;
        ans=max(ans,a[i].sum1);
    }
    cout<<ans<<endl;
}