知识点:绝对值不等式
拓展:
知识点:简单dp–数字三角形模型
拓展:
2.1AcWing 1015. 摘花生
2.2AcWing 1027. 方格取数
2.3AcWing 382. K取方格数
知识点:网格图的向量遍历技巧
这个题之前在语法基础课里做过,直接上代码吧:
#include<iostream>
using namespace std;
int st[110][110];
int num[110][110];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int main()
{
int n,m;
cin>>n>>m;
int x=1,y=1,z=0;
for(int i=1;i<=n*m;++i)
{
num[x][y]=i;
st[x][y]=1;
int x1=x+dx[z%4],y1=y+dy[z%4];//这个z%4是个值得思考的地方，有点东西！！！！！
if(x1>n||x1<1||y1>m||y1<1||st[x1][y1]==1) z++;
x+=dx[z%4];y+=dy[z%4];
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
cout<<num[i][j]<<" ";
cout<<endl;
}
return 0;
}
其实不用设置数组st[].因为数组num[]是全局变量，所以只要num[]中的数值不为零，就表示这个已经填过数了，要进行转向。
#include<iostream>
using namespace std;
int n,m;
int num[100][100];
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};//涉及到这种循环转换的时候一定要按照下标从0开始!!!
int main()
{
cin>>n>>m;
int x=0,y=0,z=0;
for(int i=1;i<=m*n;++i)
{
num[x][y]=i;
if(x+dx[z%4]==n||y+dy[z%4]==m||y+dy[z%4]<0||num[x+dx[z%4]][y+dy[z%4]]!=0)
z++;
x=x+dx[z%4];y=y+dy[z%4];
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j)
cout<<num[i][j]<<" ";
cout<<endl;
}
return 0;
}
这个题最核心的地方一个是dx[]和dy[]数组，另一个地方就是变量z取余进行变向。
这两个地方(可以归结为偏移量技巧)是可以用在其他题上边的.
y总代码:
#include<iostream>
using namespace std;
int res[100][100];
int main()
{
int n, m;
cin >> n >> m;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
for (int x = 0, y = 0, d = 0, k = 1; k <= n * m; ++k)
{
res[x][y] = k;
int a = x + dx[d], b = y + dy[d];
if(a < 0 || a >= n || b < 0 || b >= m || res[a][b])
{
d = (d + 1) % 4;
a = x + dx[d], b = y + dy[d];
}
x = a, y = b;
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; j ++) cout << res[i][j] << " ";
cout << endl;
}
return 0;
}
其他思路: 利用left right top bottom 四个变量来表示这个矩形的边界
#include <iostream>
using namespace std;
const int N = 105;
int a[N][N];
int n, m;
int main() {
cin >> n >> m;
int left = 0, right = m - 1, top = 0, bottom = n - 1;
int k = 1;
while (left <= right && top <= bottom) {
for (int i = left ; i <= right; i ++) {
a[top][i] = k ++;
}
for (int i = top + 1; i <= bottom; i ++) {
a[i][right] = k ++;
}
for (int i = right - 1; i >= left && top < bottom; i --) {
a[bottom][i] = k ++;
}
for (int i = bottom - 1; i > top && left < right; i --) {
a[i][left] = k ++;
}
left ++, right --, top ++, bottom --;
}
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++) {
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
拓展:
4.AcWing 1113. 红与黑AcWing 1113. 红与黑
知识点:flood fill算法
拓展:
知识点:进制转换
进制转换一直没掌握，看到这个题第一反应是笑了哈哈哈哈，那就在今天把你解决了吧!!!
这个题关键在于:如何将十进制数转换成B进制数；另一个是如何判断回文数.
我们在判断回文数的时候对字符串的处理是最简单的，那么这个题在进制转换时就可以转换成字符串.
先来解决十进制转换成R进制:
核心代码:
char c[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};//注意c[]数组的每个值都要加上单引号,包括数字也要加上单引号.
string s;//存储转换后的R进数(注意是逆序！！)
while(j)//j表示十进制数
{
s+=c[j%b];//b表示B进制
j=j/b;
}//此时s存储的转换后的R进制数是逆序的！！！要给倒过来
for(int left=0,right=s.size()-1;left<right;left++,right--)
swap(s[left],s[right]);
拿这个题来检验一下上面代码的正确性 HDU 2031.二进制转换
#include<iostream>
using namespace std;
char c[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G'};
int main()
{
int n,r;
while(cin>>n>>r)
{
if(n==0)//对0要进行特判，易错！！！！！！！！
{
cout<<0<<endl;
continue;
}
string s;
bool st=false;
if(n<0)
{
st=true;
n=0-n;
}
while(n)
{
s+=c[n%r];
n=n/r;
}
if(st) s+='-';
for(int l=0,right=s.size()-1;l<right;l++,right--)
swap(s[l],s[right]);
cout<<s<<endl;
}
return 0;
}
对回文数的判断就简单了，用双指针
#include<iostream>
using namespace std;
char c[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
int main()
{
int n;
cin>>n;
for(int i=1;i<=300;++i)
{
int j=i*i;
string s;
while(j)
{
s+=c[j%n];
j=j/n;
}
bool st=true;//默认是回文
for(int left=0,right=s.size()-1;left<right;left++,right--)
if(s[left]!=s[right])//当有一个字符不是的时候
{
st=false;
break;
}
if(st==true)
{
//输出的第一个数表示满足平方值转化为 B 进制后是回文数字那个数，由于题干要求这个数是在B进制下数，所以要转换
int k=i;
string s1;
while(k)
{
s1+=c[k%n];
k=k/n;
}
for(int left=0,right=s1.size()-1;left<right;left++,right--)
swap(s1[left],s1[right]);
cout<<s1<<" "<<s<<endl;
}
}
return 0;
}
精简一下:
#include<iostream>
using namespace std;
char c[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
string transform(int num,int b)
{
string s;
while(num)
{
s+=c[num%b];
num=num/b;
}
for(int left=0,right=s.size()-1;left<right;left++,right--)
swap(s[left],s[right]);
return s;
}
bool check(string s)
{
bool st=true;//默认是回文
for(int left=0,right=s.size()-1;left<right;left++,right--)
if(s[left]!=s[right])//当有一个字符不是的时候
return false;
return true;
}
int main()
{
int b;
cin>>b;
for(int n=1;n<=300;++n)
{
string s1;
s1=transform(n*n,b);//进制转换
bool st=check(s1);
if(st==true)
{
//输出的第一个数表示满足平方值转化为 B 进制后是回文数字那个数由于题干要求这个数是在B进制下的数,所以要转换
string s2;
s2=transform(n,b);
cout<<s2<<" "<<s1<<endl;
}
}
return 0;
}
注意c[]数组的每个值都要加上单引号包括数字也要加上单引号.
出事了:上面HDU那个题,在SDUT( SDUT1252进制转换 )上有个一摸一样的，并且显示来源是HDU，但是提交上边的代码一直是WA，这是怎么回事呢?
原来0在任何进制下都是0，但是按照上边的写法输入0，什么都不输出，因为字符串s为空.
所以要特判一下,HDU后台应该没有0这个样例.
#include<iostream>
using namespace std;
char c[]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G'};
int main()
{
int n,r;
while(cin>>n>>r)
{
if(n==0)//对0要进行特判，易错！！！！！！！！
{
cout<<0<<endl;
continue;
}
string s;
bool st=false;
if(n<0)
{
st=true;
n=0-n;
}
while(n)
{
s+=c[n%r];
n=n/r;
}
if(st) s+='-';
for(int l=0,right=s.size()-1;l<right;l++,right--)
swap(s[l],s[right]);
cout<<s<<endl;
}
return 0;
}
由于AcWing1346.回文平方这个题从1开始，所以不需要特判！！！
对0要进行特判,易错易忘！！！！！！！！！！！！
拓展:
5.1 AcWing124. 数的进制转换
上面的transform()函数只是针对于十进制转成N进制,那么M进制转成N进制怎么转呢?
知识点:浮点数二分
拓展
知识点:整数二分
#include<iostream>
using namespace std;
int n,k;
int h[100005],w[100005];
int main()
{
cin>>n>>k;
int max=0;
for(int i=1;i<=n;++i)
{
cin>>h[i]>>w[i];
if(min(h[i],w[i])>max) max=min(h[i],w[i]);
}//得到一个从全局来看,可以切出的最大边长
for(int i=max;i>=1;--i)//将最大边长从大到小开始遍历
{
int cnt=0;//统计N块巧克力可以切出来多少i*i的巧克力
for(int j=1;j<=n;++j)
cnt+=(h[j]/i)*(w[j]/i);
if(cnt>=k)//当cnt>k时,表示切出来的i*i的巧克力可以满足K个小朋友,输出
{
cout<<i;
break;
}
}
return 0;
}
说明整体思路是没错的,要进行优化.
上面代码的复杂度是0($n^2$)的.而n<=$10^5$,肯定是超时的
这个题要想不超时，是要用二分的.
