- Кекс
описание проблемы
Сегодня день рождения Xiaming, у него есть N Cakes, которые будут распространяться для друзей. Вес N Cake (номер 1 до N) – A1, A2, …, An. Xiaoming хочет разделить каждого друга, по крайней мере, K Cakes, которые взвешивают K. Друзья Xiaming уже выстроились в очередь, чтобы подготовиться к торту. Для каждого друга Сяоминг всегда разделяет его на самый маленький торт в руке. Когда торт, этот друг получает вес торта меньше, чем K, он продолжит уходить Оставшиеся остатки. Наименьшее число в торте было дано ему, пока торт Сяомина не был разделен или общий вес торта, который распространялся этот друг, был больше, чем равна К.
Когда торт Данга Сями был разделен, сколько друзей в общей сложности было назначено на торт.
Входной формат
Первая линия ввода содержит два целых числа n и k, что, как описано выше.
Вторая строка содержит n положительного целого числа, что означает A1, A2, …, An.
Выходной формат
Вывод на целое число, указывая, сколько друзей в торте.
Вход пример
6 9
2 6 5 6 3 5
Образец вывода
3
Образец примера
Первый друг был разделен на первые три пирога, второй друг был разделен на четвертый и 5 кусочек пирожных, а третий друг был назначен на последний кусок торта.
Шкала и согласие случая оценки
Для всех случаев оценки 1 ≤ n ≤ 1000, 1 ≤ k ≤ 10000, 1 ≤ ai ≤ 1000.
Код:
#include <iostream>
using namespace std;
int main(){
int n, m, a, ans = 0, tmp = 0;
cin >> n >> m;
while(n --){
cin >> a;
tmp += a;
if(tmp >= m){
++ ans;
tmp = 0;
}
}
if(tmp)
++ ans;
cout << ans << endl;
return 0;
}
- Студенческая очередь
описание проблемы
Преподаватель спорта Синьон хочет стоять в очереди учащихся в своем классе в порядке. Сначала он попросил учеников выстроиться в заказ номера школы от малого до большого, и маленький номер школы занял первое место, а затем несколько раз приспособился. Когда -то Xiaoming может позволить однокласснику пойти в команду, двигаться вперед или назад, а затем вставить очередь.
Например, группа мобильных примеров приведена ниже, с количеством учеников средней школы с 8 людьми.
0) Номер школы начальной очереди составляет 1, 2, 3, 4, 5, 5, 6, 7, 8;
1) Для первой корректировки команда была «одноклассники № 3 возвращается 2», что указывает на то, что одноклассники № 3 отправились в команду, вернулись на расстояние 2 учеников, а затем вставлены в очередь., 2, 4, 5, 3, 6, 7, 7, 8;
2) Вторая корректировка, команда была «№ 8 студентами движения вперед 3», указывая на то, что студенты № 8 отправились в команду, переместились на расстояние 3 учеников, а затем вставили в очередь., 2, 4 , 5, 8, 3, 6, 7;
3) Для третьей корректировки команда является «№ 3 студенты движутся вперед 2», указывая на то, что одноклассники № 3 обращаются к команде, перейдут на расстояние 2 ученика, а затем вставьте его в очередь., 2 , 4, 3, 5, 8, 6, 7.
Xiaming записал весь процесс корректировки. Сколько в школе число всех учащихся в конце?
Пожалуйста, обратите особое внимание, число, связанное с вышеуказанным мобильным процессом, относится к номеру школы, а не к должности в команде. При движении назад расстояние между движением не превышает количество людей, стоящих за одноклассниками. Если расстояние, чтобы перейти назад, точно равно числу людей, стоящих за одноклассниками, одноклассник перейдет к концу очереди. При движении вперед расстояние между движением не превышает количество людей перед одноклассниками. Если расстояние для движения вправо равно числу людей перед одноклассником, одноклассник перейдет к фронту очередь.
Входной формат
Вход первой строки содержит целое число N, указывающее количество учащихся, а номер школы ученика пронумерован от 1 до N.
Вторая строка содержит целое число M, что означает количество корректировок.
Следующая M Line, два целочисленного p, Q, если Q положительный, это означает, что учащиеся с номером школы P возвращаются в Q назад. Если Q отрицательный, это означает, что учащиеся с номером школы P продвигаются вперед-Q Анкет
Выходной формат
Выходная линия содержит n пересечений, а два смежных целых числа разделены пространством, что указывает на то, что школьный номер всех учащихся с конца конца.
Вход пример
8
3
3 2
8 -3
3 -2
Образец вывода
1 2 4 3 5 8 6 7
Шкала и согласие случая оценки
Для всех случаев оценки, 1 ≤ n ≤ 1000, 1 ≤ m ≤ 1000, все движение является законным.
Код:
#include <iostream>
using namespace std;
const int MAXN = 1010;
int cnt[MAXN], arr[MAXN];
int main(){
int n, m;
int a, b;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cnt[i] = i, arr[i] = i;
while(m --){
cin >> a >> b;
if(b > 0){
for(int i = cnt[a]; i < cnt[a] + b; i ++){
cnt[arr[i + 1]] --;
arr[i] = arr[i + 1];
}
}else{
for(int i = cnt[a]; i > cnt[a] + b; i --){
cnt[arr[i - 1]] ++;
arr[i] = arr[i - 1];
}
}
cnt[a] += b;
arr[cnt[a]] = a;
}
for(int i = 1; i <= n; i ++)
cout << arr[i] << " ";
return 0;
}
- Markdown
описание проблемы
Markdown – это популярный легкий язык лейбла (легкий язык разметки), который широко используется для написания документов с форматами. Например, следующий текст записывается в синтаксисе Маркдауна:
Хотя этот текст, написанный в Markdown, хотя это чистый текстовый формат, читатели могут легко увидеть свою структуру документа. В то же время существует множество инструментов, которые могут автоматически преобразовать текст разметки в HTML или даже Word, PDF и другие форматы для достижения лучших эффектов набора набора. Например, код HTML, полученный приведенным выше текстом, показан ниже:
Этот вопрос требует, чтобы вы написали инструмент преобразования разметки, чтобы завершить работу преобразования из текста Markdown в HTML -код. Упрощенные причины, описание правил грамматики и правил конверсии, определенных в этом вопросе ::
● Блок: блок – верхняя структура документа. Синтаксис Marckdown этого вопроса имеет три блочных формата. На входе одна или несколько пустых линий разделены между двумя соседними блоками. Удалите все пустые линии отдельного блока во время вывода.
○ Параграф: При нормальных обстоятельствах несколько строк входов представляют собой абзац. Правила преобразования параграфов вставлены в первую строку параграфов<p>, Вставьте в конце последней строки</p>。
○ Название: Есть только одна строка для каждого блока заголовка, по нескольким#В начале, затем одно или несколько пробелов, а затем контент заголовка, до конца строки.#Число определяет уровень заголовка. Во время преобразования,# HeadingКонвертировать<h1>Heading</h1>，## HeadingКонвертировать<h2>Heading</h2>, И так далее. Самые глубокие названия 6.
○ Нет последовательного списка: список последовательностей состоит из нескольких строк, каждая строка состоит из*В начале, затем одно или несколько мест, а затем текст элемента списка до конца строки. Во время преобразования вставьте линию в начале<ul>, Наконец, вставьте линию</ul>; Для каждой строки,* ItemКонвертировать<li>Item</li>Сущность В этом вопросе есть только один слой, и не будет никакого отступления.
● Внутри: для содержания в блоке есть две внутренние структуры.
○ Подчеркните:_Text_Конвертировать<em>Text</em>Сущность Подчеркните, что в каждой строке не будет никакого вложенного_Число должно быть равномерным, и оно не будет смежным непрерывным. Уведомление_Text_Передняя и задняя часть не обязательно являются космическим персонажем.
○ Супер ссылка:[Text](Link)Конвертировать<a href="Link">Text</a>Сущность Супер ссылки и акцент могут быть вложены друг на друга, но каждый формат не будет превышать один слой.
Входной формат
Введите документ, записанный рядом строк, указывающий документ, написанный в грамматике Markdown, указанный в этом вопросе.
Выходной формат
Вывод состоит из ряда строк, указывающих на то, что документ ввода нанесенную маркировку преобразуется в сгенерированный HTML -код.
Вход пример
# Hello
Hello, world!
Образец вывода
<h1>Hello
<p>Hello, world!
Шкала и согласие случая оценки
Тестовая точка этого вопроса соответствует следующим условиям:
● Количество строк, содержащихся в каждой тестовой точке каждой тестовой точки, не превышает 100, и количество каждой строки символов (включая символ последней линии обмена) не превышает 100.
● За исключением изменения строк, все символы являются печатными символами из кода ASCII от 32 до 126.
● В каждой строке и конец строки не будет пространства.
● Входные данные, за исключением синтаксиса Markdown, они не появятся в содержимовом#、*、_、[、]、(、)、<、>、&Эти персонажи.
● Все тестовые точки соответствуют грамматике разметки, указанной в теме. Ваша программа не должна рассматривать ситуацию грамматических ошибок.
Код:
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 110;
string arr[MAXN];
int main() {
string s;
int n = 0;
bool op = true;
while (getline(cin, s)) {
arr[n++] = s;
}
for (int i = 0; i < n; i++) {
string s;
int pos = 0;
while (pos < arr[i].length()) {
if (arr[i][pos] == '_') {
s += "<em>";
++pos;
while (pos < arr[i].length() && arr[i][pos] != '_')
s += arr[i][pos++];
++pos;
s += "</em>";
} else {
s += arr[i][pos++];
}
}
arr[i] = s;
s.clear();
pos = 0;
while (pos < arr[i].length()) {
if (arr[i][pos] == '[') {
string a, b;
++pos;
while (pos < arr[i].length() && arr[i][pos] != ']')
a += arr[i][pos++];
pos += 2;
while (pos < arr[i].length() && arr[i][pos] != ')')
b += arr[i][pos++];
++pos;
s += "<a href=\"" + b + "\">" + a + "</a>";
} else {
s += arr[i][pos++];
}
}
arr[i] = s;
}
for (int i = 0; i < n; i++) {
s = arr[i];
if (s[0] == '#') {
int cnt = 0;
while (cnt < s.length() && s[cnt] == '#')
++cnt;
cout << "<h" << cnt << ">";
int pos = cnt;
while (pos < s.length() && s[pos] == ' ')
++pos;
cout << s.substr(pos);
cout << "</h" << cnt << ">" << endl;
} else if (s[0] == '*') {
cout << "<ul>" << endl;
while (arr[i][0] == '*') {
int pos = 1;
while (pos < arr[i].length() && arr[i][pos] == ' ')
++pos;
cout << "<li>" << arr[i].substr(pos) << "</li>" << endl;
++i;
}
i--;
cout << "</ul>" << endl;
} else if (s.empty()) {
continue;
} else {
if (op) {
cout << "<p>";
op = false;
}
cout << s;
if (!op && (i + 1 == n) || (arr[i + 1].empty())) {
op = true;
cout << "</p>";
}
cout << endl;
}
}
return 0;
}
- Строительство метро
описание проблемы
Город A имеет N Transportation Hubs, из которых № 1 и N очень важны. Чтобы укрепить транспортную мощность, город А решил построить метро между № 1 и № N Hubs.
Метро состоит из многих участков туннелей, и каждая секция туннеля подключена к двум транспортным центрам. После исследования существуют туннели M -сечения в качестве кандидатов. Между двумя транспортными центрами есть только один кандидат -туннель, и нет концов туннеля, соединяющего один и тот же транспортный центр.
Теперь существуют строительные компании n туннелей. Каждый туннель -кандидат может быть построен только одной компанией, а количество дней, необходимых для строительства каждой компании, одинаково. Каждая компания может построить только максимум кандидата. Все компании начинают строительство одновременно.
Как человек, отвечающий за проект, вы получаете информацию о туннеле -кандидате. Теперь вы можете выбрать часть туннеля для строительства в соответствии с вашими собственными идеями. Сколько дней вам нужно для строительства всего метро.
Входной формат
Вход первой линии содержит два целых числа N и M, которые разделены пространством, которое соответственно представляют количество транспортных центров и количество туннелей -кандидатов.
Строка от 2 до M+1, каждая строка содержит три целых числа A, B, C, указывает, что туннель может быть построен между концентратором A и Hub B, а необходимое время – C.
Выходной формат
Выведите целое число для создания минимального количества дней, необходимых для всей линии метро.
Вход пример
6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6
Образец вывода
6
Образец примера
Есть два типа линий, которые могут быть построены.
Первый поворот прохода составляет 1, 2, 3, 6, и необходимое время составляет 4, 4, 7, и вся линия метро должна быть завершена 7 дней;
Второй поворот прохода составляет 1, 4, 5, 6, и требуемое время составляет 2, 5, 6, а вся линия метро занимает 6 дней.
Количество дней, используемых во второй схеме, еще меньше.
Шкала и согласие случая оценки
Для 20%случаев оценки 1 ≤ n ≤ 10, 1 ≤ m ≤ 20;
Для 40%случаев оценки 1 ≤ n ≤ 100, 1 ≤ m ≤ 1000;
Для 60%случаев оценки 1 ≤ n ≤ 1000, 1 ≤ m ≤ 10000, 1 ≤ c ≤ 1000;
Для 80%случаев оценки 1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000;
Для 100%случаев оценки 1 ≤ n ≤ 100000, 1 ≤ m ≤ 200000, 1 ≤ a, b ≤ n, 1 ≤ c ≤ 1000000.
Все случаи оценки гарантируют, что концентратор № 1 может достичь всех других концентраторов через туннель, когда все кандидаты будут отремонтированы.
Код:
#include <iostream>
#include <cstring>
#define ac cin.tie(0); cin.sync_with_stdio(0);
using namespace std;
const int N = 100010, M = 400010;
int head[N], ver[M], edge[M], nxt[M], dist[N], q[N], cnt = 0;
int n, m;
void add(int a, int b, int c){
ver[++ cnt] = b;
edge[cnt] = c;
nxt[cnt] = head[a];
head[a] = cnt;
}
bool check(int mid){
memset(dist, 0x3f, sizeof(dist));
dist[1] = 0;
q[0] = 1;
int hh = 0, tt = 1;
while(hh != tt){
int cur = q[hh ++];
if(hh == N)
hh = 0;
for(int i = head[cur]; i; i = nxt[i]){
int u = ver[i];
if(edge[i] > mid)
continue;
if(dist[u] > dist[cur] + 1){
dist[u] = dist[cur] + 1;
q[tt ++] = u;
if(tt == N)
tt = 0;
}
}
}
return dist[n] != 0x3f3f3f3f;
}
int main(){
ac
int a, b, c;
cin >> n >> m;
while(m --){
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
int le = 0, ri = 1e6, mid;
while(le < ri){
mid = le + ri >> 1;
if(check(mid)) ri = mid;
else le = mid + 1;
}
cout << ri;
return 0;
}
- Дриммист в город
описание проблемы
MF City построен на плато. Поскольку единственный источник воды в городе находится в озере в долине реки, люди строили водопроводную трубу в форме сетки на склоне, чтобы перекачать озеро в город. Как показано ниже:
Эта трубная сеть состоит из узлов колонны N линии M (красный, на рисунке n = 5, M = 6), горизонтальной трубы (фиолетовой) и продольных труб (оранжевый).
Линии и столбцы представлены целым числом от 1 до N и 1 до M соответственно. Любой узел в первой строке может быть извлечен. Вода озера достигает любого узла в линии Ni, чтобы представить город.
За исключением первой линии и последней строки, должен быть трубопровод между двумя узлами соседнего или вертикального соседнего района. Каждый трубопровод имеет наибольшую скорость накачки, и необходимо выбрать накачку или воду в соответствии с ситуацией Анкет Для вертикальных трубопроводов (оранжевый) дайте воду сверху вниз или воду из нижнего направления; если вода может проходить от нижней части рисунка, количество воды, которая может проходить во время единицы, не может превышать максимум Скорость трубопровода; если нижнее направление находится от нижнего направления, поставляя воду выше, поскольку высота внизу высока, на итальянском языке может быть любое количество воды. Для горизонтальных труб (фиолетовых) вода может быть разрешена слева направо или справа влево, а вода не допускается. В обоих случаях количество воды, протекающей через единое время, не может превышать максимальную скорость трубопровода.
Теперь лицо, отвечающее за водоснабжение городов MF, хочет знать, что в случае временной пропускной способности каждого трубопровода озеро может быть введено в максимум за единицу времени на единицу города MF.
Входной формат
Из -за больших входных масштабов мы используем псевдо -Random Production для генерации данных.
Каждый набор данных содержит только 6 негативных целых чисел N, M, A, B, Q, x0. Среди них n и m, как упоминалось ранее, указывая на размер трубной сети, гарантированно 2 ≤ n, m ≤ 5000; гарантированно 1 ≤ a, b, q, x0 ≤ 109.
A, B, Q, x0 – сгенерированные данные параметры. Мы определяем квоту {xi} следующими способами:
Xi+1 = ( AXi + B) mod Q, (i ≥ 0)
Мы используем первый элемент числа для (n-1) m в качестве единичной пропускной способности продольного трубопровода. Пропускная способность Ti-Column Pipeline Unit; (N-1) M+1 из столбца номера (N-1 ) m+(n-2) (m-1) (то есть следующий (n-2) (M-1) элемент) в качестве единичной временной емкости горизонтального трубопровода, из которых x (n-1) m+( S-2) (M-1) +T представляет узел линии S. +1.
Выходной формат
Выводит линию целого числа, что указывает на количество воды, которая может быть введена на единицу города MF.
Обратите внимание, что некоторые параметры в процессе расчета могут превышать максимальное значение 32 -битного целочисленного представления, пожалуйста, обратите внимание на использование 64 -бит целочисленного хранилища соответствующих данных.
Вход пример
3 3 10 3 19 7
Образец вывода
38
Образец примера
Используйте параметры, чтобы получить число {xi} = {7, 16, 11, 18, 12, 9, 17, 17, 4, …}. Согласно входному формату, вы можете получить максимальный водяной насос каждого Конвейер, как показано на рисунке ниже:
В стандартном ответе время единицы может быть направлено на 38 единиц. Все продольные трубки могут быть перекачены вниз. Нет необходимости качать воду или ставить воду вверх.
Вход пример
2 5 595829232 749238243 603779819 532737791
Образец вывода
1029036148
Вход пример
5 2 634932890 335818535 550589587 977780683
Образец вывода
192923706
Вход пример
5 5 695192542 779962396 647834146 157661239
Образец вывода
1449991168