problem1 link
从大到小贪心，较大的数字应该放置在较浅的位置。
problem2 link
最后的位置要么都是整数（经过偶数次变换），要么是$(p.5, q.5)$这种位置（奇数次变换）。
先假设是偶数次变换。那么可以从最终的点向前枚举变换的次数，可以发现，每两次变换相等于向外扩展一圈。假设向外扩展了$k$圈（经过$2k$步变换）,那么如果每个最终的点向外扩展$k$圈后，由于这些正方形相交导致出现了一个新的正方形（这个正方形边长也是$2k$），那么就出现了错误（因为这将导致最后的答案多了一个点）。所以答案是最大的不导致出现错误的值。
如果答案是奇数，那么可以先看答案是1的时候是否可以。然后就变成跟答案是偶数类似的问题。
problem3 link
首先，这个可以看做一个无向图，给每个节点赋一个值，边的权值为两个顶点权值乘积。最后使得所有边权值和最大。
最后肯定是一些节点的值是最小值，一些是最大值，剩下的是中间值。
假设是中间值的顶点集合是$S$。如果$S$中存在两个节点$u,v$，它们之间没有边相连，设它们现在的权值为$p_{u},p_{v}$，与它们相连的点的权值和分别为$w_{u},w_{v}$。设$w_{u} ge w_{v}$.令$x=min(upper[u]-p_{u},p[v]-lower[v])$,那么将$u$的权值设为$p_{u}+x$,$v$的权值设为$p_{v}-x$，这样所有节点总的权值不变，但是最后的答案不会变小。但是这样的结果是又多了一个节点是最大值或者最小值。所以，按照这个思路一直做下去，那么最后$S$中的节点一定是两两相连的。
设$|S|=k$，其中的节点为$x_{1},x_{2},...,x_{k}$，$S$外与$x_{i}$相连的节点总和为$a_{i}$,$S$中所有点的权值和为$m$.那么$S$中与$x_{i}$相连的点的总权值为$m-x_{i}$。所以最后$S$中的点对答案的贡献为$sum_{i=1}^{k}x_{i}(a_{i}+frac{m-x_{i}}{2})$.除以2是因为出现了重复计算。
假设现在为$k$个点随机赋一个值为$x_{1},x_{2},...,x_{k}$。
考虑其中的两个点$x_{i},x_{j}$,令$T=x_{i}+x_{j}$,那么如果$x_{i}+x_{j}$是个定值的话，下面看$x_{i},x_{j}$分别取什么值时答案是最大值。这两个节点对答案的贡献为
$x_{i}x_{j}+x_{i}(m-T+a_{i})+x_{j}(m-T+a_{j})$
=$x_{i}x_{j}+x_{i}(m-T+a_{i})+(T-x_{i})(m-T+a_{j})$
=$-x_{i}^{2}+(a_{i}-a_{j}+T)x_{i}+T(m-T+a_{j})$
所以当$x_{i}=frac{a_{i}-a_{j}+T}{2},x_{j}=frac{a_{j}-a_{i}+T}{2}$时值最大。
此时有$x_{i}-a_{i}=x_{j}-a_{j}=frac{-a_{i}-a_{j}+T}{2}$
从两个推广到$k$个，所以存在一个常数$c$，使得对于所有的$i$，满足$x_{i}-a_{i}=c$,由于$sum_{i=1}^{k}x_{i}=m$，所以$c=frac{m-sum_{i=1}^{k}a_{i}}{k}$，所以$x_{t}=a_{t}+frac{m-sum_{i=1}^{k}a_{i}}{k}$
code for problem1
#include <vector>
#include <algorithm>
class TomekPhone {
public:
int minKeystrokes(std::vector<int> frequencies, std::vector<int> keySizes) {
int total = 0;
for (auto x : keySizes) {
total += x;
}
int N = static_cast<int>(frequencies.size());
if (total < N) {
return -1;
}
int M = static_cast<int>(keySizes.size());
int result = 0;
std::sort(frequencies.begin(), frequencies.end());
std::vector<int> added(M, 0);
int idx = 0;
for (int i = N - 1; i >= 0; --i) {
result += (added[idx] + 1) * frequencies[i];
if (i == 0) {
break;
}
added[idx] += 1;
idx = (idx + 1) % M;
while (idx < M && added[idx] >= keySizes[idx]) {
idx = (idx + 1) % M;
}
}
return result;
}
};
int main() {}
code for problem2
#include <memory.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <set>
#include <vector>
const int MAX = 427;
int g[MAX][MAX];
class DrawingPointsDivOne {
public:
int maxSteps(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
return -1;
}
auto EvenCheck = [&](const Range &range, int radius) -> bool {
int num = 0;
for (int x = range.min_x; x <= range.max_x; ++x) {
for (int y = range.min_y; y <= range.max_y; ++y) {
if (RangeCheck(x - radius, y - radius, x + radius, y + radius)) {
++num;
}
}
}
return num == static_cast<int>(x.size());
};
return std::max(CheckOld(x, y), CheckEven(x, y, EvenCheck));
}
private:
struct Range {
int min_x;
int max_x;
int min_y;
int max_y;
Range() { Initialize(); }
void Initialize() {
min_x = min_y = std::numeric_limits<int>::max();
max_x = max_y = std::numeric_limits<int>::min();
}
void Update(int x, int y) {
min_x = std::min(min_x, x);
max_x = std::max(max_x, x);
min_y = std::min(min_y, y);
max_y = std::max(max_y, y);
}
void Move(int detx, int dety) {
min_x += detx;
max_x += detx;
min_y += dety;
max_y += dety;
}
};
int Get(int x, int y) {
if (x < 0 || y < 0) {
return 0;
}
return g[x][y];
}
bool RangeCheck(int x1, int y1, int x2, int y2) {
return Get(x2, y2) - Get(x2, y1 - 1) - Get(x1 - 1, y2) +
Get(x1 - 1, y1 - 1) ==
(x2 - x1 + 1) * (y2 - y1 + 1);
}
int CheckOld(const std::vector<int> &x, const std::vector<int> &y) {
const int N = static_cast<int>(x.size());
std::set<std::pair<int, int>> points;
for (int i = 0; i < N; ++i) {
points.insert({x[i], y[i]});
points.insert({x[i] + 1, y[i]});
points.insert({x[i], y[i] + 1});
points.insert({x[i] + 1, y[i] + 1});
}
auto Contains = [&](int x, int y) {
return points.find({x, y}) != points.end();
};
auto Check = [&Contains](int x, int y) {
return Contains(x, y) && Contains(x + 1, y) && Contains(x, y + 1) &&
Contains(x + 1, y + 1);
};
int num = 0;
for (auto element : points) {
if (Check(element.first, element.second)) {
++num;
}
}
if (num != N) {
return 0;
}
std::vector<int> px, py;
for (auto element : points) {
px.push_back(element.first);
py.push_back(element.second);
}
auto OldCheck = [&](const Range &range, int radius) -> bool {
int num = 0;
int dx[] = {0, 1, 0, 1};
int dy[] = {0, 0, 1, 1};
for (int x = range.min_x; x <= range.max_x; ++x) {
for (int y = range.min_y; y <= range.max_y; ++y) {
bool tag = true;
for (int k = 0; k < 4; ++k) {
if (!RangeCheck(x + dx[k] - radius, y + dy[k] - radius,
x + dx[k] + radius, y + dy[k] + radius)) {
tag = false;
break;
}
}
if (tag) {
++num;
}
}
}
return num == N;
};
int even_result = CheckEven(px, py, OldCheck);
if (even_result == -1) {
return -1;
}
return even_result + 1;
}
int CheckEven(const std::vector<int> &x, const std::vector<int> &y,
std::function<bool(const Range &, int)> Check) {
Range search_range;
for (size_t i = 0; i < x.size(); ++i) {
search_range.Update(x[i], y[i]);
}
const int MAX_EXTEND = 141;
int low = 0, high = MAX_EXTEND + 1;
int result = 0;
while (low <= high) {
int radius = (low + high) >> 1;
memset(g, 0, sizeof(g));
Range range;
for (size_t i = 0; i < x.size(); ++i) {
range.Update(x[i] - radius, y[i] - radius);
range.Update(x[i] + radius, y[i] + radius);
}
int detx = -range.min_x;
int dety = -range.min_y;
range.Move(detx, dety);
search_range.Move(detx, dety);
for (size_t i = 0; i < x.size(); ++i) {
Update(x[i] - radius + detx, y[i] - radius + dety, x[i] + radius + detx,
y[i] + radius + dety);
}
Initialize();
if (Check(search_range, radius)) {
result = std::max(result, radius * 2);
low = radius + 1;
} else {
high = radius - 1;
}
search_range.Move(-detx, -dety);
}
if (result == (MAX_EXTEND + 1) * 2) {
return -1;
}
return result;
}
void Update(int x1, int y1, int x2, int y2) {
g[x1][y1] += 1;
g[x1][y2 + 1] -= 1;
g[x2 + 1][y1] -= 1;
g[x2 + 1][y2 + 1] += 1;
}
void Initialize() {
for (int i = 1; i < MAX; ++i) {
g[0][i] += g[0][i - 1];
g[i][0] += g[i - 1][0];
}
for (int i = 1; i < MAX; ++i) {
for (int j = 1; j < MAX; ++j) {
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
}
}
if (g[0][0] != 0) {
g[0][0] = 1;
}
for (int i = 1; i < MAX; ++i) {
if (g[0][i] != 0) {
g[0][i] = 1;
}
if (g[i][0] != 0) {
g[i][0] = 1;
}
g[0][i] += g[0][i - 1];
g[i][0] += g[i - 1][0];
}
for (int i = 1; i < MAX; ++i) {
for (int j = 1; j < MAX; ++j) {
if (g[i][j] != 0) {
g[i][j] = 1;
}
g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
}
}
}
};
code for problem3
#include <string>
#include <vector>
class BoundedOptimization {
public:
double maxValue(std::vector<std::string> expr, std::vector<int> lowerBound,
std::vector<int> upperBound, int maxSum) {
n = static_cast<int>(lowerBound.size());
Initialize(expr);
int max_mask = 1;
for (int i = 0; i < n; ++i) {
max_mask *= 3;
}
double result = 0.0;
for (int mask = 0; mask < max_mask; ++mask) {
std::vector<int> lower, upper, middle;
Split(lower, upper, middle, mask);
if (!CheckClique(middle)) {
continue;
}
std::vector<double> value(n, 0.0);
int m = maxSum;
for (auto x : lower) {
value[x] = lowerBound[x];
m -= lowerBound[x];
}
for (auto x : upper) {
value[x] = upperBound[x];
m -= upperBound[x];
}
if (m >= 0 &&
ComputeMiddleValue(lowerBound, upperBound, middle, m, value)) {
double current_result = 0.0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
current_result += graph[i][j] * value[i] * value[j];
}
}
result = std::max(result, current_result);
}
}
return result;
}
private:
bool ComputeMiddleValue(const std::vector<int> &lowerBound,
const std::vector<int> &upperBound,
const std::vector<int> &middle, int m,
std::vector<double> &value) {
if (middle.empty()) {
return true;
}
int k = static_cast<int>(middle.size());
std::vector<double> a(k, 0.0);
double total_a = 0.0;
for (int i = 0; i < k; ++i) {
int p = middle[i];
for (int j = 0; j < n; ++j) {
if (graph[p][j] != 0) {
a[i] += value[j];
}
}
total_a += a[i];
}
double c = (m - (total_a + k * m / 2.0)) / k;
bool tag = true;
for (int i = 0; i < k; ++i) {
int p = middle[i];
double val = a[i] + m / 2.0 + c;
if (lowerBound[p] <= val && val <= upperBound[p]) {
value[p] = val;
} else {
tag = false;
break;
}
}
return tag;
}
void Split(std::vector<int> &lower, std::vector<int> &upper,
std::vector<int> &middle, int mask) {
for (int i = 0; i < n; ++i) {
int t = mask % 3;
if (t == 0) {
lower.push_back(i);
} else if (t == 2) {
upper.push_back(i);
} else {
middle.push_back(i);
}
mask /= 3;
}
}
bool CheckClique(const std::vector<int> &clique) {
for (size_t i = 0; i < clique.size(); ++i) {
for (size_t j = i + 1; j < clique.size(); ++j) {
if (graph[clique[i]][clique[j]] != 1) {
return false;
}
}
}
return true;
}
void Initialize(const std::vector<std::string> &expr) {
graph.resize(n);
for (int i = 0; i < n; ++i) {
graph[i].resize(n);
}
std::string all;
for (auto &s : expr) {
all += s;
}
for (size_t i = 0; i < all.size(); i += 3) {
int u = all[i] - 'a';
int v = all[i + 1] - 'a';
graph[u][v] = graph[v][u] = 1;
}
}
int n;
std::vector<std::vector<int>> graph;
};