算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0
终于AK了,作为题解写在这里,我的ID: hanfei19910905

A
简单的字符串处理(略)

B
有N张扑克牌(N<=52)排成一行,四种花色12种点数。每次可以将最右一堆牌(位置k)至于k-1或者k-3的顶部,当且仅当花色或者点数相等。问最后是否可以合并为一堆。
算法分析:
    动态规划,DP[i,a,b,c]代表长度为i,最后三堆顶部为a,b,c,是否可以合并为一堆。
    转移: dp[i,a,b,c] = dp[i-1,c,a,b] | dp[i-1,num[i-3],a,c]。

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
const string aa = "23456789TJQKA";
const string bb = "SDHC";
string ch[100];
int num[100];
int dp[60][60][60][60];
bool chk(int a,int b){
    return a/13 == b/13 || a % 13 == b%13;
}
bool dfs(int p,int a,int b,int c){
    int &ans = dp[p][a][b][c];
    if(ans !=-1) return ans;
    if(p == 0) return chk(b,c) && chk(a,c);
    ans = 0;
    if(chk(c,b)) ans = dfs(p-1,num[p-1],a,c);
    if(chk(num[p-1],c)) ans |= dfs(p-1,c,a,b);
    return ans;
}
int find(const string& a, char b){
    for(int i=0;i<a.size();i++)
        if(b==a[i]) return i;

}
int main(){
    int n;
    while(cin >> n){
        for(int i=0;i<n;i++){
            cin >> ch[i];
            num[i] = find(bb,ch[i][1]) * 13 + find(aa,ch[i][0]);
        }
        memset(dp,-1,sizeof(dp));
        if(n == 1) puts("YES");
        if(n == 2) puts(chk(num[0],num[1]) ? "YES" : "NO");
        if(n >= 3) puts(dfs(n-3,num[n-3],num[n-2],num[n-1]) ? "YES" : "NO");
    }
}
C
有点数为N(N<=100)的无向图。现在要选择一个点,给这个点的邻接边染色。让1到n的所有最短路经过的染色边的期望最高,求最高期望。
算法分析:
    设f(s,e)是s到e有多少条最短路,广搜可求。复杂度O(V+E)
    先将1到n有多少条最短路求出来。
    然后枚举每个点u,如果这是最短路上的点,那么选择它的期望是 2*f(1,u)*f(u,n)/f(1,n)。
    复杂度O(V*(V+E))

#include<iostream>
#include<cstdio>
using namespace std;
const int V = 105;
int G[V][V],dis[V][V]; double dp[V];
int Q[V], stp[V],Du[V]; double way[V];
int n,m;
template <typename T>inline void chkmax(T &a, const T b){if(a<b) a= b;}
void bfs(int s,int e){
    for(int i=0;i<n;i++){
        stp[i] = -1;
        way[i] = 0;
    }
    way[s] = 1.0;
    stp[s] = 0;
    Q[0] = s;
    int head = 0, tail = 1;
    while(head<tail){
        int u= Q[head++];
        for(int v = 0; v<n; v++) if(G[u][v]){
            if(stp[v] == -1){
                stp[v] = stp[u] + 1;
                way[v] = way[u];
                Q[tail ++] = v;
                if(v == e) Du[v] = 1;
            }
            else if(stp[v] == stp[u] + 1){
                way[v] += way[u];
                if(v == e) Du[v] ++;
            }
        }
    }
    dis[s][e] = dis[e][s] = stp[e];
    dp[e] *= way[e];
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                G[i][j] = 0;
        for(int i=0;i<n;i++) Du[i] = 0, dp[i] = 1.0;
        for(int i=0;i<m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            u--; v--;
            G[u][v] = G[v][u] = 1;
        }
        bfs(0,n-1);
        bfs(n-1,0);
        double ans =1.0; 
        for(int i=1;i<n-1;i++){
            bfs(0,i);
            bfs(n-1,i);
            if(dis[0][i] + dis[i][n-1] == dis[0][n-1])
                chkmax(ans, 2* dp[i]/dp[0] );
        }
        printf("%.10lf\n",ans);
    }
}
D
简单贪心(略)
E
给一个森林,点数为100,000。询问100,000次。每次给点u,整数数k。问有多少个点v,是u的第k个祖先的孩子,且距离还是k。
算法分析:
    
    预处理出u的2^i个祖先。再把同一深度的点放到一个vector里。
    设u的k祖先是v。在深度为k+deep[v]的vector里,找第一时间戳位于v的第一时间戳和第二时间戳的之间的所有点。二分可解。
    预处理O(nlogn)询问log(n)
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int MXB = 18;
const int V = 100005;
const int E = V<<1;
// build graph
int head[V], nxt[E], pnt[E], e;
void add(int u,int v){
    nxt[e] = head[u];
    head[u] = e;
    pnt[e++] = v;
}
// dfs
int dep[V],tm,pre[V],snd[V],P[V][MXB];
vector<int> temp[V];
void dfs(int u,int f){
    dep[u] = dep[f] + 1;
    temp[dep[u]].push_back(tm);
    pre[u] = tm++;
    P[u][0] = f;
    for(int i=1; i< MXB; i++){
        P[u][i] = P[P[u][i-1]][i-1];
    }
    for(int i=head[u];i!=-1;i=nxt[i]){
        int v = pnt[i];
        if(v == f) continue;
        if(pre[v]==-1) dfs(v,u);
    }
    snd[u] = tm++;
}
// lca
inline void goup(int &u,int d){
    for(int i=0;i<MXB;i++) if((1<<i) & d)
        u = P[u][i];
}
int find(int v,int k){
    vector<int> &t = temp[k];
    int l =0, r = t.size();
    while(l<r){
        int mid = l+r >>1;
        if(t[mid] >= v) r = mid; else l = mid+1;
    }
    return r;
}
// main
int main(){
    int n;
    cin >> n;
    static int prt[V] ;
    for(int i=1;i<=n;i++) pre[i] = head[i] = -1;
    tm = e = 0;
    for(int i=1;i<=n;i++){
        scanf("%d",&prt[i]);
        if(prt[i]) {add(i,prt[i]); add(prt[i],i);}
    }
    forint i=1; i<=n ; i++) if(!prt[i]) dfs(i, 0);
    int q,u,k; cin >> q;
    while(q -- ){
        scanf("%d%d",&u,&k);
        goup(u,k);
        if(!u) {cout<<"0 "; continue;}
        k += dep[u];
        cout<< find(snd[u],k) - find(pre[u],k) - 1 <<" ";
    }
    cout<< endl;
}
posted on 2012-07-24 17:23 西月弦 阅读(288) 评论(2)  编辑 收藏 引用 所属分类: 解题报告

FeedBack:
# re: codeforces #130 div2
2012-07-25 19:29 | wuyiqi
最后一题你找LCA用的是什么方法?好简洁  回复  更多评论
  
# re: codeforces #130 div2
2012-07-25 19:30 | 西月弦
@wuyiqi
倍增法  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理