网易有道笔试题（一）
文章目录
网易有道笔试题（一）前言一、牛牛铺瓷砖（动态规划问题）1.问题描述2.解决方案 二、分模拟赛/分试卷（二分法）1.题目描述2.解决方案 三、单词统计（map，set，数据结构）1.题目描述2.解决方案 四、小易爱回文（综合性问题，回文）1.题目描述2.解决方案 总结前言
准备面游戏研发岗位，特此对算法进行学习
一、牛牛铺瓷砖（动态规划问题）
1.问题描述
牛牛有一块"2n"的空白瓷砖并且有足够多的"12"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件:地毯之间不能相互重叠地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖问你-共有多少种不同的方案并且结果模上10007输出.
输入描述:
第一行输入一个正整数T .表示有T组数据.
接下来T行,每行输入一个正整数n.
1<= T <= 100
1<= n <= 100000
输出描述:
输出T行，每一行对应每组数据的输出，
输入
4
1
2
5
输出
1
2
4
13
2.解决方案
#include<iostream>using namespace std;//设共有f(n)种情况，如果我们先横着放一块1*2的地毯时剩下的情况是f(n-1)，//如果我们先竖着放一块1*2的地毯时剩下的情况是f(n-2)，//如果先放上一块2*3的地毯时剩下的情况是是f(n-3)。//即f(n) = f(n-1)+ f(n-2)+ f(n-3)。n>=4int main(){int T;//输入T组数据cin >> T;int dp[100001]; //dp[1]到dp[100000]为对应n的方案数dp[1] = 1;dp[2] = 2;dp[3] = 4; //初始化for (int i = 4; i <= 100000; i++)//同Fibonacci数列{dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]; //递推}for (int i = 0; i < T; i++) //输入n{int n;cin >> n;cout << dp[n]%100007 << endl;}return 0;}
二、分模拟赛/分试卷（二分法）
1.题目描述
有三种难度的题目难度分别为Easy,Medium,Hard。现在你总共有E+EM+M+MH+H道题，各个字符串的含义如下:
.1. E表示有E道题目难度为Easy。
2. EM表示有EM道题目难度可以为Easy或Medium。
3. M表示有M道题目难度为Medium。
4. MH表示有MH道题目难度可以为Medium或Hard。
5. H表示有H道题目难度为Hard。
你要用这些题目出尽量多的模拟赛，为了保证题目质量且含有一-定的区分度，每场模拟赛需要包含Easy,Medium,Hard三种难度的题目各-道。求你最多能出多少场模拟赛。
输入描述:
-行五个整数E, EM, M, MH, H。
日<= E+EM+M+MH+H <= 1018
输出描述:
一行一个数字表示答案
输入
22122
输出
说明
三组分别是
E+EM+H
E+MH+H
EM+M+MH
2.解决方案
#include<bits/stdc++.h>using namespace std;#define ll long long int//总共有 E+EM+M+MH+H 道题，求最多多少场比赛int main(){ll a[5];for(int i=0;i<5;i++){cin>>a[i];}ll low=0;ll high=1000; //最大场数1000ll mid; //代表二分查找的比赛场数,low和high代表场数的区间范围while(low<=high){mid=low+((high-low)>>1);//a[0]+a[1]，a[3]+a[4]，a[1]+a[2]+a[3] 他们中的最小值决定了场数的上限，//场数的三倍要小于等于所有题目总和，//若if成立，场数太多，需要收缩右边界，否则则需要收缩左边界//比赛场数超出任意一个条件，代表场数过多，就需要收缩右边界，所以用或连接if(mid>a[0]+a[1]||mid>a[3]+a[4]||mid>a[1]+a[2]+a[3]||a[0]+a[1]+a[2]+a[3]+a[4]<3*mid) high=mid-1;else low=mid+1;cout<<low <<'\t'<<mid <<'\t'<<high<<endl;}//二分至最后一次，总是else，因为最后一次是符合条件的，所以是low-1cout<<low-1<<endl;return 0;}
三、单词统计（map，set，数据结构）
1.题目描述
小易今天读了一篇英语文章，他现在想从里面找出一个单词作为这篇文章的关键词，一个单词可以作为关键词当且仅当它在这篇文章中出现的频率不低于1%，现在他想知道有多少个不同的单词可以作为关键词。
2.解决方案
#include<bits/stdc++.h>using namespace std;//直接统计词频即可//ceil向上取整int main(){int n;cin>> n;int edge = ceil(n * 0.01);//超过频率edge的才算关键词// cout<< "n:" << n << endl;map<string, int> mp;set<string> se;for(int i = 0; i < n ;++i){string str;cin>>str;mp[str]++;//mp[str]++; 初始结果为1if(mp[str] >= edge){se.insert(str);}}cout<<se.size() <<endl;return 0;}
四、小易爱回文（综合性问题，回文）
1.题目描述
小易得到了一个仅包含大小写英文字符的字符串，该字符串可能不是回文串。（“回文串”是一个正读和反读都一样的字符串，比如“level”或者“noon”等等就是回文串，“asds”就不是回文串。）小易可以在字符串尾部加入任意数量的任意字符，使其字符串变成回文串。现在请你编写一个程序，程序要能计算出小易可以得到的最短回文串。
输入描述：
一行包括一个字符串s,1<|s|<1e3。1
输出描述:
一行包括一个字符串，代表答案。
1
示例1：
输入：
noon
1
输出：
noon
1
示例2：
输入：
noo
1
输出：
noon
1
示例3：
输入：
helloworld
1
输出：
helloworldlrowolleh
2.解决方案
#include<bits/stdc++.h>using namespace std;bool judge(int start,int end,string s){//判断该部分字符串 是否是回文while(start<end){if(s[start]!=s[end]) break;start++;end--;}if(start==end||s[start]==s[end]) return true;//sds就会出现start=end这种情况||ss字符串就会出现start!=endreturn false;}int main(){string str;cin >> str;int end = str.size()-1;//最后一个字符的位置int start = end;for(int i=0;i<str.size();i++){if(judge(i,end,str)){//如果是回文，返回指向回文的第一个字符的下标start = i;break;}}for(int i=start-1;i>=0;i--){//下标指向回文第一个字符，所以从下标-1到第1个字符进行补充str+=str[i];}cout << str << endl;return 0;}
总结
第一天刷算法，很多都是根据题解来的，然后自己研究每一行代码的意义，有什么作用，总结我真菜
