logoChat01.ai

Задача [B'-B] 6: Оценка за курс Условие задачи (pd...

Créé le : 3 septembre 2025

Répondu en utilisant GPT-5 Thinking par Chat01

Question

Задача [B'-B] 6: Оценка за курс
Условие задачи (pdf)

Миша изучает курс по алгоритмам в Высшей Школе Битовых операций. Итоговая оценка за курс вычисляется следующим образом: в каждом из
n
домашних заданий студент решает какое-то количество задач, затем студент выбирает любые
k
различных домашних заданий и вычисляет побитовое И количества сданных задач из выбранного множества домашних заданий.

К концу семестра Миша решил повысить свою оценку. В каждом домашнем задании у него уже решено сколько-то задач, а также осталось время чтобы решить ещё
m
задач из любых домашек (можно дорешивать как одну домашку, так и несколько разных, возможно, он дорешает меньшее количество задач). К сожалению, Миша круто решает задачи по алгоритмам, но не может понять какие задачи ему стоит дорешать. Ваша задача определить его максимальную оценку за курс.

Напомним, что побитовое И неотрицательных целых чисел
a
и
b
равно неотрицательному целому числу, у которого в двоичном представлении на определенной позиции находится единица тогда и только тогда, когда в двоичных записях
a
и
b
на этой позиции находятся единицы. Например,
3
10
AND
5
10

0011
2
AND
0101
2

0001
2

1
10
.

Формат входных данных
В первой строке входных данных содержится три целых числа
n
,
m
,
k
(
1
≤
k
≤
n
≤
2
⋅
10
5
,
0
≤
m
<
2
30
) — количество домашних заданий, количество задач, которые Миша успеет дорешать и количество домашних заданий, которые учитываются в вычислении итоговой оценки.

Во второй строке содержится
n
целых чисел
a
1
,
a
2
,
…
,
a
n
(
0
≤
a
i
<
2
30
) — количество задач, которые решил Миша в каждом из домашних заданий.

Формат выходных данных
Выведите одно целое число — максимальную итоговую оценку за курс после того как Миша дорешает не больше
m
задач.

Примеры
Входные данные
5 2 3
6 6 15 7 4
Выходные данные
7
Входные данные
3 2 3
4 4 4
Выходные данные
4
Примечания
В первом примере Миша может дорешать по одной задаче из первого и второго домашнего задания и выбрать для подсчета итоговой оценки домашние задания с номерами
1
,
2
и
4

Во втором примере Мише выгодно не дорешивать задачи.

(Дай мне код решения этой задачи на c++)

Python

python
def cost(ai, mask):
    y = ai
    for b in reversed(range(0, 30)):
        if (mask>>b)&1 and ((y>>b)&1)==0:
            y += (1<<b) - (y & ((1<<b)-1))
    return y - ai

def feasible(A, m, k, mask):
    costs = [cost(a, mask) for a in A]
    costs.sort()
    return sum(costs[:k]) <= m

def solve(n,m,k,A):
    ans=0
    for b in reversed(range(0,30)):
        T=ans | (1<<b)
        if feasible(A,m,k,T):
            ans=T
    return ans

print(solve(5,2,3,[6,6,15,7,4]))
print(solve(3,2,3,[4,4,4]))

Réflexion

Optimizing with nth_element

Instead of sorting the entire vector, I'll use nth_element to find the smallest k elements directly, without sorting them fully. I'll accumulate the sum of the first k elements, even though they're not ordered. In my C++ implementation, I'll handle everything as long long and use unsigned long long for the cost function. Time complexity looks manageable.

Thought for 2m 10s

Réponse

Вот надёжное решение на C++ с жадной побитовой проверкой и вычислением минимальной «доделки» для каждого задания. Работает за ~30 · O(n) на проверку благодаря nth_element.

cpp
#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

// Минимальная "доделка" x >= 0 такая, что (a + x) имеет все биты mask установлены.
static inline ull need_inc(ull a, ull mask) {
    ull y = a;
    for (int b = 29; b >= 0; --b) {
        if ((mask >> b) & 1ULL) {
            if (((y >> b) & 1ULL) == 0ULL) {
                ull low = y & ((1ULL << b) - 1ULL);     // младшие b бит
                y += (1ULL << b) - low;                 // поднимаем до числа с битом b = 1 и низ обнуляется
            }
        }
    }
    return y - a;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    ull m;
    if (!(cin >> n >> m >> k)) return 0;

    vector<ull> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    auto feasible = [&](ull mask) -> bool {
        static vector<ull> cost;
        cost.resize(n);
        for (int i = 0; i < n; ++i) cost[i] = need_inc(a[i], mask);
        // Возьмём k минимальных и проверим сумму
        nth_element(cost.begin(), cost.begin() + k, cost.end());
        ull sum = 0;
        for (int i = 0; i < k; ++i) {
            if (sum > m) return false; // ранний выход
            sum += cost[i];
        }
        return sum <= m;
    };

    ull ans = 0;
    for (int b = 29; b >= 0; --b) {
        ull trial = ans | (1ULL << b);
        if (feasible(trial)) ans = trial;
    }

    cout << ans << "\n";
    return 0;
}

Идея: строим ответ по битам сверху вниз. Для выбранной маски mask проверяем, можно ли выбрать k домашних заданий и накинуть задачи (в сумме не более m), чтобы у всех этих k чисел были выставлены биты mask. Минимальная «доделка» для одного числа считается функцией need_inc, которая последовательно (от старших битов к младшим) поднимает число до ближайшего, удовлетворяющего маске. Затем берём k наименьших «стоимостей» через nth_element и сравниваем их сумму с m.

Question

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 256M
Задача [B-A'] 3: Граф-штурвал
Условие задачи (pdf)

Петя обнаружил древний граф-штурвал с
n
+
1
вершинами, пронумерованными от
0
до
n
. Этот граф напоминает колесо, где центральная сокровищница (вершина
0
) соединена с другими сокровищницами, образующими кольцо. Каждая вершина представляет сокровищницу, а рёбра — пути, за прохождение которых нужно заплатить золотые монеты.

Граф устроен следующим образом:

Для каждого
i

1
,
2
,
…
,
n
есть путь (неориентированное ребро) между центральной сокровищницей
0
и сокровищницей
i
, за который нужно заплатить
p
i
золотых монет.

Для каждого
i

1
,
2
,
…
,
n
есть путь между сокровищницей
i
и сокровищницей
i
+
1
, за который нужно заплатить
q
i
золотых монет. (Здесь сокровищница
n
+
1
— это сокровищница
1
)

Петя хочет разделить сокровищницы на две группы, чтобы можно было путешествовать только между сокровищницами разных групп (то есть сделать граф двудольным). Для этого он может закрыть некоторые пути, но за каждый закрытый путь с весом
w
он теряет
w
золотых монет. Помогите Пете определить, сколько золотых монет он должен потратить, чтобы граф-штурвал стал двудольным.

Формат входных данных
Первая строка содержит одно целое число
n
(
3
≤
n
≤
200
000
) — количество вершин графа-штурвала минус один.

Вторая строка содержит
n
целых чисел
p
1
,
p
2
,
…
,
p
n
(
1
≤
p
i
≤
10
9
) — количество золотых монет за пути между сокровищницей
0
и сокровищницами
1
,
2
,
…
,
n
.

Третья строка содержит
n
целых чисел
q
1
,
q
2
,
…
,
q
n
(
1
≤
q
i
≤
10
9
) — количество золотых монет за пути между сокровищницей
i
и сокровищницей
i
+
1
(где сокровищница
n
+
1
— это сокровищница
1
).

Формат выходных данных
Выведите одно целое число — минимальную сумму золотых монет, которую Пете нужно потратить, чтобы граф-штурвал стал двудольным.

Примеры
Входные данные
4
1 1 1 1
5 5 5 5
Выходные данные
2
Входные данные
5
1 2 3 4 5
3 3 2 6 1
Выходные данные
7
(Дай мне код решения этой задачи на c++)

Réflexion

Analyzing bipartiteness of wheel graph

We need to solve the problem of making a wheel graph bipartite by deleting the minimum weight edges. The issue is related to removing edges in a way that the graph's structure is preserved as bipartite. For a wheel graph, it is bipartite if the cycle length is even, as the center must connect to an opposite-colored partition of outer nodes.

Making the wheel graph bipartite

A wheel graph consists of a cycle and a central hub connected to all rim vertices. It's bipartite only if the cycle length is even, but odd triangles form when both adjacent rim nodes are connected to the center. These triangles make the graph non-bipartite, so we must delete edges to remove all odd cycles, particularly breaking these triangles.

Ensuring all odd cycles are removed

We need to remove at least one edge from each triangle formed by vertices {0, i, i+1} in the wheel graph. We're aiming to minimize the total weight by selecting edges to delete. It's like finding a minimum vertex cover for the cycle, but careful—deleting edges could create other odd cycles, although the only ones we care about are the triangles.

Handling odd cycles in the rim

If n is odd, the rim itself can form an odd cycle. To ensure the graph is bipartite, we must delete at least one rim edge if n is odd. While breaking triangles could handle some of the rim edges, we might need to delete more to fully avoid odd cycles and ensure bipartiteness.

Ensuring bipartiteness and removing odd cycles

To prevent odd cycles and make the wheel graph bipartite, we need to minimize edge deletions under certain constraints. If n is odd, we should avoid keeping all rim edges. We need to ensure that no path along the rim with consecutive kept spokes forms an odd-length cycle. This involves deleting some rim edges and spokes strategically, maintaining alternating colors to enforce bipartiteness.

Dynamic programming for max cut on a wheel graph

To minimize deletions and make the wheel graph bipartite, we model the problem as a max-cut problem. Using dynamic programming, I can maximize the total weight of chosen edges while keeping the graph bipartite. By alternating rim edges and optimizing the label assignments ("0" or "1") for each vertex, we achieve the desired solution. I’ll solve it in O(n) time.

Thought for 2m 46s

Réponse

Вот надёжное и быстрое решение за O(n) через сведение к задаче максимального разреза (max-cut) на «штурвале». Мы фиксируем цвет центра (0) и максимизируем сумму весов рёбер, которые можно оставить (пересекают разрез). Остаётся двоичная DP по циклу с «унарными» весами p_i и «парными» q_i. Минимальная цена = сумма всех рёбер − максимум оставленных.

cpp
#include <bits/stdc++.h>
using namespace std;

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    if (!(cin >> n)) return 0;
    vector<int64> p(n+1), q(n+1); // 1..n
    for (int i = 1; i <= n; ++i) cin >> p[i];
    for (int i = 1; i <= n; ++i) cin >> q[i];
    
    // total weight of all edges (sum of all spokes and rim edges)
    long long total = 0;
    for (int i = 1; i <= n; ++i) total += p[i];
    for (int i = 1; i <= n; ++i) total += q[i];

    const long long NEG = (long long)-4e18;
    auto max_kept_for_center = [&](int c)->long long {
        // DP over cycle by fixing x1=c (цвет вершины 1), затем закрывающий ребро q[n]
        long long dp0 = NEG, dp1 = NEG; // значения для x_{i} = 0/1
        // i = 1
        if (c == 0) { dp0 = 0; dp1 = NEG; }
        else        { dp0 = NEG; dp1 = p[1]; } // если x1=1, получаем p1 как "унарный" вклад

        // i = 2..n, используем q[i-1] между (i-1) и i
        for (int i = 2; i <= n; ++i) {
            long long ndp0 = max(dp0 /* +0 */              /* +0 */,
                                 dp1 /* +0 */ + q[i-1]);
            long long ndp1 = max(dp0 + p[i] + q[i-1],
                                 dp1 + p[i] /* +0 */);
            dp0 = ndp0; dp1 = ndp1;
        }
        // добавляем замыкающее ребро между n и 1 с весом q[n]
        long long res = NEG;
        // если x_n = 0, добавим q[n], когда 0 != c
        res = max(res, dp0 + ((0 != c) ? q[n] : 0));
        // если x_n = 1, добавим q[n], когда 1 != c
        res = max(res, dp1 + ((1 != c) ? q[n] : 0));
        // также добавлены все "унарные" p[i] когда x_i=1 и все q[i-1] для переходов s!=t
        // это и есть максимум оставленных рёбер при фиксированном x1=c и x0=0
        // (центр фиксирован в 0 без потери общности)
        if (c == 0) {
            // учли p[1] = 0 в старте (верно)
        } else {
            // p[1] учтён в dp1 стартом
        }
        return res;
    };

    long long best_kept = max(max_kept_for_center(0), max_kept_for_center(1));
    long long answer = total - best_kept;
    cout << answer << "\n";
    return 0;
}

Почему это работает

  • Минимизировать стоимость удалённых рёбер ≡ максимизировать сумму оставленных, причём оставленный граф обязан быть двудольным. Это ровно max-cut: выбираем разбиение вершин на 2 доли, оставляем рёбра «через разрез».
  • Фиксируем цвет центра равным 0 (симметрия). Тогда вклад «спиц» превращается в унарные прибыли p_i * x_i. «Кольцевые» рёбра дают прибыль q_i, если цвета соседей различны.
  • Получаем двоичную оптимизацию на цикле: максимизируем
    F(x) = Σ p_i * x_i + Σ q_i * [x_i != x_{i+1}].
    Решаем DP по пути для двух случаев x_1 = 0/1, а затем добавляем замыкающее ребро q_n и берём максимум.
  • Ответ = (сумма всех p и q) − (максимум оставленных). Всё за O(n) по памяти O(1).

Question

Задача [B-A'] 4: Игра на графе
Условие задачи (pdf)

Дан неориентированный взвешенный связный граф из
n
вершин и
m
ребер.

Никита и Миша играют в игру. Сначала Никита красит каждую вершину графа в один из двух цветов (в том числе разрешается покрасить все вершины в один цвет). После этого Миша выбирает две различные вершины
s
и
t
, покрашенные Никитой в одинаковый цвет. Результатом игры считается расстояние между вершинами
s
и
t
в графе (минимальная сумма весов ребер на пути между
s
и
t
).

Никита стремится максимизировать итоговый результат, а Миша — минимизировать. Найдите итоговый результат игры, если Никита и Миша играют оптимально.

Формат входных данных
Первая строка содержит два целых числа
n
и
m
(
3
≤
n
≤
200
000
,
n
−
1
≤
m
≤
min
(
n
(
n
−
1
)
2
,
200
000
)
) — количество вершин и ребер графа соответственно.

Следующие
m
строк содержат три целых числа
u
,
v
и
w
(
1
≤
u
<
v
≤
n
,
1
≤
w
≤
10
9
), задающих неориентированное ребро между вершинами
u
и
v
веса
w
.

Гарантируется, что граф является связным и все пары
(
u
,
v
)
попарно различны.

Формат выходных данных
Выведите итоговый результат игры при условии, что оба игрока играют оптимально.

Примеры
Входные данные
3 3
1 2 3
2 3 4
1 3 8
Выходные данные
7
Примечания
Пусть Никита покрасил вершины с номерами
1
и
3
в одинаковый цвет, а вершину с номером
2
— в другой цвет. Миша же, в свою очередь, может выбрать
s

1
и
t

3
. Расстояние между этими вершинами равняется
7
.

Можно показать, что Никита не может гарантировать себе больший ответ, поэтому результат игры равняется
7
.

(Дай мне код решения этой задачи на c++)

Partager cette Q&R