程序员经验分享-hwhale

【TODO】2023年秋招笔试未竞

2023-10-26

腾讯20230326笔试三道

米哈游20230813笔试第三题

是计算抽中什么当期五星的期望。
现在的程序结果是99.6087。结果不对，有时间再调。

在这里插入图片描述

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

int n = 90;
double p;
// double min_p = 1e-7;
double min_p = 0.0000000000000001;
vector<vector<double>> dp;

// x 0 保底、1 不保底
// y 0 必、1-89 不必
// acc 累计概率
// 返回抽到当期期望数
double dfs(int x, int y, double acc){
    if(dp[x][y] != -1) return dp[x][y] + 1;
    if(acc <= min_p) {
        // TODO
        cout << x << " " << y << " " << acc << " " << dp[x][y] << "==================" << endl;
        return 1e18;
    }

    double g = 1;

    if(x == 1 && y == 0){
        dp[x][y] = 0.5 + 0.5 * dfs(0, 1, acc * 0.5);
    } else if(x == 0){
        dp[x][y] = p + (g-p) * dfs(0, (y+1) % n, acc * (g-p));
    } else{
        dp[x][y] = p/2 + (p/2) * dfs(0, (y+1) % n, acc * (p/2)) + (g-p) * dfs(1, (y+1) % n, acc * (g-p));
    }
    cout << x << " " << y << " " << acc << " " << dp[x][y] << endl;
    // xxx: 注意！！！要加1
    return dp[x][y] + 1;
}

int main() {
    // int a, b;
    // while (cin >> a >> b) { // 注意 while 处理多个 case
    //     cout << a + b << endl;
    // }
    freopen("D:\\auxiliaryPlane\\project\\scuCode\\input.txt","r",stdin);
	freopen("D:\\auxiliaryPlane\\project\\scuCode\\output.txt","w",stdout);

    // cin >> p;
    p = 0.006;
    // 输出 104.5497057
    // 要求误差在1e-6内

    dp = vector<vector<double>>(2, vector<double>(n, -1));
    // 是否保底，连续没五次数 下次期望
    // 估计一个当前概率阈值
    dp[0][0] = 0;

    cout << dfs(1, 1, 1);
    // cout << 1;
    // cout << min_p;
    // printf("%.3f", min_p);
}
// 64 位输出请用 printf("%lld")

网易雷火0820第2、3、4题

第三题

没调出来

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int n, m, a, b;
vector<bool> vis;
vector<vector<int>> team;
vector<vector<int>> stat;
vector<vector<int>> dp;

void maintain(vector<int> &arr){
    int p = 0, n = arr.size();
    for(int i=0;i<n;i++){
        if(vis[arr[i]]) continue;
        arr[p] = arr[i];
        p++;
    }
    int t = n - p;
    while(t--){
        arr.pop_back();
    }
}

void noABFind(){
    maintain(stat[0]);
    maintain(stat[1]);
    maintain(stat[2]);
    maintain(stat[3]);

    // 根据vis和stat[0]维护dp

    int emp = m-2;
    dp = vector<vector<int>>(m-1, vector<int>());
    for(auto &x: stat[0]){
        if(vis[x]) continue;
        for(int i=m-2;i>0;i--){
            if(dp[i].size()) continue;
            int p = i-team[x][0];
            if(p >= 0){
                if(p == 0 || dp[p].size()){
                    // dp[i] = dp[p];
                    for(auto t: dp[p]) dp[i].push_back(t);
                    dp[i].push_back(x);
                    emp--;
                }
            } else break;
        }
        if(emp == 0) break;
    }
}

void output(vector<int> &x){
    sort(x.begin(), x.end());
    for(auto &y : x) {
        vis[y] = true;
        cout << y + 1 << " ";
    }
    cout << endl;
    
}

int main() {
    // int a, b;
    // while (cin >> a >> b) { // 注意 while 处理多个 case
    //     cout << a + b << endl;
    // }
    
    cin >> n >> m >> a >> b;
    // 只要ab职业和总数不超就加，否则就向后找
    vis = vector<bool>(n, false);    // 用过 或 报名失败
    team = vector<vector<int>>(n, vector<int>());     // 几个a，几个b，几个其他
    stat = vector<vector<int>>(4, vector<int>());

    for(int i=0;i<n;i++){
        int t; cin >> t;
        vector<int> arr = {0, 0, 0, 0};
        for(int j=0;j<t;j++){
            int jt; cin >> jt;
            arr[0]++;
            if(jt == a) arr[1]++;
            else if(jt == b) arr[2]++;
            else arr[3]++;
        }
        team[i] = arr;
        if(arr[1] > 1 || arr[2] > 1) vis[i] = true;

        if(arr[1] == 0 && arr[2] == 0) stat[0].push_back(i);
        else if(arr[1] == 1 && arr[2] == 0) stat[1].push_back(i);
        else if(arr[1] == 0 && arr[2] == 1) stat[2].push_back(i);
        else stat[3].push_back(i);
    }
    
    for(int i=0;i<n;i++){
        if(vis[i]) continue;
        if(team[i][1] == 0 && team[i][2] == 0) continue;
        // 以当前有ab的为首查找
        vector<int> cnt = {team[i][0], team[i][1], team[i][2], team[i][3]};
        vector<int> subans = {i};

        noABFind();
        if(cnt[1] == 1 && cnt[2] == 0){
            // 先找有一个b的
            for(auto &j : stat[2]){
                if(vis[j]) continue;
                int t = team[j][0] + cnt[0];
                if(t > m) continue;
                else if(t == m){
                    subans.push_back(j);
                    output(subans);
                    break;
                } else if(dp[m - t].size() != 0){
                    subans.push_back(j);
                    subans.insert(subans.end(), dp[m-t].begin(), dp[m-t].end());
                    output(subans);
                    break;
                }
            }
        } else if(cnt[1] == 0 && cnt[2] == 1){
            for(auto &j : stat[1]){
                if(vis[j]) continue;
                int t = team[j][0] + cnt[0];
                if(t > m) continue;
                else if(t == m){
                    subans.push_back(j);
                    output(subans);
                    break;
                } else if(dp[m - t].size() != 0){
                    subans.push_back(j);
                    subans.insert(subans.end(), dp[m-t].begin(), dp[m-t].end());
                    output(subans);
                    break;
                }
            }
        } else{
            int t = cnt[0];
            if(t > m) continue;
            else if(t == m){
                output(subans);
            } else if(dp[m - t].size() != 0){
                subans.insert(subans.end(), dp[m-t].begin(), dp[m-t].end());
                output(subans);
            }
        }
        vis[i] = true;
    }


}

// 只过了3.33%

// 8 6 1 2
// 4 1 2 3 3
// 1 1
// 1 1
// 1 3
// 5 3 3 3 4 2
// 4 4 5 6 2
// 1 1
// 1 1



// 64 位输出请用 printf("%lld")

深信服0912B卷3、4题

第三题（背包装满最小数量）

有一些长度的木头数组woods[]，用这些木头拼接length，每根可取无限个，最少需要多少根木头，拼接不出返回-1。其中1<=len(woods)<=100，1<=woods[i]<=1000，1<=length<=10000。样例（对你没看多，字符串格式的数组，自己解析，和4399一样）：

输入：
[1, 2, 3, 5]
9
输出：
3

第四题

现有任务数组t1, t2, t3...tn，每个数表示执行时间，长度为n，现从中挑选k个任务，并保持这k个任务的顺序，将这k个任务分隔为两部分，前一部分给A同学执行，后一部分给B同学执行，每个同学执行时间为任务时间之和，两位同学总时间为两人中的最大时间。问总时间最小是多少，询问T组数据。其中1<=k<=n<=300000，1<=ti<=10^9，T组数据n的总和<=3 * 10^5，样例：

输入：
2
10 6
10 8 18 13 3 8 6 4 14 12
10 5
9 9 2 11 14 33 4 9 14 12
输出：
21
18

腾讯0915重考最后一道

有n个（105 ）点的坐标（1~109），有两种点，红色0和蓝色1，每次可以进行两种操作：

  1. 把红色点坐标+1 / -1；
  2. 把蓝色点变为红色

最多进行第二种操作k次，问最少需要进行第一种操作多少次使得任意两个红色点之间没有蓝色点。

输入n、k、n个点坐标、n个点颜色

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

LL maxx = 1e17 + 1;
int n, k;
vector<LL> x;
vector<bool> c;

vector<int> xr;
vector<int> xb;
// vector<bool> vis;
set<int> sset;


LL ans = maxx;

void cal(){
    // 写暴力都很复杂啊
    vector<int> tr = xr;
    for(auto &i : sset){
        tr.push_back(i);
    }
    sort(tr.begin(), tr.end());
    
    vector<int> tb;
    int last_b = -1;
    int pb = 0, pr = 0;
    // 还得过滤掉 三个蓝色点之间都没有红色点的那个中间蓝色点
    while(pr < tr.size() && pb < xb.size()){
        if(sset.count(xb[i])) {
            pb++;
            continue;
        }
        ...
    }
    
    last_b = -1;
    for(int i=1;i<xb.size();i++){
        pb = xb[i];
        LL subans = 0;
        if(sset.count(xb[i])) continue;
        if(last_b == -1){
            last_b = i;
            for(auto &j : tr){
                if(j < pb) continue;
                subans += x[j] - (x[pb] - 1);
            }
        } else{
            
            for(auto &j : tr){
                if(j < last_b) {
                    subans += x[last_b] + 1 - x[j];
                } else if(j > pb){
                    subans += x[j] - (x[pb] - 1);
                }
                
            }
            last_b = i;
        }
        ans = min(ans, subans);
    }
    // 最右边
    ...
    ans = min(ans, subans);
    
}

void dfs(int p, int cnt){
    if(cnt == k){
        cal();
        return ;
    }
    int m = xb.size();
    if(m - p <= k - cnt){
        for(int i=p;i<m;i++){
//             vis[i] = true;
            sset.insert(i);
        }
        cal();
        for(int i=p;i<m;i++){
//             vis[i] = false;
            sset.erase(i);
        }
        return ;
    }
    dfs(p+1, cnt);
//     vis[p] = true;
    sset.insert(p);
    dfs(p+1, cnt+1);
//     vis[p] = false;
    sset.erase(p);
}

int main(){
    // 所有红点要连成一整片
    cin >> n >> k;
    x = vector<LL>(n);
    c = vector<bool>(n);
    for(int i=0;i<n;i++) cin >> x[i];
    int sum = 0, l = -1, r = -1;
    int cnt_blue = 0;
    vector<int> xt;
    for(int i=0;i<n;i++){
        int t; cin >> t;
        if(t == 0) {
            c[i] = true;
            r = x[i];
            if(l != -1){
                xb = xb.insert(xb.end(), xt.begin(), xt.end());
                sum += cnt_blue;
                cnt_blue = 0;
            }
            if(l == -1) l = x[i];
            xr.push_back(i);
        } else {
            if(l != -1){
                xt.push_back(i);
                cnt_blue++;
            }
            c[i] = false;
        }
    }
//     vis = vector<bool>(xb.size(), false);
    if(sum <= k) {
        cout << 0;
        return 0;
    }
    
    // cout << 0; // 先拿点分
    
    
    // 前i个蓝色的做了k次操作，这个太复杂了，记录状态，还要考虑新变成红色的。
//     vector<vector<LL>> dp(sum + 1, vector<LL>(k + 1, maxx));
//     vector<vector<int>> last(sum + 1, vector<int>(k + 1, -1));
//     for(int i=1;i<=sum;i++){
//         for(int j=0;j<=min(i+1, k);j++){
            
//         }
//     }
    
    // 写暴力吧
    dfs(0, 0);
    cout << ans;
    return 0;
}

字节0917秋招第五场第一题AC自动机

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct TireNode{
    
    int ind;
    TireNode* last;
    vector<TireNode*> next = vector<TireNode*>(26);
    TireNode(int ind){
        ind = ind;
    };
    TireNode(int ind, TireNode* last) {
        ind = ind;
        last = last;
    };
};


vector<int> arr;

TireNode* root;

// void kmp(string par){
//     int m = par.size();
//     arr = vector<int>(m + 1);
//     if(m == 1) return ;
//     // if(par[0] == par[1]) arr[1] = 1;
//     for(int i=1;i<m;i++){
//         int j = arr[i];
//         while(j > 0 && par[j] != par[i]) j = arr[j];
//         if(par[j] == par[i]) arr[i+1] = j + 1;
//         else arr[i+1] = 0;
//     }
// }

void kmp(string par, int index){
    int m = par.size();
    vector<TireNode*> tt;
    if(root->next[par[0] - 'a'] == nullptr){
        TireNode* head = new TireNode(-1, root);
        root->next[par[0] - 'a'] = head;
        if(m == 1) {
            head->ind = index;
            return ;
        }
    } else{
        if(m == 1){
            root->next[par[0] - 'a']->ind = index;
            return ;
        }
    }
    tt.push_back(root->next[par[0] - 'a']);
    
    for(int i=1;i<m;i++){
        // int j = arr[i];
        // while(j > 0 && par[j] != par[i]) j = arr[j];
        // if(par[j] == par[i]) arr[i+1] = j + 1;
        // else arr[i+1] = 0;

        TireNode* j = tt[i];
        while(j != root && )
    }
}

int main() {
    int n, q; cin >> n >> q;
    string str; cin >> str;
    root = new TireNode(0);
    while(q--){
        string t; cin >> t;
        // int m = t.size();
        
        // int cnt = 0;
        // 暴力
        // for(int i=0;i<=n-m;i++){
        //     bool flag = true;
        //     for(int j=0;j<m;j++){
        //         if(str[i+j] != t[j]){
        //             flag = false;
        //             break;
        //         }
        //     }
        //     if(flag) cnt++;
        // }

        kmp(t);
        
        // for(int i=0;i<arr.size();i++){
        //     cout << arr[i] << " ";
        // }
        // cout << endl;
        // int pt = 0;
        // for(int i=0;i<n;i++){
        //     while(pt > 0 && t[pt] != str[i]) pt = arr[pt];
        //     if(t[pt] == str[i]) pt++;
        //     else pt = 0;

        //     if(pt == m){
        //         cnt++;
        //         pt = arr[m];
        //     }
        // }

        
        

        // AC 自动机？


        cout << cnt << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

面经

算法

数据结构

概率论

【TODO】2023年秋招笔试未竞 的相关文章

随机推荐

  • 一文实现：在python中调用matlab程序，保姆级安装windows环境下的matlab.engine教程

    一 前言 我最近在做一个基于图像融合的目标检测工程 我经常用matlab去研究和创新新型的图像融合算法 因为matlab有着python所不可比拟的数据可视化功能和大量的滤波分解框架包 在目标检测等涉及到神经网络的程序编写上 python又

  • 机器学习

    学习目标 了解什么是EM算法 知道极大似然估计 知道EM算法实现流程 一 初识EM算法 EM算法也称期望最大化 Expectation Maximum 简称EM 算法 它是一个基础算法 是很多机器学习领域算法的基础 比如隐式马尔科夫算法 H

  • 2、TCP、多进程并发、多线程并发（linux网络编程）

    三次握手和四次挥手的过程都是在内核实现的 三次握手 通信的时候不再需要SYN标识位了 只有在请求连接的时候需要SYN标识位 传输数据的时候的随机序号seq就是最近一次对方发送给自己的ACK的随机序号值 而发给对方的ACK就是上次刚刚发给对方

  • JDK安装配置教程

    JDK简介 Java Development Kit JDK 是 Sun 公司 已被 Oracle 收购 针对 Java 开发员的软件开发工具包 自从 Java 推出以来 JDK 已经成为使用最广泛的 Java SDK Software d

  • Windows10下安装Git

    Git是一个开源的分布式版本控制系统 可以有效 高速的处理从很小到非常大的项目版本管理 具体安装步骤如下 第一步 先从官网下载最新版本的Git 官网地址 https git scm com downloads 点击上图中表示的地方进行下载

  • 如何修改安卓系统为自己的云服务器,安卓手机改装云服务器

    安卓手机改装云服务器 内容精选 换一换 本节操作介绍华为云上云服务器的跨账号跨区域迁移 建议采用镜像迁移方式 服务器迁移的常见场景与常用的迁移方式请参考迁移的背景知识 跨账号跨区域迁移的方法请参考方案介绍常见的服务器迁移场景包括物理服务器与

  • 【论文精读】Grounded Language-Image Pre-training（GLIP）

    一 背景 https arxiv org abs 2112 03857 https github com microsoft GLIP 这篇论文做的任务是phrase grounding 属于visual grounding的一种 phra

  • MySQL 修改默认值

    alter TABLE tableName alter COLUMN columnName set default defaultValue

  • 电阻式湿度传感器原理

    电阻式湿度传感器是利用湿敏元件的电气特性 如电阻值 随湿度的变化而变化的原理进行湿度测量的传感器 湿敏元件一般是在绝缘物上浸渍吸湿性物质 或者通过蒸发 涂覆等工艺制各一层金属 半导体 高分子薄膜和粉末状颗粒而制作的 在湿敏元件的吸湿和脱湿过

  • 大模型应用落地实践：2大路径、3大痛点、5大革命、6大预判！

    省时查报告 专业 及时 全面的行研报告库 省时查方案 专业 及时 全面的营销策划方案库 免费下载 2023年8月份全网热门报告合集 ChatGPT提词示例 让你的ChatGPT聪明100倍 超百页干货资料 AI应用的难点 痛点与未来 202

  • 双端队列，以顺序表实现双端队列，在队头和队尾添加删除元素

    include

  • opencv之kmeans原理与分割实例

    opencv之K Means原理与实现方法 C 和python版本 KMeans原理 今天记录一下opencv中kmeans中的原理以及图像分割的一个实例 K Means是对数据进行分类的算法 属于无监督学习的一种 首先需要确定对图像进行类

  • 关于QT多界面切换

    1 新增一窗体文件 会自动生成ui1 cpp ui1 h ui1 ui这三个文件 可以进行设计 绑定ui中的控件与数据模型 比如ui gt lable setText string 2 再增加一个UI文件 ui2 也会生成相应的 同上 3

  • 原本是list类型，pandas读入后变成str、obejct等其他的类型，恢复成list，并进行数据炸裂explode操作

    文章目录 本文章拟解决问题 不是这些问题请绕路 一 需求 二 操作步骤 1 从数据库中读入数据 读入的原始数据如图 2 将数据炸裂 将JSON列表拆分 一个JSON对象一行 1 具体的代码过程 踩坑 因为pandas读入数据 将 JSON列

  • XTUOJ 1176 I Love Military Chess(模拟）

    I Love Military Chess Accepted 45 Submit 141 Time Limit 1000 MS Memory Limit 65536 KB 题目描述 陆军棋 又称陆战棋 简称军棋 是中国近代的一种两人棋类 设

  • Niantic CEO访谈：元宇宙、AR眼镜和公司发展史

    Meta宣布转型元宇宙社交平台后 人们一度觉得VR是元宇宙的未来 与此同时 一些AR公司表示不服 认为AR在元宇宙的布局更超前 尤其是Snap Niantic等较成熟的移动端AR公司 对于元宇宙有各自不同的看法和规划 比如 此前Nianti

  • 下载、安装IntelliJ IDEA

    文章目录 一 下载IntelliJ IDEA 二 安装IntelliJ IDEA 三 配置主题与插件 1 设置界面主题 2 配置缺省插件 3 配置特色插件 四 设置IntelliJ IDEA 1 设置编译器用鼠标滚鼠来缩放字号 2 设置编辑

  • uml交互图

    交互图用来描述系统中的对象是如何进行相互作用的 即一组对象是如何进行消息传递的 当交互图建模时 通常既包括对象 每个对象都扮演某一特定的角色 又包括消息 每个消息都代表对象之间的通信活动 并导致一定的动作发生 关键字 对象 顺序 消息 顺序

  • 7.13字节跳动模拟面试

    GDB调试常见命令 进入GDB 取消联系 插入端点 gdb help 查看命令帮助 具体命令查询在gdb中输入help 命令 简写h gdb run 重新开始运行文件 run text 加载文本文件 run bin 加载二进制文件 简写r

  • 【TODO】2023年秋招笔试未竞

    2023年秋招笔试没做完的题 腾讯20230326笔试三道 米哈游20230813笔试第三题 网易雷火0820第2 3 4题 第三题 深信服0912B卷3 4题 第三题 背包装满最小数量 第四题 腾讯0915重考最后一道 字节0917秋招第

热门标签