11 months 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;
        }
};
← SRM 578 弱鸡题解 SRM 591 弱鸡题解 →
 
comments powered by Disqus