记第一次正式线上笔试（Tencent——正式考-技术研发类-综合-2018实习生招聘）

时间：2021-11-26 18:32:20

选择题做的跟傻逼一样，不多说了。。大学只打了ACM还不是计算机科班出身的我，连好多名词都不认识。。。。。

三道编程题很简单，下面给出三道题的大致题意以及题解。

1.给出n和m，满足(2m)可以整除n。求a1~an的和，m表示每m个数变一次符号，ai满足|ai|=i。

例如n=8，m=2，则数列为 -1 -2 3 4 -5 -6 7 8

题解：规律是显然的，每2m个数分别求一下部分和，显然是m*m，然后把所有的部分和累加起来，为n/(2m)*m*m=n*m/2

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;

int main()
{
    LL n,m;
    while(cin>>n>>m)
        cout<<n*m/<<'\n';
}

2.给出X个长为A的小棍和Y个长为B的小棍，恰拼出一个长为K的小棍，其中所有小棍两两颜色不同，拼接时不考虑顺序，求问共有多少种合法方案。

题解：答案就是下面的这个公式

记第一次正式线上笔试（Tencent——正式考-技术研发类-综合-2018实习生招聘）

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;

+;
;

LL qpow(LL x,LL n)
{
    LL ret=;
    )
    {
        ) ret=ret*x%mod;
        x=x*x%mod;
    }
    return ret;
}

LL fac[N],inv_of_fac[N];

void init()
{
    fac[]=;
    ;i<N;i++) fac[i]=fac[i-]*i%mod;
    inv_of_fac[N-]=qpow(fac[N-],mod-);
    ;i>=;i--) inv_of_fac[i]=inv_of_fac[i+]*(i+)%mod;
}

LL C(LL a,LL b)
{
    ) ;
    return fac[a]*inv_of_fac[b]%mod*inv_of_fac[a-b]%mod;
}

int main()
{
    init();
    LL K,A,B,X,Y;
    while(cin>>K>>A>>X>>B>>Y)
    {
        LL ans=;
        ;i<=X&&i*A<=K;i++)
        {
            )
            {
                LL t=(K-i*A)/B;
                ans+=C(X,i)*C(Y,t);
                ans%=mod;
            }
        }
        cout<<ans<<'\n';
    }
}

3.有n台机器和m个任务。每个机器一天有一个最多工作时间（<1000?）和能力level（<100），每个任务有所需时间time（<1000?）和最低所需机器能力level（<100），完成一个任务的对应收益为200*time+3*level，每个机器一天最多一个任务，求问最多一天完成多少任务，如果有多种方案，给出最大收益。

题解：贪心，对机器按照能力为第一关键字，时间为第二关键字，由小到大排序，依次从剩余任务中选取，（能够完成并且总价值最大）的任务，具体的算法见代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

;

struct node
{
    int t;
    int v;
    ;
    node() {}
    node(int t_,int v_)
    {
        t=t_,v=v_,used=;
    }
    bool operator<(const node& rhs)const
    {
        if(used!=rhs.used) return used>rhs.used;
        +v*<rhs.t*+rhs.v*;
    }
};

vector<int> a[N],b[N];
vector<node> c;
int n,m;
LL ans=,ans1=;

void init()
{
    ; i<N; i++) a[i].clear(),b[i].clear();
    c.clear();
    ans=,ans1=;
}

int main()
{
    scanf("%d%d",&n,&m);
    init();
    ; i<n; i++)
    {
        int t,v;
        scanf("%d%d",&t,&v);
        a[v].push_back(t);
    }
    ; i<m; i++)
    {
        int t,v;
        scanf("%d%d",&t,&v);
        b[v].push_back(t);
    }
    ; i<N; i++)
    {
        sort(a[i].begin(),a[i].end());
        ; j<b[i].size(); j++) c.push_back(node(b[i][j],i));
        sort(c.begin(),c.end());
        ; j<a[i].size(); j++)
        {
            ;
            ) continue;
            &&c[pos].used) pos--;
            ) continue;
            c[pos].used=;
            ans1++;
            ans+=c[pos].t*+c[pos].v*;
        }
    }
    printf("%lld %lld\n",ans1,ans);
}

相关文章