2020.08.11
四道编程题，做出来了一道半
文章目录
-
-
-
- 一、回文串构造
- 二、方格染色
- 三、数字拆分
- 四、矩阵取数
-
-
一、回文串构造
-
分析
定义两个指针分别从字符串首尾向中间遍历，碰到两指针值不一样的情况就将统计值+1。
- 代码
#include<iostream>
#include<string>
using namespace std;
int CountNum(int len, string str)
{
int x=0,y=len-1;
int count = 0;
for(int i=0;i<len/2;i++)
{
if(str[x] != str[y])
{
count++;
}
str[x++];
str[y--];
}
return count;
}
int main()
{
int len;
string str;
cin>>len;
cin>>str;
int n = CountNum(len, str);
cout<<n;
return 0;
}
二、方格染色
- 分析
- 做题时候的思路：要是m或n里有2的倍数，结果就是是2；要是m和n都为3的倍数，就输出3；其他情况就输出m*n，只通过了10%。
- 后来从知道这道题实际上是让求m*n的公因子（除了1外）。
- 代码：
#include<iostream>
#include<vector>
using namespace std;
//其实就是找最小公因数
int main()
{
int t;
cin>>t;
int m = t;
int n=2;
vector<vector<int>> a(m);
for(int i=0;i<m;i++)
{
a[i].resize(n);
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
for(int i=0;i<m;i++)
{
int x = a[i][0], y = a[i][1];
if(x*y ==1)//1是特殊情况特殊处理
{
cout<<1<<endl;
}
else//否则找到m*n的最小因子输出
{
int i;
int z = x*y;
for(i=2;i<z;i++)
{
if(x*y%i==0)
break;
}
cout<<i<<endl;
continue;
}
}
return 0;
}
三、数字拆分
- 分析：
| n | k | 数字和 |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 2 | 1+1 |
| 3 | 2 | 1+2 |
| 4 | 3 | 1+2+1 |
| 5 | 3 | 1+2+2 |
| 6 | 3 | 1+2+3 |
| 7 | 4 | 1+2+3+1 |
| 8 | 4 | 1+2+3+2 |
| 9 | 4 | 1+2+3+3 |
| 10 | 4 | 1+2+3+4 |
由以上规律可得，每n要都满足题目所要求的条件，都必须从1开始加和，一直到能得到该值为止，并且每次相加到最后一位时都从1开始相加，比如
6=1+2+3
，
7=1+2+3+1
。画个图比较好理解：总之就是不断网后加数所加的数每次都是从1开始，所以在统计k的值时，只需要统计从1开始相加，每加一次k值相应加一次，直到相加的数大于等于n为止，返回k值。
- 代码：
#include<iostream>
using namespace std;
int DivideNum(int t, int n)
{
if(t<1 || n==NULL)
return -1;
int k=0;
int sum=0;
for(int i=1;i<n;i++)
{
sum+=i;
k++;
if(sum>=n)
{
return k;
}
}
}
int main()
{
int t=10;
int num[10]={1,2,3,4,5,6,7,8,9,10};
for(int i=0;i<t;i++)
{
int r = DivideNum(t, num[i]);
cout<<r<<endl;
}
return 0;
}
四、矩阵取数
输入例子：
2 2 2 2
2 3
3 3
输出例子：
11
- 分析：
- 这道题在做的时候是完全看不懂题的状态，没有搞懂这写数减去d的这些数指的是什么，一直以为是用最终的sum去减。
- 之后才发现题目：
每次操作可以选择一行或者一列将其中的元素的值全部累加到sum中，然后把这些数都减去d，求sum的最大值
中的这些数指的就是让sum加和最大的行和或列和所在的行或列的元素，实在绕口。
-
其实就是找到每行或每列中的最大行和或列和，然后将所在的行或列中的元素全部减去d；
然后重复k次上述操作；
最后输出sum即可。
- 代码
#include<iostream>
#include<vector>
using namespace std;
int FindMatrixMaxSum(int m, int n, int k, int d, vector<vector<int>> a)
{
int sum=0;
while(k>0)
{
int colSum=0, maxColSum=0, rowSum=0, maxRowSum=0,max=0;
int maxRowSumIndex=0, maxColSumIndex=0;
//找行和最大值
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
rowSum += a[i][j];
}
if(rowSum>maxRowSum)
{
maxRowSum = rowSum;
maxRowSumIndex = i;
}
rowSum=0;
}
//找列和最大值
for(int j=0;j<n;j++)
{
for(int i=0;i<m;i++)
{
colSum += a[i][j];
}
if(colSum>maxColSum)
{
maxColSum = colSum;
maxColSumIndex = j;
}
colSum=0;
}
//找到最大值然后累加，并让最大值所在的行或列全部减去d值
if(maxRowSum >= maxColSum)
{
sum += maxRowSum;
for(int j=0;j<n;j++)
{
a[maxRowSumIndex][j] -= d;
}
}
else
{
sum += maxColSum;
for(int i=0;i<m;i++)
{
a[i][maxColSumIndex] -= d;
}
}
k = k-1;
}
return sum;
}
int main()
{
int m,n,k,d;
cin>>m>>n>>k>>d;
vector<vector<int>> a(m);
for(int i=0;i<m;i++)
{
a[i].resize(n);
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
cin>>a[i][j];
}
}
int r = FindMatrixMaxSum(m,n,k,d,a);
cout<<r;
return 0;
}