2019-7-29 考试总结

A. 辣鸡(ljh)

打暴搜，然后$TLE75$，

丑陋的考试$75$分代码：

#include
#include
#include
#include
#include
#include
#define int long long
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define abs(x) ((x)<0?(-1*(x)):(x))
#define Maxn 100050
#define Reg register
using namespace std;
bool vis[Maxn];
int totx1,totx2,toty1,toty2;
int n,sum=0,X1[Maxn],X2[Maxn],Y1[Maxn],Y2[Maxn];
map<int,int> XX1,XX2,YY1,YY2;
vectorint> >Xs1(Maxn),Xs2(Maxn),Ys1(Maxn),Ys2(Maxn);
signed main()
{
//    freopen("text.in","r",stdin);
//    freopen("text2.out","w",stdout);
    scanf("%lld",&n);
    for(Reg int i=1;i<=n;++i)
    {
        scanf("%lld%lld%lld%lld",&X1[i],&Y1[i],&X2[i],&Y2[i]);
        if(!XX1[X1[i]]) XX1[X1[i]]=++totx1;
        if(!XX2[X2[i]]) XX2[X2[i]]=++totx2;
        if(!YY1[Y1[i]]) YY1[Y1[i]]=++toty1;
        if(!YY2[Y2[i]]) YY2[Y2[i]]=++toty2;
        Xs1[XX1[X1[i]]].push_back(i);
        Xs2[XX2[X2[i]]].push_back(i);
        Ys1[YY1[Y1[i]]].push_back(i);
        Ys2[YY2[Y2[i]]].push_back(i);
    }
    sum=0;
    for(Reg int i=1,x;i<=n;++i)
    {
        x=2*((X2[i]-X1[i]+1)*(Y2[i]-Y1[i]+1)-(X2[i]-X1[i]+1)-(Y2[i]-Y1[i]+1)+1);
        if(XX2[X1[i]-1])
        {
            int p=XX2[X1[i]-1];
            for(Reg int k=0;kk)
            {
                int j=Xs2[p][k]; if(j>=i||vis[j]) continue;
                if(Y2[i]==Y1[j]-1) ++x;
                else if(Y1[i]==Y2[j]+1) ++x;
                vis[j]=1;
                if(Y1[i]>Y2[j]||Y1[j]>Y2[i]) continue;
                if(Y1[i]==Y1[j]) --x;
                if(Y2[i]==Y2[j]) --x;
                x+=2*(min(Y2[i],Y2[j])-max(Y1[i],Y1[j])+1);
            }
        }
        if(XX1[X2[i]+1])
        {
            int p=XX1[X2[i]+1];
            for(Reg int k=0;kk)
            {
                int j=Xs1[p][k]; if(j>=i||vis[j]) continue;
                if(Y2[i]==Y1[j]-1) ++x;
                else if(Y1[i]==Y2[j]+1) ++x;
                vis[j]=1;
                if(Y1[i]>Y2[j]||Y1[j]>Y2[i]) continue;
                if(Y1[i]==Y1[j]) --x;
                if(Y2[i]==Y2[j]) --x;
                x+=2*(min(Y2[i],Y2[j])-max(Y1[i],Y1[j])+1);
            }
        }
        if(YY2[Y1[i]-1])
        {
            int p=YY2[Y1[i]-1];
            for(Reg int k=0;kk)
            {
                int j=Ys2[p][k]; if(j>=i||vis[j]) continue;
                if(X2[i]==X1[j]-1) ++x;
                else if(X1[i]==X2[j]+1) ++x;
                vis[j]=1;
                if(X1[i]>X2[j]||X1[j]>X2[i]) continue;
                if(X1[i]==X1[j]) --x;
                if(X2[i]==X2[j]) --x;
                x+=2*(min(X2[i],X2[j])-max(X1[i],X1[j])+1);
            }
        }
        if(YY1[Y2[i]+1])
        {
            int p=YY1[Y2[i]+1];
            for(Reg int k=0;kk)
            {
                int j=Ys1[p][k]; if(j>=i||vis[j]) continue;
                if(X2[i]==X1[j]-1) ++x;
                else if(X1[i]==X2[j]+1) ++x;
                vis[j]=1;
                if(X1[i]>X2[j]||X1[j]>X2[i]) continue;
                if(X1[i]==X1[j]) --x;
                if(X2[i]==X2[j]) --x;
                x+=2*(min(X2[i],X2[j])-max(X1[i],X1[j])+1);
            }
        }
        
        if(XX2[X1[i]-1])
        {
            int p=XX2[X1[i]-1];
            for(Reg int k=0;kk)
                vis[Xs2[p][k]]=0;
        }
        if(XX1[X2[i]+1])
        {
            int p=XX1[X2[i]+1];
            for(Reg int k=0;kk)
                vis[Xs1[p][k]]=0;
        }
        if(YY2[Y1[i]-1])
        {
            int p=YY2[Y1[i]-1];
            for(Reg int k=0;kk)
                vis[Ys2[p][k]]=0;
        }
        if(YY1[Y2[i]+1])
        {
            int p=YY1[Y2[i]+1];
            for(Reg int k=0;kk)
                vis[Ys1[p][k]]=0;
        }
        sum+=x;
    }
    printf("%lld",sum);
    return 0;
}

B. 模板(ac)

$70$分算法：

测试点分治，前$30$分暴力，后$40$分简单的线段树合并。

错误总结：

1、没有正确推测测试点，

考试时看到前边的测试点一个$m<=10$一个$m<=1000$，

然后我ZZ地认为暴力不能跑过$1000$，于是：

if(m<=10){}
else{}

结果连暴力的$30$分都没拿到。

2、题目中显然没有给颜色的范围，于是我把$m>1000$的测试点离散化，然而：

if(m<=10)
{
    dfs(1);
    for(Reg int i=1,x,c;i<=m;++i)
    {
        scanf("%lld%lld",&x,&c);
        change(x,c);
    }
    scanf("%lld",&q);
    for(Reg int i=1,x;i<=q;++i)
    {
        scanf("%lld",&x);
        printf("%lld\n",an[x]);
    }
}
else
{
    for(Reg int i=1,x,c;i<=m;++i)
    {
        scanf("%lld%lld",&x,&c);
        if(!p[c]) p[c]=++top;
        if(!pos[x]) pos[x]=New();
        work(pos[x],1,m,c);
    }
    memset(vis,0,sizeof(vis));
    dfs_re(1);
    scanf("%lld",&q);
    for(Reg int i=1,x;i<=q;++i)
    {
        scanf("%lld",&x);
        printf("%lld\n",ans[x]);
    }
}

上边没有离散化。

3、数组我显然没开够(因为我认为$m<=1000$的点不能跑)。

丑陋的考试$20$分代码：

#include
#include
#include
#include
#include
#define int long long
#define New() new Tree
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define abs(x) ((x)<0?(-1*(x)):(x))
#define Maxn 100050
#define Reg register
using namespace std;
bool vis[Maxn];
int n,m,q,tot,fir[Maxn],fat[Maxn],K[Maxn],lss[25][Maxn],an[25];
int top,lsh[Maxn],ans[Maxn];
map<int,int> p;
struct Tu {int st,ed,next;} lian[Maxn*2];
struct Tree {Tree *lch,*rch; int val;};
Tree *pos[Maxn];
void add(int x,int y)
{
    lian[++tot].st=x;
    lian[tot].ed=y;
    lian[tot].next=fir[x];
    fir[x]=tot;
    return;
}
void dfs(int x)
{
    vis[x]=1;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!vis[lian[i].ed])
        {
            dfs(lian[i].ed);
            fat[lian[i].ed]=x;
        }
    }
    return;
}
void change(int x,int num)
{
    if(lss[x][0]<K[x])
    {
        if(!lss[x][num]) ++an[x];
        ++lss[x][0];
        ++lss[x][num];
    }
    if(fat[x]) change(fat[x],num);
    return;
}
void work(Tree *root,int l,int r,int pos)
{
    if(l==r)
    {
        root->val=1;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)
    {
        if(root->lch==NULL) root->lch=New();
        work(root->lch,l,mid,pos);
    }
    else
    {
        if(root->rch==NULL) root->rch=New();
        work(root->rch,mid+1,r,pos);
    }
    root->val=0;
    if(root->lch!=NULL) root->val+=root->lch->val;
    if(root->rch!=NULL) root->val+=root->rch->val;
    return;
}
Tree* merge(Tree *rot1,Tree *rot2,int l,int r)
{
    if(rot1==NULL) return rot2;
    else if(rot2==NULL) return rot1;
    else
    {
        if(l==r)
        {
            rot1->val|=rot2->val;
            return rot1;
        }
        int mid=(l+r)/2;
        rot1->lch=merge(rot1->lch,rot2->lch,l,mid);
        rot1->rch=merge(rot1->rch,rot2->rch,mid+1,r);
        rot1->val=0;
        if(rot1->lch!=NULL) rot1->val+=rot1->lch->val;
        if(rot1->rch!=NULL) rot1->val+=rot1->rch->val;
        return rot1;
    }
}
void dfs_re(int x)
{
    vis[x]=1;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!vis[lian[i].ed])
        {
            dfs_re(lian[i].ed);
            pos[x]=merge(pos[x],pos[lian[i].ed],1,m);
        }
    }
    if(pos[x]!=NULL) ans[x]+=pos[x]->val;
    return;
}
signed main()
{
    scanf("%lld",&n);
    for(Reg int i=1,x,y;i<=n-1;++i)
    {
        scanf("%lld%lld",&x,&y);
        add(x,y); add(y,x);
    }
    for(Reg int i=1;i<=n;++i) scanf("%lld",&K[i]);
    scanf("%lld",&m);
    if(m<=10)
    {
        dfs(1);
        for(Reg int i=1,x,c;i<=m;++i)
        {
            scanf("%lld%lld",&x,&c);
            change(x,c);
        }
        scanf("%lld",&q);
        for(Reg int i=1,x;i<=q;++i)
        {
            scanf("%lld",&x);
            printf("%lld\n",an[x]);
        }
    }
    else
    {
        for(Reg int i=1,x,c;i<=m;++i)
        {
            scanf("%lld%lld",&x,&c);
            if(!p[c]) p[c]=++top;
            if(!pos[x]) pos[x]=New();
            work(pos[x],1,m,c);
        }
        memset(vis,0,sizeof(vis));
        dfs_re(1);
        scanf("%lld",&q);
        for(Reg int i=1,x;i<=q;++i)
        {
            scanf("%lld",&x);
            printf("%lld\n",ans[x]);
        }
    }
    return 0;
}

丑陋的$70$分代码：

#include
#include
#include
#include
#include
#define int long long
#define New() new Tree
#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define abs(x) ((x)<0?(-1*(x)):(x))
#define Maxn 100050
#define Reg register
using namespace std;
bool vis[Maxn];
int n,m,q,tot,fir[Maxn],fat[Maxn],K[Maxn],lss[1050][1050],an[1050];
int top,lsh[Maxn],ans[Maxn];
map<int,int> p;
struct Tu {int st,ed,next;} lian[Maxn*2];
struct Tree {Tree *lch,*rch; int val;};
Tree *pos[Maxn];
void add(int x,int y)
{
    lian[++tot].st=x;
    lian[tot].ed=y;
    lian[tot].next=fir[x];
    fir[x]=tot;
    return;
}
void dfs(int x)
{
    vis[x]=1;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!vis[lian[i].ed])
        {
            dfs(lian[i].ed);
            fat[lian[i].ed]=x;
        }
    }
    return;
}
void change(int x,int num)
{
    if(lss[x][0]<K[x])
    {
        if(!lss[x][num]) ++an[x];
        ++lss[x][0];
        ++lss[x][num];
    }
    if(fat[x]) change(fat[x],num);
    return;
}
void work(Tree *root,int l,int r,int pos)
{
    if(l==r)
    {
        root->val=1;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)
    {
        if(root->lch==NULL) root->lch=New();
        work(root->lch,l,mid,pos);
    }
    else
    {
        if(root->rch==NULL) root->rch=New();
        work(root->rch,mid+1,r,pos);
    }
    root->val=0;
    if(root->lch!=NULL) root->val+=root->lch->val;
    if(root->rch!=NULL) root->val+=root->rch->val;
    return;
}
Tree* merge(Tree *rot1,Tree *rot2,int l,int r)
{
    if(rot1==NULL) return rot2;
    else if(rot2==NULL) return rot1;
    else
    {
        if(l==r)
        {
            rot1->val|=rot2->val;
            return rot1;
        }
        int mid=(l+r)/2;
        rot1->lch=merge(rot1->lch,rot2->lch,l,mid);
        rot1->rch=merge(rot1->rch,rot2->rch,mid+1,r);
        rot1->val=0;
        if(rot1->lch!=NULL) rot1->val+=rot1->lch->val;
        if(rot1->rch!=NULL) rot1->val+=rot1->rch->val;
        return rot1;
    }
}
void dfs_re(int x)
{
    vis[x]=1;
    for(Reg int i=fir[x];i;i=lian[i].next)
    {
        if(!vis[lian[i].ed])
        {
            dfs_re(lian[i].ed);
            pos[x]=merge(pos[x],pos[lian[i].ed],1,m);
        }
    }
    if(pos[x]!=NULL) ans[x]+=pos[x]->val;
    return;
}
signed main()
{
    scanf("%lld",&n);
    for(Reg int i=1,x,y;i<=n-1;++i)
    {
        scanf("%lld%lld",&x,&y);
        add(x,y); add(y,x);
    }
    for(Reg int i=1;i<=n;++i) scanf("%lld",&K[i]);
    scanf("%lld",&m);
    if(m<=1000)
    {
        dfs(1);
        for(Reg int i=1,x,c;i<=m;++i)
        {
            scanf("%lld%lld",&x,&c);
            if(!p[c]) p[c]=++top;
            if(!pos[x]) pos[x]=New();
            change(x,p[c]);
        }
        scanf("%lld",&q);
        for(Reg int i=1,x;i<=q;++i)
        {
            scanf("%lld",&x);
            printf("%lld\n",an[x]);
        }
    }
    else
    {
        for(Reg int i=1,x,c;i<=m;++i)
        {
            scanf("%lld%lld",&x,&c);
            if(!p[c]) p[c]=++top;
            if(!pos[x]) pos[x]=New();
            work(pos[x],1,m,p[c]);
        }
        memset(vis,0,sizeof(vis));
        dfs_re(1);
        scanf("%lld",&q);
        for(Reg int i=1,x;i<=q;++i)
        {
            scanf("%lld",&x);
            printf("%lld\n",ans[x]);
        }
    }
    return 0;
}

 

 

总结：

上来先看的$T1$，题意很好理解，可以暴搜。。

然后$10$分钟码了一个$n^2$的代码，样例过了。

然后想了想，用了个$vector$存边界，然后就$75$分超时，好像是这个常数有点大。

码完$T1$之后考试将近一半，

马上看$T2$，一看$T2$，线段树合并，然后看到测试点，仿佛可以过掉$10$个点左右。

然后就码了一颗线段树合并和一个暴力，测试点分治嘛。

然后两个样例直接过。。我以为可以拿到$50$到$60$分，然后就跳到$T3$，

其实这个第二个样例跟我打的线段树合并没什么关系，我第一个暴力的范围是$m<=10$。。

然后考试最后20分钟发现。。

我打的线段树合并，它$RE$，然后非常紧张，调了半天，然后过样例了。

最后$20$分。。有点可惜。

$T3$他们都说很水，然而，我并没有剩很长时间，然后码了$dfs$，还死活调不对，

最后凭借我的"骗分"技巧，输出样例$+$错误的$dfs$得了$5$分。

最后$75+20+5=100$，第二题有点可惜。

没什么水平。。。

考试

相关

PMP考试技巧(必备)关键词篇

SQL72 考试分数(一)

6.11考试总结(NOIP模拟7)

PMP考试计算题汇总

第一次考试机试笔记

第一次考试机试笔记

美团-后端开发工程师-在线考试-20211024

毕设：高校考试信息数字化平台（六）——通过form外按钮提交表单

毕设：高校考试信息数字化平台（六）——通过form外按钮提交表单

毕设：高校考试信息数字化平台（六）——通过form外按钮提交表单

期末免考资格考试

普法考试 charles

标签