算法设计基础（一）

算法设计基础，对贪心，动态规划，双指针等基础算法
做了一个总结和回顾

问题求解策略

const int maxn = 1e4 + 10;
const string name[] = {"L", "Turning", "R"};
int L, T, N;

class Ant {
public:
    int id, p, dir;
    Ant() = default;

    Ant(int id, int p, int dir) : id(id), p(p), dir(dir) {}

    bool operator< (const Ant& rhs) const {
        return p < rhs.p;
    }
} st[maxn], ed[maxn];

int A[maxn];

void solve() {
    sort(st+1, st+1+N);
    _rep(i, 1, N) {
        A[st[i].id] = i;
    }

    sort(ed+1, ed+1+N);
    _rep(i, 1, N-1) {
        if(ed[i].p == ed[i+1].p) ed[i].dir = ed[i+1].dir = 0;
    }

    _rep(i, 1, N) {
        int i2 = A[i];
        if (ed[i2].p < 0 || ed[i2].p > L) printf("Fell off\n");
        else printf("%d %s\n", ed[i2].p, name[ed[i2].dir + 1].c_str());
    }
    printf("\n");
}

void init() {
    memset(A, 0, sizeof(A));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    _rep(_, 1, kase) {
        printf("Case #%d:\n", _);

        init();
        scanf("%d%d%d", &L, &T, &N);
        _rep(i, 1, N) {
            char d[2];
            int p, dir;
            scanf("%d %s", &p, d);
            dir = (strcmp(d, "L") == 0 ? -1 : 1);
            //debug(dir);

            st[i] = Ant(i, p, dir);
            ed[i] = Ant(0, p + T*dir, dir);
        }

        // then solve
        solve();
    }
}

处理立方体问题的一种思路

ZOJ2714

algorithm
视图$(x, y)$，原视图为 $view(x,y, z)$

• 对于每个坐标 $(x, y)$，逐层检查 $\forall lv \in [0, n)$
  • 如果符合 $p(x, y, z)=\emptyset$ continue，检查下一层 $lv$
  • 如果 $p(x,y,z)= *$，那么表示这一层未被染色
    $p(x,y,z) \leftarrow view(x,y,z)$
  • 如果 $p(x,y,z) \neq view(x,y,z)$, delete $p(x,y,z)$
    并且标记 删除操作未完成
• 一直删除，到不能删除为止

const int maxn = 10 + 1;
int n;

char p[maxn][maxn][maxn];
char view[maxn][maxn][maxn];

char read() {
    char ch;
    for(;;) {
        ch = getchar();
        if ((ch >= 'A' && ch <= 'Z') || ch == '.') return ch;
    }
}

inline void data(int k, int i, int j, int lv, int &x, int &y, int &z) {
    if (k == 0) { x = lv; y = j; z = i; }
    if (k == 1) { x = n-1-j; y = lv; z = i; }
    if (k == 2) { x = n-1-lv; y = n-1-j; z = i; }
    if (k == 3) { x = j; y = n-1-lv; z = i; }
    if (k == 4) { x = n-1-i; y = j; z = lv; }
    if (k == 5) { x = i; y = j; z = n-1-lv; }
}

void getdata() {
    _for(i, 0, n) _for(k, 0, 6) _for(j, 0, n) {
                view[k][i][j] = read();
            }

    _for(x, 0, n) _for(y, 0, n) _for(z, 0, n) p[x][y][z] = '#';
    _for(k, 0, 6) _for(i, 0, n) _for(j, 0, n) if (view[k][i][j] == '.') {
                    _for(lv, 0, n) {
                        int x, y, z;
                        data(k, i, j, lv, x, y, z);
                        p[x][y][z] = '.';
                    }
                }
}

void dfs() {
    bool done = true;

    _for(k, 0, 6) _for(i, 0, n) _for(j, 0, n) if (view[k][i][j] != '.') {
                    _for(lv, 0, n) {
                        int x, y, z;
                        data(k, i, j, lv, x, y, z);

                        if (p[x][y][z] == '.') continue;
                        if (p[x][y][z] == '#') {
                            p[x][y][z] = view[k][i][j];
                            break;
                        }
                        if (p[x][y][z] == view[k][i][j]) break;

                        p[x][y][z] = '.';
                        done = false;
                    }
                }

    if (!done) dfs();
    return;
}

void init() {
    memset(view, 0, sizeof(view));
    memset(p, 0, sizeof(p));
}

int main() {
    freopen("input.txt", "r", stdin);
    while (scanf("%d", &n) == 1 && n) {
        init();

        // then get data
        getdata();

        // then dfs
        dfs();
        int ans = 0;
        _for(x, 0, n) _for(y, 0, n) _for(z, 0, n) if (p[x][y][z] != '.') ans++;
        //debug(ans);

        printf("Maximum weight: %d gram(s)\n", ans);
    }
}

dfs用能否顺利做完来递归

UVA11210

使用cnt+dfs需要注意的点
因为递归成功的时候，cnt值是搜索树最底层的值
也就是说，递归判断“和牌”成功的时候, cnt数组的值被打乱了
为搜索树最底层的cnt

所以每次枚举一个新的牌，都必须对cnt数组进行初始化

const char* mahjiong[] = {
        "1T", "2T", "3T", "4T", "5T", "6T", "7T", "8T", "9T",
        "1S", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S",
        "1W", "2W", "3W", "4W", "5W", "6W", "7W", "8W", "9W",
        "DONG", "NAN", "XI", "BEI",
        "ZHONG", "FA", "BAI"
};
// 34

int mj[15];

// convert string to ID
inline int convert(const char* str) {
    _for(i, 0, 34) if (strcmp(mahjiong[i], str) == 0) return i;
    return -1;
}

int cnt[34 + 5];

bool dfs(int dep) {
    if (dep == 4) return true;

    _for(i, 0, 34) {
        if (cnt[i] >= 3) {
            // ke zi
            cnt[i] -= 3;
            if (dfs(dep + 1)) return true;
            cnt[i] += 3;
        }
    }
    _rep(i, 0, 24) {
        // shun zi
        if (i % 9 <= 6 && cnt[i] >= 1 && cnt[i+1] >= 1 && cnt[i+2] >= 1) {
            cnt[i]--; cnt[i+1]--; cnt[i+2]--;
            if (dfs(dep + 1)) return true;
            cnt[i]++; cnt[i+1]++; cnt[i+2]++;
        }
    }

    return false;
}

bool check() {
    _for(i, 0, 34) {
        if (cnt[i] >= 2) {
            cnt[i] -= 2;
            if (dfs(0)) return true;
            cnt[i] += 2;
        }
    }
    return false;
}

void solve() {
    vector<string> ans;

    _for(i, 0, 34) {
        memset(cnt, 0, sizeof(cnt));
        _for(j, 0, 13) cnt[mj[j]]++;

        if (cnt[i] >= 4) continue;

        cnt[i]++;
        if (check()) ans.push_back(string(mahjiong[i]));
        cnt[i]--;
    }

    if (ans.empty()) printf(" Not ready");
    else {
        for(auto x : ans) printf(" %s", x.c_str());
    }
    printf("\n");
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    char s[100];

    int kase = 0;
    while (scanf("%s", s) == 1) {
        init();
        if (s[0] == '0') break;
        printf("Case %d:", ++kase);

        // convert s to id
        mj[0] = convert(s);
        _for(i, 1, 13) {
            scanf("%s", s);
            mj[i] = convert(s);
        }

        // get 13 mahjiong finished
        // then solve
        solve();
    }
}

Hanoi塔问题

UVA10795

const int maxn = 60 + 5;
int st[maxn], ed[maxn], n;

inline ll f(const int* P, int k, int ed) {
    if (k == 0) return 0;
    if (P[k] == ed) return f(P, k-1, ed);
    return f(P, k-1, 6-ed-P[k]) + (1ll<<(k-1));
}

ll solve() {
    int k = n;
    while (st[k] == ed[k] && k >= 1) k--;

    ll ans = 0;
    if (k >= 1) {
        int other = 6 - st[k] - ed[k];
        ans = f(st, k-1, other) + f(ed, k-1, other) + 1;
    }
    return ans;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (scanf("%d", &n) == 1 && n) {
        init();
        _rep(i, 1, n) scanf("%d", &st[i]);
        _rep(i, 1, n) scanf("%d", &ed[i]);

        // then solve
        ll res = solve();
        printf("Case %d:", ++kase);
        printf(" %lld\n", res);
    }
}

字典序问题处理

给个算法模版

template<class T>
bool lexSmaller(vector<T> a, vector<T> b) {
    int n = a.size(), m = b.size();
    int i;
    for(i = 0; i < n && i < m; i++) {
        if (a[i] < b[i]) return true;
        else if (b[i] < a[i]) return false;
    }
    return (i == n && i < m);
}

集合思想求mex

newcoder

在博弈论问题中，我们常常需要求区间 $[l,r]$ 的 mex函数
即在区间 $[l,r]$ 中，最小的未出现的 自然数

const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], n, q;

int pre[maxn], suf[maxn];

void prework() {
    pre[0] = suf[n+1] = n;
    _rep(i, 1, n) pre[i] = min(pre[i-1], a[i]);
    for(int i = n; i >= 1; i--) suf[i] = min(suf[i+1], a[i]);
}

void solve() {
    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);

        int ans = min(pre[l-1], suf[r+1]);
        printf("%d\n", ans);
    }
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    scanf("%d%d", &n, &q);
    _rep(i, 1, n) scanf("%d", &a[i]);

    prework();
    solve();
}

树上的最优化问题

树形结构，最常见的是要把无根树转换成为有根树

UVA1267

特别注意，如果使用

vector<int> G[maxn];
G[x].push_back(y);
G[y].push_back(x);

来建立无根树，实际上是一个无向图
叶子节点如何判定？实际上是

G[u].size() == 1

$sz = 1$的点是叶节点

另外，dfs 处理无根树转换成为有根树问题的时候
常常需要处理子树
子树需要把 $u$ 的 $pa$ 重置为 $-1$

void dfs(int u, int pa, int dep)
then
dfs(u, -1, 0)
处理 u 为根的子树

const int maxn = 1000 + 10;
vector<int> G[maxn], node[maxn];
int n, s, k;

int pa[maxn];
bool covered[maxn];

void dfs(int u, int fa, int dep) {
    pa[u] = fa;
    if (G[u].size() == 1 && dep > k) node[dep].push_back(u);

    for(auto v : G[u]) {
        if (v != fa) dfs(v, u, dep+1);
    }
}

void dfs2(int u, int fa, int dep) {
    // put serve in u node
    if (dep > k) return;
    covered[u] = true;
    for (auto v : G[u]) {
        if (v != fa) dfs2(v, u, dep+1);
    }
}

void solve() {
    int ans = 0;
    for (int d = n-1; d > k; d--) for(auto u : node[d]) {
        if (covered[u]) continue;

        int v = u;
        _for(_, 0, k) v = pa[v];

        dfs2(v, -1, 0);
        ans++;
    }
    printf("%d\n", ans);
}

void init() {
    _for(i, 0, maxn) G[i].clear(), node[i].clear();
    memset(pa, 0, sizeof(pa));
    memset(covered, 0, sizeof(covered));
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase;
    cin >> kase;
    while (kase--) {
        init();
        scanf("%d%d%d", &n, &s, &k);

        // build graph
        _for(i, 0, n-1) {
            int x, y;
            scanf("%d%d", &x, &y);
            G[x].push_back(y);
            G[y].push_back(x);
        }

        // then dfs
        dfs(s, -1, 0);

        // then try to solve
        solve();
    }
}