over 6 years ago
嘟噜噜... 还有一个月就NOIP了，AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧
简单写点弱鸡题解， 第一是督促一下作业进度，第二呢也可以来熟悉一下输入法。岂不是很妙。
TomekPhone
关键词：贪心
算法简述
可以把所有键的权给搞出来，然后排个序，贪心就可以了。
一点点小代码
class TomekPhone {
public:
int minKeystrokes(vector<int> A, vector<int> B) {
vector<int> C;
C.clear();
sort(A.begin(), A.end(), greater<int>());
REP(i, 0, B.size() - 1) REP(j, 1, B[i]) C.PB(j);
sort(C.begin(), C.end());
int ans = 0;
REP(i, 0, A.size() - 1) {
if (i >= C.size()) return -1;
ans += A[i] * C[i];
}
return ans;
}
};
DrawingPointsDivOne
关键词：DP，数学
算法简述
这个题目还是有点妙的。会发现，每个点都放在中间和每个点都放在左下角的情况是一样的，因为点与点之间的相对位置是一样的。那么问题就转化成，填一些点，让每个点作为一个k*k的正方形的左下角，且不存在其他点满足这个条件。那么就可以枚举k或者二分，然后用dp验证了。
一点点小代码
const int N = 400;
int f[N * 2][N * 2];
int a[N * 2][N * 2];
int n, x[N], y[N];
int dp(int l) { //dp 判断步数为l是否可行
CL(a, 0);
CL(f, 0);
REP(i, 1, n) {
REP(j, x[i] - l, x[i])
REP(k, y[i], y[i] + l) { //把每个点都摆在一个大小为k * k的正方形的左下角
a[j][k] = 1;
}
}
int cnt = 0;
REP(i, 0, 600)
REP(j, 0, 600) if (a[i][j]) {
f[i][j] = min(min(f[i - 1][j - 1], f[i][j - 1]), f[i - 1][j]) + 1; //计算总共有多少点是一个大小为k * k的正方形的一个角
cnt += (f[i][j] > l);
}
return cnt;
}
class DrawingPointsDivOne {
public:
int maxSteps(vector<int> X, vector<int> Y) {
n = X.size();
REP(i, 1, n) x[i] = X[i - 1] + 300, y[i] = Y[i - 1] + 300; //把坐标平移到正的地方
int l = 0, r = 141, res = 0;
while (l <= r) { //二分答案
int mid = (l + r) >> 1;
if (dp(mid) == n) res = mid, l = mid + 1;
else r = mid - 1;
}
if (res == 141) return -1; //如果答案超过了140就说明肯定存在无限大小的步数
return res;
}
};
BoundedOptimization
关键词：数学
题目简述
给定一个多项式，且每一项都是两个变量的乘积。给定每个变量共同的取值范围[l, r]， 这个多项式的最大值。
变量数不超过13
算法简述
这题非常有意思。可以把这个变量看成点，两个变量的乘积就是一条边，现在要给点确定值，让边权和最大。因为n比较小，枚举有哪些点是取到最大值或最小值的。根据调整法可得，如果两个点不相邻且他们都没取到最值，那么把其中一个调成最值一定不会更劣，所以没取到最值的点就成了一个团。那么这个团里的值要怎么取呢，可以求个导看看，具体可以看代码的注释。
一点小代码
const int N = 20;
bool G[N][N]; //邻接矩阵
int M, a[N], n;//a[i]代表未被分配到极值的点i 与其相邻的极值点的点权和 M为非极值点的点权和
double f[N];
/*
* f[i]为每个点所分配的值
* 现在要最大化：sigma f[i] * (a[i] + M / 2 - f[i] / 2)
* 其中sigma f[i] * M / 2的值已经固定
* f[i] * a[i] - f[i] ^ 2 / 2 的导数是 a[i] - f[i]
* 根据拉格朗日乘数法可知一定存在一个数C, 满足
* a[i] - f[i] + c = 0
* 由于f[i]的和是M，这样就可以计算得到C的值了
*/
bool isClique(int S) {//判断一个集合是否构成了一个clique
REP(i, 0, n - 1) if (S & (1 << i))
REP(j, i + 1, n - 1) if (S & (1 << j))
if (!G[i][j]) return false;
return true;
}
class BoundedOptimization {
public:
double maxValue(vector<string> expr, vector<int> lowerBound, vector<int> upperBound, int maxSum) {
n = lowerBound.size();
REP(i, 1, expr.size() - 1) expr[0] += expr[i];
CL(G, 0);
for (int i = 0; i < expr[0].size(); i += 3)
G[expr[0][i] - 'a'][expr[0][i + 1] - 'a'] =
G[expr[0][i + 1] - 'a'][expr[0][i] - 'a'] = 1; //把相邻的点连边
double ans = 0;
REP(S, 0, (1 << n) - 1) { //枚举取到极值的点的集合
if (!isClique((1 << n) - 1 - S)) continue; //所有没取到极值的点要在一个团里面
for (int T = S; ; T = (T - 1) & S) { //枚举取到lowerbound的点
M = maxSum;
double tmp = 0;
int k = __builtin_popcount((1 << n) - 1 - S); //计算未被分配到值的点的个数
int sa = 0;
REP(i, 0, n - 1) if (S & (1 << i)) {
if (T & (1 << i)) f[i] = lowerBound[i];
else f[i] = upperBound[i];
M -= f[i];
}
if (M < 0) goto LOOP; //第一步分配不能超过上限
REP(i, 0, n - 1) {
if (S & (1 << i)) continue;
a[i] = 0;
REP(j, 0, n - 1) if (S & (1 << j)) if (G[i][j]) a[i] += f[j]; //a[i]代表与点i相邻的已经分配的点的权值和
sa += a[i]; //a[i]的和
}
REP(i, 0, n - 1) {
if (S & (1 << i)) continue;
f[i] = 1.0 * a[i] + 1.0 * M / k - 1.0 * sa / k; //根据导数计算每点应该分配的值
if (f[i] < 1.0 * lowerBound[i] || f[i] > 1.0 * upperBound[i]) goto LOOP;
}
REP(i, 0, n - 1)
REP(j, i + 1, n - 1) if (G[i][j]) tmp += f[i] * f[j];
getmax(&ans, tmp);
LOOP: if (!T) break;
}
}
return ans;
}
};
