这就是一个乱搞题，暴力发现TLE了，然后看了看discuss里说可以矩阵加速，想了一会才想明白怎么用矩阵，分着算的啊。先算f[num[i]-1]之类的，代码太长了，还是找找规律吧。。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define eps 1e-8
int num[];
int judge(double x,double y)
{
double t = x-y;
if(t < )
t = -t;
if(t < eps)
return ;
else
return ;
}
int main()
{
int i,j,n,maxz;
double p,f1,f2;
while(scanf("%d%lf",&n,&p)!=EOF)
{
maxz = ;
for(i = ; i < n; i ++)
{
scanf("%d",&num[i]);
maxz = max(num[i],maxz);
}
sort(num,num+n);
if(num[] == )
{
printf("0.0000000\n");
}
else
{
f2 = ;
f1 = ;
for(i = ; i <= maxz+; i ++)
{
double t;
for(j = ;j < n;j ++)
{
if(num[j] == i)
break;
}
if(j != n)
{
swap(f2,f1);
f2 = ;
}
else
{
t = f2;
f2 = f2*p + f1*(-p);
f1 = t;
}
if(judge(f1,f2))
{
for(j = ;j < n;j ++)
{
if(num[j] > i)
{
i = num[j]-;
break;
}
}
}
}
printf("%.7lf\n",f2);
}
}
return ;
}
乱推推，题意看清楚。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;
#define eps 1e-8
double dp[][];
int in[][];
double dfs(int w,int b)
{
double t;
if(in[w][b])
return dp[w][b];
if(w == )
return ;
t = w*1.0/(w+b);
in[w][b] = ;
if(b >= )
{
if(b- > )
return dp[w][b] = t + b*1.0/(w+b)*(b-)/(w+b-)*(b-)/(w+b-)*dfs(w,b-) + b*1.0/(w+b)*(b-)/(w+b-)*w/(w+b-)*dfs(w-,b-);
else
return dp[w][b] = t + b*1.0/(w+b)*(b-)/(w+b-)*w/(w+b-)*dfs(w-,b-);
}
return dp[w][b] = t;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
printf("%.9lf\n",dfs(n,m));
return ;
}
入门题。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
using namespace std;
#define eps 1e-6
double dp[][];
double w[][][];
int judge(double x)
{
if(x < )
x = -x;
if(x < eps)
return ;
else
return ;
}
int main()
{
int m,n,i,j,k;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i = ;i < n;i ++)
{
for(j = ;j < m;j ++)
{
for(k = ;k < ;k ++)
scanf("%lf",&w[i][j][k]);
}
}
dp[n-][m-] = ;
for(i = n-;i >= ;i --)
{
for(j = m-;j >= ;j --)
{
if(i == n-&&j == m-) continue;
if(judge(w[i][j][]-)) continue;
dp[i][j] = (dp[i][j+]*w[i][j][] + dp[i+][j]*w[i][j][] + )/(-w[i][j][]);
}
}
printf("%.3lf\n",dp[][]);
}
return ;
}
硬做就行，取整符号，你认识吗...
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define eps 1e-8
double dp[];
int in[];
int c[];
int n;
double dfs(int x)
{
int i;
if(in[x])
return dp[x];
double ans,t2;
t2 = ((sqrt(5.0)+))*0.5;
ans = ;
for(i = ;i < n;i ++)
{
if(x > c[i])
ans += (int)(t2*c[i]*c[i]);
else
ans += dfs(x+c[i])+;
}
ans /= n;
in[x] = ;
return dp[x] = ans;
}
int main()
{
int i,f;
while(scanf("%d%d",&n,&f)!=EOF)
{
memset(in,,sizeof(in));
for(i = ;i < n;i ++)
scanf("%d",&c[i]);
printf("%.3lf\n",dfs(f));
}
return ;
}
ZOJ 3380 Patchouli's Spell Cards
这个题，完全就是组合DP的感觉。
题意要求至少有l个，求反面，所有的数字都是0-l-1就行了。
dp[i][j] 前j种，放了i个位置，枚举当前颜色，放0到l-1种，这个问题就是m个位置，插入n个相同的数，以前做过，把n插板，然后从m+1个空里选。
用java第一次TLE了，记忆化了一下fun函数，就过了。
import java.math.BigInteger;
import java.util.Scanner; public class Main {
static BigInteger c[][] = new BigInteger[101][101];
static BigInteger s[][] = new BigInteger[110][110];
static boolean in[][] = new boolean[110][110];
public static BigInteger gcd(BigInteger a, BigInteger b) {
if (b.compareTo(BigInteger.valueOf(0)) == 0)
return a;
else
return gcd(b, a.mod(b));
} public static BigInteger fun(int n, int m) {
int minz, i;
if(in[n][m])
return s[n][m];
if (n == 0 || m == 0)
return BigInteger.valueOf(1);
if (n < m + 1)
minz = n;
else
minz = m + 1;
BigInteger ans = BigInteger.valueOf(0);
for (i = 1; i <= minz; i++) {
ans = ans.add(c[m + 1][i].multiply(c[n - 1][i - 1]));
}
in[n][m] = true;
return s[n][m] = ans;
} public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
BigInteger dp[][] = new BigInteger[101][101];
int i, j, k, n, m, l;
for (i = 0; i <= 100; i++) {
for (j = 0; j <= 100; j++)
c[i][j] = BigInteger.valueOf(0);
}
for (i = 0; i <= 100; i++)
c[i][0] = BigInteger.valueOf(1); for (i = 1; i <= 100; i++) {
for (j = 1; j <= 100; j++)
c[i][j] = c[i - 1][j - 1].add(c[i - 1][j]);
}
while (cin.hasNext()) {
m = cin.nextInt();
n = cin.nextInt();
l = cin.nextInt();
if (l > m) {
System.out.println("mukyu~");
continue;
}
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++)
dp[i][j] = BigInteger.valueOf(0);
}
dp[0][0] = BigInteger.valueOf(1);
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
for (k = 0; k < l; k++) {
if (dp[i][j].compareTo(BigInteger.valueOf(0)) == 0)
continue;
if (i + k > m)
continue;
dp[i + k][j + 1] = dp[i + k][j + 1].add(dp[i][j]
.multiply(fun(i, k)));
}
}
}
BigInteger ans = BigInteger.valueOf(n).pow(m);
BigInteger res = BigInteger.valueOf(0);
for (i = 1; i <= n; i++) {
res = res.add(dp[m][i]);
}
BigInteger t = gcd(ans.subtract(res), ans);
System.out.println(ans.subtract(res).divide(t) + "/"
+ ans.divide(t));
} }
}
感觉是神题呢，这是咋推的,我想了半天，硬做来了个二维的...看别人的题解，直接一位搞定。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int n,num;
double dp[];
double dfs(int step,int m)
{ double ans;
if(step == n)
{
return (m*1.0/num);
}
ans = (m*1.0/num)*(dfs(step+,m-) + );
if(m != num)
ans += (num-m)*1.0/num*dfs(step+,m);
return ans;
}
int main()
{
int m,i;
// while(scanf("%d%d",&m,&n)!=EOF)
// {
// num = m;
// printf("%.9lf\n",dfs(1,m));
// }
while(scanf("%d%d",&n,&m)!=EOF)
{
dp[] = ;
for(i = ;i <= m;i ++)
dp[i] = (-dp[i-])*dp[i-] + dp[i-]*(dp[i-]-1.0/n);
double ans = ;
for(i = ;i <= m;i ++)
ans += dp[i];
printf("%.10lf\n",ans);
}
return ;
}
跟省赛的题非常相似,所有的dp[i]都用o1[i]*dp[0]+o2[i]表示,最后就解出dp[0]来了。
#include <cstdio>
using namespace std;
double o1[];
double o2[];
int main()
{
int n,k1,k2,k3,a,b,c,i,j,k,u,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d%d%d%d%d%d",&n,&k1,&k2,&k3,&a,&b,&c);
for(i = n;i >= ;i --)
{
o1[i] = 1.0/k1/k2/k3;
o2[i] = ;
for(j = ;j <= k1;j ++)
{
for(k = ;k <= k2;k ++)
{
for(u = ;u <= k3;u ++)
{
if(i+j+k+u > n) continue;
if(j == a&&k == b&&u == c) continue;
o1[i] += 1.0/k1/k2/k3*o1[i+j+k+u];
o2[i] += 1.0/k1/k2/k3*o2[i+j+k+u];
}
}
}
}
printf("%.10lf\n",o2[]/(1.0-o1[]));
}
return ;
}