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;
}