2020.09.18-京东笔试复盘+“赛码网”笔试总结
一、京东
选择题，30个，30*2
考了很多：
1）shell脚本
2）C++基础
3）排序算法，快速排序，稳定排序
4）几个SQL语句
考完后收集大家的：
第一题背包卡9%，想贪心混点分居然直接a了 第二题并查集没优化合并，居然也直接a了 这次的题目用例太水
（1）道具的魅力值
考点：多重背包
我记得是“动态规划”，但是忘记怎么写了。
PS：考完后，有人告诉我“贪心”AC了100%，这就很显然，表明这次笔试，第一次的样例很水，这题的做法，“贪心”是不正确的，“动态规划”才是正解，比如下面的“贪心”就显然会错
作者：叽叽叽叽唄吡唄 链接：https://www.nowcoder.com/discuss/514954?type=post&order=time&pos=&page=1&channel=1009&source_id=search_post 来源：牛客网 第一题贪心为啥可以啊， 例如假如三个商品： 1.价格5 荣誉值6 2.价格3 荣誉值4 3.价格2 荣誉值3 如果你拥有的钱为5 正确的解法应该是2+3，荣誉值为7 但是贪心算法要么选择第一个商品、要么2个第三个商品，荣誉值都为6，
道具的魅力值 时间限制： 1000MS 内存限制： 65536KB 题目描述： 在某网络游戏中提供了一个道具库，在道具库中每种道具均有若干件（数量已知），游戏玩家购买一件道具将获得一定的魅力值。 已知每种道具的价格和魅力值，请编写一个程序，在总价格不超过某个上限的情况下使得所购道具的魅力值之和达到最大。 输入描述 单组输入。 每组测试数据的输入有n+1行，n表示道具的种类。 第1行包含两个正整数，分别表示道具种类数n和总价值的上限p，两个数字之间用空格隔开。 （n<=100，p<=10000） 第2行到第n+1行分别对应于第1种道具到第n种道具的信息，每1行包含三个正整数，两个数字之间用空格隔开，三个正整数分别表示某一种道具的数量、单个道具的价格和魅力值。 输出描述 每组测试数据的输出只有一行，即道具魅力值的最大和。 样例输入 3 10 2 2 3 1 5 10 2 4 12 样例输出 27 规则 请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果 点击“调试”亦可保存代码 编程题可以使用本地编译器，此页面不记录跳出次数
代码
#include<bits/stdc++.h>
using namespace std;
//考点：背包问题
int n,up;
const int maxn=105;
int solve[maxn][3];
int main()
{
while(~scanf("%d%d",&n,&up))
{
for(int i=0;i<n;++i)
{
//中间是价值，左边是num，可以减枝
scanf("%d%d%d",&solve[i][0],&solve[i][1],&solve[i][2]);
}
}
return 0;
} 二、小明去旅游
考点：并查集
小明去旅游 时间限制： 1000MS 内存限制： 65536KB 题目描述： 小明想去X星球旅游，X星球有很多很多旅游景点。有些旅游景点之间有道路相连，有些旅游景点之间没有。 如果景点a和b之间有道路相连，b和c之间有道路相连，那么意味着a和c之间也有道路相连。 小明有若干次询问，每个询问包含两个数字，表示两个旅游点之间是否有道路相连。 输入描述 单组输入。 输入的第1行包含三个正整数n、m和q，分别表示有n个旅游景点（编号为1-n），m条道路和q个查询，三个正整数之间用空格隔开。(n<=10000, m<=10000, q<=10000) 接下来m行，每行包含两个正整数u和v，表示编号为u的旅游景点和编号为v的旅游景点之间有道路相连，两个数字之间用空格隔开。 再接下来q行，每行也包含两个正整数x和y，查询编号为x的旅游景点和编号为y的旅游景点之间是否存在道路相连，两个数字之间用空格隔开。 输出描述 针对每一次查询，输出是否有道路相连，如果有请输出“YES”，否则输出“NO”。 样例输入 3 2 3 1 2 2 3 3 2 2 1 1 3 样例输出 YES YES YES 规则 请尽量在全场考试结束10分钟前调试程序，否则由于密集排队提交，可能查询不到编译结果 点击“调试”亦可保存代码 编程题可以使用本地编译器，此页面不记录跳出次数
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=10000+5;
//改为1000有下面
//说明：
//所有测试数据正确率为 27%！，所以我怀疑是题目的内存要求太高了
//可以尝试再次完善代码，并调试，争取全部AC通过
int tag[maxn][maxn];
int n,m,q;
void solve()
{
for(int i=1;i<=n;++i)
{
tag[i][i]=1;
}
for(int i=1;i<=n;++i)
{
for(int j=i+1;j<=n;++j)
{
if(tag[i][j])
{
for(int num=1;num<=n;++num)
{
if(tag[j][num])
{
tag[i][num]=1;
tag[num][i]=1;
}
}
}
}
}
}
int test(int s)
{
if(s<1)
{
return 0;
}
if(s>n)
{
return 0;
}
return 1;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&q))
{
memset(tag,0,sizeof(tag));
for(int i=0;i<m;++i)
{
int a,b;
scanf("%d%d",&a,&b);
if( (test(a)&&test(b)) )
{
tag[a][b]=1;
tag[b][a]=1;
}
}
solve();
for(int i=0;i<q;++i)
{
int a,b;
scanf("%d%d",&a,&b);
//判读是否合法查询
if(!(test(a)&&test(b)))
{
printf("NO\n");
continue;
}
if(tag[a][b])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
}
return 0;
} //用例1 运行结果： // //说明：测试数据未输出正确结果！ // //运行内存：1844 KB // // //错误信息： //你的输出为：Runtime Error:Segmentation fault //这个都能出错，很怀疑这个OJ
二、“赛码网”笔试注意事项
0、“赛码网”开局随机发卷时间
- 开局随机发卷时间在5分钟之内，看自己运气，但是不要担心，随机的那些时间，会补给你的，只是，干等着还是无聊的，23333，我这次随机了二分多钟
1、选择题
- 1)选择题代码格式，有时候有误，最好问问监考人员，都会回答的!
- 2)“赛码网”体验不如牛客，选择题经常点下一题没反应，需要等上几秒。（有待考察，本次笔试还行）
2、可以用本地IDE吗？
- 能不能用本地IDE和笔试网站无关，和公司的要求有关。会有说明的。
3、笔试代码调试
- 1）笔试题的提交有冷却时间，15秒，很不喜欢这个功能。
- 2）提交完还要点保存。（有待考察）
