最近挺久没写比赛类的blog了
链接：http://211.140.156.254:2333/contest/59
这次的题目主要考验的是爆搜+打表的能力
其实如果你上来就把所有题目都看过一次就可以知道：正确的顺序是3->1->2
先切T3的意思是你可以很快的爆搜之后开始打表，但T2考思维，T1考语文，这就导致大量的出现前两题A了但最后一题打表时间不够了的情况。
虽然我T2才打表弄了20，但凭借的最后一题的42分表（还忘记把大样例的的两个抄进去了），还是涨了rating。
祝贺CJJ涨了1百多分
T1 重点是理解题意，一定要当一个人跑到最前面的时候下一个人才开始跑。
然后就是一顿乱推了，先把阶乘去掉再n^2枚举，得到u*n/(c[i]-d[i]*(j-1)-v)/n（i=1-n;j=1-n)
然后可以发现两个n可以消去：u/(c[i]-d[i]*(j-1)-v)（i=1-n;j=1-n)
CODE
#include<cstdio>
using namespace std;
typedef double DB;
const int N=;
int n,i,j;
DB v,u,c[N],d[N],ans;
int main()
{
scanf("%d%lf%lf",&n,&v,&u);
for (i=;i<=n;++i)
scanf("%lf",&c[i]);
for (i=;i<=n;++i)
scanf("%lf",&d[i]);
for (i=;i<=n;++i)
for (j=;j<=n;++j)
ans+=u/(c[i]-d[i]*(j-)-v);
printf("%.3lf",ans);
return ;
}
T2 朴素的全排列验证为O((n^2)!)，显然会飞妈（但可以打表出1-4）
仔细观察，因为它们都是01串，就很容易让人想到二进制。
因此所有的串都可以压缩成0-2^n-1之间的数
我们可以用vis[]数组表示这个串（压成数之后）是否被使用，可以发现：
比如一个串010，二进制下记为2，能接在它后面的串为100或101，对应二进制下的4或5
稍微想一下就知道一个串压成数(x)后可以接在它后面的数为x<<1或x<<1|1
也很好理解，整体左移一位后最后一位可能是1或0，就两种情况。
因此我们可以先选0，然后往后找（优先拿1），因为一定有解，因此可以保证正确性。
CODE
#include<cstdio>
using namespace std;
const long long N=(<<)+;
bool vis[N];
long long n,len,i,k;
int main()
{
scanf("%d",&n); len=<<n; vis[]=;
for (i=;i<=n;++i)
putchar('');
for (i=n+;i<=len;++i)
{
k=(k<<)%len;
if (!vis[k+]) vis[++k]=,putchar(''); else vis[k]=,putchar('');
}
return ;
}
T3 难度有一些，没有dalao现场切掉，yu‘ben’ao打表拿了58分（真恐怖）
看一下Manchery的正解
首先要知道约数个数的公式
然后这个题就是把 n!n! 分解质因数 然后把每个质因数的指数分配给A,BA,B，使得他们的指数+1的积相等
这个正如LJN想的一样是可以折半的，但是他跑了20分钟，std却只要400ms，说明这个搜索是很细致的
关键就在于折半的时候怎么分两半
比如现在有 kk 个质因子 ∏kpaii∏kpiai
那么比较直观的是直接枚举在哪mm分开，使得 max{∏m1ai+1,∏km+1ai+1}max{∏1mai+1,∏m+1kai+1} 最小
但这还不是最优的，因为这些质因子最后一段必然都是只出现一次的，这些只会对乘积相等造成×2×2的影响，我们可以在折半之后枚举他
假设有rr个指数是11，那么我们要找的是 max{(∏m1ai+1)×r,∏k−rm+1ai+1}max{(∏1mai+1)×r,∏m+1k−rai+1} 最小
具体可参见std
是不是很diao，但是我们可以打表：
#include<cstdio>
using namespace std;
long long ans[]={,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,};
int main()
{
int n;
scanf("%d",&n);
if (n==) { printf("%lld",); return ; }
if (n==) { printf("%lld",); return ; }
printf("%lld",ans[n]);
}