网站备案查询站长工具,微网站是不是就是手机网站,网站建设及外包,营销型网站设计价格CF传送门 洛谷传送门 【题目分析】 在zxy大佬的讲解下终于懂了这道题的做法了qwq。。。 首先根据题意#xff0c;出发点不一定在特殊点上#xff0c;但第一次操作后#xff0c;之后所有的操作都是在特殊点上#xff0c;所以先考虑从线上出发的最大概率#xff0c;再加一步… CF传送门 洛谷传送门 【题目分析】 在zxy大佬的讲解下终于懂了这道题的做法了qwq。。。 首先根据题意出发点不一定在特殊点上但第一次操作后之后所有的操作都是在特殊点上所以先考虑从线上出发的最大概率再加一步即可得到从点出发的最大概率二者取较大值即可。 记数组f[i][j][k]表示从i点走k步到j点的概率所以转移方程就出来了 然后发现这个形式其实就是矩阵乘法所以可以利用矩阵快速幂优化计算出走2^i步的概率。 但每次都进行一次快速幂的计算复杂度为O(n^3log(q))所以继续优化。 因为我们只需要考虑最后到达t的最大概率所以在进行矩阵乘法的时候很多位置都是没用的所以考虑将初始矩阵简化为一个1*n的矩阵表示走0步到达t的概率显然只有base[t]1其他位置均为0。 然后将操作数进行二进制拆分进行左乘因为初始矩阵只有1行所以不管乘几次都只有一行这样直接优化了一个n的复杂度。 从直线开始就是比从点开始少了一步因为要先走到点上所以就先处理从直线开始走的情况统计答案最后再计算一次就可以得到从点开始走的概率。 考虑构造f[i][j][0]显然从i点走一步到达j点的概率为(1/(经过i点直线数)*直线i,j上的点数)根据这个构造即可。 然后就是各种小细节。。。 1.直线去重这样可以避免进行重复计算。 2.将一个vector的值赋给另一个vector的时候加个传址符会快一点。 3.在计算f数组和base数组的时候如果f[i][j][k]或g[i]已经小于1e-6了那么其实并没有必要继续计算下去了因为精度太小反而可能会爆炸而且题目也说了误差在1e-6以内即可这样大大减少运行时间。 【代码~】 #includebits/stdc.h
using namespace std;
const int MAXN201;
const int MAXM15;int n,q;
int x[MAXN],y[MAXN];
int vis[MAXN],cnt[MAXN];
double ans;
double f[MAXN][MAXN][MAXM1];
double Base[MAXN],zy[MAXN];
vectorint point[MAXN][MAXN];
vectorpairint,int line; inline int Read(){int i0,f1;char c;for(cgetchar();(c9||c0)c!-;cgetchar());if(c-)f-1,cgetchar();for(;c0c9;cgetchar())i(i3)(i1)c-0;return i*f;
}bool check(int a,int b,int c){return (y[b]-y[a])*(x[c]-x[a])(y[c]-y[a])*(x[b]-x[a]);
}int main(){nRead();for(int i1;in;i)x[i]Read(),y[i]Read();for(int i1;in;i){memset(vis,0,sizeof(vis));for(int j1;jn;j){if(ij)continue;if(vis[j])continue;cnt[i];for(int k1;kn;k){if(check(i,j,k)){point[i][j].push_back(k);vis[k]1;}}line.push_back(make_pair(point[i][j][0],point[i][j][1]));}}sort(line.begin(),line.end());line.erase(unique(line.begin(),line.end()),line.end());int siz1line.size();for(int i0;isiz1;i){vectorint vecpoint[line[i].first][line[i].second];int siz2vec.size();for(int j0;jsiz2;j){for(int k0;ksiz2;k){f[vec[j]][vec[k]][0]1.0/siz2*1.0;}}}for(int i1;in;i){for(int j1;jn;j){f[i][j][0]/cnt[i];}}for(int i1;iMAXM;i){for(int j1;jn;j){for(int k1;kn;k){if(f[j][k][i-1]1e-6){for(int t1;tn;t){f[j][t][i]f[j][k][i-1]*f[k][t][i-1];}}}}}qRead();while(q--){int tRead(),stepRead()-1;memset(Base,0,sizeof(Base));Base[t]1;for(int i0;iMAXM;i){if((1i)step)break;if((1i)step){memset(zy,0,sizeof(zy));for(int j1;jn;j){if(Base[j]1e-6){for(int k1;kn;k){zy[k]f[k][j][i]*Base[j];}}}memcpy(Base,zy,sizeof(zy));}}ans0.0;int sizline.size();for(int i0;isiz;i){vectorint vecpoint[line[i].first][line[i].second];double tot0.0;int siz2vec.size();for(int j0;jsiz2;j){totBase[vec[j]];}tot/1.0*siz2;ansmax(ans,tot);}memset(zy,0,sizeof(zy));for(int i1;in;i){if(Base[i]1e-6){for(int j1;jn;j){zy[j]Base[i]*f[j][i][0];}}}memcpy(Base,zy,sizeof(zy));for(int i1;in;i)ansmax(ans,Base[i]);printf(%.10lf\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/Ishtar/p/10010705.html
