MB
в связном неориентированном графе есть нечётный цикл тогда и только тогда, если между двумя вершинами x и y, для которых минимальные расстояния от определённой вершины равны, есть ребро
Предлагаю рассмотреть какой-нибудь нечетный цикл
Size: a a a
2020 May 20
MB
Взять в нем вершину и противоположное ребро
MB
Проблема в том, что расстояние может быть короче, чем по циклу, но выглядит преодолимо
K
Я думаю так: если наш цикл нечётный только в одной вершине соединён с остальной частью графа, то для него такое правило выполняется. Теперь возьмём вторую точку соединения. Ясно, что таким образом образуется ещё один цикл. Если во внешнем цикле тоже есть вторая точка, то возьмём цикл ещё больше, и так до тех пор, пока у нас не будет большой цикл с одной точкой соединения
K
Если он нечётный, то мы уже доказали всё
CD
в связном неориентированном графе есть нечётный цикл тогда и только тогда, если между двумя вершинами x и y, для которых минимальные расстояния от определённой вершины равны, есть ребро
BFS умеет раскрашивать граф в два цвета
CD
Если это свойство выполнено, то нечетный цикл предъявлен
Если это свойство не выполнено, проведем BFS из определенной вершины. Любое ребро u <-> v соединяет вершины |d[u] - d[v]| <= 1, и свойство запрещает d[u] - d[v] == 0
Если это свойство не выполнено, проведем BFS из определенной вершины. Любое ребро u <-> v соединяет вершины |d[u] - d[v]| <= 1, и свойство запрещает d[u] - d[v] == 0
CD
значит, |d[u] - d[v]| == 1 и d[u] % 2 раскраска в два цвета
2020 May 21
t
Здравствуйте,
Подскажите, пожалуйста, где посмотреть хорошую реализацию decimal fixed point.
При делении fixed point чисел требуется хранить временное значение с большей длиной, чем используется для представления числа. Т.е.
Но что делать, если для хранения значения использовать int128_t?
Подскажите, пожалуйста, где посмотреть хорошую реализацию decimal fixed point.
При делении fixed point чисел требуется хранить временное значение с большей длиной, чем используется для представления числа. Т.е.
class fixed {
int64_t value;
void operator/(other) {
int128_t v = value;
v *= exponent();
v /= other;
value = v
}
}
где
exponent() - 10^число знаков после запятойНо что делать, если для хранения значения использовать int128_t?
t
Можно ли сделать что-то лучше, чем использовать какую-то long integer арифметику, учитывая, что умножение делается на степень 10?
AT
int128_t - это long integer арифметика под капотом
t
окей. Но int256 арифметики под капотом пока нет, поэтому я ищу оптимальный способ это сделать
t
особенно в части деления, с умножением попроще
2020 May 22
AT
Проще всего, если нужен вывод, вручную реализовать двоично-десятичный формат. В uint16 можно хранить числа до 10000. Правда пара бит будут незадействованы. Т.е. у тебя 1 цифра будет от 0 до 9999
AT
Насчёт деления не скажу
MB
Зачем это тут?
DK
Кремлебот вошел в чат
/¯
Кремлебот вошел в чат
И вышел из чата
mq
извините за немного научпоп-стайл вопрос, но если сплей-деревья такие классные и волшебные, то почему их никто не использует в спортпроге (ну кроме линкката, скажем)?
mq
насколько я понимаю можно легко писать сплеи вместо декартачей и вообще просто вместо стандартного сета