北京清北综合强化班 Day2

a

【问题描述】

你是能看到第一题的 friends呢。
—— hja
世界上没有什么比卖的这贵弹丸三还令人绝望事了，所以便么一道题。定义 f(x)为满足 (a×b)|x的有序正整数对 (a,b)的个数。现在给定 N，求 Σⁿ_i=1f(i)

【输入格式】

一行个整数 N。

【输出格式】

一行个整数代表答案。

【样例输入】

【样例输出】

【数据范围与规定】

对于 30%的数据， 1≤N≤100。
对于 60%的数据， 1≤N≤1000。
对于 100%的数据， 1≤N≤10^11。

思路:

　　1.一开始写的O(n^3)还以为会超时,结果竟然奇迹的60???

　　2.正解如下:

　　　　根据题意转化成a*b*c<=n
　　　　强行假定a<b<c，求得一个答案，然后直接乘以6.
　　　　所以1<=a<=(根下n 3次方)，即可直接写成:

for(int a=,v; a*a<=(v=n/a); ++a,++ans)

//++ans是因为会有a,a,a的情况,不会出现重复的(在下面弄的话太麻烦,所以直接特殊弄上a*a*a的情况)

    for(int b=a+; b*b<=v; ++b)

        tmp+=n/(a*b)-b;

        //因为在这里的a,b已经确定,所以可以直接把c表示出来,又因为c必须要>b,所以c是从b+1进行取的,所以最后表示的时候需要把b减去,因为如果直接+c的话会多加了b种情况,故-b

ans+=tmp*; //明显排列问题

　　　　但是这样做是不对的,因为a,b,c他们三个的数值不一定是不相等的,还会出现相等的情况((a,a,b)之类的),所以需要把那些相等的排列算上.
　　但是这里就又会出现一个问题:

　　　　重复加该怎么办?
　　当然就是减掉啦!
　　　　减掉的方法:

　　 for(int a=,v; (v=a*a)<=n; ++a) {

　　　　tmp+=n/v;

　　　　if(a*a<=n/a) tmp--;

　　 }

上代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int Maxn = ;

int n,ans,cnt;

int a[Maxn],prime[Maxn],w[Maxn];

bool notprime[Maxn];

void gets() {

    notprime[]=true;

    for(int i=; i<=n; ++i) {

        if(!notprime[i]) prime[++cnt]=i;

        for(int j=; j<=cnt && i*prime[j]<=n; ++j) {

            notprime[i*prime[j]]=true;

            if(i%prime[j]==) break;

        }

    }

    for(int i=; i*i<=n; ++i)

        w[i*i]=;

}

int calc1(int x) { //只能过样例233

    int ret=;

    if(a[x] && a[x]!=) return a[x];

    for(int i=; i<x; ++i)

        if(x%i==) {

            if(w[i]) ret--;

            ret+=calc1(i);

        }

    if(w[x]) ret--;

    return a[x]+ret;

}

int calc2(int x) {

    int ret=;

    for(int i=; i<=x; ++i)

        for(int j=x; j>=; --j) {

            int c=i*j;

            if(x/c*c==x) ret++;

        }

    return ret;

}

int main() {

    freopen("a.in","r",stdin);

    freopen("a.out","w",stdout);

    scanf("%d",&n);

    gets();

    for(int i=; i<=n; ++i) a[i]=;

    a[]=;

    for(int i=; i<=n; ++i)

        if(notprime[i]) a[i]=calc2(i);

    for(int i=; i<=n; ++i)

        ans+=a[i];

    printf("%d",ans);

    return ;

}

#include <iostream>

#include <cstdio>

#define LL long long

using namespace std;

/*

#ifdef unix

#define LL "%lld"

#else

#define LL "%I64d"

#endif

//自适应评测系统

*/

/*

使用方法:

scanf(LL,&n);

printf(LL "\n",n);

*/

LL n,ans,tmp;

int main() {

    scanf("%lld",&n);

    for(LL a=,v; a*a<=(v=n/a); ++a,++ans)

        for(LL b=a+; b*b<=v; ++b)

            tmp+=n/(a*b)-b;

    ans+=tmp*;

    tmp=;

    for(LL a=,v; (v=a*a)<=n; ++a) {

        tmp+=n/v;

        if(a*a<=n/a) tmp--;

    }

    ans+=tmp*;

    printf("%lld\n",ans);

    return ;

}

b

【问题描述】

你是能看到第二题的 friends 呢。
——laekov
Hja 和 Yjq 为了抢男主角打了起来，现在他们正在一棵树上决斗。Hja 在 A 点，Yjq 在 B 点，Hja 先发制人开始移动。每次他们可以沿着一条边移动，但一旦一条边被对方走过了自己就不能再走这条边了。每条边上都有权值，他们都希望自己的权值尽量多。现在给你这棵树以及他们俩开始的位置，问 Hja 能够获得的最大权值。

【输入格式】

第一行两个整数N,M，代表树的点数和询问的个数。
接下来N-1行每行三个整数a,b,c，代表从a到b有一条权值为c的边。
接下来M行，每行两个整数A,B代表一次询问。

【输出格式】

对于每次询问，输出一个整数代表答案。

【样例输入 1】

2 1
1 2 3
1 2

【样例输出 1】

【样例输入 2】

3 2
1 2 3
1 3 1
2 3
1 3

【样例输出 2】

3
4

【数据范围与规定】

30%的数据，1 ≤ N,M ≤ 1000。
另外30%的数据，M = 1。
对于100%的数据，1 ≤ N,M ≤ 10^5 ,0 ≤ c ≤ 10^3 ,1 ≤ a,b,A,B ≤ N。

上代码:

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

using namespace std;

const int M = ;

int n,m,tot,cnt;

int depth[M],pw[M],dad[M][];

int z[M*],value[M],sum[M*][];

int q[M],start[M],end[M];

int top,head[M];

struct edge {

    int to,w,next;

}e[M<<];

void add(int u,int v,int w) {

    top++;

    e[top].to=v;

    e[top].w=w;

    e[top].next=head[u];

    head[u]=top;

}

int jump(int p,int w) { //将p1跳到与p2同样的深度

    if(w==-) return p;

    int x=;

    while(w) {

        if(w&) p=dad[p][x];

        w>>=;

        x++;

    }

    return p;

}

int LCA(int p1,int p2) {

    if(depth[p1]<depth[p2]) swap(p1,p2);

    p1=jump(p1,depth[p1]-depth[p2]);

    int x=;

    while(p1!=p2) {

        if(!x || dad[p1][x]!=dad[p2][x]) {

            p1=dad[p1][x];

            p2=dad[p2][x];

            x++;

        }

        else x--;

    }

    return p1;

} 

int calc(int p1,int p2) {

    if(p1==dad[p2][]) return value[]-value[p2];

    else return value[p1]+pw[p1];

}

int calcp(int p,int v) {

    int l=start[p]-,r=end[p];

    while(l+!=r) {

        int m=(l+r)>>;

        if(v>z[m]) l=m;

        else r=m;

    }

    return r;

}

int main() {

//    freopen("b.in","r",stdin);

//    freopen("b.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=,u,v,w; i<n; i++) {

        scanf("%d%d%d",&u,&v,&w);

        tot+=w;

        add(u,v,w),add(v,u,w);

    }

    depth[]=;

    int h=,t=;

    q[t]=;

    while(h<=t) {

        int now=q[h++];

        for(int i=head[now],v,w; i; i=e[i].next) {

            v=e[i].to,w=e[i].w;

            if(!depth[v]) {

                depth[v]=depth[now]+;

                dad[v][]=now;

                pw[v]=w;

                int p=now,x=;

                while(dad[p][x]) { //不断更新dad值

                    dad[v][x+]=dad[p][x];

                    p=dad[p][x];

                    x++;

                }

                q[++t]=v;

            }

        }

    }

    for (int a=n; a>=; a--) {

        int now=q[a];

        start[now]=cnt+;

        for(int i=head[now],v,w; i; i=e[i].next) {

            v=e[i].to,w=e[i].w;

            if (depth[v]==depth[now]+) {

                z[++cnt]=value[v]+w;

                value[now]+=value[v]+w;

            }

        }

        z[++cnt]=tot-value[now];

        end[now]=cnt;

        sort(z+start[now],z+end[now]+);

        sum[end[now]][]=z[end[now]];

        sum[end[now]][]=;

        for(int b=end[now]-; b>=start[now]; b--) {

            sum[b][]=sum[b+][];

            sum[b][]=sum[b+][];

            if((b&)==(end[now]&)) sum[b][]+=z[b];

            else sum[b][]+=z[b];

        }

        cnt++;

    }

    for (int i=,p1,p2; i<=m; i++) {

        scanf("%d%d",&p1,&p2);

        int lca=LCA(p1,p2);

        int dist=depth[p1]+depth[p2]-*depth[lca];

        int delta=dist/+(dist&);

        int px,px1,px2;

        if(depth[p1]-depth[lca]<delta) px=jump(p2,dist-delta);

        else px=jump(p1,delta);

        if(depth[p1]-depth[lca]<delta-) px1=jump(p2,dist-delta+);

        else px1=jump(p1,delta-);

        if(depth[p2]-depth[lca]<dist-delta-) px2=jump(p1,delta+);

        else px2=jump(p2,dist-delta-);

        int ans=;

        if(p1==px) {

            if(p2==px) ans=sum[start[px]][];

            else {

                int v2=calc(px2,px);

                int p=calcp(px,v2);

                ans=sum[p+][]+sum[start[px]][]-sum[p][];

            }

        } else {

            if (p2==px) {

                int v1=calc(px1,px);

                int p=calcp(px,v1);

                ans=v1+sum[p+][]+sum[start[px]][]-sum[p][];

            } else {

                int v1=calc(px1,px);

                int pp1=calcp(px,v1);

                int v2=calc(px2,px);

                int pp2=calcp(px,v2);

                if (pp2==pp1) pp2++;

                if (pp1>pp2) swap(pp1,pp2);

                ans=v1+sum[pp2+][dist&]+sum[pp1+][-(dist&)]-sum[pp2][-(dist&)]+sum[start[px]][dist&]-sum[pp1][dist&];

            }

        }

        printf("%d\n",ans);

    }

    return ;

}

c

【问题描述】

你是能看到第三题的friends呢。
——aoao
Yjq买了36个卡包，并且把他们排列成6×6的阵型准备开包。

左上角的包是(0,0)，右下角为(5,5)。为了能够开到更多的金色普通卡，Yjq会为每个包添加1-5个玄学值，每个玄学值可以是1-30中的一个整数。

但是不同的玄学值会造成不同的欧气加成，具体如下：
　　1、同一个卡包如果有两相的玄学值会无限大欧气加成。
　　2、同一个卡包如果有两个相邻的玄学值会A点欧气加成。
　　3、相邻的两个卡包如果有同玄学值会B点欧气加成。
　　4、相邻的两个卡包如果有玄学值会C点欧气加成。
　　5、距离为2的卡包如果有相同玄学值会D点欧气加成。
　　6、距离为2的卡包如果有相邻玄学值会E点欧气加成。
以上的所有加成是每存在一个符合条件的就会加一次，如一包卡有1,2,3的玄学值就会加两次。
但是，玄学值是个不可控的东西，即使是Yjq也只能自己决定(2,2),(2,3),(3,2),(3,3)这几包卡的玄学值。

为了能够抽到更多的金色普通卡，Yjq想知道自己能够获得的最少的欧气加成是多少。

注意你只能修改玄学值，不能修改玄学值的个数。

【输入格式】

输入的第一行有5个整数A,B,C,D,E。
接下去有6×6的代表初始的玄学值。
每个玄学值为[n:a1,a2,...,an]的描述形式。

【输出格式】

一行一个整数代表答案。

【样例输入】

5 4 3 2 1
[1:1][1:2][1:3][1:4][1:5][1:6]
[1:1][1:2][1:3][1:4][1:5][1:6]
[1:1][1:2][5:1,2,3,4,5][5:1,2,3,4,5][1:5][1:6]
[1:1][1:2][5:1,2,3,4,5][5:1,2,3,4,5][1:5][1:6]
[1:1][1:2][1:3][1:4][1:5][1:6]
[1:1][1:2][1:3][1:4][1:5][1:6]

【样例输出】

250

【数据规模与约定】

对于100%的数据，1≤A,B,C,D,E≤100,1≤n≤5,1≤ai≤30。
有部分分。

上代码:

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define now pre[a][b][c][d][e][s1][s2][s3][s4]

#define dis(a,b,c,d) (abs(a-c)+abs(b-d))

const int INF=0x3f3f3f3f;

int A,B,C,D,E,num[][],value[][][],delta[][][],dp[][][][][][][][][];

char s[];

bool map[][][][];

int main()

{

    freopen("c.in","r",stdin);

    freopen("c.out","w",stdout);

    scanf("%d%d%d%d%d",&A,&B,&C,&D,&E);

    for (int a=;a<;a++)

    {

        scanf("%s",s);

        int p=;

        for (int b=;b<;b++)

        {

            int px=p;

            while (s[px]!=']')

                px++;

            p++;

            num[a][b]=s[p]-'';

            p++;

            p++;

            for (int c=;c<=num[a][b];c++)

            {

                int v=;

                while (s[p]>='' && s[p]<='')

                {

                    v=v*+s[p]-'';

                    p++;

                }

                value[a][b][c]=v;

                p++;

            }

            p=px+;

        }

    }

    int base=;

    for (int a=;a<;a++)

        for (int b=;b<;b++)

            if (a>= && a<= && b>= && b<=) ;

            else

            {

                sort(value[a][b]+,value[a][b]+num[a][b]+);

                for (int c=;c<=num[a][b];c++)

                    if (value[a][b][c]-value[a][b][c-]==) base+=A;

                for (int c=;c<=;c++)

                    for (int d=;d<=;d++)

                    {

                        if (dis(a,b,c,d)==)

                        {

                            for (int e=;e<=num[a][b];e++)

                            {

                                delta[c][d][value[a][b][e]]+=B;

                                delta[c][d][value[a][b][e]-]+=C;

                                delta[c][d][value[a][b][e]+]+=C;

                            }

                        }

                        if (dis(a,b,c,d)==)

                        {

                            for (int e=;e<=num[a][b];e++)

                            {

                                delta[c][d][value[a][b][e]]+=D;

                                delta[c][d][value[a][b][e]-]+=E;

                                delta[c][d][value[a][b][e]+]+=E;

                            }

                        }

                    }

                for (int c=;c<;c++)

                    for (int d=;d<;d++)

                        if (dis(a,b,c,d)<= && (c!=a || d!=b) && !map[a][b][c][d])

                        {

                            map[a][b][c][d]=map[c][d][a][b]=true;

                            if (c>= && c<= && d>= && d<=) ;

                            else

                            {

                                int dist=dis(a,b,c,d);

                                for (int e=;e<=num[a][b];e++)

                                    for (int f=;f<=num[c][d];f++)

                                    {

                                        if (abs(value[a][b][e]-value[c][d][f])==)

                                        {

                                            if (dist==) base+=B;

                                            else base+=D;

                                        }

                                        if (abs(value[a][b][e]-value[c][d][f])==)

                                        {

                                            if (dist==) base+=C;

                                            else base+=E;

                                        }

                                    }

                            }

                        }

            }

    memset(dp,0x3f,sizeof(dp));

    dp[][][][][][][][][]=base;

    for (int a=;a<;a++)

        for (int b=;b<=num[][];b++)

            for (int c=;c<=num[][];c++)

                for (int d=;d<=num[][];d++)

                    for (int e=;e<=num[][];e++)

                        for (int s1=;s1<=;s1++)

                            for (int s2=;s2<=;s2++)

                                for (int s3=;s3<=;s3++)

                                    for (int s4=;s4<=;s4++)

                                        if (dp[a][b][c][d][e][s1][s2][s3][s4]!=INF)

                                        {

                                            int v=dp[a][b][c][d][e][s1][s2][s3][s4];

                                            for (int sx1=;sx1<=(b!=num[][]);sx1++)

                                                for (int sx2=;sx2<=(c!=num[][]);sx2++)

                                                    for (int sx3=;sx3<=(d!=num[][]);sx3++)

                                                        for (int sx4=;sx4<=(e!=num[][]);sx4++)

                                                        {

                                                            int wmt=;

                                                            if (sx1)

                                                            {

                                                                wmt+=delta[][][a+];

                                                                if (s1) wmt+=A;

                                                                if (s2) wmt+=C;

                                                                if (s3) wmt+=C;

                                                                if (s4) wmt+=E;

                                                            }

                                                            if (sx2)

                                                            {

                                                                wmt+=delta[][][a+];

                                                                if (s1) wmt+=C;

                                                                if (s2) wmt+=A;

                                                                if (s3) wmt+=E;

                                                                if (s4) wmt+=C;

                                                            }

                                                            if (sx3)

                                                            {

                                                                wmt+=delta[][][a+];

                                                                if (s1) wmt+=C;

                                                                if (s2) wmt+=E;

                                                                if (s3) wmt+=A;

                                                                if (s4) wmt+=C;

                                                            }

                                                            if (sx4)

                                                            {

                                                                wmt+=delta[][][a+];

                                                                if (s1) wmt+=E;

                                                                if (s2) wmt+=C;

                                                                if (s3) wmt+=C;

                                                                if (s4) wmt+=A;

                                                            }

                                                            if (sx1 && sx2) wmt+=B;

                                                            if (sx1 && sx3) wmt+=B;

                                                            if (sx1 && sx4) wmt+=D;

                                                            if (sx2 && sx3) wmt+=D;

                                                            if (sx2 && sx4) wmt+=B;

                                                            if (sx3 && sx4) wmt+=B;

                                                            int &t=dp[a+][b+sx1][c+sx2][d+sx3][e+sx4][sx1][sx2][sx3][sx4];

                                                            if (t>v+wmt) t=v+wmt;

                                                        }

                                        }

    int ans=INF;

    for (int a=;a<=;a++)

        for (int b=;b<=;b++)

            for (int c=;c<=;c++)

                for (int d=;d<=;d++)

                    ans=min(ans,dp[][num[][]][num[][]][num[][]][num[][]][a][b][c][d]);

    printf("%d\n",ans);

    return ;

}

巴特西

北京清北综合强化班 Day2

a

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【数据范围与规定】

思路:

上代码:

b

【问题描述】

【输入格式】

【输出格式】

【样例输入 1】

【样例输出 1】

【样例输入 2】

【样例输出 2】

【数据范围与规定】

上代码:

c

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【数据规模与约定】

上代码:

最新文章

热门文章

巴特西

北京清北 综合强化班 Day2

a

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【数据范围与规定】

思路:

上代码:

b

【问题描述】

【输入格式】

【输出格式】

【样例输入 1】

【样例输出 1】

【样例输入 2】

【样例输出 2】

【数据范围与规定】

上代码:

c

【问题描述】

【输入格式】

【输出格式】

【样例输入】

【样例输出】

【数据规模与约定】

上代码:

最新文章

热门文章

北京清北综合强化班 Day2