677A - Vanya and Fence
Для каждого друга смотрим, будет ли его высота больше h. Если да, то его ширина — 2, иначе — 1.
Complexity O(n).
Code#include <iostream>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x;
int main()
{
cin >> n >> h;
ans = n;
for (i = 0; i < n; i++)
{
cin >> x;
ans += (x>h);
}
cout << ans << endl;
return 0;
}
677B - Vanya and Food Processor
Решение, которое просто делает то, что описано в условии, не пройдет, т.к. если высота каждой картофелины будет 109, а скорость измельчения — 1, то на каждую картофелину будем тратить 109 операций.
С каждой новой картофелиной высотой ai будем измельчать картофель до высоты ai MOD k, тогда мы будем тратить на это a[i] / k секунд. Если мы не можем засунуть после этого новую картофелину, то мы потратим еще 1 секунду, иначе просто положим эту картофелину. Мы получим такой же ответ, как бы если мы делали то, что описано в условии.
Асимптотика O(n).
Code#include <iostream>
#include <stdio.h>
using namespace std;
typedef long long ll;
ll i,n,h,ans,x,cur_h,k;
int main()
{
cin >> n >> h >> k;
ans = 0;
cur_h = 0;
for (i = 0; i < n; i++)
{
scanf("%I64d", &x);
if (cur_h + x <= h)
cur_h += x;
else
ans++, cur_h = x;
ans += cur_h/k;
cur_h %= k;
}
ans += cur_h/k;
cur_h %= k;
ans += (cur_h>0);
cout << ans << endl;
return 0;
}
677C - Vanya and Label
Переведем слово в 2-ичную систему счисления, это сделать легко, так как 64 — степень двойки. Проходимся по битах этого числа: если бит равен 0, то у нас может быть 3 различных варианта этого бита в нашей паре слов: 0&1, 1&0, 0&0, иначе только один вариант: 1&1. В таком случае результатом будет 3nullbits, где nullbits — количество нулевых битов.
Асимптотика O(|s| * 6).
Code#include <iostream>
#include <stdio.h>
#include <string>
#define MOD 1000000007
using namespace std;
typedef long long ll;
ll i,j,n,h,ans,x,cur_h,k;
string s;
string pattern;
ll symbol_val[305];
int main()
{
cin >> s;
for (char i = '0'; i <= '9'; i++)
pattern.push_back(i);
for (char i = 'A'; i <= 'Z'; i++)
pattern.push_back(i);
for (char i = 'a'; i <= 'z'; i++)
pattern.push_back(i);
pattern.push_back('-');
pattern.push_back('_');
for (i = 0; i < 64; i++)
symbol_val[pattern[i]] = i;
ll ans = 1;
for (i = 0; i < s.size(); i++)
{
ll x = symbol_val[s[i]];
for (j = 0; j < 6; j++)
if ((x&(1<<j)) == 0)
ans = (ans*3)%MOD;
}
cout << ans << endl;
return 0;
}
677D - Vanya and Treasure
Сделаем динамику dp[col][row], где dp[col][row] — минимальное время, которое нужно для того, чтобы открыть сундук в клетке (col, row). Для клеток цвета 1 dp[x][y] = x + y. Для каждого следующего цвета color будем перебирать все клетки цвета color - 1 и все клетки цвета color, тогда для каждой клетки цвета color с координатами (x1, y1) и клетки цвета color - 1 с координатами (x2, y2) dp[x1][y1] = dp[x2][y2] + abs(x1 - x2) + abs(y1 - y2).
Но этого решения будет недостаточно, так как его асимптотика — O(n2 * m2)
Можем сделать такое улучшение: пусть cnt[x] — количество клеток цвета x, тогда когда cnt[color] * cnt[color - 1] ≥ n * m, можно сделать поиск в ширину от клеток цвета color - 1 к клеткам цвета color.
В таком случае будет асимптотика O(n * m * sqrt(n * m)).
Code#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#define MOD 1000000007
#define N 2005
#define mp make_pair
#define X first
#define Y second
using namespace std;
typedef int ll;
ll i,j,n,h,x,y,cur_h,k,m,p,fx,fy;
ll a[505][505], dp[505][505], d[505][505];
ll dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
vector<pair<ll,ll> > g[250505];
vector<pair<ll, pair<ll,ll> > > lst, bfs;
ll Abs(ll x)
{
return x>0?x:-x;
}
ll find_dist(ll x1, ll y1, ll x2, ll y2)
{
return Abs(x1-x2) + Abs(y1-y2);
}
bool in_range(ll x, ll y)
{
return (x >= 0 && x < y);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin >> n >> m >> p;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
dp[i][j] = (ll)1e+9;
for (i = 0; i < n; i++)
for (j = 0; j < m; j++)
{
scanf("%d", &a[i][j]);
g[a[i][j]].push_back(mp(i,j));
if (a[i][j] == 1)
dp[i][j] = i+j;
if (a[i][j] == p)
fx = i, fy = j;
}
for (i = 2; i <= p; i++)
{
ll cur_size = g[i].size();
ll last_size = g[i-1].size();
if (cur_size*last_size <= n*m)
{
for (j = 0; j < cur_size; j++)
{
ll cur_x = g[i][j].X;
ll cur_y = g[i][j].Y;
for (k = 0; k < last_size; k++)
{
ll last_x = g[i-1][k].X;
ll last_y = g[i-1][k].Y;
dp[cur_x][cur_y] = min(dp[cur_x][cur_y], dp[last_x][last_y] + find_dist(cur_x,cur_y,last_x,last_y));
}
}
} else
{
for (k = 0; k < n; k++)
for (j = 0; j < m; j++)
d[k][j] = -1;
bfs.clear();
lst.clear();
for (j = 0; j < last_size; j++)
{
ll last_x = g[i-1][j].X;
ll last_y = g[i-1][j].Y;
lst.push_back(mp(dp[last_x][last_y], mp(last_x, last_y)));
}
sort(lst.begin(), lst.end());
ll pointer = 1;
j = 0;
bfs.push_back(lst[0]);
d[lst[0].Y.X][lst[0].Y.Y] = lst[0].X;
while (j < bfs.size())
{
ll x = bfs[j].Y.X;
ll y = bfs[j].Y.Y;
ll val = bfs[j].X;
j++;
while (pointer < lst.size() && lst[pointer].X <= val)
bfs.push_back(lst[pointer++]);
for (k = 0; k < 4; k++)
if (in_range(x+dir[k][0], n) && in_range(y+dir[k][1], m) && d[x+dir[k][0]][y+dir[k][1]] == -1)
{
d[x+dir[k][0]][y+dir[k][1]] = val+1;
bfs.push_back(mp(val+1, mp(x+dir[k][0], y+dir[k][1])));
}
}
for (j = 0; j < cur_size; j++)
{
ll cur_x = g[i][j].X;
ll cur_y = g[i][j].Y;
dp[cur_x][cur_y] = d[cur_x][cur_y];
}
}
}
cout << dp[fx][fy] << endl;
return 0;
}
677E - Vanya and Balloons
Для каждой клетки (x, y) в таблице возьмем максимально возможный крест, в котором не присутствуют нули. Чтобы сделать это быстро, сохраним массивы частичных сумм для всех возможных 8 направлений, где каждая клетка будет обозначать количество ненулевых шариков в каждом из направлений. Например для того, чтобы узнать, сколько ненулевых шариков находится справа от клетки (x, y), создадим массив p[x][y], в котором p[x][y] = p[x][y - 1] + 1 если a[x][y]! = 0 иначе p[x][y] = 0
Таким образом для каждой клетки (x, y) мы можем найти крест максимального размера, в котором не будет нулей.
Мы можем сравнить значения произведений для крестов в координатах (x, y) и с радиусом r, воспользовавшись логарифмированием. К примеру, если нам нужно сравнить кресты с значениями x1 * x2 * ... * xn и y1 * y2 * ... * ym, мы можем сравнить log(x1 * x2 * ... * xn) и log(y1 * y2 * ... * yn), что будет эквивалентно сравнению log(x1) + log(x2) + ... + log(xn) и log(y1) + log(y2) + ... + log(ym).
Таким образом для нахождения значения log(x1) + log(x2) + ... + log(xn) для каждого креста мы можем аналогично хранить массивы частичных сумм для каждого с направлений и для каждой клетки (x, y) искать максимальное значение креста с центром в ней за O(1).
Итоговая асимптотика O(n2).
Code#include <iostream>
#include <stdio.h>
#include <string>
#include <cmath>
#define MOD 1000000007
#define N 2005
using namespace std;
typedef unsigned int ll;
ll i,j,n,h,x,y,cur_h,k,dir;
ll pre[8][N][N];
double sums[8][N][N],ans,logs[N][N],lg2,lg3;
ll ansx,ansy,anssize,ansdir;
ll total;
ll directions[8][2] = {{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{0,1},{-1,0},{0,-1}};
char a[N][N];
bool in_range(ll x)
{
return (x >= 0 && x < n);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
lg2 = log(2);
lg3 = log(3);
cin >> n;
for (i = 0; i < n; i++)
scanf("%s",a[i]);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (a[i][j] == '3')
logs[i][j] = lg3;
else if (a[i][j] == '2')
logs[i][j] = lg2;
for (dir = 0; dir < 8; dir++)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (!in_range(i-directions[dir][0]) || !in_range(j-directions[dir][1]))
{
k = 0;
ll d1 = directions[dir][0], d2 = directions[dir][1];
for (x = i, y = j; in_range(x) && in_range(y); x += d1, y += d2)
{
if (a[x][y] != '0')
{
k++;
if (x == i && y == j)
sums[dir][x][y] = logs[i][j];
else
sums[dir][x][y] = sums[dir][x-d1][y-d2] + logs[x][y];
}
else
{
sums[dir][x][y] = 0;
k = 0;
}
pre[dir][x][y] = k;
}
}
}
ans = -1;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (a[i][j] != '0')
{
ll tmp = n+5;
for (k = 0; k < 4; k++)
tmp = min(tmp, pre[k][i][j]);
double val = logs[i][j];
for (k = 0; k < 4; k++)
val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j];
if (val > ans)
{
ans = val;
ansx = i;
ansy = j;
anssize = tmp;
ansdir = 0;
}
tmp = n+5;
for (k = 4; k < 8; k++)
tmp = min(tmp, pre[k][i][j]);
val = logs[i][j];
for (k = 4; k < 8; k++)
val += sums[k][i+directions[k][0]*(tmp-1)][j+directions[k][1]*(tmp-1)] - sums[k][i][j];
if (val > ans)
{
ans = val;
ansx = i;
ansy = j;
anssize = tmp;
ansdir = 4;
}
}
total = a[ansx][ansy]-'0';
for (k = ansdir; k < ansdir+4; k++)
{
for (i = 1; i < anssize; i++)
total = (total*(a[ansx+directions[k][0]*i][ansy+directions[k][1]*i]-'0'))%MOD;
}
cout << total << endl;
return 0;
}