about 1 year ago

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

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


GooseInZooDivOne

关键词:并查集、图论

算法简述

这个题一看就是一个比较套路的题目,先把两之间距离小于dist的用并查集缩起来,然后数一下奇数集合的数量和偶数集合的数量,然后判一下就可以了。

一点点小代码

const int N = 51;
int id[N][N]; 
int f[N * N], cnt[N * N];
int get(int u) { //并查集
    if (u == f[u]) return u;
    return f[u] = get(f[u]);
}
void join(int u, int v) {
    f[get(u)] = get(v);
}

class GooseInZooDivOne {
    public:
        int count(vector<string> field, int dist) {
            int n = field.size(), m = field[0].size();
            int tot = 0;
            REP(i, 0, n - 1) REP(j, 0, m - 1) id[i][j] = ++tot;
            REP(i, 1, tot) f[i] = i, cnt[i] = 0;
            REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v') 
                REP(k1, 0, n - 1 ) REP(k2, 0, m - 1) if (k1 != i || k2 != j) 
                if (field[k1][k2] == 'v') if (abs(i - k1) + abs(j - k2) <= dist) join(id[i][j], id[k1][k2]);
            //把两两之间距离小于dist的那些给放到一个集合中去

            REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v') cnt[get(id[i][j])]++;
            int ans1 = 0, ans2 = 0;
            REP(i, 0, n - 1) REP(j, 0, m - 1) if (field[i][j] == 'v' && f[id[i][j]] == id[i][j]) {
                if (cnt[id[i][j]] & 1) ++ans1; //集合大小为奇数的集合个数
                else ++ans2; //集合大小为偶数的集合个数
            }
            int ans = pow(2, ans1 + ans2 - (ans1 > 0)); //因为要满足goose的数目为偶数,所以奇数的那些集合只能选偶数个

            return (ans - 1 + mo) % mo;//至少要有一个goose
     }
};

WolfInZooDivOne

关键词:动态规划

算法简述

这个题目还是比较有意思的。首先考虑如果限制不是最多放两个而是最多放一个。那么就可以写一个这样的dp. 代表现在dp到第i个位置,这个区间里不放东西的方案数。具体的转移可以根据区间的左右端点来确定。那么受到这个思路的启发,可以写出一个这样的dp,, 其中k表示这个区间最多放一个东西。

一点点小代码

const int N = 310;
int f[2][N][N];// f[i][j][k]代表目前放了前i个位置,i到j位置都不能放wolf了, (j + 1)到k位置可以放一个wolf的方案数
PII a[N]; //所有的区间
int n, m, tmp;
stringstream fin;
class WolfInZooDivOne {
    public:
        int count(int N, vector<string> L, vector<string> R) {
            fin.clear();
            n = N;
            REP(i, 1, L.size() - 1) L[0] += L[i];
            REP(i, 1, R.size() - 1) R[0] += R[i];
            fin << L[0];
            m = 0;
            while (fin >> tmp) a[++m].FR = tmp + 1;
            fin.clear();
            fin << R[0];
            m = 0;
            while (fin >> tmp) a[++m].SC = tmp + 1; //处理一下格式

            sort(a + 1, a + m + 1);
            CL(f, 0);
            f[0][0][0] = 1;
            int j = 1, c = 0, ans = 0, l = 0;
            REP(i, 0, n - 1) {
                c ^= 1; CL(f[c], 0); //滚动数组
                while (j <= m && a[j].FR <= i + 1) getmax(&l, a[j].SC), ++j;//目前包含i + 1这个位置的最远的区间
                REP(k1, 0, n) 
                    REP(k2, k1, n) {
                        f[c][k1][k2] = (f[c][k1][k2] + f[c ^ 1][k1][k2]) % mo; //这个位置不放wolf
                        if (k1 < i + 1) f[c][k2][l] = (f[c][k2][l] + f[c ^ 1][k1][k2]) % mo; //这个位置放wolf
                    }
            }
            REP(i, 0, n) 
                REP(j, i, n) ans = (ans + f[c][i][j]) % mo;

            return ans;
        }
};

DeerInZooDivOne

关键词:动态规划,费用流,KM

题目简述

给出一个个点的树,让你从中选出两个连通子图,使得这两个子图同构。

算法简述

这个题看起来挺熟悉的,不知道哪里见到过。感觉这种题也没啥好做法,就是暴力搞,复杂度反正就是玄学。

首先要先枚举一条断边,把整个树分成两部分,然后枚举这两部分中选择的点(也就是枚举两个根)。然后开始搞dp,这个dp的过程中由于需要对儿子进行配对,所以还要搞一个KM,或者费用流也可以。在dp的过程中可以瞎jb记忆化来加速。大致就是代表两个点为根的最大值。

一点小代码

class ZKW { //ZKW费用流板子
    public:
#define INF 1000000000
#define MAXN 100000
#define MAXM 100000
        struct edge_node
        {
            int p,next;
            int w,c;
        }edge[MAXM];
        int vis[MAXN],instack[MAXN];
        int head[MAXN],slk[MAXN];
        int d[MAXN];
        int cur[MAXM];
        int cnt,S,T,index,tot;
        LL ans,flow;
        void ae(int a,int b,int weight,int cost)
        {
            edge[++cnt].p=b; edge[cnt].w=weight;
            edge[cnt].c=cost; edge[cnt].next=head[a]; head[a]=cnt;
            edge[++cnt].p=a; edge[cnt].w=0;
            edge[cnt].c=-cost; edge[cnt].next=head[b]; head[b]=cnt;
        }
        int aug(int u,int now)
        {
            if (u==T)
            {
                ans+=(LL)now*d[T];
                flow+=now;
                return now;
            }
            int res=0,tmp;
            vis[u]=instack[u]=index;
            for (int &k=cur[u];k;k=edge[k].next)
            {
                int v=edge[k].p;
                int t=d[u]+edge[k].c-d[v];
                if (edge[k].w)
                {
                    slk[v]=min(slk[v],t);
                    if (!t&&instack[v]!=index)
                    {
                        tmp=aug(v,min(now,edge[k].w));
                        res+=tmp;
                        edge[k].w-=tmp;
                        edge[k^1].w+=tmp;
                        if ((now-=tmp)==0) break;
                    }
                }
            }
            instack[u]=false;
            return res;
        }
        bool modlabel()
        {
            int del=INF;
            for (int i=1;i<=T;++i) if (vis[i]!=index)
                del=min(del,slk[i]);
            if (del==INF) return false;
            for (int i=1;i<=T;++i) if (vis[i]!=index)
                d[i]+=del;
            return true;
        }
        LL MCMF(int _S, int _T, int returnflow = 0)
        {
            S = _S, T = _T;
            flow=ans=0;
            for (int i=1;i<=T;++i) d[i]=0;
            do
                do{
                    for (int i=1;i<=T;++i) slk[i]=INF,cur[i]=head[i];
                    ++index;
                }
                while (aug(S,INF));while (modlabel());
            if (returnflow) return flow;
            return ans;
        }
        void init(int n) {
            index = cnt = 1;
            REP(i, 1, n + 2) head[i] = 0, vis[i] = -1;
        }
}solver;

const int N = 53;
int n;
struct node {
    int p, next;
    bool flag;
}edge[N * 2];
int head[N], cnt;
void ae(int a, int b) {
    edge[++cnt].p = b;
    edge[cnt].next = head[a];
    head[a] = cnt;
    edge[cnt].flag = 1;
}

int f[N][N][N][N];

vector<int> X, Y;

void dfs(vector<int> &V, int u, int fa) {
    V.PB(u);
    RED(k, u) if (edge[k].flag){
        int v = edge[k].p;
        if (v != fa) dfs(V, v, u);
    }
}

int dp(int a, int fa, int b, int fb) { //记忆化搜索
    if (f[a][fa][b][fb] != -1) return f[a][fa][b][fb];
    vector<int> X, Y;
    RED(k, a) if (edge[k].flag && edge[k].p != fa)
        X.PB(edge[k].p);
    RED(k, b) if (edge[k].flag && edge[k].p != fb)
        Y.PB(edge[k].p);


    for (int i = 0; i < X.size(); ++ i) 
        for (int j = 0; j < Y.size(); ++j) dp(X[i], a, Y[j], b);


    solver.init(X.size() + Y.size()); //费用流初始化
    int S = X.size() + Y.size() + 1, T = S + 1;

    for (int i = 0; i < X.size(); ++ i) solver.ae(S, i + 1, 1, 0);  //最大权匹配
    for (int i = 0; i < Y.size(); ++ i) solver.ae(i + 1 + X.size(), T, 1, 0);

    for (int i = 0; i < X.size(); ++ i) 
        for (int j = 0; j < Y.size(); ++j) {
            solver.ae(i + 1, j + X.size() + 1, 1, -f[X[i]][a][Y[j]][b]);
        }

    f[a][fa][b][fb] = -solver.MCMF(S, T) + 1; //最大费用流
    return f[a][fa][b][fb];
}

int solve(int a, int b) { 
    CL(f, 0xff);
    X.clear(); Y.clear();
    dfs(X, a, 0);
    dfs(Y, b, 0);
    int ans = 0;
    REP(i, 0, X.size() - 1) 
        REP(j, 0, Y.size() - 1) { //枚举两边树的根
            getmax(&ans, dp(X[i], 0, Y[j], 0));
        }
    return ans;
}

class DeerInZooDivOne {
    public:
        int getmax(vector<int> a, vector<int> b) {
            n = a.size() + 1;
            cnt = 1;
            CL(head, 0);
            REP(i, 0, a.size() - 1) ae(a[i] + 1, b[i] + 1), ae(b[i] + 1, a[i] + 1); //连边
            int ans = 0;
            REP(i, 1, n) RED(k, i) { //枚举断掉的边
                int j = edge[k].p;
                if (i > j) continue;
                edge[k].flag = 0;
                edge[k ^ 1].flag = 0;
                ans = max(ans,  solve(i, j)); 
                edge[k].flag = 1;
                edge[k ^ 1].flag = 1;
            }
            return ans;
        }
};
← SRM 589 弱鸡题解 SRM 560 弱鸡题解 →
 
comments powered by Disqus