学习记录9

上午

听英语听力,看大话数据结构。

写出了八皇后。

之前只是数组开小了。开大后答案是对了,就是时间超限了。

于是看了下题解。人家是用一个数组内元素标志某列和两个对角线,我傻乎乎的二维数组直接一个个标记,对比起来,难怪超时哦。

好了,题目如下:

学习记录9

 得出的代码如下:

#include <iostream>

#include <cmath>

#include <memory.h>

#include <algorithm>

using namespace std;
int ans[115]={0},n,k;
int a[110],b[110],c[110],d[110],m,l;//用a数组记录皇后可以占领的位置,b数组表示已被使用过的列,c,d数组表示两个对角线
void dfs(int ci,int cnt)//ci为行,cnt记录皇后占领位置的个数
{
    if(cnt==n)
    {
        if(m>=3)//只需要求出前三种
        {
            m++;return;//持续计数
        }
        for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++)
                if(a[j]==i)//从记录的a数组中把找出来的点按顺序放入答案数组中
                    ans[l++]=j;
        m++;//计数
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if((!b[i])&&(!c[ci+i])&&(!d[ci-i+n]))
            {
                a[i]=ci;
                b[i]=1;
                c[ci+i]=1;
                d[ci-i+n]=1;//用几个数组统一表示行和列和对角线,对比在”地图“中一个个位置去标记,大大节省了时间复杂度
                dfs(ci+1,cnt+1);
                a[i]=0;
                b[i]=0;
                c[ci+i]=0;
                d[ci-i+n]=0;//回溯
            }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(1,0);
    for(int i=0;i<l;i++)
    {
        printf("%d ",ans[i]);
        if((i+1)%n==0)
            printf("\n");
    }
    cout <<m;
}

最主要的就是使用那几个数组标志列和两个对角线,只需要能想到这个,其他的就是正常的dfs了。

下午

做了周末测试,瓦了,六个题写了2个。

现在看一看那两个是两个入门题……还是能力不够。

题目1:

学习记录9

#include <iostream>

#include <cmath>

#include <memory.h>

#include <algorithm>

using namespace std;

int main()
{
    int a[4];
    for(int i=0;i<4;i++)
    cin >>a[i];
    sort(a,a+4,less<int>());
    if(a[0]+a[1]<a[2]&&a[1]+a[2]<a[3])
        cout <<"IMPOSSIBLE";
    else if(a[0]+a[1]>a[2]||a[1]+a[2]>a[3])
        cout <<"TRIANGLE";
    else 
        cout <<"SEGMENT";


}

 判断三角形,首先判断是否完全不能构成三角形,然后判断是否可以构成三角形,最后剩下的即为”退化的三角形“。

题目2:

学习记录9

 

#include <iostream>

#include <cmath>

#include <memory.h>

#include <algorithm>

using namespace std;

int main()
{
    int a,b,t,c;
    cin >>a>>b;
    if(a>b)
        t=a;
    else t=b;
    t=6-t+1;
    if(t==1)
        printf("1/6");
    if(t==2||t==4)
        printf("%d/%d",t/2,6/2);
    if(t==3)
       printf("1/2");
    if(t==5)
        printf("5/6");
    if(t==0)
        cout <<"0/1";
    if(t==6)
        cout <<"1/1";
}

数目也不多,直接枚举出来就可以了。

晚上

组织了一场答辩。深刻认识到了自己的不足,与他人相比有不少差距。要更灵活的思考,题目总会写出来的。

明日计划

首先早晨起来听一会儿英语听力(20分钟),背一下单词(10分钟)。

之后看大话数据结构中关于二叉树的章节。看完后开始写二叉树的题组。

目标是把这题组中的题目在星期三之前写完,之后学之后的内容。

上一篇:95-100 css表格宽高度设置案例


下一篇:pandas(三)