牛客练习赛146
想要写题解的题目：B,C,D,E..不够一下可能写不完慢慢更新
B小灰灰的火焰星球2
链接：https://ac.nowcoder.com/acm/contest/122727/B
来源：牛客网
在宇宙的最深处有一个神奇的星球，这个星球的形状类似一条直线，在这个星球的最左边（坐标为 0 处）有一个十分强力的火山，火山会影响这个星球的每一个地方的温度，温度会随着离火山的距离越远而越低。有一天小灰灰因为不写作业被发配到了这个星球上去，他需要收集足够的学分才能够回到地球。这个星球可以看成一条长度为 𝑛+1 坐标轴，每一个整数点都有两个数值，一个 v 代表这个点存在的学分，一个 h 代表当前点的温度。由于星球中的生物神通广大，所以这个星球不遵循能量守恒定律，每天 0 点的时候学分都会刷新（即一个地点的学分在某天被收集后，在之后满足条件的日子里仍然可以被再次收集），并且每天每个地方的温度都是不变的。每天他都能获得一个法力值为 x 魔法法杖，可以保护他前往至多两处温度小于 x 的地方收集学分。
小灰灰共有 T 天可以收集学分。他会告诉你每天获得的魔法法杖的法力值，请你帮他算一算，他最多一共能收集多少学分。
思考过程:当天在温度小于等于X的情况下，我们选择两个不重复的学分，最后问收集的最多的学分是多少，但是每天0点我们所有位置的学分会刷新，但都是题目给的固定值，而且每天所选的学分在最优的情况下是在符合条件范围内找到最大的两个学分累加起来.....由于复杂度的原因，我们必须用高效率的查找方式快速找到题目输入的那个X，由于题目的单调不减特性，便可以考虑一下二分查找，于是问题变成了一下几个子问题:
1.我们得维护一下小于等于当前温度下的一个最大值和次大值。
2.完成二分查找。
3.debug，造数据。
个人的失误：这题我的二分返回值不小心写在while循环里面了，debug了好一阵子，应该避免。
//题目保证了单调不减是正序角度的，该题可以不用排序，只是个人更喜欢正序维护最大值和最小值。
AC代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n, t;
cin >> n >> t;
vector<PLL> a(n + 1, {0, 0});
rep(i, 1, n) cin >> a[i].fi;
rep(i, 1, n) cin >> a[i].se;
sort_range(a, 1, n);
vll maxs(n + 2, 0), cmaxs(n + 2, 0);
rep(i, 1, n)
{
ll v1 = maxs[i - 1], v2 = cmaxs[i - 1];
if (a[i].se >= v1)
{
maxs[i] = a[i].se, cmaxs[i] = v1;
}
else if (a[i].se >= v2)
{
maxs[i] = v1;
cmaxs[i] = a[i].se;
}
else
{
maxs[i] = v1, cmaxs[i] = v2;
}
}
auto check = [&](ll x) -> ll
{
ll l = 0, r = n + 1;
while (l + 1 < r)
{
ll mid = (r - l) / 2 + l;
if (a[mid].fi < x)
l = mid;
else
r = mid;
}
// return l;
return maxs[l] + cmaxs[l];
};
ll ans = 0;
while (t--)
{
ll x;
cin >> x;
ans += check(x);
// debug(check(x));
}
// rep(i, 1, n) debug(maxs[i]);
// rep(i,1,n) debug(cmaxs[i]);
cout << ans << endl;
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}C盲目自大的小灰灰
思考:
我们要解决两个问题：
怎么才能不死？
在不死的前提下，得分范围是多少？
- 什么是“必死”?
题目说机关在ti秒出现在左边(0)或者右边（1）。
*如果在ti秒，左边有机关，那你必须在ti秒之前跳到右边去。
*如果在tj秒，右边有机关，那你必须在tj秒之前跳回左边去。
关键点： 两个机关之间的时间差，决定了你有没有机会跳过去。
比如：
第 3 秒左边杀人，第 4 秒右边杀人。
3秒时你必须在右边。4秒时你必须在左边。
中间只有 1 秒间隔，你可以在第 3.5 秒（或者第 4 秒那一瞬间跳过去）。所以是安全>的。
但是！ 如果第 3 秒左边杀人，第 3 秒右边也杀人（当然题目保证不会），你就死定>了。
2.如何算分?
得分规则： 每次跳跃（左->右 或 右->左）得 1 分。
关键逻辑：
*假设上一个机关在t1秒，位置是左边（说明你在右边）。
*下一个机关在t2秒，位置还是左边(说明你还得在右边)。
*在t1和t2秒之间，你可以跳到左边玩一会然后再跳回来(一来一回得2分)，也可以不>动（得0分）。
*结论： 在两次必须躲避的时刻之间，你可以“刷分”，但刷的分数一定是 偶数（跳出去还得跳回来）。
脑海中想象一下这个过程，大概就能够想清楚了。
AC代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n, m;
cin >> n >> m;
vll t(m + 1), x(m + 1, 1);
rep(i, 1, m) cin >> t[i] >> x[i];
ll mi = 0, ma = 0, prev = 0;
rep(i, 1, m)
{
ll len = t[i] - prev;
ll tmp = x[i] ^ x[i - 1];
mi += tmp;
ma += (len % 2 == tmp) ? len : len - 1;
prev = t[i];
}
ll tail = n - prev;
ll q;
cin >> q;
while (q--)
{
ll s;
cin >> s;
bool flag = false;
if (tail == 0)
{
if (s >= mi && s <= ma && (s % 2 == mi % 2))
flag = true;
}
else
{
if (s >= mi && s <= ma + tail)
flag = true;
}
if (flag)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}E小机器人
思路：我们暴力的模拟每次区间操作，先抛开复杂度的问题，想想问题解决的朴素思想，我们动态修改{l,r}区间内最优最小值加上k个1，最暴力的方法是说，查找区间内的最优最小值，然后让这个最优最小值加+1，同时让k--表示完成一次加法操作。完全的暴力是不可行的，于是我们想到了分块的思想，我们想一个问题，当一个最小值足够小的时候，我们是不是不用修改我们的对象，一直让最小值加+1，直到把k耗尽即可，这是其中一种况且，第二种比较特别的情况是当k不为0时，你发现你目前的最优最小值马上要变成区间内的次小值了，之后就是在最小值和次小值交替相加，如果达到某个值的时候我们会让新的次小值进来，直至把这个k耗尽。
于是我们就理解了分块优化的妙处了
AC代码：
#include <bits/stdc++.h>
using namespace std;
// CJX__//
typedef long long ll; // 不开long long 见祖宗
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<PII> vPII;
#define IOS \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define debug(...) cout << "[debug] " #__VA_ARGS__ " = " << (__VA_ARGS__) << endl;
#define out(x) cout << ((x) ? "YES" : "NO") << endl
#define mod(x, P) (((x) % (P) + (P)) % (P))
#define endl '\n'
#define gcd __gcd
#define lc p << 1
#define rc p << 1 | 1
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define lowbit(x) ((x) & (-x))
#define rep(i, x, n) for (ll i = x; i <= n; i++)
#define dep(i, x, n) for (ll i = x; i >= n; i--)
#define mem(a, x) memset(a, x, sizeof a)
const double eps = 1e-5;
const int N = 1e5 + 10, M = 2 * N, K = 26;
const ll MOD = 1e9 + 7, Md3 = 998244353, Md7 = 1e9 + 7, Md9 = 1e9 + 9;
const ll base1 = 131, base2 = 13331;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
template <typename T>
bool cmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
bool cmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template <typename T>
void sort_range(vector<T> &v, int l, int r) { sort(v.begin() + l, v.begin() + r + 1); }
template <typename T>
struct BIT1
{
int n;
vector<T> tr;
BIT1(int n) : n(n), tr(n + 1) {}
void add(int x, T v)
{
for (; x <= n; x += x & -x)
tr[x] += v;
}
T sum(int x)
{
T r = 0;
for (; x; x -= x & -x)
r += tr[x];
return r;
}
T range(int l, int r) { return sum(r) - sum(l - 1); }
};
template <typename T>
struct BIT2
{
int n, m;
vector<vector<T>> t1, t2, t3, t4;
BIT2(int n_ = 0, int m_ = 0) { init(n_, m_); }
void init(int n_, int m_)
{
n = n_;
m = m_;
t1.assign(n + 1, vector<T>(m + 1, T{}));
t2.assign(n + 1, vector<T>(m + 1, T{}));
t3.assign(n + 1, vector<T>(m + 1, T{}));
t4.assign(n + 1, vector<T>(m + 1, T{}));
}
void _add(int x, int y, const T &v)
{
for (int i = x; i <= n; i += i & -i)
for (int j = y; j <= m; j += j & -j)
{
t1[i][j] += v;
t2[i][j] += v * x;
t3[i][j] += v * y;
t4[i][j] += v * x * y;
}
}
void rangeAdd(int x1, int y1, int x2, int y2, const T &v)
{
_add(x1, y1, v);
_add(x1, y2 + 1, -v);
_add(x2 + 1, y1, -v);
_add(x2 + 1, y2 + 1, v);
}
T prefixSum(int x, int y)
{
T r{};
for (int i = x; i > 0; i -= i & -i)
for (int j = y; j > 0; j -= j & -j)
r += t1[i][j] * (x + 1) * (y + 1) - t2[i][j] * (y + 1) - t3[i][j] * (x + 1) + t4[i][j];
return r;
}
T rangeSum(int x1, int y1, int x2, int y2)
{
if (x1 > x2 || y1 > y2)
return T{};
return prefixSum(x2, y2) - prefixSum(x1 - 1, y2) - prefixSum(x2, y1 - 1) + prefixSum(x1 - 1, y1 - 1);
}
};
struct Random
{
mt19937_64 rng;
Random() : rng(chrono::steady_clock::now().time_since_epoch().count()) {}
ull rand_ull(ull max_val = -1) { return rng() % (max_val + 1); }
ll rand_ll(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }
int rand_int(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
double rand_db(double l, double r) { return uniform_real_distribution<double>(l, r)(rng); }
bool rand_bool(double p = 0.5) { return bernoulli_distribution(p)(rng); }
template <typename T>
void shuffle(vector<T> &v) { std::shuffle(v.begin(), v.end(), rng); }
};
ll qmi(ll a, ll b, ll p)
{
ll res = 1 % p;
a %= p;
while (b)
{
if (b & 1)
res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
/*
*/
void solve()
{
ll n, m;
cin >> n;
vll a(n + 1, 0);
rep(i, 1, n) cin >> a[i];
cin >> m;
rep(op, 1, m)
{
ll l, r, k;
cin >> l >> r >> k;
while (k)
{
vll id;
id.push_back(l);
rep(j, l + 1, r)
{
if (a[j] > a[id[0]])
continue;
if (a[j] < a[id[0]])
id.clear();
id.push_back(j);
}
ll mi = INF;
rep(j, l, r)
{
if (a[j] > a[id[0]])
cmin(mi, a[j]);
}
ll d = min(k / (ll)id.size(), mi - a[id[0]]);
ll rem = 0;
k -= id.size() * d;
if (d < mi - a[id[0]])
rem = k % id.size();
for (auto x : id)
{
a[x] += d;
if (rem)
{
a[x]++;
rem--;
k--;
}
}
}
}
rep(i, 1, n) cout << a[i] << " ";
cout << endl;
}
int main()
{
IOS;
int _ = 1;
// cin>>_;//如果是多组数据
while (_--)
{
solve();
}
return 0;
}分块的基础题:
数列分块入门9题