个人题解| ACGO排位赛#14
2024-11-11 13:54:27
发布于：山东
115阅读
0回复
0点赞
A. 混淆字符串
按照题意模拟即可，将两个字符串中的混淆字符都改成相同字符，最后判断两个字符串是否相等。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
string s, t;
cin >> s >> t;
for (auto &c : s)
{
if (c == '1')
c = 'l';
else if (c == '0')
c = 'O';
else if (c == '5')
c = 'S';
}
for (auto &c : t)
{
if (c == '1')
c = 'l';
else if (c == '0')
c = 'O';
else if (c == '5')
c = 'S';
}
if (s == t)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
B. 循环小数
按照题意模拟，找到循环节，输出循环节即可。
当余数 为 0 的时候的时候证明能够除尽，输出0即可，否则当等到 上一次出现过的时候输出证明找到了循环节，输出循环节即可。
细节见代码，时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int x, y;
cin >> x >> y;
x %= y;
map<int, int> mp;
int cnt = 0;
mp[x] = cnt++;
vector<int> v;
while (1)
{
if (x == 0)
{
cout << 0 << endl;
return 0;
}
x *= 10;
v.push_back(x / y);
x %= y;
if (x && mp.count(x))
{
for (int i = mp[x]; i < v.size(); i++)
cout << v[i];
cout << endl;
return 0;
}
}
return 0;
}
C. 特殊的染料
注意到 很小，因此考虑直接暴力。
贪心的考虑，因为最后要把所有桶按顺序排好，所以一个桶一定会通过交换换到他应该在的地方，如果先把最大的桶放好，那么这个桶在之后一定不会与其他的桶发生交换，这样显然更优。
因此我们能够得到一个策略，从大到小把对应的桶给直接放好即可。而每次选择交换的容器的时候，可以 暴力求出花费最小的交换容器。
整体时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 100 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], b[maxn];
int vis[maxn];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i], vis[a[i]] = i;
for (int i = 1; i <= n; i++)
cin >> b[i];
int ans = 0;
for (int i = n; i >= 1; i--)
{
if (vis[i] == i)
continue;
int pos = vis[i];
while (pos != i)
{
int mi = inf;
for (int j = 1; j <= n; j++)
{
if (j != a[pos] && j != a[pos + 1] && (j + a[pos] <= n || j + a[pos + 1] <= n))
mi = min(mi, b[j]);
}
swap(vis[a[pos]], vis[a[pos + 1]]);
swap(a[pos], a[pos + 1]);
pos++;
ans += mi;
}
}
cout << ans << endl;
return 0;
}
D. 君往何处
搜索。
注意剪枝优化，不然会 TLE。
细节见代码，注意每次应该让最前面的手指匹配音符，这个过程可以拿一个堆来维护。
实测跑的挺快，最慢的点也只跑了 ， 时间复杂度为目测估计为 ，常数略大。
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn];
int n, ans;
void dfs(int i, priority_queue<int, vector<int>, greater<int>> q, int sz)
{
if (sz > 4)
return;
if (sz >= ans)
return;
if (i > n)
{
ans = min(ans, sz);
return;
}
int x = q.top();
if (a[i] + 30 - x >= 100)
{
auto t = q;
t.pop();
if (100 + x <= a[i] - 30)
{
t.push(max(100 + x, a[i] - 30));
dfs(i + 1, t, sz);
}
else
{
t.push(max(100 + x, a[i] - 30));
dfs(i + 1, t, sz);
auto s = q;
s.push(max(0, a[i] - 30));
dfs(i + 1, s, sz + 1);
}
}
else
{
auto s = q;
s.push(max(0, a[i] - 30));
dfs(i + 1, s, sz + 1);
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
ans = inf;
priority_queue<int, vector<int>, greater<int>> q;
q.push(-100);
dfs(1, q, 1);
if (ans == inf)
cout << -1 << endl;
else
cout << ans << endl;
}
return 0;
}
E. 万圣糖果
毒瘤 dp 题，写了好久，估计想复杂了。
注意到只有两种形式的修改
- 第一种就是找两个不相交的区间，然后每个区间施法一次
- 第二种就是两个区间相交，重叠部分的点会施法两次，其余点施法一次，这种情况可以转换为一个大区间施法一次，在这个大区间的一个小区间里面会施法两次
以这两种状态设计转移方程做 dp 即可
细节特别多，具体细节见代码，时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
ll a[maxn], b[maxn], c[maxn];
ll dp[maxn][5];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
for (int i = 1; i <= n; i++)
cin >> c[i];
ll ans = 0;
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) // 第二种操作的dp转移方程
{
dp[i][0] = max({dp[i - 1][0] + a[i], 0ll});
dp[i][1] = max({dp[i][0] - a[i] + b[i], dp[i - 1][1] + b[i], dp[i - 1][0] + b[i], 0ll});
dp[i][2] = max({dp[i][1] - b[i] + c[i], dp[i - 1][2] + c[i], dp[i - 1][1] + c[i], dp[i - 1][0] + c[i], 0ll});
dp[i][3] = max({dp[i - 1][3] + b[i], dp[i - 1][2] + b[i], dp[i - 1][1] + b[i], dp[i - 1][0] + b[i], 0ll});
dp[i][4] = max({dp[i - 1][4] + a[i], dp[i - 1][3] + a[i], dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i - 1][0] + a[i], 0ll});
ans = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4], ans});
}
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= n; i++) // 第一种操作的dp转移方程
{
dp[i][0] = max({dp[i - 1][0] + a[i], 0ll});
dp[i][1] = max({dp[i][0] - a[i] + b[i], dp[i - 1][1] + b[i], 0ll});
dp[i][2] = max({dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i - 1][0] + a[i], 0ll});
dp[i][3] = max({dp[i][2] - a[i] + b[i], dp[i - 1][3] + b[i], dp[i - 1][2] + b[i], dp[i - 1][1] + b[i], 0ll});
dp[i][4] = max({dp[i - 1][4] + a[i], dp[i - 1][3] + a[i], dp[i - 1][2] + a[i], dp[i - 1][1] + a[i], dp[i - 1][0] + a[i], 0ll});
ans = max({dp[i][0], dp[i][1], dp[i][2], dp[i][3], dp[i][4], ans});
}
cout << ans << endl;
return 0;
}
F. 可变数组
考察线段树。
如果你不知道线段树是什么，可以点这里：线段树 - OI Wik。
第一种操作和第二种操作都是线段树的单点修改，第三种操作是线段树的区间查询，第四种操作是线段树区间二分查询。
注意操作四不可以二分右边界再使用线段树查询，来找到第一个大于等于 的元素，这样的时间复杂度会是 的，在本题会TLE，只有 90 pts 。
操作四可以优化成 的原因是线段树的查询实际上二分区间内的过程，如果左区间内的元素查询满足了要求则不用再去遍历右区间，直接返回即可。
代码实现使用了快读，因为之前拿 的做法做的，想着能不能卡常过，事实上是不行。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1e5 + 10;
const int maxn = 1e6 + 10;
const int inf = 0x3f3f3f3f;
namespace QuickRead
{ // 快读
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int getc()
{
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
void Cin(T &a)
{
T ans = 0;
bool f = 0;
char c = getc();
for (; c < '0' || c > '9'; c = getc())
{
if (c == '-')
f = 1;
}
for (; c >= '0' && c <= '9'; c = getc())
{
ans = ans * 10 + c - '0';
}
a = f ? -ans : ans;
}
template <typename T, typename... Args>
void Cin(T &a, Args &...args)
{
Cin(a), Cin(args...);
}
template <typename T>
void write(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
} // namespace QuickRead
using namespace QuickRead;
struct SegmentTree
{
struct tree
{
int l, r;
int mx, add;
} tr[4 * maxn];
int a[maxn];
int n;
#define lc (p << 1)
#define rc (p << 1 | 1)
void calc(int p, int k)
{
tr[p].mx = k;
}
void pushup(int p)
{
tr[p].mx = max(tr[lc].mx, tr[rc].mx);
}
void pushdown(int p)
{
// return;
if (tr[p].add)
{
calc(lc, tr[p].add);
calc(rc, tr[p].add);
tr[p].add = 0;
}
}
void build(int p, int l, int r)
{
tr[p].l = l, tr[p].r = r;
if (l == r)
{
tr[p].mx = a[l];
return;
}
int mid = l + r >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(p);
}
void change(int p, int x, int y, int k)
{
if (x <= tr[p].l && y >= tr[p].r)
{
calc(p, k);
return;
}
int mid = tr[p].l + tr[p].r >> 1;
// pushdown(p);
if (x <= mid)
change(lc, x, y, k);
if (y > mid)
change(rc, x, y, k);
pushup(p);
}
int query(int p, int x, int y)
{
if (x <= tr[p].l && y >= tr[p].r)
return tr[p].mx;
int mid = tr[p].l + tr[p].r >> 1;
// pushdown(p);
int mx = 0;
if (x <= mid)
mx = max(mx, query(lc, x, y));
if (y > mid)
mx = max(mx, query(rc, x, y));
return mx;
}
int query2(int p, int x, int y, int k)
{
if (y < tr[p].l || x > tr[p].r)
return -1;
if (tr[p].l == tr[p].r)
{
if (tr[p].mx >= k)
return tr[p].l;
else
return -1;
}
if (x <= tr[p].l && y >= tr[p].r)
{
if (tr[p].mx < k)
return -1;
}
int mid = tr[p].l + tr[p].r >> 1;
int t1 = query2(lc, x, y, k);
if (t1 != -1)
return t1;
return query2(rc, x, y, k);
}
void debug(int p = 1)
{
// return;
cout << "[" << tr[p].l << ", " << tr[p].r << "]: ";
cout << "add = " << tr[p].add << ", ";
cout << endl;
if (tr[p].l == tr[p].r)
return;
debug(lc), debug(rc);
}
#undef lc
#undef rc
} t;
signed main()
{
int n, m;
Cin(n, m);
for (int i = 1; i <= n; i++)
{
Cin(t.a[i]);
}
t.build(1, 1, n);
for (int i = 1; i <= m; i++)
{
int op;
Cin(op);
if (op == 1)
{
int x, y;
Cin(x, y);
t.a[x] = y;
t.change(1, x, x, y);
}
else if (op == 2)
{
int l, r;
Cin(l, r);
swap(t.a[l], t.a[r]);
t.change(1, l, l, t.a[l]);
t.change(1, r, r, t.a[r]);
}
else if (op == 3)
{
int l, r;
Cin(l, r);
if (l > r)
swap(l, r);
write(t.query(1, l, r));
puts("");
}
else
{
int l, r, x;
Cin(x, l, r);
write(t.query2(1, l, r, x));
puts("");
}
}
}
写的比较赶，以后有时间部分题目的解释会改详细一点
有帮助，赞一个