【A. Heroes】
就是一个DFS枚举，然后模拟。
最坏时间3^7 * 7^2
【B. Falling Anvils】
【题目大意】
给定一个方程
。然后p的范围是[0,a]，q的范围是[-b,b]。
p,q在各自区间上等概率分布。
问这个方程有解的概率。
【算法分析】
就是求p-4q>=0的概率。
然后把p看成x，q看成y。然后画出对应的平面图形分类讨论一下即可。高中数学课本的例题阿
代码就这样
if (fabs(b)<1e-9) ret=1;
else
if (a ret=(2*b+a/4)/(4*b); } else{ ret=1-b/a; } 注意b=0的情况。被坑了一次。 【C. Beavermuncher-0xFF】 【题目大意】 给定一棵有根树，每个点上有w[i]只鱼(其实题目是海狸= =)，一开始你在根上。你每走一条边x->y，那么y上要少一条鱼。如果y上没鱼，那么不能走边x->y。现在要求你结束时依然需要站在根处，问你最多能干掉多少条鱼(即最多能走多少步)。 n<=10^5 【算法分析】 首先很容易发现我们可以把走出去的路线分解为很多圈圈，每个圈圈只包含两个点。 于是我们可通过点来划分路径。 考虑一棵以p为根的子树 我们可以以p为分界点把路径分隔开。 那么p下面怎么走和上面无关，只要剩下一条鱼在p上，就足够把p这个子树拼接到fa上。 我们考虑p上的鱼消失的两种方式。 A、从儿子走回来 B、从fa走下来 如果能选A，我们肯定尽量选A。因为如果选了B，那么必须要走回fa那儿去，那么就要同时消耗fa上鱼的数目，这就会影响以后的决策，使得后面取得的鱼变少。 于是这个贪心算法就很显然了。令F[i]表示以i为根，绕一圈回到i最多能吃到多少鱼。(如果i不为根，那么要求最后i上剩的鱼>=1，否则>=0)。 然后每次将自己的儿子按F[i]排个序。然后拼接就好了。 如果拼接完还有在i上的鱼多出来，那么就找个儿子卡能不能抵消。最后输出F[i]即可。 附代码
#include #include #include #include #include using namespace std; const int N=100005; const int oo=0x80000000; int n,S; int w[N]; int fa[N]; int Q[N]; long long F[N]; vector void bfs(){ int head=0,tail=1; Q[1]=S; fa[S]=0; while (head!=tail){ head++; int x=Q[head]; int L=G[x].size(); for (int i=0;i int y=G[x][i]; if (fa[x]!=y){ fa[y]=x; Q[++tail]=y; } } } } bool cmp(int i,int j){ return F[i]>F[j]; } void solve(){ for (int i=1;i<=n;i++) F[i]=oo; for (int j=n;j>=1;j–){ int low_limit= (j==1) ? 0 : 1; int x=Q[j]; int L=G[x].size(); F[x]=0; sort(G[x].begin(),G[x].end(),cmp); for (int i=0;i int y=G[x][i]; if (fa[x]!=y){ if (w[x]>low_limit && w[y]>0){ F[x]+=F[y]+2; w[x]–; w[y]–; } } } for (int i=0;i int y=G[x][i]; if (fa[x]!=y){ if (w[x]>low_limit && w[y]>0){ int delta=min(w[x]-low_limit,w[y]); F[x]+=delta*2; w[x]-=delta; w[y]-=delta; } } } } cout << F[S] << endl; } int main(){ freopen("input.txt","r",stdin); scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&w[i]); for (int x,y,i=1;i scanf("%d%d",&x,&y); G[x].push_back(y); G[y].push_back(x); } scanf("%d",&S); bfs(); solve(); } 【D. Domino Carpet】 【题目大意】 经过一些人肉转换以后，题目变成了m*n个格子，这些格子有3种类型。 1、只允许被2*1的方块覆盖的。 2、只允许被1*2的方块覆盖的。 3、允许被1*2或2*1的方块覆盖的。 然后用2*1或者1*2的格子去完美覆盖这些格子。问有多少种方案。 n,m<=250 还有一个重要条件，假如放了一块1*2的方块占在(i,j)和(i,j+1)，那么就不能存在其它的1*2方块放在(k,j-1)(k,j)或(k,j+1)(k,j+2)。 【算法分析】 由于那个重要条件，我们可以一列一列地dp转移。 要么直接整列竖的2*1方块。要么就是存在1*2方块的两列。 第一种很好算直接F[j+1]+=F[j]。 第二种可以在里面套一个dp。G[i][0]表示到达第i行，还没有放过1*2的方块，这时候的方案数。G[i][1]就是放过2*1的方块的方案数了。 然后F[j+2]+=G[m][1]*F[j]。 【E. Martian Food】 = =，算了10页草稿纸发现算不出来。唉，太弱小了。不会捉。 、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、、 比赛时前3题都是迅速反应出算法，但是第3题写的时候，头脑有点混，悲剧写挂了。今天重打一遍不到10分钟就1Y了 然后就前两题那个沙茶分数排到了DIV I 150+。居然还涨rating了
其实很显然本身就是对的啊。。。
