Всем привет! Сегодня раунд получился довольно интересным, поэтому я решил сделать разбор на задачи A–D1. P>S Если вам не понятны какие то части разбора, то смело смотрите код).
Полное решение:
Пусть f(x) — количество вхождений числа x в массив. При построении последовательности мы всегда ограничены минимальным f(x) среди выбранных элементов.
Если взять элемент с частотой f(x), то длина последовательности может увеличиться:
mx = max(mx, f(x) * cnt),
где cnt — количество уже добавленных элементов, включая текущий.
Так последовательно обновляем ответ и выводим mx.
Алгоритм:
- Посчитать частоты
f(x)для всех чисел. - Отсортировать или перебрать их по убыванию.
- На каждом шаге обновлять
mx. - Вывести максимальный результат.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll st = 0;
map<ll,ll> mp;
ll cnt = 0;
ll n; cin >> n;
vector<ll> a(n);
for (ll &x: a){
cin >> x;
mp[x]++;
}
vector<pair<ll,ll>> ans;
map<ll,ll> mpp;
for (ll x: a){
mpp[x]++;
if(mpp[x]==1){
ans.pb({mp[x],x});
}
}
sort(allr(ans));
ll sm = 0;
for (ll i = 0;i<ans.size();i++){
// cout << ans[i].f << endl;
sm = max(sm,ans[i].f*(i+1));
}
cout << sm << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Полное решение:
Ответ невозможен, если хотя бы один элемент от 1 до m отсутствует во всех множествах.
Теперь рассмотрим множества, где для каждого элемента количество вхождений ≥ 2 (включая учёт подмножеств). Пусть таких множеств cnt.
Если cnt ≥ 2, то мы всегда можем построить как минимум три разные конфигурации:
- взять всё множество +
sx, - взять всё множество +
sy, - взять всё множество +
sx + sy.
Значит, в этом случае решение существует.
Алгоритм:
- Проверить, что все элементы от
1доmвстречаются. - Посчитать
cnt— число множеств, удовлетворяющих условию. - Если
cnt ≥ 2, вывести "YES", иначе "NO".
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll a,b; cin >> a >> b;
ll cnt = 0;
map<ll,ll> mp;
map<ll,ll> mpp;
vector<vector<ll>> ak(a);
for (ll i = 0;i<a;i++){
ll x; cin >> x;
ak[i].resize(x);
// map<ll,ll> mpp;
for (ll j = 0;j<x;j++){
ll op; cin >> op;
ak[i][j] = op;
mpp[op]++;
}
}
// ll cnt = 0;
for (ll i = 0;i<a;i++){
bool check = 1;
for (ll j = 0;j<ak[i].size();j++){
if(mpp[ak[i][j]]==1){
check = 0;
break;
}
}
if(check){
cnt++;
}
}
bool opt = 1;
for (ll i = 1;i<=b;i++){
if(mpp[i]==0){
opt = 0;
break;
}
}
if(!opt){
cout << "NO" << endl;
}else{
cout << (cnt>=2 ?"YES": "NO") << endl;
}}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Полное решение:
Разберём, как работает бинарный поиск:
- если
a[m] == i→ элемент найден; - если
a[m] > i→ двигаем правую границу; - если
a[m] < i→ двигаем левую границу.
Чтобы x был найден, элементы слева должны быть меньше него, а справа — больше.
Значит:
- если
s[i] == '1', можно поставитьans[i] = i; - если
s[i] == '0', то нужно поставитьans[i] ≠ i, сохранив корректность.
Простейшее решение — перестановка [2, 3, ..., n, 1]. Она гарантирует, что для всех позиций с 0 элемент отличается от индекса. Естественно не стоит забывать про s[i]=='1', тогда ставим ans[i] = i.
Особый случай: если встречается символ 0, окружённый единицами (...101...), то условие нарушается: элементу придётся соответствовать позиции, но это запрещено. Тогда ответ невозможен.
Алгоритм:
- Проверить строку на наличие "невозможного" шаблона.
- Если он найден → вывести "NO".
- Иначе построить перестановку
[2, 3, ..., n, 1]. - Вывести её как ответ.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll n; cin >> n;
string s; cin >> s;
vector<ll> a(n);
for (ll i = 0;i<n;i++){
if(s[i]=='1'){
a[i] =(i+1);
}
}
bool opt = 1;
map<ll,ll> mp;
vector<ll> temp(n);
for (ll i = 0;i<n;i++){
if(s[i]=='0'){
}else{
temp[i] = i+1;
mp[i+1]++;
}
}
ll i = 0;
while (i<n){
if(s[i]=='1'){
i++;
continue;
}
ll j = i;
ll op = j;
while (j<n && s[j]=='0'){
j++;
}
if(j-i==1){
opt = 0;
break;
}
for (ll k = i;k<j-1;k++){
temp[k] = k+2;
}
temp[j-1] = i+1;
i = j;
}
if(!opt){
cout << "NO" << endl;
}else{
cout << "YES" << endl;
for (ll x: temp){
cout << x << " ";
}cout << endl;}
//cout << opt << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Полное решение:
Нужно максимизировать
Σ (ai OR bi).
Пусть у нас есть перестановка p. Несложно заметить, что чтобы сделать сумму максимальной, выгодно каждому числу поставить его битовую инверсию.
Почему?
- Инверсия по битам гарантирует, что при
ORполучится максимальное количество единиц. - Это работает для любого числа в диапазоне.
Пример:
x = 9 (1001₂), инверсия = 6 (0110₂).
9 OR 6 = 1111₂ = 15.
Значит, при такой паре значение OR максимально возможное. Стоит отметить, что если r == 0, то это не сработает, а значит нужно просто вывести 0 и 0, как ответ.
Алгоритм:
- Идём по всем числам от
nдо1. - Для каждого числа
xсчитаем его инверсию (по длине битовn). - Сохраняем в
mp[x]. - Формируем перестановку:
ans[i] = mp[i]
- Считаем итоговую сумму и выводим её вместе с перестановкой.
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
using namespace std;
//vector<ll> vis;void
void bruh(){
ll a,b; cin >> a >> b;
if(b==0){
cout << 0 << endl;
cout << "0" << endl;
}else{
vector<ll> temp(b+1);
map<ll,ll> mp;
for (ll i = b;i>=0;i--){
ll k = 32-__builtin_clz(i);
ll mask = (1<<k)-1;
ll opt = (~i)&mask;
if(mp[i]==0 && mp[opt]==0){
mp[i] = opt;
mp[opt] = i;
}
// cout << opt << endl;
}
for (ll i = 0;i<=b;i++){
temp[i] = mp[i];
}
ll sum = 0;
vector<ll> ans(b+1);
for (ll i = 0;i<=b;i++){
ans[i] = i;
}
for (ll i = 0;i<=b;i++){
sum+=temp[i]|ans[i];
}
cout << sum << endl;
for (ll x: temp){
cout << x << " ";
}cout << endl;}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
ll t; cin >> t;
// cout << dp[3][2] << endl;
// for (ll i = 1;)
while (t--){
bruh();
}
}
Автокомментарий: текст был обновлен пользователем Goddless (предыдущая версия, новая версия, сравнить).