暑假集训系列题解（十二）

题目1

题目链接

Flowerpot

题目描述

老板需要你帮忙浇花。给出N滴水的坐标，y表示水滴的高度，x表示它下落到x轴的位置。

img

每滴水以每秒1个单位长度的速度下落。你需要把花盆放在x轴上的某个位置，使得从被花盆接着的第1滴水开始，到被花盆接着的最后1滴水结束，之间的时间差至少为D。

我们认为，只要水滴落到x轴上，与花盆的边沿对齐，就认为被接住。给出N滴水的坐标和D的大小，请算出最小的花盆的宽度W。

输入

第一行2个整数 N 和 D。
第2.. N+1行每行2个整数，表示水滴的坐标(x,y)。
1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤106。

输出

仅一行1个整数，表示最小的花盆的宽度。如果无法构造出足够宽的花盆，使得在D单位的时间接住满足要求的水滴，则输出-1。

样例输入

4 5
6 3
2 4
4 10
12 15

样例输出

2

提示

有4滴水， (6,3), (2,4), (4,10), (12,15).水滴必须用至少5秒时间落入花盆。花盆的宽度为2是必须且足够的。把花盆放在x=4..6的位置，它可以接到1和3水滴, 之间的时间差为10-3 = 7满足条件。

题解

单调栈，维护单调上升的y，然后求x之差的最小值。

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
    int x,y;
    bool operator <(const node& a) const
    {
        if(a.x!=x)
            return x<a.x;
        else
            return y<a.y;
    }
};
node a[100500]={0},s[100500]={0};
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    sort(a+1,a+n+1);
    int head=1,tail=1,ans=inf;
    s[1]=a[1];
    for(int i=2;i<=n;i++)
    {
        while(tail>=head&&s[tail].y>a[i].y)
        {
            if(s[tail].y-a[i].y>=m)
                ans=min(ans,a[i].x-s[tail].x);
            tail--;
        }
        s[++tail]=a[i];
        while(tail>=head&&s[tail].y-s[head].y>=m)
            ans=min(ans,s[tail].x-s[head].x),head++;
    }
    printf("%d\n",ans==inf?-1:ans);
}

题目2

题目链接

Haybale Restacking

题目描述

Farmer John has just ordered a large number of bales of hay. He would like to organize these into N piles (1 <= N <= 100,000) arranged in a circle, where pile i contains B_i bales of hay. Unfortunately, the truck driver delivering the hay was not listening carefully when Farmer John provided this information, and only remembered to leave the hay in N piles arranged in a circle. After delivery, Farmer John notes that pile i contains A_i bales of hay. Of course, the A_i's and the B_i's have the same sum.

Farmer John would like to move the bales of hay from their current configuration (described by the A_i's) into his desired target configuration (described by the B_i's). It takes him x units of work to move one hay bale from one pile to a pile that is x steps away around the circle. Please help him compute the minimum amount of work he will need to spend.

输入

* Line 1: The single integer N.
* Lines 2..1+N: Line i+1 contains the two integers A_i and B_i (1 <= A_i, B_i <= 1000).

输出

* Line 1:the minimum amount of work he will need to spend.

样例输入

4
7 1
3 4
9 2
1 13

样例输出

13

提示

设xi为第i堆干草与第i-1堆干草的交换数

令B[i]等于B[i]-A[i],则我们的目标是让B[i]全部变为0

B[1]-x1+x2=0 ==> x2=x1-B[1]

B[2]-x2+x3=0 ==> x3=x2-B[2]=x1-B[1]-B[2]

......xn-1=x1-B[1]-B[2]-...-B[n-1]

而我们要使 x1+x2+x3+...+xn-1 最小, 即|x1|+|x1-B[1]|+...+|x1-B[1]-B[2]-...-B[n-1]| 最小

所以x1要等于B[1],B[1]+B[2],...,B[1]+B[2]+...+B[n-1]的中位数

代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll b[100500]= {0};
ll a[100500]= {0};
ll sum[100500]= {0};
int main()
{
    ll n;
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        b[i]-=a[i];
        sum[i]=sum[i-1]+b[i];
    }
    sort(sum+1,sum+n+1);
    ll tmp=sum[(n+1)/2],ans=0;
    for(ll i=1; i<=n; i++)
        ans+=abs(sum[i]-tmp);
    cout<<ans<<endl;
}

题目3

题目链接

123 Triangle

题目描述

You are given four positive integers x0, x1, a, b. And you know $x_i=a⋅x_{i−1}+b⋅x_{i−2}$ for all i≥2.

Given two positive integers n, and MOD, please calculate xn modulo MOD.

Does the problem look simple? Surprise! The value of n may have many many digits!

输入

The input contains two lines.

The first line contains four integers x0, x1, a, b,a,b (1≤x0,x1,a,b≤109).

The second line contains two integers n, MOD (

img, n has no leading zero).

输出

Print one integer representing the answer.

样例输入

1 1 1 1
10 1000000001

样例输出

89

提示

The resulting sequence x is Fibonacci sequence. The 11-th item is 89.

题解

首先是十进制快速幂，例如：

$3^{1234}=((((ans*3^1)^{10}*3^2)^{10}*3^3)^{10}*3^4)^{10}$

然后是矩阵快速幂，$x_i=a⋅x_{i−1}+b⋅x_{i−2}$可以转换为：

$\left( \matrix{ a & b \\ 1& 0 \ } \right) ^{n-1} * \left(\matrix {x1 \\ x0 } \right) $

求出矩阵变为答案。

参考与：

https://blog.csdn.net/qq_41650771/article/details/98108098

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x0,x1,a,b,mod;
struct node
{
    ll data[3][3];
    void clear1()
    {
        data[1][2]=data[2][1]=0;
        data[1][1]=data[2][2]=0;
    }
    void clear()
    {
        data[1][2]=data[2][1]=0;
        data[1][1]=data[2][2]=1;
    }
    node operator * (const node& a) const
    {
        node tmp;
        tmp.clear1();
        for(ll i=1; i<=2; i++)
        {
            for(ll j=1; j<=2; j++)
            {
                for(ll k=1; k<=2; k++)
                {
                    tmp.data[i][j]+=data[i][k]*a.data[k][j];
                    tmp.data[i][j]%=mod;
                }
            }
        }
        return tmp;
    }
    void print()
    {
        printf("%lld %lld\n%lld %lld\n**\n",data[1][1],data[1][2],data[2][1],data[2][2]);
    }
};
char t[1005000]= {0};
node ksm(node a,int b)
{
    node ans1,ans2=a;
    ans1.clear();
    while(b!=0)
    {
        if(b%2)
            ans1=ans1*ans2;
        ans2=ans2*ans2;
        b/=2;
    }
    return ans1;
}
int main()
{
    scanf("%lld%lld%lld%lld",&x0,&x1,&a,&b);
    scanf("%s",t+1);
    scanf("%lld",&mod);
    node tmp1,tmp2;
    tmp2.data[1][1]=a;
    tmp2.data[1][2]=1;
    tmp2.data[2][1]=b;
    tmp2.data[2][2]=0;
    tmp1.data[1][1]=x1;
    tmp1.data[1][2]=x0;
    tmp1.data[2][1]=0;
    tmp1.data[2][2]=0;
    node tmp4;
    tmp4.clear();
    for(int i=1;t[i];i++)
    {
        tmp4=ksm(tmp4,10);
        node tmp3=ksm(tmp2,t[i]-'0');
        tmp4=tmp3*tmp4;
    }
    tmp1=tmp1*tmp4;
    cout<<tmp1.data[1][2]<<endl;
}

题目4

题目链接

XOR Game

题目描述

There are 2N integers written on a blackboard. The i-th integer is Ai.

Alice and Bob will play a game consisting of N rounds. In each round, they do the following:

First, Alice chooses an integer on the blackboard and erases it. Let x be the integer erased here.

Second, Bob chooses an integer on the blackboard and erases it. Let y be the integer erased here.

Finally, write the value x⊕y on a notebook, where ⊕ denotes the bitwise XOR.

In the end, all the integers on the blackboard will be erased, and the notebook will have N integers written

on it. The greatest integer written on the notebook will be the score of the game. Alice wants to maximize

this score, while Bob wants to minimize it. Find the score of the game when both players play optimally

under their objectives.

Constraints

1≤N≤$2×10^5$

0≤Ai<$2^{30}$

All values in input are integers.

输入

Input is given from Standard Input in the following format:

N

A1 A2 ⋯ A2N

输出

Print the answer.

样例输入

【样例1】
2
0 1 3 5
【样例2】
2
0 0 0 0
【样例3】
10
974654030 99760550 750234695 255777344 907989127 917878091 818948631 690392797 579845317 549202360 511962375 203530861 491981716 64663831 561104719 541423175 301832976 252317904 471905694 350223945

样例输出

【样例1】
4
【样例2】
0
【样例3】
268507123

提示

样例1解释：
Below is one possible progress of the game (it may contain suboptimal choices).

Round 1:

Alice chooses A1=0.

Bob chooses A3=3.

They write 0⊕3=3 on the notebook.

Round 2:

Alice chooses A4=5.

Bob chooses A2=1.

They write 5⊕1=4 on the notebook.

The score of the game is max(3,4)=4.

题解

字典树，即01trai，由于一个要最大化异或值，一个要最小化异或值，则答案为异或后最大值的最小值，即找两个数使得其异或值最小化即可。

代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int tree[10000005][2]= {0};
int size1[10000005]= {0};
int cnt=1;
void insert1(int k)
{
    int p=1;
    size1[p]++;
    for(int i=29; i>=0; i--)
    {
        int tmp=(k&(1<<i))?1:0;
        if(tree[p][tmp]==0)
            tree[p][tmp]=++cnt;
        p=tree[p][tmp];
        size1[p]++;
    }
}
int solve(int a,int b,int dp)
{
    if(dp<0)
        return 0;
    if(size1[a]==0||size1[b]==0)
        return inf;     ///左右无法再进行匹配
    if(a==b)
    {
        if(size1[tree[a][0]]%2==1)
        {
            return solve(tree[a][0],tree[a][1],dp-1)+(1<<dp);
        }
        else
        {
            int tmp1=solve(tree[a][0],tree[a][0],dp-1);
            int tmp2=solve(tree[a][1],tree[a][1],dp-1);
            if(tmp1>=inf)
                return tmp2;
            else if(tmp2>=inf)
                return tmp1;
            else
                return max(tmp1,tmp2);
        }
    }
    else
    {
        int ans=inf;
        if((tree[a][0]&&tree[b][0])||(tree[a][1]&&tree[b][1]))
        {
            ans=min(ans,solve(tree[a][0],tree[b][0],dp-1));
            ans=min(ans,solve(tree[a][1],tree[b][1],dp-1));
        }
        else
        {
            ans=min(ans,solve(tree[a][1],tree[b][0],dp-1)+(1<<dp));
            ans=min(ans,solve(tree[a][0],tree[b][1],dp-1)+(1<<dp));
        }
        return ans;
    }
}
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i=1; i<=2*n; i++)
    {
        scanf("%d",&m);
        insert1(m);
    }
    cout<<solve(1,1,29)<<endl;
}

题目5

题目链接

Mountain Climbing

题目描述

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.

样例输入

3
6 4
8 1
2 3

样例输出

17

题解

二级车间调度问题，贪心，让下山比上山快的先上，然后在贪心的缩短上山时间和扩大下山时间。

代码

#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;
}

题目6

题目链接

Tower

题目描述

There are N blocks, numbered 1,2,…,N. For each i (1≤i≤N), Block i has a weight of wi, a solidness of si and a value of vi.

Taro has decided to build a tower by choosing some of the N blocks and stacking them vertically in some order. Here, the tower must satisfy the following condition:

For each Block i contained in the tower, the sum of the weights of the blocks stacked above it is not greater than si.
Find the maximum possible sum of the values of the blocks contained in the tower.

Constraints
All values in input are integers.

1≤N≤$10^3$

1≤wi,si≤$10^4$

1≤vi≤$10^9$

输入

Input is given from Standard Input in the following format:
N
w1 s1 v1
w2 s2 v2
:
wN sN vN

输出

Print the maximum possible sum of the values of the blocks contained in the tower.

样例输入

【样例1】
3
2 2 20
2 1 30
3 1 40
【样例2】
4
1 2 10
3 1 10
2 4 10
1 6 10
【样例3】
5
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
1 10000 1000000000
【样例4】
8
9 5 7
6 2 7
5 7 3
7 8 8
1 9 6
3 3 3
4 1 7
4 5 5

样例输出

【样例1】
50
【样例2】
40
【样例3】
5000000000
【样例4】
22

提示

样例1解释：If Blocks 2,1 are stacked in this order from top to bottom, this tower will satisfy the condition, with the total value of 30+20=50.

样例2解释：Blocks 1,2,3,4 should be stacked in this order from top to bottom.

样例3解释：The answer may not fit into a 32-bit integer type.

样例4解释：We should, for example, stack Blocks 5,6,8,4 in this order from top to bottom.

题解

首先贪心排序，对于a和b两个物品，如果a放在b上面则权值为s[b]-w[a]，如果b放在a上面，则权值为s[a]-w[b]，则a和b的顺序由s[b]-w[a]和s[a]-w[b]所决定，移项可得即为比较s[a]+w[a]和s[b]+w[b]，所以根据s[a]+w[a]的大小贪心排序，后根据重量限制动态规划，即假设dp[i]为重量为i时的最大权值，则转移方程为：

$dp[j+w[i]]=max(dp[j+w[i]],dp[j]+v[i])(0<=j<=s[i])$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll w, s, v;
};
node a[1005] = {0};
ll dp[30050] = {0};
int main()
{
    ll n;
    scanf("%d", &n);
    for (ll i = 1; i <= n; i++)
        scanf("%d%d%d", &a[i].w, &a[i].s, &a[i].v);
    sort(a + 1, a + n + 1, [](node a, node b)
         { return a.s + a.w < b.s + b.w; });
    ll ans = 0;
    for (ll i = 1; i <= n; i++)
    {
        for (ll j = a[i].s; j >= 0; j--)
            dp[j + a[i].w] = max(dp[j + a[i].w], dp[j] + a[i].v);
    }
    for (ll j = 0; j < 30050; j++)
        ans = max(ans, dp[j]);
    cout << ans << endl;
}