A.小乔和小灰灰
题解：
用两个数组记录所需的序列，再用两个下标来记录当前原数组能组成的最长的满足条件的子序列位置，遍历整个序列，最后判断两个下标是否遍历完所需序列
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char s[maxn];
string a = "XiaoQiao";
string b = "XiaoHuiHui";
int x, y;
int main()
{
scanf("%s", s + 1);
for (int i = 1; i <= strlen(s + 1); i++)
{
if (s[i] == a[x])
x++;
if (s[i] == b[y])
y++;
}
if (x == a.length() && y == b.length())
puts("Happy");
else
puts("emm");
return 0;
}B.牛能和小镇
题解：
贴下官方题解
最终所求为
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
ll x, y;
scanf("%lld%lld", &x, &y);
a[i] = x * x * y + y * y * (y - 2ll * x);
}
sort(a + 1, a + n + 1);
printf("%lld\n", a[n] - a[1]);
return 0;
}
C.装备合成
题解（三分）：
枚举用2件材料a和3件材料b合成的装备数量，剩下所能合成的装备数量为 ，可以发现这个做法是存在单调性极值的，所以用三分查找极值即可
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn];
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
{
int x, y;
scanf("%d%d", &x, &y);
int l = 0, r = min(x / 2, y / 3);
while (r - l > 10)
{
int midl = l + (r - l) / 3;
int midr = r - (r - l) / 3;
if (midl + min((x - 2 * midl) / 4, y - 3 * midl) > midr + min((x - 2 * midr) / 4, y - 3 * midr))
r = midr;
else
l = midl;
}
int ans = 0;
for (int i = l; i <= r; i++)
ans = max(ans, i + min((x - 2 * i) / 4, y - 3 * i));
printf("%d\n", ans);
}
return 0;
}题解（线性规划）：
令用2件材料a和3件材料b合成的装备数量为a，用4件材料a和1件材料b也合成的装备数量为b。
a>=0
b>=0
2a+4b<=x
3a+b<=y
求x+y的最大值
画图即可枚举出所有情况，因为2a+4*b<=x,所以x要去偶数，x=x-(x&1)最后综合为min((x + y) / 5, min(x / 2, y)));
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll a[maxn];
int main()
{
int t;
for (scanf("%d", &t); t >= 1; t--)
{
ll x, y;
scanf("%lld%lld", &x, &y);
x -= (x & 1);
printf("%lld\n", min((x + y) / 5, min(x / 2, y)));
}
return 0;
}D.取石子游戏（博弈论）
题解：
贴上官方题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
ll s[105], e[105];
int tot, t;
void init()
{
s[++tot] = 1;
e[tot] = 1;
s[++tot] = 2;
e[tot] = 3;
while (e[tot] < 1e18)
{
tot++;
s[tot] = e[tot - 1] + 1;
if (tot & 1)
e[tot] = e[tot - 1] * 2;
else
e[tot] = e[tot - 1] * 2 + 1;
}
}
int main()
{
init();
for (scanf("%d", &t); t >= 1; t--)
{
ll n;
scanf("%lld", &n);
int pos = upper_bound(s + 1, s + tot + 1, n) - s - 1;
if (pos & 1)
puts("XiaoQiao");
else
puts("XiaoHuiHui");
}
return 0;
}E.石子搬运（分治）
题解：
贴上官方题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 405;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, m, q, sum, a[maxn], len[maxn << 2];
ll dp[maxn << 2][maxn];
void pushdown(int rt)
{
memset(dp[rt], INF, sizeof(dp[rt]));
for (int i = len[rt << 1]; i <= m; i++)
for (int j = len[rt << 1 | 1]; i + j <= m; j++)
dp[rt][i + j] = min(dp[rt][i + j], dp[rt << 1][i] + dp[rt << 1 | 1][j]);
}
void build(int l, int r, int rt)
{
len[rt] = r - l + 1;
if (l == r)
{
memset(dp[rt], INF, sizeof(dp[rt]));
for (int i = 1; i <= min(a[l], m); i++)
{
dp[rt][i] = a[l] / i;
dp[rt][i] = a[l] % i * (dp[rt][i] + 1) * (dp[rt][i] + 1) + (i - a[l] % i) * dp[rt][i] * dp[rt][i];
}
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushdown(rt);
}
void update(int l, int r, int rt, int pos)
{
if (l == r)
{
memset(dp[rt], INF, sizeof(dp[rt]));
for (int i = 1; i <= min(a[l], m); i++)
{
dp[rt][i] = a[l] / i;
dp[rt][i] = a[l] % i * (dp[rt][i] + 1) * (dp[rt][i] + 1) + (i - a[l] % i) * dp[rt][i] * dp[rt][i];
}
return;
}
int mid = l + r >> 1;
if (pos <= mid)
update(l, mid, rt << 1, pos);
else
update(mid + 1, r, rt << 1 | 1, pos);
pushdown(rt);
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
sum += a[i];
}
build(1, n, 1);
scanf("%d", &q);
while (q--)
{
int x, v;
scanf("%d%d", &x, &v);
sum -= a[x];
sum += v;
a[x] = v;
update(1, n, 1, x);
printf("%lld\n", dp[1][min(sum, m)]);
}
return 0;
}F.小松鼠吃松果（二维偏序）
题解：
如果吃到了松果i、松果j，要满足 其中x代表松树位置，去掉绝对值相当于
和
,移项得
和
,相当于二维偏序，可以用树状数组维护
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[maxn], b[maxn];
struct Node
{
int x, y, c;
bool operator<(const Node &C) const
{
if (x == C.x)
return y < C.y;
return x < C.x;
}
} node[maxn];
int tmp[maxn];
ll bit[maxn];
inline int lowbit(int x) { return x & (-x); }
void add(int x, ll val)
{
for (; x < maxn; x += lowbit(x))
bit[x] = max(bit[x], val);
}
ll query(int x)
{
ll res = 0;
for (; x; x -= lowbit(x))
res = max(res, bit[x]);
return res;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= m; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)
{
int t, p, c;
scanf("%d%d%d", &t, &p, &c);
int x = a[p];
int y = b[p] + t;
node[i] = {x - y, -x - y, c};
tmp[i] = -x - y;
}
sort(node + 1, node + n + 1);
sort(tmp + 1, tmp + n + 1);
for (int i = 1; i <= n; i++)
{
int x = lower_bound(tmp + 1, tmp + n + 1, node[i].y) - tmp;
add(x, query(x) + node[i].c);
}
printf("%lld\n", query(n));
return 0;
}
京公网安备 11010502036488号