Всем привет! Давно не было разборов, поэтому сегодня я решил сделать разбор на сегодняшний div2 контест. Всем приятного просмотра, а если возникнут вопросы, смело смотрите код решения. Постараюсь объяснить максимально понятно, ну от вас жду лайка.
Полное решение:
Дается число n, нужно узнать мин кол-во кусочков, которое наш гг съест. Заметим, что мы всегда можем делать что-то по типу: 1 1 n-2, пока (n-2>=3). Из этого можно вывести формулу: floor((n-1)/2)
Сложность: O(1)
P/S: Вы конечно можете попробовать симуляцией, но боюсь по времени это не зайдет.
#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> par(2e5+100);
const ll MOD = 1e9+7;
vector<ll> dep(200001);
ll cur;
vector<pair<ll,ll>> ans;
ll bp(ll a, ll b, ll MOD){
ll res = 1;
while (b){
if(b%2==1){
res = res%MOD*a%MOD;
}
a = a%MOD*a%MOD;
b>>=1;
}
return res;
}
struct nig{
ll l;
ll r;
ll sum;
};
ll ask(ll a, ll b){
cout << a << " " << b << endl;
ll x; cin >> x;
return x;
}
vector<ll> d = {0,-1,1,0};
vector<ll> dd = {1,0,0,-1};
void dfs(ll x, ll y, vector<vector<bool>> &vis, ll n, ll m, vector<vector<char>> &a, ll &k){
vis[x][y] = 1;
for (ll i = 0;i<4;i++){
ll nx = x+d[i];
ll ny = y+dd[i];
if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny] && a[nx][ny]=='.'){
dfs(nx,ny, vis, n,m,a,k);
}
}
if(k>0){
a[x][y] = 'X';
k--;
}
}
void bruh() {
// 1 1 6
// 1 1 4
// 1 1 2
// 1 1 1
ll n; cin >> n;
ll cnt = 0;
cout << (n-1)/2 << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//build_spf();
ll t; cin >> t;
while (t--){
// dep.clear();
//// cur = 0; par.clear();
// ans.clear();
bruh();
}
}
Полное решение:
Давайте рассмотрим решение-симуляцию. Какой для нас худший случай? Это когда все буквы в строке равны ‘A’. В таком случае у нас будет что то вроде O(1e9*n*q), что ясно не зайдет.
Вместо этого для этого случая мы можем вывести формулу: floor(N/len(s))+(N%len(s)).
Иначе можем просто просимулировать, потому если в строке есть хотя бы одна ‘B’, то симуляция займет log2(x) в худшем случае.
Сложность: O(n*log2(x)), на запрос.
#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> par(2e5+100);
const ll MOD = 1e9+7;
vector<ll> dep(200001);
ll cur;
vector<pair<ll,ll>> ans;
ll bp(ll a, ll b, ll MOD){
ll res = 1;
while (b){
if(b%2==1){
res = res%MOD*a%MOD;
}
a = a%MOD*a%MOD;
b>>=1;
}
return res;
}
struct nig{
ll l;
ll r;
ll sum;
};
ll ask(ll a, ll b){
cout << a << " " << b << endl;
ll x; cin >> x;
return x;
}
vector<ll> d = {0,-1,1,0};
vector<ll> dd = {1,0,0,-1};
void dfs(ll x, ll y, vector<vector<bool>> &vis, ll n, ll m, vector<vector<char>> &a, ll &k){
vis[x][y] = 1;
for (ll i = 0;i<4;i++){
ll nx = x+d[i];
ll ny = y+dd[i];
if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny] && a[nx][ny]=='.'){
dfs(nx,ny, vis, n,m,a,k);
}
}
if(k>0){
a[x][y] = 'X';
k--;
}
}
void bruh() {
ll n,q; cin >> n >> q;
string s; cin >> s;
vector<ll> a(q);
//
bool check = 0;
for (ll &x: a) cin >> x;
for (char x: s){
if(x=='B'){
check = 1;
}
}
for (ll i = 0;i<q;i++){
ll x = a[i];
ll pos = 0;
ll cnt = 0;
if(check){
while (x!=0){
cnt++;
if(s[pos%n]=='B'){
x = x/2;
}else{
x--;
}
pos++;
}}else{
cnt = (x/n)*n+x%n;
}
cout << cnt << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//build_spf();
ll t; cin >> t;
while (t--){
// dep.clear();
//// cur = 0; par.clear();
// ans.clear();
bruh();
}
}
Полное решение:
Оптимально сперва рассмотреть операцию “Разделить”, т.к она бесконечна. В каком случае x, подойдет для нашего y, в качестве данной операции?
Мы можем сделать что-то вроде n, x’ x’+(n%x) x’*2, однако данная стратегия не зайдет для чисел <x*4. Поэтому предположим, что любое число, что больше или равно нашему x*4, мы сможем разделить.
Теперь осталось лишь найти кол-во чисел <x*4, не считая чисел которые уже нам подходят, проверить сможем ли мы покрыть их к операциями. Так делаем для каждого x, от 1 до n.
Выведем максимальный ответ, как максимум из всех возможных вариантов.
Сложность: O(n) или O(nlogn) в зависимости от имплементации.
#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> par(2e5+100);
const ll MOD = 1e9+7;
vector<ll> dep(200001);
ll cur;
vector<pair<ll,ll>> ans;
ll bp(ll a, ll b, ll MOD){
ll res = 1;
while (b){
if(b%2==1){
res = res%MOD*a%MOD;
}
a = a%MOD*a%MOD;
b>>=1;
}
return res;
}
struct nig{
ll l;
ll r;
ll sum;
};
ll ask(ll a, ll b){
cout << a << " " << b << endl;
ll x; cin >> x;
return x;
}
vector<ll> d = {0,-1,1,0};
vector<ll> dd = {1,0,0,-1};
void dfs(ll x, ll y, vector<vector<bool>> &vis, ll n, ll m, vector<vector<char>> &a, ll &k){
vis[x][y] = 1;
for (ll i = 0;i<4;i++){
ll nx = x+d[i];
ll ny = y+dd[i];
if(nx>=0 && nx<n && ny>=0 && ny<m && !vis[nx][ny] && a[nx][ny]=='.'){
dfs(nx,ny, vis, n,m,a,k);
}
}
if(k>0){
a[x][y] = 'X';
k--;
}
}
bool opt(ll x, ll g){
ll a1 = g;
ll a2 = a1+x%g;
ll a3 = x-(a1+a2);
return(a3%g==0 && a3>=a2);
}
bool check(vector<ll> a, ll mid, ll k){
ll n = a.size();
ll cnt = 0;
for (ll i = 0;i<n;i++){
if(a[i]%mid==0 || opt(a[i],mid)){
}else{
cnt++;
}
}
return cnt<=k;
}
void bruh() {
/// cout << opt(9, 2) << endl;
//17 (4) = 4, 5, 8
ll n,k; cin >> n >> k;
vector<ll> a(n);
for (ll &x: a) cin >> x;
sort(all(a));
// for (ll x: a){
// cout << x << " ";
// }cout << endl;
map<ll,ll> mp;
for (ll x: a){
mp[x]++;
}
vector<ll> s(n+1);
for (ll i = 1;i<=n;i++){
s[i] = s[i-1]+mp[i];
}
ll mx = 1;
for (ll i = 1;i<=n;i++){
ll opt1 = s[min(n,i*4-1)];
ll opt2 = mp[i];
opt2+=(i*2<=n? mp[i*2]: 0);
opt2+=(i*3<=n? mp[i*3]: 0);
if(opt1-opt2<=k){
mx = max(mx,i);
}
}
cout << mx << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
//build_spf();
ll t; cin >> t;
while (t--){
// dep.clear();
//// cur = 0; par.clear();
// ans.clear();
bruh();
}
}
