关键词：
一眼题...输出分数格式才是这题的难点QAQ
学习了分数结构体...
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=60,inf=1e9; struct fra{ll u,d;fra(ll a=0,ll b=1){u=a,d=b;}}f[maxn][maxn]; int n,m; bool mp[maxn][maxn]; int readch() { char ch=getchar(); while(ch==‘ ‘||ch==‘ ‘||ch==‘ ‘||ch==‘ ‘)ch=getchar(); return ch==‘*‘; } ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} void sim(fra &x){ll t=gcd(x.u,x.d);x.u/=t;x.d/=t;} fra operator+(fra x,fra y) { ll t=gcd(x.d,y.d); fra c=fra(y.d/t*x.u+x.d/t*y.u,x.d/t*y.d); return sim(c),c; } fra operator*(fra x,fra y) { fra c=fra(x.u*y.u,x.d*y.d); return sim(c),c; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) mp[i][j]=readch(); f[1][1]=fra(1,1); for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) if(mp[i][j])f[i+1][j]=f[i+1][j]+f[i][j]*fra(1,2),f[i+1][j+1]=f[i+1][j+1]+f[i][j]*fra(1,2); else f[i+2][j+1]=f[i+2][j+1]+f[i][j]; printf("%lld/%lld",f[n+1][m+1].u,f[n+1][m+1].d); return 0; }
bzoj千题计划189：bzoj1867:[noi1999]钉子和小球
http://www.lydsy.com/JudgeOnline/problem.php?id=1867 dp[i][j]落到（i，j）的方案数dp[i][j]=0.5*dp[i-1][j] [(i-1,j)位置有钉子]+0.5*dp[i-1][j-1] [（i-1.j-1）位置有钉子]+dp[i-1][j-2] [（i-1，j-2） 查看详情
bzoj1867:[noi1999]钉子和小球dp(代码片段)
设f[i][j]为掉到f[i][j]时的概率然后分情况随便转移一下就好主要是要手写分数比较麻烦#include<iostream>#include<cstdio>usingnamespacestd;constintN=55;intn,m;chara[N][N];longlonggcd(longlonga,longlongb)return!b?a:gcd(b,a%b);s 查看详情
[poj1189][bzoj1867][codevs1709]钉子和小球
...;Description有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排... 查看详情
bzoj1867钉子和小球(代码片段)
题目链接简单$DP$$$dp[1][1]=1( ext显然)$$$$map[i][j]==‘*‘?dp[i+1][j]+=dp[i][j]/2,dp[i+1][j+1]+=dp[i][j]/2:dp[i+2][j+1]+=dp[i][j]$$如果直接输出概率这样就好，但是让写成分数咋整？开个结构体记录分子分母可以(好像大部分人这么做的)本宝宝一开始... 查看详情
bzojnoi1999钉子和小球动态规划+分数类
题目大意：不太好描写叙述，自己看吧。。思路：首先从最上面的点開始考虑。由于球一定是从最上面開始往下掉，所以球经过最上面的点的概率是1，然后他会有1/2的几率向左，1/2的几率向右，也就是以下的两个点均分上面点... 查看详情
poj1189钉子和小球
题目大意：一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排... 查看详情
bzoj3243:[noi2013]向量内积
Description两个d维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和，即：现有n个d维向量x1,...,xn，小喵喵想知道是否存在两个向量的内积为k的倍数。请帮助她解决这个问题Solution首先做一个转换:如果把\(B=A*A^T\... 查看详情
[bzoj]3243向量内积(noi2016)
小C做了之后很有感觉的题目之一，但因为姿势不对调了很久。 Description 两个d维向量A=[a1,a2,...,ad]与B=[b1,b2,...,bd]的内积为其相对应维度的权值的乘积和，即： 现有n个d维向量x1,...,xn，小喵喵想知道是... 查看详情
bzoj1491[noi2007]社交网络
题解：Floyd应用d[i][j]两点最短路c[i][j]两点最短路条数转移若d[i][k]+d[k][j]<d[i][j]则c[i][j]=c[i][k]*c[k][j]若d[i][k]+d[k][j]==d[i][j]则c[i][j]+=c[i][k]*c[k][j];统计答案时当d[s][v]+d[v][t]==d[s][t]则对答案有贡献c[s][v]*c[v][t]/c[s][t] 查看详情
[bzoj4945][noi2017]游戏
题目大意：有$n$个位置，有三种数，每个位置只可以填一种数，$d(dleqslant8)$个位置有三种选择，其他位置只有两种选择。有一些限制，表示第$i$个位置选了某种数,那么第$j$个位置就只能选规定的数输出一组合法的选数方案,无解... 查看详情
bzoj1562[noi2009]变换序列：二分图匹配
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1562题意： 给定n，定义D(x,y)= min(|x-y|,n-|x-y|)，然后给定数组d[i]=D(i,T[i])。 让你求一个0到n-1的排列T，下标i∈[0,n-1]，满足给定的D(i,T[i])，且字典序最小。 若没有答案... 查看详情
[noi2006]神奇口袋
题面在这里题意开始时袋中有(t)种小球,第(i)种小球有(t_i)个,之后每次等概率取出一个球,第(i)次取球时观察这个球的颜色(c_i)放回并向袋中加入(d)个颜色为(c_i)的球;给出一组询问([x_i,y_i](1leilen)),求同时满足第(x_i)次取球的颜色为(y_... 查看详情
bzoj2006noi2010超级钢琴
补了下前置技能……题意就是求一段区间的权值和前k大的子序列的和。把段扔进优先队列每次拿出来之后按照所选择的j进行分裂#include<bits/stdc++.h>#defineN500005#definemp(a,b,c,d)(seg){a,b,c,d}usingnamespacestd;typedeflonglongll;structseg{inti,l,r,... 查看详情
bzoj3240noi2013—矩阵游戏
http://www.lydsy.com/JudgeOnline/problem.php?id=3240 (题目链接)题意 F[1][1]=1 F[i,j]=a*F[i][j-1]+b(j!=1) F[i,1]=c*F[i-1][m]+d(i!=1) 求解F[n][m]，a，b，c，d为常数。Solution 原来费马小定理对于矩阵乘法同样适用。。设a为一矩阵，p为... 查看详情
bzoj1497:[noi2006]最大获利&&3996:[tjoi2015]线性代数
给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D Input第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.接下来一行输入N个整数，代表矩... 查看详情
bzoj_1408_[noi2002]robot_数学
DescriptionInputOutputSampleInput3213251SampleOutput8675HINT 90号机器人有10个老师，加上它自己共11个。其中政客只有15号；军人有3号和5号；学者有8个，它们的编号分别是：2,6,9,10,18,30,45,90。$\sum\limits_d|n\mu(d)=n$因此总和为n。只需要求约数中... 查看详情
bzoj3243[noi2013]向量内积/uoj121
本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。 本文作者：ljh2000作者博客：http://www.cnblogs.com/ljh2000-jump/转载请注明出处，侵权必究，保留最终解释权！ Description两个d维向... 查看详情
bzoj1497:[noi2006]最大获利
1#include<cstdio>2#include<iostream>3#include<cstring>4#defineM1000085#defineinf21390621436usingnamespacestd;7intT,head[M],next[10*M],u[10*M],v[10*M],d[M],n,m,cnt=1,ans,q[2*M],sum;8v 查看详情