about 1 year ago

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

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


TheTree

关键词:数学

算法简述

枚举一下直径的两个端点的深度,然后判一下就可以了

一点点小代码

int a[100];
class TheTree {
    public:
        int maximumDiameter(vector<int> cnt) {
            int ans = 0;
            int n = cnt.size();
            REP(i, 0, n - 1) a[i + 1] = cnt[i];
            a[0] =1;
            REP(i, 0, n ) {
                int r = i;
                PER(j, i, 0) if (a[j] == 1) {
                    r = j;
                    break;
                }
                if (a[i] > 1) getmax(&ans, 2 * i - 2 * r);
                REP(j, i + 1, n) getmax(&ans, j + i - 2 * r);
            }
            return ans;
        }
};

PyramidSequences

关键词:数学

算法简述

这题其实挺恶心的,好多部分是否重复根本想不清楚,不过代码还是很好写的。式子也就一行

一点点小代码

class PyramidSequences {
    public:
        long long distinctPairs(int N, int M) {
            LL d = __gcd((LL)N - 1, (LL)M - 1);
            return 1LL * (d-1) * ((N-1)/d) * ((M-1)/d) + 1LL * ((1+(N-1)/d)*(1+(M-1)/d)+1)/2; //只要一行式子就可以了
     }
};

StringPath

关键词:dp

题目简述

给你 的方阵,你要给每个格子都填上一个小写字母,使得从左上角到右下角存在两条不走弯路的路径恰好为字符串A和字符串B.

算法简述

这种题一看就无脑状压DP一波.. 表示一下轮廓线上每个位置的状态,要么是不合法的,要么是能作为A的结尾,要么是能作为B的结尾。稍微优化一下就能过了。

一点小代码

const int N = 10;
struct node { //dp状态
    int x, y; //目前已经dp到了(x, y)
    string s; //目前上面一列的状态 0 代表都不行 1代表可以作为A的结尾 2代表可以作为B的结尾
    node() {}
    node (int _x, int _y, string _s): x(_x) , y(_y), s(_s) {}
};
bool operator < (const node &A, const node &B) {
    if (MP(A.x, A.y) == MP(B.x, B.y)) return A.s < B.s;
    return MP(A.x, A.y) < MP(B.x, B.y);
}
map<node, int> S; //用map来记录所有状态
void add(char &x,  int a) {  //把这个位置打上标记 说明可以放a
    if (x == '3') return;
    if (x - '0' == a) return;
    x += a;
}
bool check(string &x, int k, int a) { //检查位置k是否能作为a的结尾
    if (k < 0) return false;
    if (x[k] == '3') return true;
    return x[k] - '0' == a;
}
queue<node> q;
class StringPath {
    public:
        int countBoards(int n, int m, string A, string B) {
            if (A[0] != B[0]) return 0;
            int ans = 0;
            while (!q.empty()) q.pop();
            S.clear();
            string s,zero;
            REP(i, 0, m - 1) s.PB('0'), zero.PB('0');
            s[0] = '3';
            q.push(node(0, 0, s));
            S[node(0, 0, s)] = 1; //初始状态 

            while (!q.empty()) {
                node now = q.front(); q.pop();
                int i = now.x, j = now.y;
                ++j; if (j >= m) ++i, j = 0;
                int tmp = S[now];
                if (i >= n) { //已经dp完了
                    if (now.s[m - 1] == '3') 
                        ans = (ans + tmp) % mo;
                    continue;
                }
                int zz = 0;
                REP(c, 'A', 'Z') { //枚举这个位置所填的字母
                    if (c != A[i + j] && c != B[i + j]) { //如果发现这个字符一定不行 就留到最后一起处理
                        ++zz;
                        continue;
                    }
                    string s = now.s;
                    char r = '0'; //r代表这个位置可以是哪些串的结尾
                    if (c == A[i + j] && (check(s, j - 1, 1) || check(s, j, 1))) add(r, 1);
                    if (c == B[i + j] && (check(s, j - 1, 2) || check(s, j, 2))) add(r, 2);
                    s[j] = r;
                    node nxt(i, j, s);
                    if (S.find(nxt) == S.end())  //如果还没有这个状态就加进去
                        q.push(nxt);
                    S[nxt] = (S[nxt] + tmp) % mo;
                }
                string s = now.s;
                s[j] = '0'; 
                node nxt(i, j, s);
                if (S.find(nxt) == S.end()) 
                    q.push(nxt);
                S[nxt] = (S[nxt] + 1LL * tmp * zz % mo) % mo; //最后处理那些这个位置填0的串,优化常数
            }
            return ans;
        }
};
← SRM 560 弱鸡题解 SRM 580 弱鸡题解 →
 
comments powered by Disqus