这套题。。除了几何的都出了
完全没时间学几何。杯具
A，B，J
水题不解释
C.Pen Counts
这题的话
写几个不等式限制边得范围就行了
然后枚举最小边
D.Maximum Random Walk
这题的话。
正解是一个n^3的dp
dp[i][j][k] 表示第i步走到第j位置最右为k的概率
然后用滚动数组搞，非常简单。
但是还有一种n ^ 2的方法。 被我在比赛中试出来的。
大概是直接记录的第i步走到最右为j的概率
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define MAXN 111111
#define INF 1000000007
using namespace std;
int st;
double dp[1111][1111];
double L, R;
int main()
{int T, cas;scanf("%d", &T);while(T--){scanf("%d%d", &cas, &st);memset(dp, 0, sizeof(dp));dp[0][0] = 1;scanf("%lf%lf", &L, &R);for(int i = 1; i <= st; i++)for(int j = 0; j <= st; j++){dp[i][j] += dp[i - 1][j + 1] * L + dp[i - 1][j] * (1.0 - L - R);if(j > 0) dp[i][j] += dp[i - 1][j - 1] * R ;else dp[i][j] += dp[i - 1][j] * L;}double ans = 0;for(int i = 1; i <= st; i++)ans += dp[st][i] * i;printf("%d %.4f\n", cas, ans);}return 0;
}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。 呵呵
H, I 留坑
