一场蛇皮比赛qwq


Task 1 DFS

第一题是个提交答案题。给你一个迷宫,每个点要么有确切方向(必须走这个方向)或者没有(自己填方向),请求出一种填写方案使得可以从起点走到终点。

这道题抱着试试看的态度写了裸的DFS结果真成了!嘿!

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,sx,sy,tx,ty;
char mp[1000][1000];
bool use[1000][1000];
bool DFS(int x,int y)
{
    bool tmp;
    if(use[x][y]) return false;
    use[x][y]=true;
    if(x==tx&&y==ty) {use[x][y]=false;return true;}
    switch(mp[x][y])
    {
        case '.':
        {
            mp[x][y]='w';if(DFS(x-1,y)) {use[x][y]=false;return true;}
            mp[x][y]='a';if(DFS(x,y-1)) {use[x][y]=false;return true;}
            mp[x][y]='s';if(DFS(x+1,y)) {use[x][y]=false;return true;}
            mp[x][y]='d';if(DFS(x,y+1)) {use[x][y]=false;return true;}
            {use[x][y]=false;return false;}
        }
        case 'w':tmp=DFS(x-1,y);use[x][y]=false;return tmp;
        case 'a':tmp=DFS(x,y-1);use[x][y]=false;return tmp;
        case 's':tmp=DFS(x+1,y);use[x][y]=false;return tmp;
        case 'd':tmp=DFS(x,y+1);use[x][y]=false;return tmp;
    }
}
int main()
{
    scanf("%d%d%d%d%d%d\n",&n,&m,&sx,&sy,&tx,&ty);
    for(int i=1;i<=n;++i) scanf("%s",mp[i]+1);
    DFS(sx,sy);
    printf("%d %d %d %d %d %d\n",n,m,sx,sy,tx,ty);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j) printf("%c",mp[i][j]);
        printf("\n");
    }
    return 0;
}

Task 2 暴……力?

给你$n$个矩形,这些矩形初始不相交。有的矩形向上移动,有的矩形向右移动(速度均为1),问$(-infty,infty)$时间内一个点最多被覆盖多少次。

这题显然向右和向上的是分别一体的,所以答案不是0,1就是2。考虑这样一种方法:每个矩形的右上角和左下角分别连出一条$y=-x+b$的直线。如果这条直线与另一方向的矩形相交那么一定有2个同时覆盖。

没毛病,挺简单的,但是首先我没想到需要是另一方向的,WA*N.

之后改过来之后疯狂提交疯狂90pts,醉了……

后来明白发生了什么:对于一个矩形因为覆盖关系的定义边重合不算相交所以需要将长宽适当减少以防止边相交被视为相交。我(们)的想法是都减少1,在测试中也过了,但是实际上是不!行!的!删去太多会出现一系列的问题,可能是小数时间相交,所以需要减小0.1(类似)之后用小数计算可以避免这个问题。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define R register
#define N 100010
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
    int ret=0,mus=1;char tmp=nc();
    while(!isdigit(tmp))
    {
        if(tmp=='-') mus=-1;
        tmp=nc();
    }
    while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
    return mus*ret;
}
int n,x,y,w,h,d,res[2],bel[N],a[N],ta,b[N],tb;
bool ans,use[N];
struct point
{
    double b;int c;
    point(){}
    point(double x,int y){b=x,c=y;}
}p[N<<1];
bool cmp(const point &x,const point &y){return x.b<y.b;}
int main()
{
    int T=RI();
    while(T--)
    {
        res[0]=res[1]=0,ans=false;
        n=RI();
        if(!n) {puts("0");continue;}
        for(R int i=1;i<=n;++i) x=RI(),y=RI(),w=RI(),h=RI(),d=RI(),p[i]=point(y+x,i),p[n+i]=point(y+h+x+w-0.1,i),bel[i]=d;
        sort(p+1,p+(n<<1)+1,cmp);
        for(int i=1;i<=(n<<1);++i)
        {
            ta=tb=0;
            for(int j=i;j<=(n<<1)&&p[j].b==p[i].b;i=j,++j)
            {
                if(!use[p[j].c]) a[++ta]=j;
                else b[++tb]=j;
                use[p[j].c]^=1;
            }
            for(int j=1;j<=ta;++j) res[bel[p[a[j]].c]]++;
            if(res[0]&&res[1]) ans=true;
            for(int j=1;j<=tb;++j) res[bel[p[b[j]].c]]--;
        }
        if(ans) puts("2");
        else puts("1");
    }
}