A
裸最短路.
class TravelOnMars {
public:
int minTimes(vector <int>, int, int);
};
vector<int> e[maxn];
int n;
int dist(int a,int b) {
if (a>b) swap(a,b);
int res = min( b-a , a+n-b);
return res;
}
int d[maxn],inq[maxn];
queue<int> q;
int bfs(int s,int t) {
for (int i= ; i<n ; i++ ) d[i] = ;
d[s] = ;
inq[s] = true;
q.push(s);
while (!q.empty()) {
int cur = q.front(); q.pop();
printf("d[%d]:%d\n",cur,d[cur]);
inq[cur] = false;
for (int i= ; i<(int)e[cur].size() ; i++ ) {
int v = e[cur][i];
if (d[v]>d[cur]+) {
d[v] = d[cur]+;
if (!inq[v]) {
inq[v] = true;
q.push(v);
}
}
}
}
return d[t];
}
int TravelOnMars::minTimes(vector <int> range, int startCity, int endCity) {
n = range.size();
printf("n=%d\n",n);
for (int i= ; i<n ; i++ ) {
for (int j= ; j<n ; j++ ) if (dist(i,j)<=range[i]) {
e[i].push_back(j);
}
}
int ans = bfs(startCity,endCity);
return ans;
}
B
f(u,s)表示以u为根子树的答案 , s=1表示有从u祖先下来的路径 , s=0表示没有.
f(u,s) 可以通过一个dp得到 :
dp[i][size]表示现在考虑第u的i个孩子,当前已经向下连了size条边时的最小代价 , 答案就是min(dp[ cntson ] [ size ] ),
然后需要加一些强制转移.
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
using namespace std;
#define maxn 55
class TurnOnLamps {
public:
int minimize(vector <int>, string, string);
};
struct edge{
int v,c;
}; vector<edge> e[maxn];
bool debug;
int var[maxn],n,dp[maxn][],dp2[][maxn][maxn];
int getvar(int x) {
if (x<) return ;
int res = x/ + (x&);
if (debug) printf("var:%d = %d\n",x,res);
return res;
}
int better(int a,int b) {
if (a==-) return b;
if (b==-) return a;
return min(a,b);
}
int dfs(int u,int s,int fa) {
if (dp[u][s]!=-) return dp[u][s];
vector<edge> son;
for (int i= ; i<(int)e[u].size() ; i++ ) {
int v = e[u][i].v;
if (v==fa) continue;
son.push_back(e[u][i]);
dfs(v,,u);
dfs(v,,u);
}
debug = (u==);
printf("u:%d s:%d debug=%d\n",u,s,debug);
for (int i= ; i<(int)e[u].size() ; i++ ) if (e[u][i].v != fa) {
printf("son:%d c:%d\n",e[u][i].v,e[u][i].c);
}
// {{0, 1, 0, 2, 0, 1, 1, 2, 4, 6, 10, 10, 11, 10, 9, 9, 10, 15, 7}, "0111100111001010000", "0100001100101000111"}
int res = ;
// for (int i=0 ; i<son.size() ; i++ ) printf("%d %d\n",son[i].v,son[i].c);
if (son.size()) {
if (son[].c==) {
dp2[s][son[].v][] = dp[son[].v][];
dp2[s][son[].v][] = dp[son[].v][] + getvar(-s);
} else if (son[].c==) {
dp2[s][son[].v][] = dp[son[].v][] + getvar(-s);
} else if (son[].c==) {
dp2[s][son[].v][] = dp[son[].v][];
}
for (int i= ; i<(int)son.size() ; i++ ) {
int lastv = son[i-].v;
int v = son[i].v;
int c = son[i].c;
for (int j= ; j<=i ; j++ ) if (dp2[s][lastv][j] != -) {
if (u==) printf("dp2[%d][%d][%d]=%d\n",s,lastv,j,dp2[s][lastv][j]);
// printf("dp2[%d][%d]=%d\n",lastv,j,dp2[lastv][j]);
if (c == ) {
int tmp;
tmp = better(dp2[s][v][j] , dp2[s][lastv][j]+dp[v][]);
// if (u==10) printf("update: dp2[%d][%d][%d] from %d to %d\n",s,v,j,dp2[s][v][j],tmp);
dp2[s][v][j] = tmp;
tmp = better(dp2[s][v][j+] , dp2[s][lastv][j]-getvar(j-s)+dp[v][]+getvar(j+-s));
// if (u==10) printf("update: dp2[%d][%d][%d] from %d to %d\n",s,v,j+1,dp2[s][v][j+1],tmp);
dp2[s][v][j+] = tmp;
} else if (c == ) {
int tmp = better(dp2[s][v][j+] , dp2[s][lastv][j]-getvar(j-s)+dp[v][]+getvar(j+-s));
// if (u==10) printf("update: dp2[%d][%d][%d] from %d to %d\n",s,v,j+1,dp2[s][v][j+1],tmp);
dp2[s][v][j+] = tmp;
} else if (c == ) {
int tmp = dp2[s][v][j] = better(dp2[s][v][j] , dp2[s][lastv][j]+dp[v][]);
// if (u==10) printf("update: dp2[%d][%d][%d] from %d to %d\n",s,v,j,dp2[s][v][j],tmp);
dp2[s][v][j] = tmp;
}
}
}
int smlcost = -;
int v = son[son.size()-].v;
for (int i= ; i<=(int)son.size() ; i++ )
if (dp2[s][v][i]!=-) {
smlcost = better(smlcost , dp2[s][v][i]);
}
// if (smlcost != -1) res = smlcost;
res = smlcost;
}
printf("dp[%d][%d]=%d\n",u,s,res);
return dp[u][s] = res;
}
int TurnOnLamps::minimize(vector <int> roads, string init, string imp) {
n = roads.size()+;
for (int i= ; i<n- ; i++ ) {
e[i+].push_back((edge){roads[i],imp[i]==''?imp[i]-''+init[i]-'':});
e[roads[i]].push_back((edge){i+,imp[i]==''?imp[i]-''+init[i]-'':});
}
memset(dp,-,sizeof(dp));
memset(dp2,-,sizeof(dp2));
int ans = dfs(,,-);
return ans;
}
C
概率题好费脑筋啊。。
模拟样例算不对 , 后来发现是少算了转移到自己的情况 , 然后就不会做了: 考虑每次能转移到自己的情况会出现无数步 , 怎么计算期望就成了问题;
题解在这个问题上处理地很巧妙 :
(1) 从期望的公式出发,推导得到了一个简单的形式 : sum ( 第i步没有完成的概率 ) (0<=i <INF);
(2) 可以用容斥来计算第i步没有完成的概率;
(3) 将容斥的公式变形 , 得到一系列的收敛的无穷级数 , 于是解决了i有无穷多的问题;
最后就得到了一个简单的统计模型: 对于给定的值x , 求有多少个元素个数为奇数的集合sum为x , 和有多少个个数为偶数的集合sum为x , 求他们的差,递推即可.
#define maxn 2000
class RandomPaintingOnABoard {
public:
double expectedSteps(vector <string>);
};
int cnt[maxn],sum[maxn],n,m,f[][maxn],tot;
double RandomPaintingOnABoard::expectedSteps(vector <string> prob) {
n = prob.size();
m = prob[].size();
vector<string> tmp;
if (m>n) {
for (int i= ; i<m ; i++ ) {
string s = "";
for (int j= ; j<n ; j++ ) s += prob[j][i];
tmp.push_back(s);
}
prob = tmp;
swap (n,m);
for (int i= ; i<n ; i++ ) cout<<prob[i]<<endl;
}
double ans = ;
printf("n:%d m:%d\n",n,m);
for (int i= ; i<n ; i++ ) for (int j= ; j<m ; j++ ) tot += prob[i][j]-'';
for (int i= ; i<(<<m) ; i++ ) { // for (int j=0 ; j<n ; j++ ) sum[j] = 0;
// for (int j=0 ; j<n ; j++ ) for (int k=0 ; k<=tot ; k++ ) f[j][k] = 0;
memset(sum,,sizeof(sum));
memset(f,,sizeof(f)); for (int j= ; j<n ; j++ ) for (int k= ; k<m ; k++ ) if (((i>>k)&)==) {
sum[j] += prob[j][k]-'';
}
f[][] = -;
for (int j= ; j<m ; j++ ) if ((i>>j)&) f[][] *= -;
for (int j= ; j<n ; j++ ) for (int k= ; k<=tot ; k++ ) {
f[j+][k] -= f[j][k];
if (k+sum[j]<=tot) f[j+][k+sum[j]] += f[j][k];
}
for (int j= ; j<tot ; j++ ) cnt[j] += f[n][j];
}
for (int i= ; i<tot ; i++ ) {
ans += (double)cnt[i] * ((double)tot/(double)(tot-i));
}
return ans;
} //Powered by [KawigiEdit] 2.0!