贝壳找房函数最值

题意

来源:计算之道2018复赛g

贝壳找房的攻城狮最近在研究一次函数 $f(x) = ax + b$。

现在有$n$个一次函数,$f_i(x) = a_ix+b_i$

容易发现,一次函数嵌套一次函数,还是一次函数。

$\displaystyle f_{i}(f_{j}(x)) = a_{i} ( a_{j}x + b_{j}) + b_{i}$

给定$x$,并且对于所有的$f_i(x)$ 可以任意改变顺序嵌套函数,求 $f(f(f(…f(x))…)$ 的最大值。

分析

考虑两个函数的互相嵌套
$ax + b$ 和 $cx+d$

$acx + ad + b$ 和 $acx + cb + d$

所以只要按$ad + b$和$cb + d$排序即可

代码

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
//ybmj
#include<bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 1e4+5;
struct P{
int u,v;
bool operator<(const P &A) const{
int a = u * A.v + v;
int b = A.u * v + A.v;
return a < b;
}
};
P a[maxn];
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
std::ios::sync_with_stdio(false);

int T;
cin >> T;
while(T--){
int n,x;
cin >> n >> x;
for(int i=0;i<n;i++){
cin >> a[i].u;
}
for(int i=0;i<n;i++){
cin >> a[i].v;
}
sort(a,a+n);
for(int i=0;i<n;i++){
x = x * a[i].u + a[i].v;
x %= 10;
}
cout << x << endl;
}
}