2024昆明邀请赛
B 金牌
真是忙碌的一周!这个周末, 将会有
每场竞赛将会从每
堡堡是一所大学的教练, 该大学有
贪心
#define int long long
void solve() {
int n, k;cin >> n >> k;
vector<int> a(n + 1), yu(n + 1);
int sum = 0;
for (int i = 1;i <= n;i++) {
cin >> a[i];sum += a[i] / k;yu[i] = a[i] % k;
}
int m;cin >> m;
sort(yu.begin() + 1, yu.end(), greater<int>());
for (int i = 1;i <= n;i++) {
if (m >= k - yu[i])sum++, m -= k - yu[i];
}
cout << sum + m / k << '\n';
}
G 乐观向上
求字典序最小的序列
对于所有
void solve() {
int n;cin >> n;
if (n % 4 == 0 || n == 1) {
cout << "impossible\n";return;
}
cout << "1 0 ";
for (int i = 2;i < n;i++) {
if (i % 4 == 0) {
cout << i - 1 << ' ';continue;
}
if (i % 4 == 3) {
cout << i + 1 << " ";continue;
}
cout << i << " ";
}
cout << '\n';
}
I 左移 2
给定一个由小写字母组成的字符串, 称该字符串是美丽的, 若字符串中每一对相邻的字符都不相同。
给定由小写英文字母组成的, 长度为
令
找到一个非负整数
Solution:
容易知道的是:若将这个字符串看作环形字符串,那么在这个环形字符串中相同的各段中只要出现了偶数,答案就可以割掉一个。
void solve() {
string s;cin >> s;
vector<int> a;
int cnt = 1;
for (int i = 1;i < s.size();i++) {
if (s[i] == s[i - 1]) {
cnt++;
} else {
a.push_back(cnt);
cnt = 1;
}
}
a.push_back(cnt);
if (a.size() == 1) {
cout << a[0] / 2 << '\n';return;
}
if (s[0] == s[s.size() - 1]) {
a[0] += a.back();a.pop_back();
}
int ans = 0, ok = 0;
for (auto x : a) {
if (x % 2 == 0)ok = 1;
ans += x / 2;
}
cout << ans - ok << '\n';
}
A 两星级竞赛
教育专家们出于某种原因, 准备对
据说每项竞赛都会依据
如果一项星级更高的赛事有更高的分数, 看起来会比较自然。专家们要求, 对于任意两项竞赛
从小到大贪心即可,注意一个 trick:如何将下标还原?
#define int long long
void solve() {
int n, m, k;cin >> n >> m >> k;
vector<int> s(n + 1);
vector<vector<int>> v(n + 1, vector<int>(m + 4));
for (int i = 1;i <= n;i++) {
cin >> s[i];v[i][0] = s[i];
int sum = 0, cnt = 0;
for (int j = 1;j <= m;j++) {
cin >> v[i][j];
if (v[i][j] != -1) {
sum += v[i][j];
} else {
cnt++;
}
}
v[i][m + 1] = sum;
v[i][m + 2] = cnt;
v[i][m + 3] = i;
}
sort(v.begin(), v.end(), [](auto x, auto y) {
return x[0] < y[0];
});
int last = -1, cur = -1;
for (int i = 1;i <= n;i++) {
if (v[i][0] != v[i - 1][0]) {
last = cur;
}
int x = v[i][m + 1] - last - 1;
if (x >= 0) {
for (int j = 1;j <= m;j++) {
if (v[i][j] == -1) {
v[i][j] = 0;
}
}
} else {
x = -x;
if (v[i][m + 2] * k + v[i][m + 1] <= last) {
cout << "No\n";return;
}
for (int j = 1;j <= m;j++) {
if (v[i][j] == -1) {
v[i][j] = min(k, x);
x -= v[i][j];
}
}
}
int sum = 0;
for (int j = 1;j <= m;j++) {
sum += v[i][j];
}
cur = max(cur, sum);
}
cout << "Yes\n";
sort(v.begin(), v.end(), [&](auto x, auto y) {
return x[m + 3] < y[m + 3];
});
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= m;j++) {
cout << v[i][j] << " \n"[j == m];
}
}
}
E 学而时习之
给定长度为
选择两个整数
和 满足 , 之后对于每个 , 将 变为 。
即区间
差分思想+思维
暴力:发现这个题目对于差分数组只会涉及到两个下标,若纯差分,则只需要枚举差分数组中的两个下标即可。只是时间复杂度为
void solve() {
int n, k;cin >> n >> k;
vector<int> a(n + 1), dif(n + 2);
int ans = a[1];
for (int i = 1;i <= n;i++)cin >> a[i], ans = __gcd(ans, a[i]);
for (int i = 1;i <= n;i++)dif[i] = a[i] - a[i - 1];
for (int i = 1;i <= n;i++) {
for (int j = i;j <= n;j++) {
dif[i] += k;dif[j + 1] -= k;
int res = dif[1];
for (int k = 1;k <= n;k++) {
res = __gcd(dif[k], res);
}
ans = max(ans, abs(res));
dif[i] -= k;dif[j + 1] += k;
}
}
cout << ans << '\n';
}
Solution:这个题目可以将
答案为
对于前缀和后缀的 gcd 和之前结果相比改变了的点不会很多,依次枚举即可。
方法不止一种,关键在于想到使得 gcd 改变的数量很少的特性。
#define int long long
void solve() {
int n, k;cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1;i <= n;i++)cin >> a[i];
if (n == 1) {
cout << k + a[1] << '\n';return;
}
unordered_set<int>s1, s2;
s1.insert(1);
s2.insert(n);
int g = a[1];
for (int i = 1;i <= n;i++) {
int gg = g;
g = __gcd(g, a[i]);
if (gg != g) {
s1.insert(i);
}
}
g = a[n];
for (int i = n;i >= 1;i--) {
int gg = g;
g = __gcd(g, a[i]);
if (gg != g) {
s2.insert(i);
}
}
vector<int> pre(n + 1), suf(n + 1);
pre[1] = a[1];suf[n] = a[n];
for (int i = 2;i <= n;i++) {
pre[i] = __gcd(pre[i - 1], a[i]);
}
for (int i = n - 1;i >= 1;i--) {
suf[i] = __gcd(suf[i + 1], a[i]);
}
int ans = pre[n];
for (auto l : s1) {
for (auto r : s2) {
if (l <= r) {
int x = __gcd(pre[l - 1], suf[r + 1]);
if (l == 1) {
x = suf[r + 1];
}
if (r == n) {
x = pre[l - 1];
}
int res = l != r ? abs(a[l] - a[l + 1]) : a[r] + k;
for (int i = l + 1;i <= r - 1;i++) {
res = __gcd(res, abs(a[i] - a[i + 1]));
}
int y = __gcd(res, a[r] + k);
if (l == 1 && r == n) {
x = y;
}
ans = max(ans, __gcd(x, y));
}
}
}
cout << ans << '\n';
}
M 意大利美食
堡堡为您准备了一份披萨!这个披萨是一个凸多边形,每条饼边里都有芝士夹心。但这些夹心边很脆弱,导致切披萨的时候只能经过多边形的顶点,而不能从边的中间切开。
不幸的是,披萨上有一片您肯定不喜欢的, 巨大的圆形菠夢片。
求沿着直线切一刀之后, 可以获得的最大的没有菠萝的披萨的面积。称一块披萨上没有菠萝, 当且仅当菠萝没有任何部分严格位于披萨块内。也就是说, 菠萝和披萨的相交面积为 0 。

(挖坑...)
J 冲向黄金城
某个国家有
是
您想要从城市 1 开始进行全国旅行。您已经为旅行购买了
由于决定车票的使用顺序太麻烦了,您打算直接按现有的顺序使用车票。更正式地,您将执行
L 漫步野径
堡堡正在一块无穷大的二维平面上散步。对于平面上每个满足
堡堡只能沿着小径移动。令
两个整数