2017-10-6模拟赛T1 手工(handicraft.*)

题目


题解


题意很明显,就不讲了。

我们发现从一个A边形切出一个B边形有几种情况:

1. 得到一个(A-B+2)边形和一个B边形(直线过两顶点);

2. 得到一个(A-B+3)边形和一个B边形(直线过一顶点+一边);

3. 得到一个(A-B+4)边形和一个B边形(直线过两边)。

∴要从一个n边形切出p个m边形至少需要一个((p-1)(m-4)+m)边形(切(p-1)次,一次后变成1个m边形和1个(p-1)(m-4)+4=(p-2)(m-4)+m边形,...)

分情况讨论:(设X=(p-1)(m-4)+m)

①当n<X时,

若m=3,(p-1)(m-4)+m<0,不可能;

若m>3,我们可以每次从n边形中切出一个三角形来使n+1(情况3),直到n=X,再切(p-1)次就可以得到;

②当n=X时,切(p-1)次;

③当n>X时,先切出一个X边形(随你怎么切),再切(p-1)次,总共p次。

于是就欢乐地AK了。

代码


弱弱地问一句,这还需要代码吗?(逃)

原文地址:https://www.cnblogs.com/hotwords/p/7631799.html