终于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);}
}
for( int 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
西月弦 阅读(300)
评论(2) 编辑 收藏 引用 所属分类:
解题报告