个小X讨厌的数,又因为最多走p秒所以再枚举一下

作者:澳门娱乐

难题链接

2440: [安阳市选二零一二]完全平方数

Time Limit:10 SecMemory Limit:128 MB
Submit:4920Solved:2389
[Submit][Status][Discuss]

题解:

标题陈说好长啊....

差相当的少正是设一下$f[i]$表示第i秒的最大价值

首先枚举时间,然后因为机器人这一秒无论在哪儿都以有一点都不小只怕的,所以要枚举一下各类点,又因为最多走p秒所以再枚举一下脚下点的前k个点$(1<=k<=p)$

那正是说用个前缀和维护一下那k秒的价值,就能够$n^3$转移了

#include <bits/stdc++.h>
using namespace std;
int f[1010],a[1010][1010],cost[1010],n,m,p;
#define inf 0x3f3f3f3f
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            scanf("%d",&a[i][j]);
        }
    }
    for(int i=1;i<=n;i++)scanf("%d",&cost[i]);
    for(int i=1;i<=n;i++)f[i]=-inf;
    f[0]=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            int sum=0,t=j-1;
            if(!t)t=n;
            sum=a[t][i];
            for(int k=1;k<=p;k++){
                if(i-k<0)break;
                f[i]=max(f[i],f[i-k]+sum-cost[t]);
                t--;if(!t)t=n;
                sum+=a[t][i-k];
            }
        }
    }
    printf("%dn",f[m]);
} 

 

Description

小 X 自幼就很喜欢数。但奇异的是,他煞是厌倦完全平方数。他感觉这个
数看起来很令人痛苦。由此,他也恶感全体是一心平方数的正整数倍的数。但是
那丝毫不影响她对其余数的热衷。
那天是小X的生辰,小 W 想送贰个数给她当做寿辰礼物。当然她不能送一
个小X讨厌的数。他列出了具备小X不讨厌的数,然后接纳了第 K个数送给了
小X。小X非常快乐地收下了。
然而未来小 W 却记不起送给小X的是哪个数了。你能帮她须臾间吗?

Input

满含多组测验数据。文件首先行有一个整数 T,表示测验
多少的组数。
第2 至第T+1 行每行有一个莫西干发型Ki,描述一组数据,含义如题目中所描述。

Output

含T 行,分别对每组数据作出答复。第 i 行输出相应的
第Ki 个不是一心平方数的正整几倍的数。

Sample Input

4
1
13
100
1234567

Sample Output

1
19
163
2030745

HINT

对于 百分之百的数额有 1 ≤ Ki ≤ 10^9

, T ≤ 50

Source

标题大要:求第$n$个无完全平方因子的数

假诺直白硬求得话极度辛苦,因为大家不可能明确枚举的限制,只可以边枚举边计算,但像这种类型一定会T

由此大家转移一下思路,二分二个mid,表示$1-mid$中有多少个无完全平方因子的数

咱俩把$mid$质因数分解为$p_1*p_2*dots p_k$

设$A_i$表示$frac{x}{i*i}$,即$1-x$中含有$i*i$那么些因子的数的个数

那么答案为

$mid - (A_{p_1} + A_{p_2} + cdots + A_{p_k}) + (A_{p_1 cdot p_2} + A_{p_1 cdot p_3} + cdots + A_{p_{k-1} cdot p_澳门娱乐6165,k}) + cdots + ^{k} A_{prod_{i=1}^{k} p_i}$

然后轻便察觉各个的周密即为$mu[k]$,$k$表示分解出来的质数的个数

二个数的平方因子最大为$sqrt$,因而只要枚举到$sqrt$就好

二分的上界有四个公式,设置为$2*x$就好

澳门娱乐6165 1

#include<cstdio>#include<cstring>#include<cmath>#define int long long using namespace std;const int MAXN=1e6+10;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int N;int vis[MAXN],prime[MAXN],mu[MAXN],tot=0;void GetMu(){    vis[1]=1;mu[1]=1;    for(int i=2;i<=N;i++)    {        if prime[++tot]=i,mu[i]=-1;        for(int j=1;i*prime[j]<=N&&j<=tot;j++)        {            vis[i*prime[j]]=1;            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}            else mu[i*prime[j]]=-mu[i];        }    }}int check(int val){    int limit=sqrt,ans=0;    for(int i=1;i<=limit;i++)        ans+=mu[i]*(val/(i*i));    return ans;}main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    N=1e6+10;    GetMu();    int QWQ=read();    while(QWQ--)    {        int x=read();        int l=1,r=x<<1,ans=0;        while(l<=r)        {            int mid=l+r>>1;            if(check>=x) ans=mid,r=mid-1;            else l=mid+1;        }        printf("%dn",ans);    }    return 0;} 

本文由澳门娱乐6165发布,转载请注明来源

关键词: