2024天梯选拔赛(一)
A 私人笑声
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string str;
getline(cin, str);
for (int i = 0; i < str.size(); i ++) {
cout << str[i] ;
if (str[i] == '.')
cout << "xixixixi.";
}
return 0;
}
B 孵化小鸡
数据小,dfs
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, M;
cin >> n >> M;
vector<int> a(n), b(n), m(n), l(m), r(m), k(m), p(m);
for (int i = 0; i < n; i ++)
cin >> a[i] >> b[i] >> m[i];
for (int i = 0; i < M; i ++)
cin >> l[i] >> r[i] >> k[i] >> p[i];
vector<bool> vis(M);
vector<int> lr(200);
i64 ans = INT_MAX;
auto dfs = [&](auto self, int num, i64 res) {
if (num == M) {
bool ok = true;
for (int i = 0; i < n; i ++) {
if (!ok) break;
for (int j = a[i]; j <= b[i]; j ++) {
if (lr[j] < m[i]) {
ok = false;
break;
}
}
}
if (ok) ans = min(ans, res);
return ;
}
self(self, num + 1, res);
for (int i = l[num]; i <= r[num]; i ++)
lr[i] += k[num];
self(self, num + 1, res + p[num]);
for (int i = l[num]; i <= r[num]; i ++)
lr[i] -= k[num];
};
dfs(dfs, 0, 0);
cout << ans << '\n';
return 0;
}
C 可怕的冻雨
考虑离线;
将落脚点按光滑程度排序,以及雪地靴按防滑程度排序;
预处理出能够直接到达的落脚点记录并存储两两点之间的距离;
遍历雪地靴,判断雪地靴能否在原有的落脚点上新增落脚点,能够新增则找到新增点的邻近点,更新原有的距离,最后判断雪地靴的行走距离能否跨过最远的冰层;
防滑程度小的雪地靴能到达的落脚点,防滑度大的可延续其之前的路线;
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<PII> A;
for (int i = 1, x; i <= n; i ++) {
cin >> x;
A.emplace_back(x, i);
}
vector<array<int, 3>> B;
for (int i = 0, k, s; i < m; i ++) {
cin >> k >> s;
B.push_back({k, s, i});
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
set<int> loc;
multiset<int> dis;
int index = 0;
while (index < A.size() && !A[index].first)
loc.insert(A[index].second), index ++;
for (auto it = loc.begin(); next(it) != loc.end(); it = next(it))
dis.insert(*next(it) - *it);
vector<int> ans(m);
for (auto [k, s, id] : B) {
while (index < A.size() && A[index].first <= k) {
int i = A[index].second;
index ++;
auto t = loc.upper_bound(i);
int r = *t, l = *(prev(t));
loc.insert(i);
dis.erase(dis.find(r - l));
dis.insert(i - l);
dis.insert(r - i);
}
ans[id] = (s >= *dis.rbegin());
}
for (auto i : ans)
cout << i << '\n';
return 0;
}
D 划分田地(easy)
枚举矩形,将在矩形内的点加入进去;
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<PII> tu(n);
for (auto &[x, y] : tu)
cin >> x >> y;
set<vector<int>> ans;
for (int i = 0; i <= 50; i ++) {
for (int j = 0; j <= 50; j ++) {
for (int k = i; k <= 50; k ++) {
for (int p = j; p <= 50; p ++) {
vector<int> ve;
int num = 0;
for (auto [x, y] : tu) {
num ++;
if (x >= i && x <= k && y >= j && y <= p)
ve.push_back(num);
}
ans.insert(ve);
}
}
}
}
cout << ans.size() << '\n';
return 0;
}
E 划分田地(hard)
对于一个矩形,如果它的上边扫描到上边界这个矩形中有\(x\)个点,下边扫描到下边界的这个矩形中有\(y\)个点,那么这个矩形可以向上向下拓展边界从而可以得到\((x + 1) \times (y + 1)\)个包含不同点的矩形(向左向右也是一样);
本题中,我采用的是上下拓展;
将坐标二维离散后,运用二维前缀和计算上矩形和下矩形中分别有多少个点,从而累加计算结果, 最后加上\(n+1\)是\(n\)个点和一个空集;
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
struct Two_D_Discrete {
int n, tot1 = 1, tot2 = 1;
vector<vector<int>> mp;
vector<int> x, y, nx, ny;
vector<pair<i64, i64>> a;
vector<PII> New;
Two_D_Discrete (int _n, vector<pair<i64, i64>>& _a): n(_n), a(_a) {
x.resize(n), y.resize(n);
nx.resize(n * 2 + 5), ny.resize(n * 2 + 5);
vector<vector<int>>(n * 2 + 5, vector<int>(n * 2 + 5)).swap(mp);
for (int i = 0; i < n; i ++) {
x[i] = a[i].first;
y[i] = a[i].second;
}
}
void work() {
//排序
sort(x.begin(), x.end());
sort(y.begin(), y.end());
// 去重 并得到有多少个点
int len1 = unique(x.begin(), x.end()) - x.begin();
int len2 = unique(y.begin(), y.end()) - y.begin();
// 离散化 x 轴
for (int i = 0; i < len1; i++) {
if (i && x[i] != x[i - 1] + 1)
nx[tot1++] = x[i] - 1, nx[tot1++] = x[i];
else
nx[tot1++] = x[i];
}
// 离散化 y 轴
for (int i = 0; i < len2; i++) {
if (i && y[i] != y[i - 1] + 1)
ny[tot2++] = y[i] - 1, ny[tot2++] = y[i];
else
ny[tot2++] = y[i];
}
//映射关系将需离散的点放入离散图中
for (int i = 0; i < n; i++) {
int newx = lower_bound(nx.begin(), nx.begin() + tot1, a[i].first) - nx.begin();
int newy = lower_bound(ny.begin(), ny.begin() + tot2, a[i].second) - ny.begin();
mp[newx][newy] = 1;
// cout << "(" << newx << ',' << newy << ")\n";
New.emplace_back(newx, newy);
}
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<PII> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
x ++, y ++;
}
Two_D_Discrete _2D(n, a);
_2D.work();
int Ke = n * 2 + 5;
vector sum(Ke, vector<int>(Ke));
for (int i = 1; i < Ke; i ++)
for (int j = 1; j < Ke; j ++)
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + _2D.mp[i][j];
auto calc = [&](int a, int b, int c, int d) {
return sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1];
};
i64 ans = 0;
for (int i = 0; i < n; i ++) {
for (int j = i + 1; j < n; j ++) {
auto [x1, y1] = _2D.New[i];
auto [x2, y2] = _2D.New[j];
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
int num1 = calc(1, y1, x1 - 1, y2);
int num2 = calc(x2 + 1, y1, Ke - 1, y2);
ans += (num1 + 1) * (num2 + 1);
}
}
cout << ans + n + 1 << '\n';
return 0;
}
F 加一余二
用set存储连续相同子串区间,multiset存储其区间长度;
对于操作的下标\(x\),要去判断子串区间中所在的位置,进行分裂与合并;
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
int m;
cin >> s >> m;
multiset<int> ans;
set<PII> res;
for (int i = 1, j; i <= s.size(); i = j + 1) {
j = i;
while (j < s.size() && s[j] == s[i - 1]) j ++;
res.insert(PII(i, j));
ans.insert(j - i + 1);
}
auto len = [](PII x) {
return x.second - x.first + 1;
};
auto Find = [&](int x) {
auto t = res.lower_bound(PII(x, -1));
if (t == res.end() || (*t).first > x) t = prev(t);
return *t;
};
while (m --) {
int x;
cin >> x;
PII t = Find(x);
res.erase(res.find(t));
ans.erase(ans.find(len(t)));
if (x != 1) {
if (t.first == x) {
PII p = Find(x - 1);
res.erase(res.find(p));
ans.erase(ans.find(len(p)));
t.first = p.first;
} else {
PII p = {t.first, x - 1};
t.first = x;
res.insert(p);
ans.insert(len(p));
}
}
if (x != s.size()) {
if (t.second == x) {
PII p = Find(x + 1);
res.erase(res.find(p));
ans.erase(ans.find(len(p)));
t.second = p.second;
} else {
PII p = {x + 1, t.second};
t.second = x;
res.insert(p);
ans.insert(len(p));
}
}
res.insert(t);
ans.insert(len(t));
cout << *ans.rbegin() << ' ';
}
return 0;
}
G 相加余三(easy)
本题分别模拟三种情况然后取最大值即可。
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &i : a) cin >> i;
i64 ans1 = 0 , ans2 = 0 , ans3 = 0 ;
for (int i = 0; i < n; i += 2) {
ans1 += ((a[i] + a[i + 1]) % 3);
}
for (int i = n; i >= 0; i -= 2) {
ans2 += ((a[i] + a[i - 1]) % 3);
}
for (int i = 0, j = n - 1; i < j; i ++, j --) {
ans3 += ((a[i] + a[j]) % 3);
}
cout << max({ans1, ans2, ans3}) << '\n';
return 0;
}
H 相加余三(hard)
考虑区间\(dp\);
从大区间往小区间转移,分奇偶讨论一下是因为每次去掉偶数个数,所以对于一个区间,到左右边界的值为奇数时是不合法的;
\[dp[i+2][j]=max(dp[i+2][j],dp[i][j]+(a[i]+a[i+1])%3) \]\[dp[i][j-2]=max(dp[i][j-2],dp[i][j]+(a[j-1]+a[j])%3); \]\[dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + (a[i] + a[j]) % 3); \]#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
vector dp(n + 1, vector<int>(n + 1));
int ans = 0;
for (int i = 1; i <= n; i ++) {
for (int j = n; j > i; j --) {
if (!((j - i) & 1) && n % 2 == 0) continue;
if (((j - i) & 1) && (n & 1)) continue;
if (i + 1 <= n) ans = max(ans, dp[i][i + 1] + (a[i] + a[i + 1]) % 3);
if (j >= i + 2) {
dp[i + 2][j] = max(dp[i + 2][j], dp[i][j] + (a[i] + a[i + 1]) % 3);
dp[i][j - 2] = max(dp[i][j - 2], dp[i][j] + (a[j - 1] + a[j]) % 3);
dp[i + 1][j - 1] = max(dp[i + 1][j - 1], dp[i][j] + (a[i] + a[j]) % 3);
}
}
}
for (int i = 1; i <= n; i ++)
for (int j = 1; j <= n; j ++)
ans = max(ans, dp[i][j]);
cout << ans << '\n';
return 0;
}
从小区间往大区间转移,预处理小区间的值
\[dp[i][j] = max(dp[i][j], dp[i + 2][j] + (a[i] + a[i + 1]) % 3); \]\[dp[i][j] = max(dp[i][j], dp[i][j - 2] + (a[j] + a[j - 1]) % 3); \]\[dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + (a[i] + a[j]) % 3); \]#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> a[i];
vector dp(n + 1, vector<int>(n + 1));
int ans = 0;
for (int len = 2; len <= n; len ++) {
for (int i = 1, j = len; j <= n; j ++, i ++) {
if (len == 2)
dp[i][j] = (a[i] + a[j]) % 3;
else {
dp[i][j] = max(dp[i][j], dp[i + 2][j] + (a[i] + a[i + 1]) % 3);
dp[i][j] = max(dp[i][j], dp[i][j - 2] + (a[j] + a[j - 1]) % 3);
dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + (a[i] + a[j]) % 3);
}
}
}
cout << dp[1][n] << '\n';
return 0;
}
I 找除数
一个正整数\(n\)可以表示为\(n=p_1^{x_1} \times p_2^{x_2} \times p_3^{x_3} \times p_4^{x_4} \dots\)(其中\(p_i\)为质数)
则\(n\)的除数的数量$=(x_1 + 1) \times (x_2 + 1) \times (x_3 + 1) \times (x_4 + 1) \times \dots $
预处理出10000以内的质数;
然后将\(n\)按质数分解,按照上述公式计算即可;
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
vector<int> prime, isnp(10005);
void solve() {
int n;
cin >> n;
int ans = 1;
for (auto k : prime) {
if (n % k == 0) {
int cnt = 1;
while (n % k == 0) n /= k, cnt ++;
ans *= cnt;
}
}
if (n != 1) ans *= 2;
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
for (int i = 2; i <= 10000; i ++) {
if (!isnp[i]) prime.push_back(i);
for (auto k : prime) {
if (k * i > 10000) break;
isnp[i * k] = 1;
if (i % k == 0) break;
}
}
int T;
cin >> T;
while (T --)
solve();
return 0;
}
J 最后都是0
\(j\)为整数\(n\)上的某一位数字.
\[f[n] = inf \\ f[n]=min(f[n],f[n-j] + 1) \]#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 1; i <= n; i ++) {
string s = to_string(i);
for (auto j : s) {
dp[i] = min(dp[i], dp[i - (j - '0')] + 1);
}
}
cout << dp[n] << '\n';
return 0;
}
K 第五人格,启动!
包括起点和终点一共五个点,计算出两两点之间的距离,用全排列表示出所有路线,然后取最短时间
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
int u[] = {1, -1, 0, 0}, v[] = {0, 0, 1, -1};
vector<string> mp(n);
for (auto &i : mp) cin >> i;
int sx, sy, ex, ey;
vector<int> t(3);
vector<PII> xy(3);
cin >> sx >> sy ;
sx --, sy --;
for (auto &[x, y] : xy) {
cin >> x >> y;
x--, y--;
}
cin >> ex >> ey;
ex--, ey--;
for (auto &i : t) cin >> i;
vector dis(5, vector<i64>(5, 0));
for (int i = 0; i < 3; i ++) {
auto [x, y] = xy[i];
dis[0][i + 1] = abs(x - sx) + abs(y - sy);
}
for (int i = 0; i < 3; i ++)
for (int j = 0; j < 3; j ++)
dis[i + 1][j + 1] = (abs(xy[i].first - xy[j].first) + abs(xy[i].second - xy[j].second));
auto bfs = [&](int x, int y, int edx, int edy) -> i64{
vector<bitset<110>> vis(m);
queue<pair<PII, i64>> Q;
Q.push({{x, y}, 0});
vis[x][y] = 1;
int res = 0;
while (Q.size()) {
auto [axy, w] = Q.front();
auto [ax, ay] = axy;
Q.pop();
if (ax == edx && ay == edy) {
res = w;
break;
}
for (int i = 0; i < 4; i ++) {
int dx = u[i] + ax;
int dy = v[i] + ay;
if (dx >= 0 && dx < n && dy >= 0 && dy < m && !vis[dx][dy] && mp[dx][dy] != '#') {
Q.push({{dx, dy}, w + 1});
vis[dx][dy] = 1;
}
}
}
return res;
};
for (int i = 0; i < 3; i ++) {
auto [x, y] = xy[i];
dis[i + 1][4] = bfs(x, y, ex, ey);
}
i64 ans = LLONG_MAX;
vector<vector<int>> st;
vector<int> sh{1, 2, 3};
do {
vector<int> jk{0};
for (int i = 0; i < 3; i ++) {
jk.push_back(sh[i]);
}
jk.push_back(4);
st.push_back(jk);
} while (next_permutation(sh.begin(), sh.end()));
for (auto v : st) {
i64 res = 0, p = 1;
for (int i = 1; i < 5; i ++) {
res += dis[v[i - 1]][v[i]] * p;
if (p != 4) p += t[v[i] - 1];
}
ans = min(ans, res);
}
cout << ans << '\n';
return 0;
}
L 加纳~
已知视频一共完整播放了 k / n 遍,然后我们需要判断一下剩下的时间是否大于 m 秒即可。
#include <bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<'\n';
using namespace std;
using i64 = long long;
typedef pair<i64, i64> PII;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n, m, k;
cin >> n >> m >> k;
cout << k / n + (k % n >= m) << '\n';
return 0;
}
标签:int,cin,2024,++,vector,选拔赛,天梯,ans,dp
From: https://www.cnblogs.com/Kescholar/p/18060068