个人题解| ACGO排位赛#13
2024-10-07 22:05:30
发布于：山东
54阅读
0回复
0点赞
A. 纪元流星雨
按照题意模拟即可。
为了便于计算，可将这个人出生的那一年设为坐标原点，计算 内出现多少次流星雨即可。
不难计算出在正半轴时第一次流星雨发生时间为 ，流星雨出现数量则为 ，并特判一下第一次流星雨是否出现即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
ll B, L, E;
cin >> B >> L >> E;
E += B;
E %= 50;
ll ans = (L - E) / 50;
if (E <= L)
ans++;
cout << ans << endl;
}
}
B.MARCOncatenation
按照题意模拟即可。
-
如果字符串以
o开头，删除该o并在开头加上MARCO。 -
如果字符串以
co开头，删除co并在开头加上MARCO。 -
如果字符串以
rco开头，删除rco并在开头加上MARCO。 -
如果字符串以
arco开头，删除arco并在开头加上MARCO。 -
如果字符串以
marco开头，只需将前 5 个字母大写。 -
否则，什么也不做，保持字符串不变。
判断从 1 到 5 每个长度的前缀是否以规定子串开头，并进行修改。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
string s;
cin >> s;
if (s.size() >= 1 && s.substr(0, 1) == "o")
s.erase(0, 1), s.insert(0, "MARCO");
else if (s.size() >= 2 && s.substr(0, 2) == "co")
s.erase(0, 2), s.insert(0, "MARCO");
else if (s.size() >= 3 && s.substr(0, 3) == "rco")
s.erase(0, 3), s.insert(0, "MARCO");
else if (s.size() >= 4 && s.substr(0, 4) == "arco")
s.erase(0, 4), s.insert(0, "MARCO");
else if (s.size() >= 5 && s.substr(0, 5) == "marco")
s.erase(0, 5), s.insert(0, "MARCO");
cout << s << endl;
}
}
C.TNT接力
二分找到第一个没有被打上标记的下标然后进行修改。
首先跳跃一定比走路更优，跳远可以向前走 的任意一步，而走路只能向前走一步。
贪心的考虑，肯定是从每个点起跳的时候跳的越远越好，显然从一个点起跳时跳的远的情况肯定比跳的近的情况更优。
同时肯定要先从离起点近的点开始起跳，因为离起点近的点所跳的区域一定能被离起点远的点所到达或者经过。
简易的证明如下：
记离起点近的点所能调到的最远点为 ，离原点近的点所能跳的最远点为 。
- 如果，由于除起点和终点外每个点最多只能经过一次，那么二者选哪个点对答案的贡献一样。
- 如果，那么显然离起点近的点跳到 点，离起点远的点跳到 点更优。如果离起点远的点跳到了点，离起点近的点可能没有位置继续向前跳，此时答案一定不可能比前一种情况大。
因此我们可以得到一个贪心策略，从到开始遍历每一个起跳点，对于每一个起跳点去找到它所能到达的最远点，此时结果一定最优。
把所有能被跳的点存到一个集合里面，每次从一个点起跳的时候二分找到这个点能够跳到的最远距离，并将这个值从集合里面删去，用set 即可 时间完成这些操作。
具体实现见代码，时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
char a[maxn];
int vis[maxn];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n, m;
cin >> n >> m;
set<int> s;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] == '#')
s.insert(i);
}
s.insert(n + 1);
if (m >= n)
{
cout << -1 << endl;
continue;
}
for (int i = 1; i <= m + 1; i++)
{
if (a[i] == '#')
vis[i] = 1;
}
for (int i = 1; i <= n; i++)
{
if (vis[i])
{
auto it = s.upper_bound(i + m + 1);
if (it == s.begin())
continue;
it--;
vis[*it]++;
if (*it != n + 1)
s.erase(it);
}
}
cout << vis[n + 1] << endl;
for (int i = 0; i <= n + 5; i++)
vis[i] = 0;
}
}
D.小丑牌
大模拟题，按照题意模拟仔细点写，没什么好说的。
注意一下如果有一个牌型符合上述多条描述，请输出符合描述的牌型中在规则中最后描述的牌型。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int n = 5;
string r[N], s[N];
int a[N];
int solve()
{
map<string, int> mp;
for (int i = 1; i <= n; i++)
{
mp[r[i]]++;
if (s[i] == "J")
a[i] = 11;
else if (s[i] == "Q")
a[i] = 12;
else if (s[i] == "K")
a[i] = 13;
else if (s[i] == "A")
a[i] = 14;
else
a[i] = stoi(s[i]);
}
bool ok = 0;
for (auto [x, c] : mp)
{
if (c == 5)
ok = 1;
}
sort(a + 1, a + 1 + n);
int tot = 0;
for (int i = 2; i <= n; i++)
{
if (a[i] - a[i - 1] == 1)
tot++;
}
if (ok)
{
if (tot == 4 && a[n] == 14)
return 1;
else if (tot == 4)
return 2;
}
else
{
if (tot == 4)
return 3;
}
map<int, int> cnt;
for (int i = 1; i <= n; i++)
cnt[a[i]]++;
int flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0;
for (auto [x, c] : cnt)
{
if (c == 2)
flag2++;
else if (c == 3)
flag3++;
else if (c == 4)
flag4++;
}
if (flag2 && flag3)
return 4;
if (flag4)
return 5;
if (flag3)
return 6;
if (flag2 == 2)
return 7;
if (flag2)
return 8;
return 9;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
for (int i = 1; i <= n; i++)
cin >> s[i] >> r[i];
int op = solve();
if (op == 9)
cout << "High Card" << endl;
else if (op == 8)
cout << "One Pair" << endl;
else if (op == 7)
cout << "Two Pairs" << endl;
else if (op == 6)
cout << "Three of a Kind" << endl;
else if (op == 5)
cout << "Four of a Kind" << endl;
else if (op == 4)
cout << "Full House" << endl;
else if (op == 3)
cout << "Straight" << endl;
else if (op == 2)
cout << "Straight Flush" << endl;
else
cout << "Royal Flush" << endl;
}
}
E. Vertex Verse
又是一道大模拟题。
开一个三维数组，第一维表示横坐标，第二维表示纵坐标，第三位表示这个点上下左右的连线情况。
数组元素代表含义如图所示：
每次读入两个点后这两个点会连成一条线段，对这两个点分别打上标记，同时判断这条线段是否与其他线段围成了新的正方形，每次连线至多会形成两个正方形，如果新的连线与 轴平行则判断上下是否形成了新的正方形，如果新的连线与 轴平行则判断左右是否形成的新的正方形即可。
由于每次新连线所形成的正方形一定不会是之前的正方形，所以并不需要额外添加标记判断。
代码细节较多，时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 2000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, Q;
cin >> n >> m >> Q;
vector<vector<array<int, 4>>> a(n + 5, vector<array<int, 4>>(m + 5));
auto solve1 = [&](int x1, int y1, int x2, int y2)
{
int res = 0;
int uy = y1 - 1, dy = y1 + 1;
if (a[x1][uy][1] && a[x2][uy][1] && a[x1][uy][0])
res++;
if (a[x1][dy][3] && a[x2][dy][3] && a[x1][dy][0])
res++;
return res;
};
auto solve2 = [&](int x1, int y1, int x2, int y2)
{
int res = 0;
int uy = y1 - 1, dy = y1 + 1;
if (a[x1][uy][1] && a[x2][uy][1] && a[x1][uy][2])
res++;
if (a[x1][dy][3] && a[x2][dy][3] && a[x1][dy][2])
res++;
return res;
};
auto solve3 = [&](int x1, int y1, int x2, int y2)
{
int res = 0;
int ux = x1 - 1, dx = x1 + 1;
if (a[ux][y1][0] && a[ux][y2][0] && a[ux][y1][1])
res++;
if (a[dx][y1][2] && a[dx][y2][2] && a[dx][y1][1])
res++;
return res;
};
auto solve4 = [&](int x1, int y1, int x2, int y2)
{
int res = 0;
int ux = x1 - 1, dx = x1 + 1;
if (a[ux][y1][0] && a[ux][y2][0] && a[ux][y1][3])
res++;
if (a[dx][y1][2] && a[dx][y2][2] && a[dx][y1][3])
res++;
return res;
};
int ans1 = 0, ans2 = 0;
while (Q--)
{
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x2 == x1 + 1)
{
a[x1][y1][0] = 1;
a[x2][y1][2] = 1;
ans1 += solve1(x1, y1, x2, y2);
}
else if (x1 == x2 + 1)
{
a[x1][y1][2] = 1;
a[x2][y1][0] = 1;
ans1 += solve2(x1, y1, x2, y2);
}
else if (y2 == y1 + 1)
{
a[x1][y1][1] = 1;
a[x1][y2][3] = 1;
ans1 += solve3(x1, y1, x2, y2);
}
else
{
a[x1][y1][3] = 1;
a[x1][y2][1] = 1;
ans1 += solve4(x1, y1, x2, y2);
}
}
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x2 == x1 + 1)
{
a[x1][y1][0] = 1;
a[x2][y1][2] = 1;
ans2 += solve1(x1, y1, x2, y2);
}
else if (x1 == x2 + 1)
{
a[x1][y1][2] = 1;
a[x2][y1][0] = 1;
ans2 += solve2(x1, y1, x2, y2);
}
else if (y2 == y1 + 1)
{
a[x1][y1][1] = 1;
a[x1][y2][3] = 1;
ans2 += solve3(x1, y1, x2, y2);
}
else
{
a[x1][y1][3] = 1;
a[x1][y2][1] = 1;
ans2 += solve4(x1, y1, x2, y2);
}
}
}
cout << ans1 << ' ' << ans2 << endl;
}
F. 最优政府大楼选址-2
考察排序。
首先思考没有 的限制，即所有的 都为 1 的情况，此时大楼选址的坐标为
下面以求证明 方向的大楼选址坐标为例， 方向的求法类似：
假设对 个居民点的坐标按大小排序后为:
对 两点来说，最近的点肯定在 之间 , 可以为二者之间的任意值，且跟两点的距离和为 ；
对 两点来说，最近的点肯定在 之间， 可以为二者之间的任意值，且跟两点的距离和为 ；
所以若 为奇数，则邮局的 坐标取最中间的值时最小；
所以若 为偶数，则邮局的 坐标可以取最中间两个值的之间的任意值;
注意到 的值为整数且不超过10，因此我们可以把 看成在这个点的大楼个数，再使用上述的方法求解。
时间复杂度，复杂度瓶颈在排序上面
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 1000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn];
vector<double> x, y;
int m;
double checkx(double z)
{
double res = 0;
for (int i = 0; i < m; i++)
res += abs(x[i] - z);
return res;
}
double checky(double z)
{
double res = 0;
for (int i = 0; i < m; i++)
res += abs(y[i] - z);
return res;
}
int 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++)
{
double sx, sy;
cin >> sx >> sy;
for (int j = 1; j <= a[i]; j++)
x.push_back(sx), y.push_back(sy);
}
m = x.size();
double ansx, ansy;
sort(x.begin(), x.end());
ansx = checkx(x[m / 2]);
sort(y.begin(), y.end());
ansy = checky(y[m / 2]);
cout << fixed << setprecision(12) << ansx + ansy << endl;
}
G. 乌龟养殖场
状态压缩 dp 板子题。
注意到对于100%的数据，保证 ，因此想到采用状态压缩 dp 求解。
如果你不知道状态压缩 dp 是什么，可以点这里：状压 DP - OI Wiki。
以 表示在前 行中在第 个状态下的最大方案数
易得：
其中 ， 是第 行的状态， 是第 行的状态
每次转移的时候记得判断一下两行的状态是否合法，最终答案即为 ，减一是因为题目要求不能全部乌龟都不放，所以要去除掉全部都不放这种状态 。
具体实现见代码，时间复杂度 ，其中 表示宽为 的合法状态数
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 2000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
int g[N];
ll dp[505][N];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < m; j++)
{
int x;
cin >> x;
if (x == 1)
g[i] += 1 << (m - j - 1);
}
}
vector<int> s;
for (int i = 0; i < (1 << m); i++)
{
if (!(i & (i >> 1)))
{
s.push_back(i);
}
}
dp[0][0] = 1;
for (int i = 1; i <= n + 1; i++)
{
for (int j = 0; j < s.size(); j++)
{
for (int k = 0; k < s.size(); k++)
{
if (!(s[j] & s[k]) && ((s[j] & g[i]) == s[j]) && ((s[k] & g[i - 1]) == s[k]))
dp[i][j] += dp[i - 1][k], dp[i][j] %= mod;
}
}
}
dp[n + 1][0]--;
dp[n + 1][0] = (dp[n + 1][0] % mod + mod) % mod;
cout << dp[n + 1][0] << endl;
}
H. 数据中心能耗分析
线段树板子题。
如果你不知道线段树是什么，可以点这里：线段树 - OI Wik。
注意到
因此我们若需要维护一段序列的立方和，同时也需要维护一段序列的平方和和区间和
注意懒标记下传的时候先更新区间的立方和，再更新区间的平方和，最后更新区间和
具体实现见代码，注意 int 可能会溢出，记得开 long long，时间复杂度
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int N = 2000 + 10;
const int maxn = 2e5 + 10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
struct tree
{
int l, r;
ll sum3, sum2, sum1, add;
} tr[4 * maxn];
ll a[maxn];
#define lc (p << 1)
#define rc (p << 1 | 1)
void calc(int p, ll k)
{
ll len = tr[p].r - tr[p].l + 1;
tr[p].sum3 += len * k % mod * k % mod * k % mod;
tr[p].sum3 %= mod;
tr[p].sum3 += 3 * tr[p].sum1 % mod * k % mod * k % mod;
tr[p].sum3 %= mod;
tr[p].sum3 += 3 * tr[p].sum2 % mod * k % mod;
tr[p].sum3 %= mod;
tr[p].sum2 += len * k % mod * k % mod;
tr[p].sum2 %= mod;
tr[p].sum2 += 2 * tr[p].sum1 % mod * k % mod;
tr[p].sum2 %= mod;
tr[p].sum1 += len * k % mod;
tr[p].sum1 %= mod;
tr[p].add += k;
tr[p].add %= mod;
}
void pushup(int p)
{
tr[p].sum3 = tr[lc].sum3 + tr[rc].sum3;
tr[p].sum2 = tr[lc].sum2 + tr[rc].sum2;
tr[p].sum1 = tr[lc].sum1 + tr[rc].sum1;
}
void pushdown(int p)
{
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].sum3 = a[l] * a[l] % mod * a[l] % mod;
tr[p].sum2 = a[l] * a[l] % mod;
tr[p].sum1 = a[l] % mod;
tr[p].add = 0;
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, ll 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);
}
ll query(int p, int x, int y)
{
if (x <= tr[p].l && y >= tr[p].r)
return tr[p].sum3;
int mid = tr[p].l + tr[p].r >> 1;
pushdown(p);
ll sum = 0;
if (x <= mid)
sum += query(lc, x, y), sum %= mod;
if (y > mid)
sum += query(rc, x, y), sum %= mod;
return sum % mod;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
build(1, 1, n);
while (m--)
{
int op;
cin >> op;
if (op == 1)
{
int l, r, k;
cin >> l >> r >> k;
change(1, l, r, k);
}
else
{
int l, r;
cin >> l >> r;
cout << (query(1, l, r) % mod + mod) % mod << endl;
}
}
}
有帮助，赞一个