学习打卡第三天
回到矩阵填数,
类似这种矩阵怎么填数?只有两种操作,从左下到右上,从右上到左下。
将每一斜列视为一列,一共n列,奇数列上,偶数列下
#include<stdio.h>
int n,a[20][20];
int main(){
scanf("%d",&n);
int m=1,k=1,x=1,y=1;
while(k<=n){
if(k%2==1){//奇数列
x=k;y=1;//每次上去都是从第一列第k行上去
for(int i=1;i<=k;i++){
a[x][y]=m++;
x--;
y++;
}
}
else{//偶数列
x=1;y=k;//每次下去都是从第k列第一行下去
for(int i=1;i<=k;i++){
a[x][y]=m++;
x++;
y--;
}
}
k++;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
printf("%-3d",a[i][j]);
}
printf("\n");
}
return 0;
}
在这里我只展示了上三角,有兴趣的可根据原理自行拓展全
矩阵填数补充完了,说一说昨晚牛客比赛情况
第一题纯属脑子傻了,没看懂题,白送的还wa了一发,我还tm先做的第二题(我当时觉得第一题有难度·····),第二题交之前没检查,也wa了一发,第三题不会,第四题以前做过差不多的,当时脑抽了,觉得排不排序都是一样的,就这样wa了五发,还剩最后20分钟时,才发现排序与不排序结果不一样······思路出来了,当然很快就写完了
来看一下第三题吧
我确实不会写这种题目,包括上次cf有一题是背包模板题,其实我做过那一类的题,但忘了怎么去写,还没熟练掌握知识点
这题乍一看不知所措,尤其是木棍可用可不用
首先怎么算面积呢,知道三边毫不犹豫海伦公式
p=(a+b+c)/2;
s=sqrt(p*(p-a)*(p-b)*(p-c));
看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int a[N];
int n;
double mx = -1e9;
double calc(int a,int b,int c)
{
double h = (a+b+c)/2;
double s = sqrt(h*(h-a)*(h-b)*(h-c));
return s;
}
//cnt记录的是当前枚举的第几根木棍
double dfs(int l1,int l2,int l3,int cnt)
{
if(cnt>n) return -1;//最优性剪枝??
if(l1+l2>l3&&l1+l3>l2&&l2+l3>l1)
{//如果是三角形才计算面积
mx = max(mx,calc(l1,l2,l3));
}
//爆搜所有情况
dfs(l1+a[cnt],l2,l3,cnt+1);
dfs(l1,l2+a[cnt],l3,cnt+1);
dfs(l1,l2,l3+a[cnt],cnt+1);
dfs(l1,l2,l3,cnt+1);
return mx;
}
int main()
{
cin>>n;
for(int i = 0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int l1 = 0,l2 = 0,l3 = 0;
double ans = dfs(l1,l2,l3,0);
if(fabs(ans+1e9)<1e-9)//也可以ans<=0来判断....
{
cout<<"-1";
return 0;
}
printf("%.1f",ans);
}
完了,要睡觉了
明天见,晚安各位