Regionals 2012, North America – Greater NY 解题报告

这套题。。除了几何的都出了

完全没时间学几何。杯具

 

A,B,J

水题不解释

 

C.Pen Counts

这题的话

写几个不等式限制边得范围就行了

然后枚举最小边

D.Maximum Random Walk

这题的话。

正解是一个n^3的dp

dp[i][j][k] 表示第i步走到第j位置最右为k的概率

然后用滚动数组搞,非常简单。

 

但是还有一种n ^ 2的方法。 被我在比赛中试出来的。

大概是直接记录的第i步走到最右为j的概率

 

 

[cpp][/cpp] view plaincopy

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #define MAXN 111111
  6. #define INF 1000000007
  7. using namespace std;
  8. int st;
  9. double dp[1111][1111];
  10. double L, R;
  11. int main()
  12. {
  13.     int T, cas;
  14.     scanf(“%d”, &T);
  15.     while(T–)
  16.     {
  17.         scanf(“%d%d”, &cas, &st);
  18.         memset(dp, 0, sizeof(dp));
  19.         dp[0][0] = 1;
  20.         scanf(“%lf%lf”, &L, &R);
  21.         for(int i = 1; i <= st; i++)
  22.             for(int j = 0; j <= st; j++)
  23.             {
  24.                 dp[i][j] += dp[i – 1][j + 1] * L + dp[i – 1][j] * (1.0 – L – R);
  25.                 if(j > 0) dp[i][j] += dp[i – 1][j – 1] * R ;
  26.                 else dp[i][j] += dp[i – 1][j] * L;
  27.             }
  28.         double ans = 0;
  29.         for(int i = 1; i <= st; i++)
  30.             ans += dp[st][i] * i;
  31.         printf(“%d %.4f\n”, cas, ans);
  32.     }
  33.     return 0;
  34. }

 

E. Faulhaber’s Triangle

按照题目所说预处理一下就行了

注意中间过程会爆int

F .The King’s Ups and Downs

这题的话。

如果观察能力强的可以推推公式

不行的话。就像我这样用状压DP打表

令dp[i][j][k] 表示第i步,末尾为j士兵,取过的士兵集合为k的方案数

那么有两种,一种是大小大小这样,一种是小大小大这样

所以要求两次

然后打个表就行了。

后来发现第一维没必要。。 因为已经包含在第三维里了

代码就不粘贴了。

G.Mad Veterinarian

逗比题目

不给数据范围

最后发现数据范围巨小,不超过10

然后BFS就行

但是没SPJ。 呵呵

标签