EZ 2018 03 09 NOIP2018 模拟赛(三)

时间:2022-12-17 00:10:53

  最近挺久没写比赛类的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=1005;
int n,i,j;
DB v,u,c[N],d[N],ans;
int main()
{
    scanf("%d%lf%lf",&n,&v,&u);
    for (i=1;i<=n;++i)
    scanf("%lf",&c[i]);
    for (i=1;i<=n;++i)
    scanf("%lf",&d[i]);
    for (i=1;i<=n;++i)
    for (j=1;j<=n;++j)
    ans+=u/(c[i]-d[i]*(j-1)-v);
    printf("%.3lf",ans);
    return 0;
}

 

  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=(1<<20)+10;
bool vis[N];
long long n,len,i,k;
int main()
{
    scanf("%d",&n); len=1<<n; vis[0]=1;
    for (i=1;i<=n;++i)
    putchar('0');
    for (i=n+1;i<=len;++i)
    {
        k=(k<<1)%len;
        if (!vis[k+1]) vis[++k]=1,putchar('1'); else vis[k]=0,putchar('0');
    }
    return 0;
}

 

  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,krm+1ai+1}max{(∏1mai+1)×r,∏m+1k−rai+1} 最小

具体可参见std

  是不是很diao,但是我们可以打表:

#include<cstdio>
using namespace std;
long long ans[43]={0,1,0,1,0,1,1,1,0,5,3,5,5,13,11,11,11,13,45,105,136,105,165,332,492,501,482,684,720,1095,1656,3273,3136,3901,4948,6674,7641,15047,12879,17217,38901,75540,37743};
int main()
{
    int n;
    scanf("%d",&n); 
    if (n==50) { printf("%lld",662019); return 0; }
    if (n==100) { printf("%lld",543194779059); return 0; }
    printf("%lld",ans[n]);
}