A - Expression
给你三个数，让你插入一些 +,−和小括号，使得值最大
直接输出所有情况的最大值即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
ios::sync_with_stdio(false);
int a,b,c;
cin>>a>>b>>c;
cout<<max({a+b+c,a*(b+c),a*b*c,(a+b)*c})<<'\n';
return 0;
}
B - Towers
大意：给你一些有高度的塔，你可以执行 k次移动操作 a，b，把 a的高度 −1， b的高度 +1，使得最后极差最小。
输出极差最小值和操作过程。
思路：直接枚举k次操作，把最大的移动到最小的上即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
ios::sync_with_stdio(false);
int n,k;
cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
vector<pair<int,int> >ans;
int tot=1e9;
for(int i=1;i<=k;i++){
int l=0,r=1e9;
int x,y;
for(int j=0;j<n;j++){
if(a[j]<r){
r=a[j];
y=j;
}
if(a[j]>l){
l=a[j];
x=j;
}
}
if(l-r<=1)break;
ans.pb(make_pair(x,y));
a[x]--;
a[y]++;
//tot=min(tot,a[x]-a[y]);
}
int l=0,r=1e9;
for(int i=0;i<n;i++){
l=max(l,a[i]);
r=min(r,a[i]);
}
tot=l-r;
cout<<tot<<' '<<ans.size()<<'\n';
for(auto k:ans)cout<<k.fi+1<<' '<<k.se+1<<'\n';
return 0;
}
C - Exams
大意：n个考试，每个考试可以在a，b两个之一的时间完成，每完成一个考试都会写下a，要求n个考试之后，写下的a递增，问最早什么时候完成。
思路：dp，表示前i个完成的最早日期，每次枚举直接根据a，b的最小值或最大值与dp[i-1]的大小关系转移即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
struct uzi {
int a, b;
bool operator<(const uzi &t) const {
if (a == t.a)
return b < t.b;
return a < t.a;
}
};
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<uzi> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i].a >> a[i].b;
}
sort(a.begin(), a.end());
int ans = a[n - 1].a;
vector<int> d(n);
for (int i = 0; i < n; i++) {
if (!i)
d[i] = min(a[i].a, a[i].b);
else {
int res = min(a[i].a, a[i].b);
if (res < d[i - 1]) {
d[i] = max(a[i].a, a[i].b);
} else {
d[i] = res;
}
}
}
cout << min(ans, d[n - 1]) << '\n';
return 0;
}
D - Long Jumps GNU
大意：给你一个长 l的尺子上的刻度，让你加最少几次刻度能量出 x，y。
思路：模拟，显然每个刻度都能当起点或者终点，新加入的也是。注意一下所有的情况模拟即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int main() {
ios::sync_with_stdio(false);
int n, x, y, l;
cin >> n >> l >> x >> y;
vector<LL> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<LL> res;
res.pb(a[0]);
int dx = 0;
int dy = 0;
int dis = y - x, sta = 0;
for (int i = 1; i < n; i++) {
LL re = a[i] - x;
if (re >= 0) {
auto f = lower_bound(res.begin(), res.end(), re) - res.begin();
if (res[f] == re) {
dx = 1;
}
}
re = a[i] - y;
if (re >= 0) {
auto f = lower_bound(res.begin(), res.end(), re) - res.begin();
if (res[f] == re) {
dy = 1;
}
}
if (a[i] >= dis) {
auto f = lower_bound(res.begin(), res.end(), a[i] - dis) - res.begin();
if (res[f] == a[i] - dis && a[i] + x <= l)
sta = a[i] + x;
else if (res[f] == a[i] - dis && a[i] - y >= 0)
sta = a[i] - y;
}
LL pa = x + y;
if (a[i] >= pa) {
auto f = lower_bound(res.begin(), res.end(), a[i] - pa) - res.begin();
if (res[f] == a[i] - pa) {
sta = res[f] + x;
}
}
res.pb(a[i]);
}
if (dx && dy) {
cout << 0 << '\n';
} else {
if (!dx && dy) {
cout << 1 << '\n' << x << '\n';
} else if (!dy && dx) {
cout << 1 << '\n' << y << '\n';
} else {
if (sta)
cout << 1 << '\n' << sta << '\n';
else {
res.pb(1e18);
auto X = lower_bound(res.begin(), res.end(), y - x) - res.begin();
auto Y = lower_bound(res.begin(), res.end(), x + y) - res.begin();
if (res[X] == y - x || res[Y] == x + y) {
cout << 1 << '\n' << y << '\n';
} else {
cout << 2 << '\n' << x << ' ' << y << '\n';
}
}
}
}
return 0;
}
E - Riding in a Lift
大意：n层楼，你初始在a，你不能到b且每次移动的距离必须小于 ∣a−b∣,且每次不能不移动，问你k次移动产生的序列数。
思路：差分维护dp转移即可。下一次到的地方一定是两个连续的区间，直接差分做一下即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
const int mod = 1e9 + 7;
void add(LL &x, LL y) {
x += y;
if(x>=mod)x-=mod;
}
void del(LL &x, LL y) {
x -= y;
if(x<0)x+=mod;
}
LL dp[5003][5003];
int main() {
ios::sync_with_stdio(false);
int n, a, b, k;
cin >> n >> a >> b >> k;
dp[0][a] = 1;
for (int i = 1; i <= k; i++) {
for (int j = 1; j <= n; j++) {
if (j == b)
continue;
int dis = abs(j - b) - 1;
if (!dis)
continue;
int l = max(1, j - dis);
int r = min(n, j + dis);
add(dp[i][l], dp[i - 1][j]);
del(dp[i][j], dp[i - 1][j]);
add(dp[i][j + 1], dp[i - 1][j]);
if (r + 1 <= n)
del(dp[i][r + 1], dp[i - 1][j]);
}
for (int j = 1; j <= n; j++) {
add(dp[i][j], dp[i][j - 1]);
}
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
add(ans, dp[k][i]);
}
cout << ans % mod << '\n';
return 0;
}
京公网安备 11010502036488号