EZ 2018 03 09 NOIP2018 模拟赛（三）

　　最近挺久没写比赛类的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的正解

首先要知道约数个数的公式

然后这个题就是把

这个正如LJN想的一样是可以折半的，但是他跑了20分钟，std却只要400ms，说明这个搜索是很细致的

关键就在于折半的时候怎么分两半

比如现在有

那么比较直观的是直接枚举在哪

但这还不是最优的，因为这些质因子最后一段必然都是只出现一次的，这些只会对乘积相等造成

假设有

具体可参见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]);
}

秒客网

EZ 2018 03 09 NOIP2018 模拟赛（三）

相关文章