about 1 year ago

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

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


LittleElephantAndString

关键词: 字符串

算法简述

这个idea还是比较简单的,只要看是否存在一段连续的位置是递增的就可以了。

一点点小代码

int n;
string A, B;
bool check(int x) {//贪心判断使用x操作是否可行
    int last = -1;
    bool flag;
    REP(i, x, n - 1) { //看看A中是否存在B[x] .. B[n - 1]这个子序列
        flag = 0;
        REP(j, last + 1, n - 1) {
            if (A[j] == B[i]) {
                last = j;
                flag = 1;
                break;
            }
        }
        if (!flag) return false;
    }
    return true;
}
class LittleElephantAndString {
    public:
        int getNumber(string A, string B) {
            ::A = A, ::B = B;
            n = A.size();
            sort(A.begin(), A.end());
            sort(B.begin(), B.end());
            if (A != B) return -1; //若AB中的字符不同则无解

            int ans = 0;

            REP(i, 0, n - 1) if (check(i)) return i;
            return -1;
        }
};

ConvexPolygonGame

关键词:计算几何

算法简述

这个题目就是给你一个凸包,问你这个凸包内是否存在一个坐标为整数的三角形。坐标范围是。由于坐标的范围比较小,我们发现,如果合法的点数大于那么些点里面一定存在一个三角形。所以只要把所有的点都找出来就可以了。至于怎么把所有的点都给找出来,可以枚举每个X,直接算出合法区间。

一点点小代码

int n;
LL area(int x1, int y1, int x2, int y2) { //计算叉积
    return 1LL * x1 * y2 - 1LL * x2 * y1;
}
int gcd(int a, int b) { // 计算gcd
    if (!b) return a;
    return gcd(b,a % b);
}
double eval(int x1, int y1, int x2, int y2, int x) { //计算x在直线上的y坐标
    return 1.0 * y1 + 1.0 * (y2 - y1) / (x2 - x1) * (x - x1);
}
PII t[210000];
vector<PII> P;
class ConvexPolygonGame {
    public:
        string winner(vector<int> X, vector<int> Y) {
            n = X.size();
            P.clear();
            CL(t, 0);
            LL side = 0, s = 0;
            int x1 = 1e9, x2 = -1e9;
            X.PB(X[0]); Y.PB(Y[0]);
            REP(i, 0, n - 1) side += gcd(abs(X[i + 1] - X[i]), abs(Y[i + 1] - Y[i])),
                s += area(X[i], Y[i], X[i + 1], Y[i + 1]);
            s = abs(s);
            LL num = side + (s + 2 - side) / 2 - n; //计算所有合法点的个数 Pick定理
            if (num > 200001) return "Masha"; //如果点大于这个数的话 那么一定就会存在三点共线
            if (num < 3) return "Petya";
            REP(i, 0, n - 1) getmin(&x1, X[i]), getmax(&x2, X[i]);
            PII *v = t + 101000;
            REP(i, 0, n - 1) { //把每个x合法的y区间给求出来
                int x1 = X[i], x2 = X[i + 1];
                int y1 = Y[i], y2 = Y[i + 1];
                if (x1 == x2)
                    v[x1] = MP(min(y1, y2) + 1, max(y1, y2) - 1);
                else if (x1 < x2) {
                    REP(j, x1 + 1, x2 - 1) {
                        v[j].FR = ceil(eval(x1, y1, x2, y2, j));
                    }
                    v[x1].FR = y1 + 1;
                    v[x2].FR = y2 + 1;
                } else {
                    REP(j, x2 + 1, x1 - 1) v[j].SC = floor(eval(x2, y2, x1, y1, j));
                    v[x1].SC = y1 - 1;
                    v[x2].SC = y2 - 1;
                }
            }
            REP(i, x1, x2){  //把每个合法的点都存下来
                REP(j, v[i].FR, v[i].SC) P.PB(MP(i, j));
            }

            REP(i, 2, P.size() - 1) if (area(P[i].FR - P[0].FR, P[i].SC - P[0].SC, P[1].FR - P[0].FR, P[1].SC - P[0].SC) != 0)
                return "Masha";
            
            return "Petya";
        }
};

LittleElephantAndBoard

关键词:组合数学

题目简述

有个大小为的网格,你要给每个格子染R, G, B三种颜色中的一种。一种染色是合法的当且仅当:

  • 任意两个相邻的格子都是不同的颜色
  • 任意一个的格子都有3种不同的颜色

现在给出每种颜色的数量,求总共有多少种合法方案。

算法简述

这个题我感觉还是比较有意思的。首先要对条件进行转化。我们可以一列一列去考虑,每一列要往里面填两种不同的颜色,其中一种是上一列中没有出现过的颜色。现在考虑能不能用这个颜色来作为每一列的代表颜色。假定已知每一列新出现的颜色,那么能还原出整个染色方案呢?

答案是可以的。可以由下一列的代表颜色来确定出这一列的颜色组成,这样就能换原出整个网格了。具体的方法可以参考:SOL

一点小代码

const int N = 2100000;
int f[N], inv[N];
int C(int a, int b) {
    return 1LL * f[a] * inv[b] % mo * inv[a - b] % mo;
}

int calc(int X, int Y, int Z) {//计算有X个R Y个G Z个B情况且相邻颜色不同的方案数
    if (X <= 0) return 0;
    int res = 0;
    REP(g, X - 1, X) //组数
        for (int ev = 0, xp = 1; ev <= g; ev++, xp = (xp + xp) % mo) { //枚举数量为偶数的组数
            if ( (g - ev + Y - Z) % 2 != 0) continue;
            int oy = (g - ev + Y - Z) / 2; // G多的
            int oz = g - ev - oy; //B多的

            if (oy >= 0 && oz >= 0 && Y - oy >= 0) {
                int r = Y - oy - ev;
                if (r < 0) continue;
                int p = C(r+g-1, r);
                p = 1LL * p * C(g,ev) % mo;
                p = 1LL * p * C(g - ev, oy) % mo;
                p = 1LL * p * xp % mo;
                res = (res + p) % mo;

            }

        }
    return res;
}
class LittleElephantAndBoard {
    public:
        int getNumber(int M, int R, int G, int B) {
            f[0] = 1;
            REP(i, 1, 2 * M) f[i] = 1LL * f[i - 1] * i % mo;
            inv[2 * M] = pow(f[2 * M], mo - 2);
            PER(i, 2 * M - 1, 0) inv[i] = 1LL * inv[i + 1] * (i + 1) % mo;
            int ans = 2LL * calc(M - R, M - G, M - B) % mo;
            ans = (ans + 2LL * calc(M - G, M - R, M - B) % mo) % mo;
            ans = (ans + 2LL * calc(M - B, M - R, M - G) % mo) % mo;
            return ans;
        }
};
← SRM 593 弱鸡题解 SRM 589 弱鸡题解 →
 
comments powered by Disqus