百度麻将笔试 10.15 题解后端卷第一题 贪心n选k 如果选择的数的下一个数没被选，积分+1所以最后一个数一定能拿一分，而在 n/2的转折处1 (2) 3 (4) 5 (6)(n = 6, k = 3) 可以拿三分k = 4 时(1) (2) 3 (4) 5 (6) 仍然可以拿三分，也就是选择了这个1 不会得分但也不会丢分然后注意数字范围取long longwhile(t --){long long int n;long long int k;cin>>n>>k;//n个数里最多可以得n/2 ……//1 - n里假如 n 是奇数 1,2,3可以选2两个数//假如是偶数那可以选long long int res = 0;if(n % 2 == 1) res = n/2 + 1;else res = n/2;//到这里是最多能拿多少分，之后每选一个还得扣if(k <= res) cout<<k<<endl;else{long long int tmp = n + 1;cout<<tmp - k << endl;}}第二题 约瑟夫环问题注意到每一次选择一个数，都能确定下来结果的一位数比如 1 2 3 4第一次1到队尾，我们就能确定2是结果里的第一位，并且每一次都能确定下来一位所以本质是约瑟夫环问题代码就不放了，我是用队列模拟的第三题 麻将想了半天dp想不出来，那就搜索一下试试，刚好过了——————//dp想破头想不出来//试一下搜索//广度优先搜索//每一轮找刻子或者顺子//然后四轮后找雀头//找得到就res ++//数据量应该支持//哈希表记录一下stringunordered_set<string> uset;void dfs(vector<int> &v,int round){if(round == 4){for(int i = 0;i<v.size();i++){if(v[i] >= 2){v[i] -=2;string tmp;for(int j = 0;j < v.size();j++){tmp.push_back(v[j] + '0');tmp.push_back(j + '0');}v[i] += 2;uset.insert(tmp);}}return;}//dfs//先搜刻子，再搜顺子for(int i = 0;i<v.size();i++){if(v[i] >= 3){v[i] -= 3;dfs(v, round + 1);v[i] += 3;}}for(int i = 1;i < v.size()-1;i++){if(v[i-1] >= 1 && v[i] >= 1 && v[i + 1] >= 1){v[i - 1] --;v[i] --;v[i + 1] --;dfs(v,round + 1);v[i - 1] ++;v[i] ++;v[i + 1] ++;}}}int main() {int n;cin>>n;if(n <= 3) cout<<0;else{vector<int> vo(n);fill(vo.begin(),vo.end(),4);dfs(vo, 0);cout<<uset.size()<<endl;}}

第一题dp，第一次卡在中间dp过程要取最大值，第二次卡在数组大小宽度要设置成1000```c++#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;int main(){int t;cin>>t;const int N = 505;const int B = 1005;while (t--){int arr[N];int box,num,single;cin>>box>>num>>single;for(int i =1;i<=num;i++){cin>>arr[i];}if(single>=box){cout<<"YES"<<endl;continue;}//calbool dp[N][B];for(int i = 0;i<B;i++)dp[0][i]=0;//只有num个物品//dp[a][b]表示选择装了前a个东西能塞满b个空间//2 3 5 7//dp[0][...]=0//dp[1][01]=0,dp[1][2]=1,dp[1][3]...=0//dp[2][01]=dp[01],dp[2][2]=1,dp[2][3]=1,dp[2][4]=0(从dp[1][1]转移过来,为0)dp[2][5]=1()for(int i = 1;i<=num;i++){for(int j = 0;j<B;j++){//如果放不下，就复制//放得下,dp[i][j]=dp[i-1][j-arr[i]]if(arr[i]>j)dp[i][j]=dp[i-1][j];else if(arr[i]==j) dp[i][j]=1;else if(arr[i]<j)//要么放进去，要么不放进去dp[i][j]=max(dp[i-1][j-arr[i]],dp[i-1][j]);}}bool res=false;//只要满足[box-single,box]的区间就能装满for(int i = box;i>=box-single;i--){if(dp[num][i]==true)res=true;}if(res)cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;}```第二题贪心，每一次往前看的时候如果是升序序列就选符合条件下尽量小的，反之亦然```c++#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;const int N = 1e5+10;int arr[N];int brr[N];int main(){int n;cin>>n;while(n--){int size;cin>>size;for(int i=0;i<size;i++){scanf("%d",&arr[i]);}for(int i=0;i<size;i++){scanf("%d",&brr[i]);}int res1=true;//升序和降序都试一次，每一次选择符合条件的且//升序的时候更小的，降序的时候更大的int cur =0;cur = min(arr[0],brr[0]);for(int i = 1;i<size;i++){int a = arr[i];int b = brr[i];if(a>=cur && b>=cur){cur = min(a,b);}else if(a<cur && b<cur){res1 = false;break;}else{cur = max(a,b);}}bool res2=true;int cur2 =0;cur2 = max(arr[0],brr[0]);for(int i = 1;i<size;i++){int a = arr[i];int b = brr[i];if(a<=cur2 && b<=cur2){cur2 = max(a,b);}else if(a>cur2 && b>cur2){res2 = false;break;}else{cur2 = min(a,b);}}if(res1||res2)cout<<"YES"<<endl;else cout<<"NO"<<endl;}return 0;}```