【日常学习】【搜索递推和其他】10.21.2015校内测试总结

比眉伴天荒 2022-08-09 11:54 13阅读 0赞

哭瞎了···昨天夜里写了一半多的博客因为卡机就这么没了TUT今天重新写，浪费我多少时间TUT

第一题 RQNOJ358 线段

画个图就知道是两点间距离的二倍···（我太傻竟没看出来）

但是！这是小圆圆心在大圆外的情况，如果在大圆内部，画图可知正解是大圆直径

然而···出题人竟然没发现这一点于是只用了第一种解法没加特判···

所以说蠢萌的出题人···

代码

标准解（OJAC）

//chord
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    int xa,ya,xb,yb,ra,rb;
    double ans;
    
    int main()
    {
        freopen("chord.in","r",stdin);
    	freopen("chord.out","w",stdout);	
        //freopen("1.txt","r",stdin);
    	//freopen("2.txt","w",stdout);
        scanf("%d%d%d",&xa,&ya,&ra);
        scanf("%d%d%d",&xb,&yb,&rb);
        ans=sqrt((double)(xb-xa)*(double)(xb-xa)+(double)(yb-ya)*(double)(yb-ya));
        
        ans*=2;
        printf("%.6f\n",ans);
        return 0;
    }

正解

//chord
    //copyright by ametake
    #include
       
        
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    int xa,ya,xb,yb,ra,rb;
    double ans;
    
    int main()
    {
        freopen("chord.in","r",stdin);
    	freopen("chord.out","w",stdout);	
        //freopen("1.txt","r",stdin);
    	//freopen("2.txt","w",stdout);
        scanf("%d%d%d",&xa,&ya,&ra);
        scanf("%d%d%d",&xb,&yb,&rb);
        ans=sqrt((double)(xb-xa)*(double)(xb-xa)+(double)(yb-ya)*(double)(yb-ya));
        int r=max(ra,rb);
        if (ans<=r) ans=r;
        ans*=2;
        printf("%.6f\n",ans);
        return 0;
    }

第二题 循环 NOIP2005PJ4

谁说PJ能AK的···

这是一个递推题，要写高精。

如果暴搜，乘幂上限到五百多能拿三十分···

但也只能三十分，因为其他点答案都是十的几十次方···

暴搜程序

（幸亏我点了保存可恶的CSDN写到第二题又给我卡死了！！！可恶！！！）

（就在我说这句话后当我粘上代码第三次卡死了）

//circle
    //copyright by ametake
    //思路 从基数开始一个个尝试基数的倍数 第一次快速幂 之后高精乘即可 每次检验
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    
    using namespace std;
    
    const int sx=600; 
    const int maxn=100+10;
    //const int power=1;
    const int base=10;
    const int jishu[10]={1,1,4,4,2,1,1,4,4,2};
    
    int a[maxn],ans[maxn],c[maxn];
    char cc[maxn];
    int now[maxn],jj[maxn];
    int k;
    
    void multi(int *aa,int *b)
    {
        memset(c,0,sizeof(c));
        int len1=aa[0];
        int len2=b[0];
        c[0]=min(100,aa[0]+b[0]-1);
        for (int i=1;i<=len1;i++)
        {
            for (int j=1;j<=min(len2+i-1,100-i+1);j++)
            {
                c[i+j-1]+=aa[i]*b[j];
                c[i+j]+=c[i+j-1]/base;
                c[i+j-1]%=base;
            }
        }
        if (c[c[0]+1]) if (c[0]<100) c[0]++;
        memcpy(aa,c,sizeof(c));
    }
    
    bool check()
    {
        memcpy(ans,now,sizeof(now));
        multi(ans,a);
        bool noo=false;
        for (int i=1;i<=k;i++) if (ans[i]!=a[i]) noo=true;
        if (noo) return false;
        else return true;
    }
    
    int main()
    {
        //freopen("1.txt","r",stdin);
        //freopen("2.txt","w",stdout);
        freopen("circle.in","r",stdin);
        freopen("circle.out","w",stdout);
        scanf("%s",cc);
        scanf("%d",&k);
        int p=0;//p是基数，a是最原始数组，now是当前数组，由a求幂而来且指数一定为基数的倍数，ans是检验时用的要再乘一遍a 
        now[0]=k;
        a[0]=k;
        if (k>strlen(cc))
        {
            printf("-1\n");
            return 0;
        }
        for (int i=strlen(cc);i>=1;i--)
        {
            a[++p]=cc[i-1]-'0';
            now[p]=cc[i-1]-'0';
            if (p==k) break;
        }
        p=jishu[now[1]];//从此a不动 
        if (p>1) multi(now,now);
        if (p==4) multi(now,now);
        memcpy(jj,now,sizeof(now));//jj是基底数组 每次乘它 
        if (check())
        {
            printf("%d\n",p);
            return 0;
        } 
        else
        {
            for (int i=2;i<=sx/p;i++)
            {
                multi(now,jj);
                if (check())
                {
                    printf("%d\n",p*i);
                    return 0;
                } 
            }
        }
        printf("-1\n");
        return 0;
    }

这道题正解至今不明白为什么是十次，只是知道每次对于某一位向前递推最后求乘积···这个大家自己去网上搜吧

第三题 altitude

没找到原题，反正也无所谓

直接暴力枚举可过

//altitude
    //copyright by ametake
    #include
        
         
    #include
         
          
    #include
          
           
    using namespace std;
    
    const int maxn=100+10;
    int a[maxn][maxn];
    int n,s,k;
    
    inline int read()
    {
    	int f=1,a=0;
    	char ch=getchar();
    	while (ch<'0'||ch>'9')
    	{
    		if (ch=='-') f=-1;
    		ch=getchar();
    	}
    	while (ch>='0'&&ch<='9')
    	{
    		a=a*10+ch-48;
    		ch=getchar();
    	}
    	a*=f;
    	return a;
    } 
    
    int main()
    {
        //freopen("1.txt","r",stdin);
        //freopen("2.txt","w",stdout);
        freopen("altitude.in","r",stdin);
        freopen("altitude.out","w",stdout);
        n=read();
        s=read();
        k=read();
        int x,y;
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                a[i][j]=read();
            }
        }
        for (int i=1;i<=k;i++)
        {
            x=read();
            y=read();
            int mi=0x3f3f3f;
            int ma=0;
            for (int i=x;i<=x+s-1;i++)
            {
                for (int j=y;j<=y+s-1;j++)
                {
                    ma=max(a[i][j],ma);
                    mi=min(a[i][j],mi);
                }
            }
            printf("%d\n",ma-mi);
        }
        return 0;
    }

也可以用DP做，但时间复杂度更大，因为DP球了所有的状态

参见显摆代码 这里不放了

第四题 sudoku

近似于codevs数独挑战 其实只是读入方式变了而已

暴搜即可 一道典型的棋盘暴搜题 和八皇后一样的判断 其实可以参见靶形数独 我感觉我几乎是比着黄学长靶形数独写的

//sudoku
    //copyright by ametake
    #include
        
         
    #include
         
          
    #include
          
           
    #define dfsnext(x,y) {y==9?dfs(x+1,1):dfs(x,y+1);}
    using namespace std;
    
    int a[10][10];//ËÑË÷Êý×é 
    bool b[10][10];//ÊÇ·ñÓÐÔÊ¼Êý×Ö ÓÐÊÇtrue true²»ÄÜÌîÊý 
    bool h[10][10],l[10][10],lit[10][10];//true²»ÄÜÌî 
    bool ok=false;
    
    bool can(int x,int y,int num)
    {
        if (h[x][num]) return false;
        if (l[y][num]) return false;
        if (lit[(x-1)/3*3+(y-1)/3+1][num]) return false;
        h[x][num]=true;
        l[y][num]=true;
        lit[(x-1)/3*3+(y-1)/3+1][num]=true;
        a[x][y]=num;
        return true;
    }
    
    void del(int x,int y,int num)
    {
        h[x][num]=l[y][num]=lit[(x-1)/3*3+(y-1)/3+1][num]=false;
        a[x][y]=0;
    }
    
    void print()
    {
        for (int i=1;i<=9;i++)
        {
            for (int j=1;j<=9;j++)
            {
                printf("%d",a[i][j]);
            }
            printf("\n");
        }
    }
    
    void dfs(int x,int y)
    {
         if (ok) return;
         if (x==10&&y==1)
         {
             ok=true;
             print();
             return;
         }
         if (b[x][y]) dfsnext(x,y);
         if (!b[x][y])
         {
             for (int i=1;i<=9;i++)
             {
                 if (can(x,y,i))
                 {
                    dfsnext(x,y);
                    if (ok) break;
                   del(x,y,i);
                 }
             }
         }
    }
    
    int main()
    {
        freopen("sudoku.in","r",stdin);
        freopen("sudoku.out","w",stdout);
        char s[10];
        for (int i=1;i<=9;i++)
        {
            scanf("%s",s);
            for (int j=1;j<=9;j++)
            {
                if (s[j-1]=='?') a[i][j]=0;
                else
                {
                    a[i][j]=s[j-1]-'0';
                    h[i][s[j-1]-'0']=true;
                    l[j][s[j-1]-'0']=true;
                    lit[(i-1)/3*3+(j-1)/3+1][s[j-1]-'0']=true;
                    b[i][j]=true;
                }
            } 
        }
        dfs(1,1);
        return 0;
    }

总结：思维能力和代码实现能力仍需增强 基础部分尤其是深广搜还要再练 算法还应该更扎实 加油啊

——连重阳节都过去了

——雾霾天，外面灰蒙蒙的一片，好像要下雨一样

——江涵秋影雁初飞，与客携壶上翠微