C 我没有发票QWQ题目分析给定 n 家独立酒店第 i 家跑路概率为 p%, 求恰好 k 家跑路的概率。解题思路这里我们采用动态规划的思想。根据题目我们可以得到这样一个关系式前 i 家酒店恰好 j 家跑路的概率 前 i - 1 家酒店恰好 j 家跑路的概率 * (1 - p%) 前 i - 1 家酒店恰好 j - 1 家跑路的概率 * p%即 dp[i][j] dp[i - 1][j] * p% dp[i - 1][j - 1] * p%.代码实现#includebits/stdc.husingnamespacestd;doublep[2005];//每个商家对应的跑路概率doubledp[2005][2005];//记录前 i 家酒店恰好 j 家跑路的概率voidsolve(){intn,k;cinnk;for(inti0;in;i){for(intj0;jn;j)dp[i][j]0;}dp[0][0]1;for(inti1;in;i){cinp[i];p[i]/100;}for(inti1;in;i){for(intj0;ji;j){dp[i][j]dp[i-1][j]*(1-p[i])dp[i-1][j-1]*p[i];}}coutsetprecision(10)dp[n][k];}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);solve();return0;}H 校园供水系统题目分析一共有 n 个宿舍楼p 个管道并给出每个管道的方向及距离要我们求出水箱-水龙头的数量并按照水箱从小到大输出水箱、水龙头、这条道路中管道直径的最小值.解题思路由于每个点最多只有一个入度和一个出度因此整个图只能由若干条互不相交的链和若干个环组成。链的起点入度为 0、出度为 1需要安装水箱 链的终点入度为 1、出度为 0需要安装水龙头 链的中间点入度和出度都为 1从每个链的起点出发沿着出边不断向后走依次经过中间点直到到达终点。遍历过程中用变量记录路径上所有边权的最小值这个最小值就是该水箱到水龙头能安全输送的最大水量。对于环所有点入度出度1和孤立点入度出度0它们不构成水箱-水龙头对直接跳过即可。最后将所有找到的链按起点编号从小到大排序输出。代码实现#includebits/stdc.husingnamespacestd;inten[1010];//每个点的入度intout[1010];//每个点的出度intto[1010];//点与点之间的关系intdist[1010];//管道的直径大小intvia[1010];//是否遍历过structfunc{//定义结构体用来存储答案intstart,end,min_dist;}ans[1010];voidsolve(){intn,p;cinnp;for(inti1;in;i){ans[i].start-1,ans[i].end-1,ans[i].min_dist0;}for(inti1;ip;i){intu,v,d;cinuvd;en[v];out[u];to[u]v;dist[u]d;}intcnt0;for(inti1;in;i){if(en[i]0out[i]1via[i]0){//确定起点即水箱inttem_ddist[i];via[i]1;inttemto[i];while(via[tem]0en[tem]1out[tem]1){//确定中间点tem_dmin(tem_d,dist[tem]);via[tem]1;temto[tem];}via[tem]1;if(out[tem]0en[tem]1){//确定终点即水龙头cnt;ans[cnt].starti,ans[cnt].endtem,ans[cnt].min_disttem_d;}}}//输出答案coutcntendl;for(inti1;icnt;i){coutans[i].start ans[i].end ans[i].min_distendl;}}intmain(){ios::sync_with_stdio(false);cin.tie(0);solve();}