4.26 腾讯笔试-数据分析与技术研究

时间有点久,题意记不清了...
第一题:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 1005
struct node{
    int x,y,m;
    node(){}
    node(int xx,int yy,int mm):x(xx),y(yy),m(mm){}
    bool operator < (const node a) const{
        return y - x*1.0/m > a.y - a.x*1.0/m;
    }
}a[MAXN];
double b[MAXN];
char s[MAXN];
bool vis[MAXN];
int n,m;
int ans,sum;

int main()
{
    scanf("%d %d",&n, &m);
    for(int i = 0 ; i < n ; i++){
        scanf("%d %d", &a[i].x, &a[i].y);
        a[i].m = m;
        b[i] = a[i].y - a[i].x * 1.0 / m;
    }
    sort(a, a+n);
    ans = 0;
    sum = 0;
    for(int i = 0 ; i < n ; i++){
        if(a[i].y - a[i].x * 1.0 / m <= 0)
            break;
        ans += a[i].y;
        sum += a[i].x;
    }
    if(sum % m)
        sum = sum / m + 1;
    else sum = sum / m;
    ans -= sum;

    printf("%d\n",ans);
    return 0;
}
第二题:求抛物线与直线之间的面积。微积分忘光了,搬一份别人的代码...
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int T, A, B, C;
double get(double y)
{
    return y * y/2/B - (1.0*C)/B * y - y*y*y/6/A;
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d %d %d", &A, &B, &C);
        int delta = 4 * A * A - 8 * A * B * C;
        if (delta <= 0)
        {
            printf("0\n");
            continue;
        }
        double a = (2 * A + sqrt((double)delta)) / 2.0 / B;
        double b = (2 * A - sqrt((double)delta)) / 2.0 / B;
        printf("%.6f\n", get(a) - get(b));
    }
    return 0;
}
第三题:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
const int mod = 100003;
#define MAXN 1005
ll n,m;
ll ans, sum;
ll powmod(ll x, ll n, int mod){
    ll res = 1;
    while(n > 0){
        if(n&1LL)
            res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
int main()
{
    scanf("%lld %lld",&m, &n);
    ans = powmod(m, n, mod);
    sum = powmod(m-1, n-1, mod);
    sum = sum * m % mod;
    ans = (ans + mod - sum)%mod;
    printf("%lld\n",ans);
    return 0;
}
第四题:求互补数组。
先已第一个数为基准处理数组,将2 11 21变成0 9 19这种。然后排序,前后两个指针向中间移动找互补的。注意有多个0 0 0的数组可以互相互补。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100005
struct node{
    int id;
    vector<int> a;
    bool operator < (const node p) const{
        for(int i = 0 ; i < a.size() ; i++){
            if(a[i] != p.a[i])
                return a[i] < p.a[i];
        }
        return id < p.id;
    }
}a[MAXN];
int n,m;
ll ans;
bool equ(int p, int q){
    for(int i = 0 ; i < m ; i++){
        if(a[p].a[i] != a[q].a[i])
            return false;
    }
    return true;
}
int ok(int p, int q){
    for(int i = 0 ; i < m ; i++){
        if(a[p].a[i] + a[q].a[i] < 0)
            return -1;
        if(a[p].a[i] + a[q].a[i] > 0)
            return 1;
    }
    return 0;
}
int main()
{
    scanf("%d %d",&n, &m);
    for(int i = 0 ; i < n ; i++){
        int p, q;
        scanf("%d", &p);
        a[i].id = i;
        a[i].a.clear();
        a[i].a.push_back(0);
        for(int j = 1 ; j < m ; j++){
            scanf("%d", &q);
            a[i].a.push_back(q - p);
        }
    }
    sort(a, a+n);
    int l = 0, r = n-1;
    ans = 0;
    while(l < r){
        int l_num = 1;
        int r_num = 1;
        while(l+l_num < r && equ(l, l+l_num)){
            l_num++;
        }
        while(r-r_num > l && equ(r, r-r_num)){
            r_num++;
        }
        int t = ok(l,r);
        if(t == 0){
            if(equ(l, r)){ //多个0 0 0
                ans += 1LL * (r - l + 1) * (r - l) / 2;
            }
            else ans += 1LL * l_num * r_num;
            l += l_num;
            r -= r_num;
        }
        else if(t < 0){
            l += l_num;
        }
        else if(t > 0){
            r -= r_num;
        }
    }
    printf("%lld\n",ans);
    return 0;
}
第五题:先离散化,然后用bfs搜联通块。没想到用并查集...
#include <bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define MAXN 100005
struct node{
    int x,y;
    node(){}
    node(int xx,int yy):x(xx),y(yy){}
    bool operator < (const node a) const{
        if(x == a.x) return y < a.y;
        return x < a.x;
    }
};
vector<int> a[MAXN * 2];
int b[MAXN][2];
int c[MAXN * 2];
char s[MAXN];
bool vis[MAXN * 2];
int n,m;
int ans;
int main()
{
    int tt,ca = 1;
    int p,q;
    scanf("%d",&tt);
    while(tt--){
        scanf("%d", &n);
        memset(vis, 0, sizeof(vis));
        for(int i = 0 ; i < n ; i++){
            scanf("%d %d", &b[i][0], &b[i][1]);
            c[i*2] = b[i][0];
            c[i*2+1] = b[i][1];
        }
        sort(c,c+2*n);
        int nn = unique(c,c+2*n)-c;
        for(int i = 0 ; i < nn ; i++)
            a[i].clear();
        for(int i = 0 ; i < n ; i++){
            p = b[i][0];
            q = b[i][1];
            int pp = lower_bound(c,c+nn,p)-c;
            int qq = lower_bound(c,c+nn,q)-c;
            a[pp].push_back(qq);
            a[qq].push_back(pp);
        }
        ans = 0;
        for(int i = 0 ; i < nn; i++){
            if(vis[i])
                continue;
            vis[i] = true;
            queue<int> que;
            que.push(i);
            int sum = 1;
            while(!que.empty()){
                int t = que.front();
                que.pop();
                for(int i = 0 ; i < a[t].size() ; i++){
                    int q = a[t][i];
                    if(vis[q])
                        continue;
                    vis[q] = true;
                    sum++;
                    que.push(q);
                }
            }
            ans = max(ans, sum);
        }
        printf("%d\n",ans);
    }
    return 0;
}






#腾讯2021暑期实习##笔试题目##腾讯#
全部评论

相关推荐

2 6 评论
分享
牛客网
牛客企业服务