終于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
西月弦 閱讀(322)
評論(2) 編輯 收藏 引用 所屬分類:
解題報告