11 months ago

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

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


HexagonalBoard

关键词:二分图判定

算法简述

首先可以观察出题目所给的这个图的色数一定不超过3。这样只要知道这个图的色数是不是2就可以了,一个floodfill之类的就行了。

一点点小代码

int c[100][100];
int g[100][100];
int n;
int dirx[] = {0, 0, 1, 1, -1, -1};
int diry[] = {-1, 1, -1, 0, 0, 1};
bool pd(int x, int y) { //判断(x, y)是否是一个合法的位置
    return x < n && x >= 0 && y < n && y >= 0 && g[x][y];
}
bool floodfill(int x, int y, int d) { // floodfill判断是否二分图
    c[x][y] = d;
    REP(i, 0, 5) {
        int xx = x + dirx[i], yy = y + diry[i];
        if (!pd(xx, yy)) continue;
        if (!c[xx][yy] && !floodfill(xx, yy, 3 - d)) return false;
        else if (c[xx][yy] == d) return false;
    }
    return true;
}
class HexagonalBoard {
    public:
        int minColors(vector<string> board) {
            CL(c, 0);
            n = board.size();
            REP(i, 0, n - 1) REP(j, 0, n - 1) g[i][j] = (board[i][j] == 'X');
            REP(i, 0, n - 1) REP(j, 0, n - 1) if (pd(i, j) && !c[i][j] && !floodfill(i, j, 1)) return 3; //如果不是二分图说明答案3
            int mx = 0;
            REP(i, 0, n - 1) REP(j, 0, n - 1) getmax(&mx, c[i][j]); //判断答案是否为0 1 2
         return mx;
        }
};

MayTheBestPetWin

关键词:背包、简单数学

算法简述

首先把式子变换一下,我们要最小化的是, 其中是选择出的第一队的A与B的和。整理一下就是, 其中是常数,因此只要知道就行了。那么就把这个看成一个整体,来做一个可行性背包,最后枚举一下就可以算出答案了。

一点点小代码

const int M = 1000001;

bitset<M> f; //代表sigma A[i] + B[i] = x 是否可行
int n;

class MayTheBestPetWin {
    public:
        int calc(vector<int> A, vector<int> B) {
            n = A.size();
            f.reset(); f[0] = 1; //最开始的时候 只有f[0] = 1
            REP(i, 0, n  - 1) f |= (f << (A[i] + B[i]));
            int ans = 1e9;
            int sa = 0, sb = 0; //A的和 与 B的和
            REP(i, 0, n - 1) sa += A[i], sb += B[i];
            REP(i, 0, sa + sb) if (f[i]) getmin(&ans, max(sb - i, i - sa)); //计算最优的Max{sb - A - B, A + B - sa}
         return ans;
        }
};

WolfDelaymasterHard

关键词:动态规划

题目简述

定义一个串是合法的:

  • 对于一个正整数,串ww..woo..o(w后面接上o) 是合法的
  • 两个合法串的拼接是合法的

现在给出一个串,其中包含有字符w,o,?,现在要把所有?的地方填上wo,使得串合法。

问有多少种不同的填法。

算法简述

这个题可以一眼看出一个十分naive的暴力DP,大概就是 ,其中的意思就是这个子串可以被填成ww..woo..o这样的形式。

考虑来优化这个DP,我们发现对于一个,所以合法的的位置组成了不超过段连续区间。这个还是比较好说明的,可以脑补一下发现是对的。

有了这个结论就可以很方便地来做这个题了。只要维护一下每一段区间,同时记录一下DP的前缀和就可以了。

一点小代码

const int N = 2100000;
char s[N];
int f[N];
int sum1[N], sum2[N]; //奇数下标的前缀和以及偶数下标的前缀和
int sw[N], so[N]; //'w'的前缀和 'o'的前缀和 用于判断子串合法
vector<PII> v; //储存合法的转移区间 不超过O(log(n))
bool check(int i, int j) { //判断[i, j]是否合法 (w^n + o^n)
    if (i <= 0 || i > j || (i - j) % 2 == 0) return false;
    int m = (i + j) / 2;
    return (so[m] - so[i - 1] == 0) && (sw[j] - sw[m] == 0);
}
class WolfDelaymasterHard {
    public:
        int countWords(int N, int wlen, int w0, int wmul, int wadd, int olen, int o0, int omul, int oadd) {
            //先生成字符串
            //
            REP(i, 1, N) s[i] = '?';
            LL x = w0;
            REP(i, 0, wlen - 1) {
                s[x + 1] = 'w';
                x = (x * wmul + wadd) % N;
            }

            x = o0; 
            REP(i, 0, olen - 1) {
                s[x + 1] = 'o';
                x = (x * omul + oadd) % N;
            }
            sw[0] = so[0] = 0;
            REP(i, 1, N) sw[i] = sw[i - 1] + (s[i] == 'w'), so[i] = so[i - 1] + (s[i] == 'o');
            f[0] = 1;
            f[1] = 0;
            sum2[0] = 1; 
            sum1[1] = 0;
            v.clear();

            REP(i, 2, N) {
                vector<PII> t;
                bool flag = false;
                for (int j = 0; j < v.size(); ++j) { //维护合法的转移区间
                    PII &A = v[j];
                    if (!check(i - 2 * A.SC - 1, i)) --A.SC;
                    A.SC++, A.FR++;
                    if (A.FR <= A.SC) {
                        if (A.FR == 2 && check(i - 1, i)) A.FR = 1, flag = 1;
                        if (s[i] != 'w')
                            t.PB(A);
                    }
                }
                if (!flag && check(i - 1, i)) t.PB(MP(1, 1));
                v = t;
                int *s;
                if (i & 1) s = sum1;
                else s = sum2;

                f[i] = 0;
                for (int j = 0; j < v.size(); ++j) {
                    PII &A = v[j];
                    f[i] = (f[i] + s[i - 2 * A.FR] - s[i - 2 * A.SC]) % mo; //通过前缀和来计算
                    f[i] = (f[i] + f[i - 2 * A.SC]) % mo;
                    if (f[i] < 0) f[i] += mo;
                }
                s[i] = (s[i - 2] + f[i]) % mo;
            }
            return f[N];
        }
};
← SRM 557 弱鸡题解 SRM 597 弱鸡题解 →
 
comments powered by Disqus