2019 01 22考试总结

· · 个人记录

忆中恨 书榜下

寒城凄切，骤雨初歇，疾风再起，望我分，不可及，时有苦笑心寒，急不可耐，慌莽一时，却回头，难再挽，竟无语，念无幸，千里烟波，万里冰封，更那堪，晓风无，残月仍，更与何人言？

待到应时，百种风情，一声怆然，似伊人，在水方，还在中心泱泱，彻夜辗转，反彻难眠，刹惊醒，痛无梦，又凝噎，思有苦，长空无鹰，浅底无鱼，怅寥廓，湿青衫，一回来，须信一回惘。

先谈谈列队一题吧。

此题玄之又玄（即有毒）我的想法是模拟出顺序，按照先左后前来，于是加上dfs，但是会遇上空间开爆的情况，看到有几组数据只有一排，于是想到特判一下骗一些分，但还是爆了。 下面附上错误代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;

struct Edge{
    int x;int y;
}e[300005];

int n,q,m,ans[300005],a[maxn][maxn],b[maxn][maxn];
void dfs1(int u,int xx,int yy)
{
    if(u>q)
    return ;
    else
    {
    ans[u]=a[xx][yy];
    if(yy!=m&&xx!=n)
    {
        b[xx][yy]=a[xx][yy];
        for(int j=yy+1;j<=m;j++)
        {
            a[xx][j-1]=a[xx][j];
        }
        for(int i=xx+1;i<=n;i++)
        {
            a[i-1][m]=a[i][m];
        }
        a[n][m]=b[xx][yy];
    }
    if(yy==m&&xx!=n)
    {
        b[xx][yy]=a[xx][yy];
        for(int i=xx+1;i<=n;i++)
        {
            a[i-1][m]=a[i][m];
        }
        a[n][m]=b[xx][yy];
    }
    if(xx==n&&yy!=m)
    {
        b[xx][yy]=a[xx][yy];
        for(int j=yy+1;j<=m;j++)
        {
            a[xx][j-1]=a[xx][j];
        }
        a[n][m]=b[xx][yy];
    }
    if(xx==n&&yy==m)
    {
        a[n][m]=a[xx][yy];
    }
    }
    dfs1(u+1,e[u+1].x,e[u+1].y);
} 

void dfs2(int u,int xx,int yy)
{
    if(u>q)
    return ;
    else
    {
        ans[u]=a[1][yy];
        b[1][yy]=a[1][yy];
        for(int j=yy+1;j<=m;j++)
        {
            a[1][j-1]=a[1][j];
        }
        a[n][m]=b[1][yy];
        dfs2(u+1,e[u+1].x,e[u+1].y);
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        a[i][j]=(i-1)*m+j;
    }
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d",&e[i].x,&e[i].y);
        //dfs(1,e[1].x,e[1].y);
    }
    if(n!=1)
    dfs1(1,e[1].x,e[1].y);
    else if(n==1)
    dfs2(1,e[1].x,e[1].y);
    for(int i=1;i<=q;i++)
    {
        printf("%d\n",ans[i]);
    }
    return 0;
}

奶酪只得了80，改正确了。

上code：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
const int MAXN=1010;

struct cir
{
    double x,y,z;
    bool operator<(const cir &cpr)const
    {
        return z<cpr.z;
    }
}p[MAXN];
bool fnd=0;
int n;
double h,r;
bool vis[MAXN];

double dist(double x1,double y1,double z1,double x2,double y2,double z2)
{
    return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)+(z2-z1)*(z2-z1));
}

void dfs(cir now,int num)
{
    if(now.z+r>=h)
    {
        fnd=1;
        return;
    }
    vis[num]=1;
    for(int i=1;i<=n;i++)
    {
        if(fnd)
            return;
        if(!vis[i]&&dist(now.x,now.y,now.z,p[i].x,p[i].y,p[i].z)<=r*2)
            dfs(p[i],i);
    }
}

int main()
{

    int T;scanf("%d",&T);
    while(T--)
    {
        memset(vis,0,sizeof(vis));
        memset(p,0,sizeof(p));
        fnd=0;
        scanf("%d%lf%lf",&n,&h,&r);
        for(int i=1;i<=n;i++)
            scanf("%lf%lf%lf",&p[i].x,&p[i].y,&p[i].z);
        std::sort(p+1,p+n+1);
        for(int i=1;i<=n;i++)//lower
            if(p[i].z-r<=0)
                dfs(p[i],i);
        if(fnd)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

宝藏不行，只打了个40的暴力，如下：

#include<bits/stdc++.h>```cpp
#include<bits/stdc++.h>
using namespace std;

int a[30], l[30],sum[30];
int cost[30][30];
int ans=2147483647,tmp=0,n,m,tot;

void dfs(int u,int num,int tmp)
{
    if(num>=n)
    {
        ans=min(tmp,ans);
        return ;
    }
    if(tmp>=ans) return;
    for(int i=1;i<=n;i++)
    {
        if(l[i]) continue;
        for(int j=1;j<=n;j++)
        {
            if(cost[j][i]==0x3f||!l[j]||j==i)
            continue;
            l[i]=1;
            sum[i]=sum[j]+1;
            dfs(i,num+1,tmp+cost[i][j]*sum[j]);
            l[i]=0; 
            sum[i]=0;
            tot--;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    memset(cost,0x3f,sizeof(cost));
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        cost[x][y]=cost[y][x]=min(cost[x][y],z);
        //cost[y][x]=cost[x][y];
    }
    for(int i=1;i<=n;i++)
    {
        memset(l,0,sizeof(l));
        for(int i=1;i<=n;i++) 
        sum[i]=1;
        l[i]=1;
        dfs(i,1,0);
    }
    printf("%d",ans);
    return 0;
}