我决定，为了去除冗余的文章长度，所有代码删掉头文件和快读。

塔(tower)

洛谷题目：P1651 塔

我几乎毫不犹豫就先花5分钟打了一发暴搜，检查没有发现任何问题，最后交上去就有80分：

int h[55],n,m,a,b,c,ans;
bool vis[55];

bool check(int cnt,int hmax,int sum,int last)
{
    if (sum==hmax && cnt==2) return 1;
    if (sum==hmax && cnt==1) return check(2,hmax,0,0);
    if (sum>hmax) return 0;
    for (int i=last+1;i<=n;i++)
    {
        if (vis[i]) continue;
        vis[i]=1;
        if (check(cnt,hmax,sum+h[i],i)) return 1;
        vis[i]=0;
    }
    return 0;
}

inline bool cmp(int x,int y)
{
    return x>y;
}

int main()
{
    n=read();
    int sum=0;
    for (int i=1;i<=n;i++) h[i]=read(),sum+=h[i];
    sort(h+1,h+n+1,cmp);
    ans=-1;
    for (int i=sum>>1;i;i--)
    {
        if (check(1,i,0,0))
        {
            ans=i;
            break;
        }
    }
    printf("%d",ans);
    return 0;
}

可以说是十分划算了，要什么正解系列。

正解就是一个dp，用 $ f[i][j] $ 表示放到了第i个，两个塔的差值是j时高塔的最大高度。决策有三种：

1. 不要
2. 放到高塔，差值变大
3. 放到低塔，差值变小（或者反超）

对应方程就是：

int f[55][500005],n,m,a,b,c,s[55],sum;

int main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read(),sum+=s[i];
    memset(f,-0x3f,sizeof(f));
    f[0][0]=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=0;j<=sum;j++)
        {
            f[i][j]=max(f[i-1][j],f[i-1][j+s[i]]);
            if (j>s[i]) f[i][j]=max(f[i][j],f[i-1][j-s[i]]+s[i]);
            else f[i][j]=max(f[i][j],f[i-1][s[i]-j]+j);
        }
    }
    if (!f[n][0]) printf("-1");
    else printf("%d",f[n][0]);
    return 0;
}

还有实名反对洛谷第一个题解，数组大小开的都是错的，真不知道怎么做出来的。

圆(circle）

洛谷题目：P1652 圆

大水题。只是注意是曲线，不是直线，我写了半天才发现看错题了。这就意味着对于每个圆只需要判断两个点在圆内还是圆外，如果在异端就把答案++即可。

int sx,sy,ex,ey,n,A,B,C,ans;
struct cir{
    int x,y,r;
} c[55];

inline double dis(int x1,int y1,int x2,int y2)
{
    return sqrt((double)(x1-x2)*(x1-x2)+(double)(y1-y2)*(y1-y2));
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) c[i].x=read();
    for (int i=1;i<=n;i++) c[i].y=read();
    for (int i=1;i<=n;i++) c[i].r=read();
    sx=read(); sy=read(); ex=read(); ey=read();
    for (int i=1;i<=n;i++)
    {
        double dis1=dis(sx,sy,c[i].x,c[i].y),dis2=dis(ex,ey,c[i].x,c[i].y);
        if (dis1<c[i].r && dis2>c[i].r) ans++;
        else if (dis1>c[i].r && dis2<c[i].r) ans++;
    }
    printf("%d",ans);
    return 0;
}

猴子(monkey)

洛谷题目：P1653 猴子

我一开始以为真的是树，这样放开以后把他的子树中所有结点更新答案即可，跑一遍dfs记录dfs序和子树大小，然后用线段树维护即可。敲完了发现TM竟然还有互相拉这种操作，然后就GG了，水了个暴力的10分。

看了题解才发现可以把放手的操作建成图。

事实上我们可以把猴子放手的时间当作这条边的边权，而不放手的边权为一个大数，我们需要求得其实就是一条单源路径，让这条路径最小边权最大，直接输出这个值即可，若这个值为那个大数，就输出-1。(https://www.luogu.org/blog/the-Despair/solution-p1653)

不过我觉得把这个叫做spfa还是有些欠妥。其实就是一个BFS。

int lson[200005],rson[200005],lfa[200005],rfa[200005],n,m,a,b,c,mn[200005],head[200005],cnt,ans[200005];
struct Edge{
    int next,to,w;
} edge[800005];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

inline void bfs()
{
    queue <int> q;
    ans[1]=m;
    q.push(1);
    while (!q.empty())
    {
        int x=q.front(); q.pop();
        for (int i=head[x];i;i=edge[i].next)
        {
            int y=edge[i].to,w=min(edge[i].w,ans[x]);
            if (w>ans[y])
            {
                ans[y]=w;
                q.push(y);
            }
        }
    }
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++) lson[i]=read(),rson[i]=read(),lfa[i]=rfa[i]=m;
    for (int i=0;i<m;i++)
    {
        a=read(); b=read();
        if (b==1) lfa[a]=min(lfa[a],i);
        else rfa[a]=min(rfa[a],i);
    }
    for (int i=1;i<=n;i++)
    {
        if (lson[i]!=-1) add(i,lson[i],lfa[i]),add(lson[i],i,lfa[i]);
        if (rson[i]!=-1) add(i,rson[i],rfa[i]),add(rson[i],i,rfa[i]);
    }
    bfs();
    for (int i=1;i<=n;i++)
    {
        if (ans[i]==m) printf("-1\n");
        else printf("%d\n",ans[i]);
    }
    return 0;
}

山(mountain)

洛谷题目：P1663 山

我一开始就被题目给吓住了，就没去做。后来发现这个着实是一个大水题。

题目的要求其实就是那个灯要在每一条线上或者上方，得出每条线的解析式后二分答案即可。

struct point{
    int x,y;
} pt[5005];
struct line{
    double k,b;
} l[5005];
int n,m,a,b,c;

inline bool check(double x)
{
    double rr=1e9,ll=-1e9;
    for (int i=1;i<=n;i++)
    {
        if (l[i].k==0 && l[i].b>x) return 0;
        if (l[i].k<0) rr=min(rr,(l[i].b-x)/l[i].k);
        if (l[i].k>0) ll=max(ll,(l[i].b-x)/l[i].k);
    }
    return ll<=rr;
}

int main()
{
    n=read();
    for (int i=1;i<=n;i++) pt[i].x=read(),pt[i].y=read();
    for (int i=1;i<n;i++)
    {
        l[i].k=(double)(pt[i+1].y-pt[i].y)/(double)(pt[i+1].x-pt[i].x);
        l[i].b=(double)pt[i].y-l[i].k*pt[i].x;
    }
    double l=0,r=1000000;
    while (r-l>=1e-3)
    {
        double mid=(l+r)/2.0;
        if (check(mid)) r=mid;
        else l=mid;
    }
    printf("%.2f",l);
    return 0;
}

总结

我今天的得分是80+100+10+0=190.总的来说还是不错，但是我发现读错题这种失误越来越多了。以后还是应该把题认真读完，不要读到一半一激动就开始打，打完了才发现读错题了。这样还特别容易心态爆炸。

以上。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/contest-summary-zj7.html