首页 > 9.6 腾讯-技术研究类和数据分析
头像
zyx_xiao
编辑于 2020-09-06 22:13
+ 关注

9.6 腾讯-技术研究类和数据分析

全A。感觉今天难度倒排

1. 山谷序列,前n个严格递减,后n个严格递增,中间两个数相同,问最长长度。
#include <bits/stdc++.h>
using namespace std;
#define MAXN 10005
#define inf 0x3f3f3f3f
int n, m, T;
int ans;
int a[MAXN], b[MAXN];
int aa[MAXN], bb[MAXN];
int left(int r){
    int c[MAXN];
    int len=0;
    memset(c,inf,sizeof(c));
    for( int i = 1; i <= r; i++){
         int k = lower_bound(c+1, c+r+1, aa[i])-c;
         c[k] = aa[i];
         len = max( len, k );
    }
    return len;
}
int right(int r){
    int c[MAXN];
    int len=0;
    memset(c,inf,sizeof(c));
    for( int i = 1; i <= r; i++){
         int k = lower_bound(c+1, c+r+1, bb[i])-c;
         c[k] = bb[i];
         len = max( len, k );
    }
    return len;
}
int main()
{
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 1 ; i <= n ; i++){
            scanf("%d", &a[i]);
            a[i] *= -1;
            b[n-i+1] = a[i];
        }
        ans = 0;
        for(int i = 1 ; i < n ; i++){
            for(int j = i+1 ; j <= n ; j++){
                if(a[i] != a[j]) continue;
                for(int k = 1 ; k <= n ; k++){
                    aa[k] = a[k];
                    bb[k] = b[k];
                    if(aa[k] > a[i]) aa[k] = a[i];
                    if(bb[k] > a[i]) bb[k] = a[i];
                }
                int l = left(i);
                int r = right(n-j+1);
                ans = max(ans, 2 * min(l, r));
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

2.模拟解方程
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[10];
double eps = 0.0005;
double f(double x){
    double t = x;
    double ans = a[n];
    for(int i = n-1 ; i >= 0 ; i--){
        ans += t * a[i];
        t *= x;
    }
    return ans;
}
int main()
{
    scanf("%d", &n);
    for(int i = 0 ; i <= n ; i++){
        scanf("%d", &a[i]);
    }
    vector<double> ans;
    for(double i = -5000 ; i < 5000 ; i += eps){
        double p = f(i);
        if( fabs(p) < 1e-8){
            ans.push_back(i);
            continue;
        }
        double q = f(i + eps);
        if(p * q <= 0)
            ans.push_back(i + eps/2);
    }
    if(ans.size() == 0)
        printf("No\n");
    else{
        for(int i = 0 ; i < ans.size() ; i++)
            printf("%.2f ", ans[i]);
        printf("\n");
    }
    return 0;
}

3.概率题:长度L,如果超过d,随机折断,扔掉左边。对右边继续操作。问操作次数期望。
#include <bits/stdc++.h>
using namespace std;
int n, m;
double ans;
int main()
{
    scanf("%d %d", &n, &m);
    if(n <= m)
        ans = 0;
    else{
        ans = log(n) - log(m) + 1;
    }
    printf("%.4f\n", ans);
    return 0;
}

4. 排序
#include <bits/stdc++.h>
using namespace std;
int n, m;
int ans;
struct Node{
    vector<int> nums;
    Node(){}
    bool operator < (const Node a) const{
        for(int i = 0 ; i < 6 ; i++){
            if(nums[i] == a.nums[i]) continue;
            return nums[i] < a.nums[i];
        }
        return true;
    }
}a[100005];
int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        for(int i = 0 ; i < n ; i++){
            a[i].nums.resize(6);
            for(int j = 0 ; j < 6 ; j++){
                scanf("%d", &a[i].nums[j]);
            }
            sort(a[i].nums.begin(), a[i].nums.end());
        }
        sort(a, a+n);
        bool flag = false;
        for(int i = 0 ; i < n-1 ; i++){
            bool f = true;
            for(int j = 0 ; j < 6 ; j++){
                if(a[i].nums[j] != a[i+1].nums[j]){
                    f = false;
                    break;
                }
            }
            if(f){
                flag = true;
                break;
            }
        }
        if(flag)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

5. 单源最短路
#include <bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define inf 0x3f3f3f3f
int n, m, T;
int ans;
struct edge{
    int to,cost;
};
typedef pair<int,int> P;  //first是最短距离,second是顶点的编号
vector<edge> G[MAXN];
int d[MAXN];
void dijkstra(int s){
    priority_queue<P,vector<P>,greater<P> > que;
    fill(d,d+n,inf);
    d[s] = 0;
    que.push(P(0,s));
    while(!que.empty()){
        P p = que.top();que.pop();
        int v = p.second;
        if(d[v] < p.first) continue;
        for(int i = 0 ; i <G[v].size() ; i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}
int main()
{
    int x, y, w;
    scanf("%d %d %d", &n, &m, &T);
    for(int i = 0 ; i < n ; i++)
        G[i].clear();
    for(int i = 0 ; i < m ; i++){
        scanf("%d %d %d", &x, &y, &w);
        x--;y--;
        G[x].push_back(edge{y, w});
    }
    dijkstra(0);
    ans = d[n-1];
    dijkstra(n-1);
    ans += d[0];
    printf("%d\n", ans*T);
    return 0;
}


全部评论

(21) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐