清北刷题冲刺 10-31 p.m

数列

#include<iostream>

#include<cstdio>

using namespace std;

long long a,b,ans;

void f(long long x,long long y){

    if(y==)return;

    ans+=x/y;

    f(y,x%y);

}

int main(){

    freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);

    cin>>a>>b;

    ans=;

    f(a,b);

    cout<<ans;

}

100分 gcd

车辆销售

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<ctime>

#define maxn 100010

#ifdef WIN32

#define PLL "%I64d"

#else

#define PLL "%lld"

#endif

using namespace std;

int n,m,num,head[maxn],mx,mn=0x7fffffff,cnt;

bool vis[maxn];

struct node{

    int to,pre,v;

}e[*];

void Insert(int from,int to,int v){

    e[++num].to=to;

    e[num].v=v;

    e[num].pre=head[from];

    head[from]=num;

}

int q[maxn],h,t;

int res;

bool flag=,com[maxn];

int bfs(int limit){

    h=;

    while(h<=t){

        int now=q[h];h++;

        if(com[now])continue;

        flag=;

        for(int i=head[now];i;i=e[i].pre){

            if(e[i].v<limit){

                flag=;

                continue;

            }

            int to=e[i].to;

            if(!vis[to]){

                res++;

                vis[to]=;

                q[t++]=to;

            }

        }

        if(flag==)com[now]=;

    }

    return res;

}

int qread(){

    int i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>='')i=i*+ch-'',ch=getchar();

    return i*j;

}

int main(){

//    freopen("Cola.txt","r",stdin);

    freopen("car.in","r",stdin);freopen("car.out","w",stdout);

    n=qread();m=qread();

    int x,y,z;

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

        x=qread();y=qread();z=qread();

        Insert(x,y,z);Insert(y,x,z);

        mx=max(mx,z);mn=min(mn,z);

    }

    long long ans;

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

        ans=;

        memset(q,,sizeof(q));h=t=;

        memset(vis,,sizeof(vis));

        memset(com,,sizeof(com));

        q[t++]=i;vis[i]=;

        res=;

        int p,now;

        for(int j=mx+;j>=mn-;j--){

            if(j<)break;

            now=bfs(j);

            if(j==mx+){p=now;continue;}

            ans+=1LL*(p-now)*(p-now);

            p=now;

        }

        printf(PLL" ",ans);

    }

//    cout<<endl<<clock();

}

30分 bfs暴力

取数

#include<iostream>

#include<cstdio>

#define maxn 1000010

using namespace std;

int n,m,k,a[maxn];

long long ans=;

int qread(){

    int i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>='')i=i*+ch-'',ch=getchar();

    return i*j;

}

void dfs(int pos,int cnt,long long sum){

    if(cnt==k){

        ans=min(ans,sum);

        return;

    }

    if(sum>=ans)return;

    if(pos>=n)return;

    int res=;

    res+=(n-pos)/m;

    if(res*m<n-pos)res++;

    if(res+cnt<k)return;

    if(cnt==){

        for(int i=pos+;i<=n;i++)dfs(i,cnt+,sum+a[i]);

        return;

    }

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

        dfs(i,cnt+,sum+a[i]);

    }

}

int main(){

    freopen("number.in","r",stdin);freopen("number.out","w",stdout);

//    freopen("Cola.txt","r",stdin);

    n=qread();m=qread();k=qread();

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

    dfs(,,);

    cout<<ans;

}

20分 暴力

预计得分100++

实际得分100++

T1有一定的思维量，但是代码很好写，也很容易从辗转相减想到辗转相除。T2T3都写的暴力，T3用的dfs，写的剪枝比较多，所以得到了20分。

感觉这几天以来上午炸的概率比较大，精神状态不好，下午相对还可以。晚上要保证睡眠充足，尽量以较好的精神面貌迎接上午的考试

小结