over 1 year ago

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

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


ICPCBalloons

关键词:枚举、贪心。

算法简述

因为大小气球之间不能切换,所以每个题目都要去确定用大气球还是小气球。这里就是一个指数的枚举就行了。之后判断可不可行就是一个贪心的问题了。把两个集合的元素都按照大小排序,然后调整一下就好了。

一点点小代码

vector<int> L, M; //尺寸为L的气球和M的气球
vector<int> A; // A题的人数
int calc(vector<int> A, vector<int> B) { //计算 A与B两个集合要符合条件的最小代价
    int sa = 0, sb = 0;
    for (int i = 0; i < A.size(); ++i) sa += A[i];
    for (int i = 0; i < B.size(); ++i) sb += B[i];
    if (sb > sa) return -1;
    int sum = 0;
    for (int i = 0; i < B.size(); ++i) {
        int x = 0; if (i < A.size()) x = A[i]; //这里使用贪心的想法 把两个集合从小到大配对
        if (x < B[i]) sum += B[i] - x;
    }
    return sum;
}
int check(int S) { //计算当选取大小气球的方案为S的时候的最小代价
    vector<int> X, Y;
    REP(i, 0, A.size() - 1) if (S & (1 << i)) X.PB(A[i]);
    else Y.PB(A[i]);
    sort(X.begin(), X.end(), greater<int>());
    sort(Y.begin(), Y.end(), greater<int>());
    int ans1 = calc(L, X), ans2 = calc(M, Y);
    if (ans1 != -1 && ans2 != -1) return ans1 + ans2;
    return -1;
}
class ICPCBalloons {
    public:
        int minRepaintings(vector<int> balloonCount, string balloonSize, vector<int> maxAccepted) {
            L.clear(); M.clear();
            A = maxAccepted;
            for (int i = 0; i < balloonCount.size(); ++i) if (balloonSize[i] == 'L') 
                L.PB(balloonCount[i]);
            else M.PB(balloonCount[i]);
            sort(L.begin(), L.end(), greater<int>());
            sort(M.begin(), M.end(), greater<int>());

            int ans = -1;

            REP(i, 0, (1 << A.size()) - 1) {//枚举每个题用大气球还是小气球
                int x = check(i); 
                if (x != -1)
                    if (ans == -1 || x < ans) ans = x;
            }
            return ans;
        }
};

CircleGame

关键词:简单几何、SG函数

算法简述

题目说了所有的圆只会相互包含,不会相交,所以就可以先把这个图形搞成树的结构。每次的操作就相当于选择树上的一个节点然后把这个点到根路径上的点全都删掉,谁不能删谁输。一看数据范围才50, 于是就可以直接算sg了。随便暴力就可以了。令为以为根的子树中进行博弈的sg。那么在计算的时候就可以枚举选择了哪个点,然后把这个点到的路径上的点删掉,递归下去求sg就好了。

一点点小代码

struct node {
    int x, y, r;
}a[100];
bool operator < (const node &A, const node &B) {
    return A.r < B.r;
}
int f[100], n;
int dist(int x, int y) { //计算距离
    return (a[x].x - a[y].x) * (a[x].x - a[y].x) + (a[x].y - a[y].y) * (a[x].y - a[y].y);
}
bool inside(int x, int y) { //判断第x个圆是否在第y个圆内
    return dist(x, y) <= a[y].r * a[y].r;
}
bool isanc(int x, int y) { //暴力判断x是否是y的祖先
    if (!y) return false;
    if (y == x) return true;
    return isanc(x, f[y]);
}
int sg[100];
vector<int> ch[100];
int dp(int);
int mex(vector<int> A) { //计算mex
    set<int> S;
    for (int i = 0; i < A.size(); ++i) S.insert(A[i]);
    REP(i, 0, 100) if (S.find(i) == S.end()) return i;
}
int rec(int x, int a) {//把选的点到根的链断开 分别计算新子树的sg
    int last = 0;
    int sum = 0;
    while (f[a] != x) {
        for (int i = 0; i < ch[x].size(); ++i) if (ch[x][i] != last) sum ^= dp(ch[x][i]);
        last = x;
        x = f[x];
    }
    return sum;
}
int dp(int a) { //记忆化搜索计算每棵树的sg值
    if (sg[a] != -1) return sg[a];
    vector<int> A;
    REP(b, 1, n) if (isanc(a, b)) A.PB(rec(b, a));
    return sg[a] = mex(A);
}
class CirclesGame {
    public:
        string whoCanWin(vector<int> x, vector<int> y, vector<int> r) {
            n = x.size();
            CL(sg, 0xff);
            REP(i, 0, n - 1) a[i + 1].x = x[i], a[i + 1].y = y[i], a[i + 1].r = r[i];
            CL(f, 0);
            sort(a + 1, a + n + 1);
            REP(i, 1, n) ch[i].clear();
            REP(i, 1, n) REP(j, i + 1, n) if (inside(i, j))  { //把圆组成的树给构出来
                f[i] = j;
                ch[j].PB(i);
                break;
            }
            int sg = 0;
            REP(i, 1, n) if (!f[i]) {
                sg ^= dp(i);//把所有树的根节点的SG值异或起来
            }
            if (sg) return "Alice";
            else return "Bob";
        }
};

Orienteering

关键词:最小割

题目简述

给你一棵个点的树,其中有不超过个特殊的点,现在从这些特殊的点中随机选出个点。任选一个起点和终点,在树上遍历完个点的最短路程是, 求的期望大小。

算法简述

首先要解决的问题是,如果给你了一些点,如何求遍历所有点的最小花费。

这个显然就是求出这些点的生成树,总花费就是这个生成树每条边长度的两倍减去这棵树直径。

由于期望是线性的,可以把这两部分分开来算。

  • 计算生成树上的边的期望条数,这个只要对每条边计算其出现在生成树上概率即可。
  • 计算生成树直径的期望,这个不是那么直观,可以先枚举树上直径的两个端点,计算其作为直径时的概率。因为一棵树可能有多个直径,我们同样还要限制这个直径是字典序最小的。那么其他点能够出现在树上有什么条件呢?实际上只要满足

$$|AB| \ge max \left( |AC|, |BC| \right)$$

这里还有一个小细节就是说,等号能不能取到。这里只要再去判一下字典序就可以了。

一点小代码

const int N = 2600;
int n, m; // 地图大小
int num; // Check Point 个数
int cp[N]; // 记录所有的Check Point
int id[51][51]; // 每个点的编号
char G[51][51]; //储存地图 . * #
int d[N][N]; //计算两点之间的最短路
double c1[N]; //C(i, K) / C(num, K)
double c2[N]; //C(i, K - 2) / C(num - 2, K - 2)

bool pd(int x, int y) { //判断(x,y)是否是合法的格子
    return x < n && y < m && x >= 0 && y >= 0 && G[x][y] != '#';
}

void dfs(int x, int y, int *f, int d) { //计算从(x, y)出发到每个点的最短路
    f[id[x][y]] = d;
    if (pd(x + 1, y) && f[id[x + 1][y]] == -1) dfs(x + 1, y, f, d + 1);
    if (pd(x - 1, y) && f[id[x - 1][y]] == -1) dfs(x - 1, y, f, d + 1);
    if (pd(x, y + 1) && f[id[x][y + 1]] == -1) dfs(x, y + 1, f, d + 1);
    if (pd(x, y - 1) && f[id[x][y - 1]] == -1) dfs(x, y - 1, f, d + 1);
}

bool check(int i, int j, int k) { //计算加入点k是否会影响直径i j的合法性
    int da = d[cp[i]][cp[j]], db = d[cp[i]][cp[k]], dc = d[cp[k]][cp[j]];
    return (da > db || (da == db && k > j)) && (da > dc || (da == dc && k > i));
}

class Orienteering {
    public:
        double expectedLength(vector<string> field, int K) {
            CL(d, 0xff);
            n = field.size(); m = field[0].size();
            num = 0;
            int tot = 0;
            REP(i, 0, n - 1) 
                REP(j, 0, m - 1) {
                    id[i][j] = ++tot;
                    G[i][j] = field[i][j];
                    if (G[i][j] == '*') cp[++num] = tot;
                }

            c1[num] = 1;
            PER(i, num - 1, 0) c1[i] = c1[i + 1] / (i + 1) * (i + 1 - K); // 计算系数1

            c2[num - 2] = 1;
            PER(i, num - 3, 0) c2[i] = c2[i + 1] / (i + 1) * (i - K + 3); // 计算系数2

            REP(i, 0, n - 1) REP(j, 0, m - 1) dfs(i, j, d[id[i][j]], 0);

            double ans = 0;

            REP(i, 1, tot - 1) 
                REP(j, i + 1, tot) if (d[i][j] == 1) {  //枚举每条树边
                    int x = 0; // 在一侧的Check Point个数
                    REP(k, 1, num) if (d[i][cp[k]] <= d[j][cp[k]]) ++x;
                    ans += 2.0 * (1.0 - c1[x] - c1[num - x]);
                }

            REP(i, 1, num - 1) 
                REP(j, i + 1, num) { //枚举 cp[i], cp[j] 作为直径
                    int x = 0; // 符合条件的k的个数
                    int dia = d[cp[i]][cp[j]]; //直径长度
                    REP(k, 1, num) if (check(i, j, k)) ++x;
                    ans -= c2[x] * dia * K * (K - 1) / num / (num - 1);
                }

            return ans;
        }
};
← SRM 558 弱鸡题解 SRM 557 弱鸡题解 →
 
comments powered by Disqus