about 2 years ago

嘟噜噜... 还有一个月就NOIP了,AFO好久了终于能来写点东西了。 其实说好的NOI游记还坑着呢.. 慢慢补吧

简单写点弱鸡题解, 第一是督促一下作业进度,第二呢也可以来熟悉一下输入法。岂不是很妙。


Stamp

关键词:枚举、动态规划。

题目简述

给你一个长度为的空白的纸带,再给你一个目标带,每个位置可能是R、G、B三种颜色的一种,或者是一个*,代表这里可以是任意颜色。为了完成目标,你需要先确定一个长度L,然后进行若干次染色操作,每次你可以选择一个颜色C以及一段长度为L的区间,将其全部染成C,同时这个操作还需要保证这个区间在染色之前不存在除了C以外的颜色。假定你进行了K次操作,那么总花费就是, 求最小花费。

算法简述

这个题显然就是先去枚举L,然后判断L是否可行,这里不知道是不是可以用贪心,我是用一个很暴力的DP来解决的。令代表前i个位置都涂好了,其中最近一次染的区间是,所用颜色是的最小花费。直接暴力转移就可以了。这个做法比较直接和暴力。

一点点小代码

bool check(int l, int r, int c) {
    REP(i, l, r) {
        if (a[i] == -1) continue;
        if (a[i] != c) return false;
    }
    return true;
}

int dp(int L) {
    REP(i, 1, n) REP(j, 0, 2) f[i][j] = 1000;
    REP(i, L, n) {
        REP(j, 0, 2) {
            if (!check(i - L + 1, i, j)) continue;
            REP(k, 0, 2)
                getmin(&f[i][j], f[i - L][k] + 1);
            REP(k, i - L + 1, i - 1) getmin(&f[i][j], f[k][j] + 1);
        }
    }
    return min(min(f[n][0], f[n][1]), f[n][2]);
}

class Stamp
{
        public:
        int getMinimumCost(string desiredColor, int stampCost, int pushCost)
        {
            map<char, int> S;
            S['*'] = -1;
            S['R'] = 1;
            S['G'] = 2;
            S['B'] = 0;
            n = desiredColor.size();
            REP(i, 1, n) a[i] = S[desiredColor[i - 1]];
            int ans = 1e9;
            REP(i, 1, n) {
                int x = dp(i);
                if (x != -1) getmin(&ans, i * stampCost + x * pushCost);
            }
            return ans;
        }
};

Ear

关键词:几何,枚举、小学数学

题目简述

在坐标系上有一些红点和一些蓝点,其中红点都在X轴上,蓝点都在X轴上方。对于一个由4个红点(A B C D)和两个蓝点(P, Q)组成的集合,我们定义它为"Ear"当且仅当它们满足下面的条件:

  • B, C严格在线段AD内。
  • P点在X轴上的投影严格在AD内,Q点在Y轴上的投影严格在BC内。
  • Q点严格在三角形PAD内。

(脑补一下这个就是个耳朵,例如下图:

现在给你一些红点和蓝点,求总共有多少只"Ear"。

算法简述

类似这样的几何计数题,首先要确定枚举的对象。相对来说P和Q这两个点的限制比较复杂(要求Q在三角形内),那么就先把P、Q两个点先枚举一下,然后再枚举D点。看看现在哪些东西是已经确定下来了。首先这个C点的位置就已经确定下来了,C只有可能在Q投影和D之间,而且C点的位置不受A B影响(因为A B两个点都在Q的投影左侧)。接下来考虑A点的位置,因为有个限制是Q在三角形PAD之内,所以A点一定在直线PQ与X轴交点的左侧。需要注意的是,A点还有一个限制就是A要在P点投影的左侧。接下来B的位置就简单了,B一定在A点和Q点投影之间。现在就可以计算数量了,一个等差数列求和就行啦。

一点点小代码

string X, Y, Z;
stringstream F;
const int N = 310;
int rx[N], bx[N], by[N];// 红的X坐标以及蓝的坐标
int n;

int area(int x1, int y1, int x2, int y2)  { // 计算叉积 
    return x1 * y2 - x2 * y1;
}

int findL(int a) { // 计算第a个蓝点在X轴投影左侧最近的一个红点
    REP(i, 1, n) if (rx[i] >= bx[a]) return i - 1;
    return n;
}

int findR(int a) { // 计算第a个蓝点在X轴投影右侧最近的一个红点
    PER(i, n, 1) if (rx[i] <= bx[a]) return i + 1;
    return 1;
}

int intersect (int a, int b) { //计算第a个蓝点和第b个蓝点所成直线在X轴上的截距
    REP(i, 1, n) if (rx[i] >= bx[a] || area(bx[a] - rx[i], by[a], bx[b] - rx[i], by[b]) <= 0) return i - 1;
    return 0;
}
class Ear {
    public:
        long long getCount(vector<string> redX, vector<string> blueX, vector<string> blueY) {
            int m = 0, t;
            { // 先处理一下格式 
                X = Y = Z = "";
                for (int i = 0; i < redX.size(); ++i) X += redX[i];
                for (int i = 0; i < blueX.size(); ++i) Y += blueX[i];
                for (int i = 0; i < blueY.size(); ++i) Z += blueY[i];
                F.clear();
                F << X;
                n = 0;
                while (F >> t) rx[++n] = t;
                F.clear();
                F << Y;
                while (F >> t) bx[++m] = t;
                F.clear();
                F << Z;
                m = 0;
                while (F >> t) by[++m] = t;
            }

            sort(rx + 1, rx + n + 1);// 对红点坐标排序

            LL ans = 0;
            REP(P, 1, m) // 枚举P点
                REP(Q, 1, m) { // 枚举Q点
                    if (by[Q] >= by[P]) continue;
                    int RA = min(intersect(Q, P), findL(P)); //A点可行的范围
                    int RB = findL(Q); // B点可行的范围
                    int LC = findR(Q); // C点可行的范围
                    REP(D, 1, n) { //枚举D点
                        if (bx[Q] >= rx[D] || bx[P] >= rx[D]) continue; //P Q点要在D点左侧
                        if (area(bx[Q] - rx[D], by[Q], bx[P] - rx[D], by[P]) >= 0) continue; //Q要在PD左侧
                        int a1 = RB - RA;
                        int num = RA;
                        ans += (2LL * a1 + num - 1) * num  * (D - LC) / 2; //等差数列求和
                    }
                }


            return ans;
        }
};

Surrounding Game

关键词:最小割

题目简述

一个人在一个棋盘上玩游戏,想要占领一个格子有两个方法:

  • 在这个格子放一个棋子。
  • 这个格子周围(四联通)的格子中都有棋子

中放棋子需要花费,占领能获得。求一种放置棋子的方法,使得总收益(收益 - 花费)最大。

算法简述

这种题一看就是个网络流的模型。这个最小割的构图还是比较妙的。

首先把图黑白染色,就构成了一个二分图。然后把每个点都拆成两个,左边的点拆成连一条容量为的边,连一条容量为的边。右边的点如法炮制,拆成, , 之间连一条的边,的边。

既然已经把两边的边都连好了,那么就可以来连中间的边了,对于每一对相邻的点,我们在之间都连上一条的边。这样来跑个最小割,用总收益减去最小割就是答案了。

那么这个构图为什么是对的呢。考虑保留每一个收益的话需要割掉哪些边,发现这个条件正好和题目要求的条件相同:

  • 把这个格子的花费边割掉
  • 把这个格子相邻的格子的花费边割掉

一点小代码

void addadj(int x, int y) { // 给相邻的点连边
    if (x) ae(id[x][y] * 2 - 1, id[x - 1][y] * 2, inf), ae(id[x][y] * 2, id[x - 1][y] * 2 - 1, inf);
    if (y) ae(id[x][y] * 2 - 1, id[x][y - 1] * 2, inf), ae(id[x][y] * 2, id[x][y - 1] * 2 - 1, inf);
    if (x < n - 1) ae(id[x][y] * 2 - 1, id[x + 1][y] * 2, inf), ae(id[x][y] * 2, id[x + 1][y] * 2 - 1, inf);
    if (y < m - 1) ae(id[x][y] * 2 - 1, id[x][y + 1] * 2, inf), ae(id[x][y] * 2, id[x][y + 1] * 2 - 1, inf);
}

class SurroundingGame {
    public:
        int maxScore(vector<string> cost, vector<string> benefit) {
            CL(head, 0);
            cnt = 1;
            n = cost.size(), m = cost[0].size();
            int tot = 0;
            REP(i, 0, n - 1) 
                REP(j, 0, m - 1) id[i][j] = ++tot; //给网格中所有点标号
            s = 2 * tot + 1; t = s + 1;// 设置源点和汇点
            
            int sum = 0;
            REP(i, 0, n - 1) REP(j, 0, m - 1) sum += val(benefit[i][j]);

            REP(i, 0, n - 1)  //建图
                REP(j, 0, m - 1) 
                if ((i & 1) ^ (j & 1)) ae(s, 2 * id[i][j] - 1, val(cost[i][j])), 
                    ae(2 * id[i][j] - 1, 2 * id[i][j], val(benefit[i][j])), addadj(i, j);
                else  ae(2 * id[i][j] - 1, t, val(cost[i][j])), 
                    ae(2 * id[i][j], 2 * id[i][j] - 1, val(benefit[i][j]));
            return sum - dinic();
        }
};
← 滚粗狗的自我修养之Codeforces练习 SRM 561 弱鸡题解 →
 
comments powered by Disqus