## 页面导航

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

#### 题目1

Flowerpot

img

##### 输入

1 ≤ N ≤ 100000，1 ≤ D ≤ 1000000，0≤x,y≤106。

##### 样例输入
4 5
6 3
2 4
4 10
12 15
##### 样例输出
2

##### 代码
#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);
s[1]=a[1];
for(int i=2;i<=n;i++)
{
{
if(s[tail].y-a[i].y>=m)
ans=min(ans,a[i].x-s[tail].x);
tail--;
}
s[++tail]=a[i];
}
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
##### 提示

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]

##### 代码
#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}$

$\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

##### 样例输入
【样例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
##### 提示

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.

##### 代码
#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

##### 题解

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