工作室小测的部分记录-171主机测评

文章目录

6-1 组队
- 题目描述
- 输入格式
- 输出格式
- 输入样例
- 输出样例
- 说明
6-7 小潘的最小因子和问题
- 输入格式:
- 输出格式:
- 输入样例1:
- 输出样例1:
- 输入样例2:
- 输出样例2:
6-8 Knowledge
- 题目描述
- 输入格式:
- 输出格式:
- 输入样例:
- 输出样例:
6-9 qspc-2002-最小花费爬楼梯
- 题目描述：
- 说明：
- 输入样例2：
- 说明：
6-10 铺地砖
- 题目描述
- 输入格式
- 输出格式
- 输入样例
- 输出样例
6-11 任何一个自然数m的立方均可写成m个连续奇数之和
- 输入格式:
- 输出格式:
- 输入样例1:
- 输出样例1:
- 输入样例2:
- 输出样例2:
n³拆分为n个连续奇数之和完整推导
- 前提设定
- 等差数列求和公式代入
- 化简求和表达式
- 联立总和等于 $n^3 n3建立等式$
- 推导首项公式
- 推导末项公式
- 校验数列数量正好为n个
6-12 房屋分拆
- 题目背景
- 输入格式:
- 输出格式:
- 输入样例:
- 输出样例:
总结一下

6-1 组队

题目描述

你的团队中有

$n$ 个人，每个人有一个能力值

$ai$ ，现在需要选择若干个人组成一个团队去参加比赛，由于比赛的规则限制，一个团队里面任意两个人能力的差值必须要小于等于

$k$ ，为了让更多的人有参加比赛的机会，你最多能选择多少个人参加比赛？

输入格式

第一行一个整数

$T$ ，表示案例组数。

每个案例有两行：

第一行两个正整数

$n$ ,

$k$ ，表示人的数量。

第二行

$n$ 个以空格分隔的整数

$a$ i ，表示每个人的能力值。

输出格式

每个案例输出一行，表示可以参加比赛的最多人数。

输入样例

在这里给出一组输入。例如：

1 5 3 8 3 5 1 6

输出样例

在这里给出相应的输出。例如：

说明

选择能力值为

$3$ ,

$5$ ,

$6$ 或者

$5$ ,

$6$ ,

$8$

其实这个题就是一个序列的问题但可以化为子数组，关键的问题就是子序列里的两个数如何做到两两差值小于k,其实很好想，我只要排序然后对于排完序的那一段最大值减最小值都小于k了，那它肯定就满足题意了，那么不小于呢，那就吐出那个最小数，用第二小的数来进行减法，以此类推，不过我在这里思考最快的方法是啥，首先想看暴力解：

#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T;
cin >> T;
while (T–) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
int maxlen = 0;
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = i; j < n; j++) {//初始为i就是要比它大，进行减法。
if (a[j] – a[i] <= k) {
count++;
} else {
break;
}
}
maxlen = max(maxlen, count);
}
cout << maxlen <<endl;
}
return 0;
}

而其实我在看这个题的时候想到了滑动窗口，其实也可以看做双指针解法：

#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t–){
int n,k;
cin>>n>>k;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end());
int left=0;
int maxlen=0;
for(int right=0;right<n;right++){
while(a[right]-a[left]>k){
left++;//和我前面说的一样。只要存在差值比k大的。那就直接吐出最小元素，用稍大一点的。
}
maxlen=max(maxlen,right-left+1);
}
cout<<maxlen<<endl;
}
}

那它是否为最优解呢？其实可以说就是的，为啥？因为这个题少说也要遍历数组要O（N)的解法，如果说不排序的话，就要用哈希表了，其实这样的时间依然是O（nlongn)的，不过空间更大，因此滑动窗口其实已经很优秀了。

6-7 小潘的最小因子和问题

小潘是个思维活跃的帅气BOY，一天，他想到一个问题：对于任一整数M（M>=2）,可以写出等式 M=1* a1*a2… *an (n>=1，a1<=a2…<=an)。显而易见，这样的式子可能有很多个。例如，12=1* 2*2*3，12=1*2*6，12=1*3*4等。现在，他想知道这些式子中，a1+a2…+an最小的那一个组合，请你编程实现这个问题。

输入格式:

第一行一个整数T，表示有T组测试用例。接下来T行，每行一个整数M。2<=M<=1000000。

输出格式:

对于每组测试用例，在一行中输出满足上述题意的式子。

输入样例1:

1 18

输出样例1:

18=1*2*3*3

输入样例2:

2 2 9

输出样例2:

$1$ *

$2$ 9=1*3*3 这个题要我来看就是在分解质因数，为啥呢?其实就是源于乘积固定时，数字越接近，总和越小，所以说在任何合数都可以拆成更小质数相乘，拆分后数字总和一定降低情况下，想要总和最小，唯一最优拆分：把 M 完全分解成全部质因数，所以代码如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
cin>>t;
while(t–){
int n;
cin>>n;
int num=n;
vector<int> ans;
ans.push_back(1);
for(int i=2;i*i<=n;i++){//分解质因数
while(n%i==0){
ans.push_back(i);
n/=i;
}
}
if(n>1) ans.push_back(n);
cout<<num<<"=";
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-1) cout<<"*";
}
cout<<endl;
}
return 0;
}

6-8 Knowledge

题目描述

每个人的学识水平化为

$0$ ~~

$9$ ，用0~9表示其学识高低程度。众所周知，与新生婴儿讨论微积分是一个非常扯淡的事情，所以，学识不为0的人群才可以参与讨论，现在给定一个

∗

m*n

$m * n$ 的人群，给定每个人的文化程度，每个人仅可和上下左右进行讨论，所以请你求出学术讨论组的个数。

输入格式:

用空格隔开的整数

$m$ ，

$n$ (

$m$ 行，

$n$ 列)矩阵(1≤

$m$ ，

$n$ ≤100)。

输出格式:

学识组的个数。

输入样例:

在这里给出一组输入。例如：

4 10 0674800011 1034560500 0039600651 0000000098

输出样例:

在这里给出相应的输出。例如：

4 这个题本质上是个搜索类的题，其实就会想到DFS和BFS，但我觉得可以并查集，为啥，因为这是个无向连通块问题，本质来说并查集适合一维的连通块问题，当其实可以用来解二维的，只要降维就行了，代码如下：

#include <bits/stdc++.h>
using namespace std;
const int MAX=100010;
int father[MAX];
bool flag[MAX];
int Mysize[MAX];
void init(int n) {
for (int i = 0; i < n; i++) {
father[i]=i;
flag[i]=false;//本质上来说要默认每个人的学识都是0
Mysize[i]=1;
}
}
int find(int x) {//压缩性
if (x != father[x]) {
father[x]=find(father[x]);
}
return father[x];
}
void Union(int x,int y) {//大挂小
int px=find(x);
int py=find(y);
if (px!=py) {
if (Mysize[px]>Mysize[py]) {
Mysize[px]+=Mysize[py];
father[py]=px;
}else {
Mysize[py]+=Mysize[px];
father[px]=py;
}
}
}
bool is_same_set(int x,int y) {
return find(x)==find(y);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int m,n;
cin>>m>>n;
init(m*n);
vector<string> grid(m);
for (int i = 0; i < m; i++) cin>>grid[i];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int index=i*n+j;//将维度操作用行*总列数+列
if (grid[i][j]!='0') {//标记那些不为0的
flag[index]=true;
}
}
}
//为啥这里只要向右向下来看呢，其实我们在判读旁边的元素的时候也把它的右下判断了，相当于把当前元素的左上也看过了，可以减少重复判断
int dx[]={0,1};
int dy[]={1,0};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int index1=i*n+j;
if (!flag[index1]) continue;//如果当前元素已经是0了，那就丢
for (int k = 0; k < 2; k++) {//再看他的右下
int x=i+dx[k];//旁边的行数
int y=j+dy[k];//旁边的列数
if (x>=m||y>=n) continue;
int index2=x*n+y;//再次降维
if (flag[index2]) {//如果不是0
Union(index1,index2);//就合并
}
}
}
}
int count=0;
for (int i = 0; i < m*n; i++) {
if (flag[i]&& find(i)==i) {//如果是在同一个连通块里就++
count++;
}
}
cout<<count<<endl;
return 0;
}

6-9 qspc-2002-最小花费爬楼梯

题目描述：

给定一个整数数组cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 1≤n≤10^5，数组中的值满足 1≤cost≤10^4

输入样例1： [2,5,20] 输出样例1： 5

说明：

你将从下标为1的台阶开始，支付5 ，向上爬两个台阶，到达楼梯顶部。总花费为5

输入样例2：

[1,100,1,1,1,90,1,1,80,1] 输出样例2： 6 6

说明：

你将从下标为 0 的台阶开始。 1.支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。 2.支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。 3.支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。 4.支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。 5.支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。 6.支付 1 ，向上爬一个台阶，到达楼梯顶部。总花费为 6。这个题本质上是个线性动态规划，就是说它和普通爬楼梯差不多，到达第 i 个楼顶位置的最小花费，等于从 i-1 楼顶位置过来加上台阶 i-1 的费用，或者从 i-2 楼顶位置过来加上台阶 i-2 的费用，二者取最小值。就以最终要抵达的楼顶位置 3 举例，它的最小花费等于抵达楼顶 2 的花费加上台阶 2 的费用，或者抵达楼顶 1 的花费加上台阶 1 的费用，选更小的那一个数值，所以代码如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> cost;
string line;
getline(cin, line);
stringstream ss(line);//将整行字符串转为数据流，用来拆分数字,f符合题目要求
int num;
while (ss >> num) {//循环提取数据流里所有数字，存入cost数组
cost.push_back(num);
}
int n = cost.size();//台阶的总个数
vector<int> dp(n + 1, 0);//// dp数组：dp[i]表示到达楼顶位置i的最小总花费
//按题目要求，起步0或1不要钱
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
// 两种抵达方式取最小值：
// 1、从楼顶i-1位置，支付台阶i-1的费用，向上爬1格到i
// 2、从楼顶i-2位置，支付台阶i-2的费用，向上爬2格到i
dp[i] = min(dp[i – 1] + cost[i – 1], dp[i – 2] + cost[i – 2]);
}
cout << dp[n] << endl;
return 0;
}

6-10 铺地砖

题目描述

小蓝家要装修了，小蓝爸爸买来了很多块（你可以理解为数量无限)2×3规格的地砖，小蓝家的地板是n × m规格的，小蓝想问你，能否用这些2×3的地砖铺满地板。

铺满地板:对于地板的每个区域，都有且只有一块地砖覆盖，地砖可以旋转，但不能切割。

例如:对于7×6的地板，一种铺地板方式是: 在这里插入图片描述当然，也存在其他别的铺法。

小蓝家是个多层小别墅，每一层的规格不一样，所以他会多次询问你不同规格的地板。

输入格式

第一行输入一个整数T，代表询问数量。

接下来T行，每行两个正整数ni, mi，代表小蓝询问的地板规格。

输出格式

对于每次询问，如果2×3的地砖可以铺满地板，输出Yes，否则输No。

输入样例

在这里给出一组输入。例如：

4 7 6 2 2 12 8 1 12

输出样例

在这里给出相应的输出。例如：

Yes No Yes No

其实这个是一个规律题，啥规律呢？就是说我们在考虑能不能满足题意，就是说从那个2*3的的标准块入手，他的面积是6，也就是说我总砖的面积一定要是6的倍数，然后就是说我要拼的总快的长和宽都要大于1，至少为2，宽为2那就3*2地放进去，长为2我就23放进去，满足这样就可以让23都填满，代码如下：

#include <iostream>
using namespace std;
typedef long long ll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
if (cin >> T) {
while (T–) {
ll n, m;
cin >> n >> m;
if ((n * m) % 6 == 0 && n >= 2 && m >= 2) {
cout << "Yes" << "\\n";
} else {
cout << "No" << "\\n";
}
}
}
return 0;
}

6-11 任何一个自然数m的立方均可写成m个连续奇数之和

任何一个自然数m的立方均可写成m个连续奇数之和。例如： 1^3=1=1 2^3=3+5=8 3^3=7+9+11=27 4^3=13+15+17+19=64 5^3 =21+23+25+27+29=125 编程实现：输入一自然数n，求组成n^3的n个连续奇数。

输入格式:

输入一个自然数n

输出格式:

如： 1^3=1=1 2^3=3+5=8 3^3=7+9+11=27 4^3=13+15+17+19=64 5^3=21+23+25+27+29=125

输入样例1:

在这里给出一组输入。例如：

输出样例1:

在这里给出相应的输出。例如：

5^3=21+23+25+27+29=125

输入样例2:

在这里给出一组输入。例如：

输出样例2:

在这里给出相应的输出。例如： 0 嘻嘻，又是个规律题！！！我的规律就是它的立方组成的第一个奇数就是它的平方减本身加1，最后一个奇数就是他的平方加本省减1，就是： m^3= m^2 -m+1…m^2+m-1,所以代码那就简单了：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin>>n;
ll res=pow(n,3);
ll m=pow(n,2);
vector<ll> ans;
for(int i=m-n+1;i<=m+n-1;i+=2){
ans.push_back(i);
}
cout<<n<<"^3"<<"=";
for(int i=0;i<ans.size();i++){
cout<<ans[i];
if(i!=ans.size()-1) cout<<"+";
}
cout<<"="<<res;
return 0;
}

那为啥是这个规律呢？可以推导一下：

n³拆分为n个连续奇数之和完整推导

前提设定

n^3 n3 能够拆分成n个连续奇数相加

连续奇数为公差

设奇数序列首项为

等差数列求和公式代入

等差数列求和公式：

总和

项数

(

首项

末项

)

总和=\\frac{项数 \\times (首项+末项)}{2}

$总和 = \frac{项数 \times ( 首项 + 末项 )}{2}$ 项数为

$n$ ，末项

(

−

)

=s+2(n-1)

$= s + 2 (n - 1)$ ，代入式子：

总和

[

(

−

)

]

总和=\\frac{n\\big[s+s+2(n-1)\\big]}{2}

$总和 = \frac{n [ s + s + 2 ( n - 1 ) ]}{2}$

化简求和表达式

总和

(

−

)

(

−

)

总和=\\frac{n(2s+2n-2)}{2}=n(s+n-1)

$总和 = \frac{n ( 2 s + 2 n - 2 )}{2} = n (s + n - 1)$

联立总和等于 $n^3 n3建立等式$

(

−

)

n(s+n-1)=n^3

$n (s + n - 1) = n^{3}$

≥

n\\ge1

$n \geq 1$ ，两边同除以

$n$ 得：

−

s+n-1=n^2

$s + n - 1 = n^{2}$

推导首项公式

移项计算首个奇数：

−

\\boldsymbol{s = n^2 – n + 1}

$s = n^{2} - n + 1$

推导末项公式

末项

(

−

)

e = s+2(n-1)

$e = s + 2 (n - 1)$ ，代入首项展开：

(

−

)

(

−

)

−

\\begin{align} e&=(n^2-n+1)+2(n-1)\\\\ &=n^2-n+1+2n-2\\\\ &=\\boldsymbol{n^2 + n -1} \\end{align}

$e = (n^{2} - n + 1) + 2 (n - 1) = n^{2} - n + 1 + 2 n - 2 = n^{2} + n - 1$

校验数列数量正好为n个

项数计算公式：

项数

末项

−

首项

公差

\\displaystyle 项数=\\frac{末项-首项}{公差}+1

$项数 = \frac{末项 - 首项}{公差} + 1$

项数

(

−

)

−

(

−

)

−

\\begin{align} 项数&=\\frac{(n^2+n-1)-(n^2-n+1)}{2}+1\\\\ &=\\frac{2n-2}{2}+1\\\\ &=n \\end{align}

$项数 = \frac{( n ^{2} + n - 1 ) - ( n ^{2} - n + 1 )}{2} + 1 = \frac{2 n - 2}{2} + 1 = n$

6-12 房屋分拆

题目背景

厂长买了一整间房屋作为车间，现准备将整个房屋分成若干个车间。装修公司规定分拆房屋的价格等于被分拆房屋的面积。如想将面积为200的房间分拆为面积为80、70和50的三个车间，第一次将房屋分拆为面积120和80的两个房间，花费200，第二次将面积为120的房间分拆为面积为70和50的两个房间，花费120，总花费为320。如果采用另一种方案，第一次将面积200的房屋分拆为150和50，花费200，第二次将面积为150的房间分拆为80和70的房间，花费150，则总花费为350。显然第一种方案花费更少。请编写程序为厂长设计花费最少的分拆方案。

输入格式:

输入为两行，第一行为一个整数n，表示所需的车间数量。第二行为n个正整数，以空格间隔，给出每个车间需要的面积。n不超过100000，且保证最终结果小于2^31

输出格式:

输出为一个整数，表示将整个房屋分拆为n个车间所需的最少花费。

输入样例:

8 1 1 1 1 2 3 4 5

输出样例:

49 这个题考验我们的读题，其实是个反过来的哈夫曼树，就是说哈夫曼树是每次取最大的两个加和，而这个是每次取最小的，所以代码如下：

#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin>>n;
vector<int> ans(n);
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<n;i++){
cin>>ans[i];
pq.push(ans[i]);
}
int res=0;
while(pq.size()>1){
int a=pq.top();
pq.pop();
int b=pq.top();
pq.pop();
int sum=a+b;
res+=sum;
pq.push(sum);
}
cout<<res<<endl;
return 0;
}

总结一下

总的来说，此次测试其实难度还是有一定的，我放上的这几个题是12个题里的简单题了，没有把难题记录下，因为太难了，还没完全写出来，实际上我们工作室测试很有价值，值得我记录它们，促进我的学习！！！

文章目录

6-1 组队

题目描述

输入格式

输出格式

输入样例

输出样例

说明

6-7 小潘的最小因子和问题

输入格式:

输出格式:

输入样例1:

输出样例1:

输入样例2:

输出样例2:

6-8 Knowledge

题目描述

输入格式:

输出格式:

输入样例:

输出样例:

6-9 qspc-2002-最小花费爬楼梯

题目描述：

说明：

输入样例2：

说明：

6-10 铺地砖

题目描述

输入格式

输出格式

输入样例

输出样例

6-11 任何一个自然数m的立方均可写成m个连续奇数之和

输入格式:

输出格式:

输入样例1:

输出样例1:

输入样例2:

输出样例2:

n³拆分为n个连续奇数之和完整推导

前提设定

等差数列求和公式代入

化简求和表达式

联立总和等于 n 3 n^3 n3建立等式

推导首项公式

推导末项公式

校验数列数量正好为n个

6-12 房屋分拆

题目背景

输入格式:

输出格式:

输入样例:

输出样例:

总结一下

相关推荐

评论 抢沙发

热门标签

热门文章

最新文章

归档

分类

联立总和等于 $n^3 n3建立等式$

评论抢沙发