本文共 18302 字，大约阅读时间需要 61 分钟。

L3-013 非常弹的球 (30分)

题意：给小球从点（0,0）按角度 [0,90] 抛出，抛出时的能量为 1000J，重力加速度为 $9.8m/s^2$，到达地面后损失的能量为 P%。问最多能够抛出多远。

思路：先计算出抛出的角度。然后就直接循环模拟。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;double m,p,g=9.8;int main(){       scanf("%lf %lf",&m,&p);    m/=100;    double dis=0,E=1000;    while(E>1e-10)    {           double v=sqrt(2*E/m);        dis+=v*v/g;        E=(100-p)*E/100;    }    printf("%.3lf\n",dis);    return 0;}

L3-014 周游世界 (30分)

题意：给定 n 条公交线路，求经过站数最少的线路，如果经过站数相同，选择换乘次数最少的线路。输出经过的站数和换成路线

思路：注意题目中一个细节，每两个站只会被一家公司承包，也就是只有一条线路经过。所以可以对两个站属于哪条线路，做标记。

• 跑最短路的时候，记录上一条线路是什么。用来判断是否和当前线路相同。

MLE了一个点

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e4+10,inf=1e9;int n,m,k;int id[maxn][maxn];vector<int> e[maxn];int dis[maxn],visit[maxn],num[maxn],pre[maxn];struct Node{       int d,u,id;    bool operator<(const Node& b) const    {           return d>b.d;    }};struct Res{       int id,s,t;};void dijstra(int s,int t){       for(int i=1; i<=10000; ++i)    {           dis[i]=inf;        visit[i]=0;        pre[i]=-1;        num[i]=0;    }    dis[s]=0;    num[s]=0;    priority_queue<Node> pq;    pq.push({   0,s,-1});    while(!pq.empty())    {           Node t=pq.top();        pq.pop();        int u=t.u;        if(visit[u]) continue;        visit[u]=1;        for(auto v: e[u])        {               if(dis[v]>dis[u]+1)            {                   dis[v]=dis[u]+1;                num[v]=num[u]+(id[u][v]!=t.id);                pre[v]=u;                pq.push({   dis[v],v,id[u][v]});            }            else if(dis[v]==dis[u]+1)            {                   if(num[v]>num[u]+(id[u][v]!=t.id))                {                       num[v]=num[u]+(id[u][v]!=t.id);                    pre[v]=u;                }            }        }    }    vector<int> ans;    for(int i=t; i!=-1; i=pre[i]) ans.push_back(i);    reverse(ans.begin(),ans.end());    int m=ans.size();    //for(int i=1; i<=m; ++i) printf("%d%c",ans[i-1],i==m?'\n':' ');    if(dis[t]==inf)    {           puts("Sorry, no line is available.");        return;    }    vector<Res> res;    int j;    for(int i=0; i<m-1; i=j)    {           j=i+1;        int id1=id[ans[i]][ans[i+1]];        while(1)        {               if(j+1>=m) break;            int id2=id[ans[j]][ans[j+1]];            if(id1==id2) j++;            else break;        }        res.push_back({   id1,ans[i],ans[j]});    }    printf("%d\n",ans.size()-1);    int len=res.size();    for(int i=0; i<len; ++i)        printf("Go by the line of company #%d from %04d to %04d.\n",res[i].id,res[i].s,res[i].t);}int main(){       scanf("%d",&n);    for(int i=1; i<=n; ++i)    {           scanf("%d",&k);        int u,v;        scanf("%d",&u);        for(int j=2; j<=k; ++j)        {               scanf("%d",&v);            e[u].push_back(v);            e[v].push_back(u);            id[u][v]=id[v][u]=i;            u=v;        }    }    scanf("%d",&m);    while(m--)    {           int s,t;        scanf("%d%d",&s,&t);        dijstra(s,t);    }    return 0;}

L3-015 球队“食物链” (30分)

题意：给定 $n\times n$ 的网格表示 n 个球队的胜负情况。要求找出一个字典序最小的排列满足，$p_1$ 打败 $p_2$,$p_2$打败 $p_3，\dots ,p_n$ 打败 $p_1$

思路：dfs 爆搜 +剪枝。要求字典序最小，那就从 1 开始搜。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=20+5;int n;vector<int> e[maxn];int visit[maxn],mp[maxn][maxn];int sta[maxn],top;bool dfs(int u){       if(top==n&&mp[u][1]) return 1;    if(top==n) return 0;    bool ok=0;    for(int i=1;i<=n;++i)    	if(!visit[i]&&mp[i][1]==1) ok=1;    if(!ok) return 0;    for(int v=1; v<=n; ++v)    {           if(!visit[v]&&mp[u][v]==1)        {               visit[v]=1;            sta[++top]=v;            if(dfs(v)) return 1;            top--;            visit[v]=0;        }    }    return 0;}int main(){       scanf("%d",&n);    for(int i=1; i<=n; ++i)    {           char s[30];        scanf("%s",s+1);        for(int j=1; j<=n; ++j)            if(s[j]=='L') mp[j][i]=1;            else if(s[j]=='W') mp[i][j]=1;    }    sta[++top]=1;    visit[1]=1;    if(dfs(1))    {           for(int i=1; i<=n; ++i) printf("%d%c",sta[i],i==n?'\n':' ');    }    else puts("No Solution");    return 0;}

L3-016 二叉搜索树的结构 (30分) （二叉搜索树：建树）

题意：给定一个序列建树，然后判断相应的操作。

思路：建完树然后做相应的判断就好了。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n,m;struct Node{       int val,depth;    Node* ls,* rs,* fa;};void insert(Node*& rt,Node* f,int val,int depth){       if(rt==NULL)    {           rt=new Node;        rt->val=val;        rt->ls=NULL;        rt->rs=NULL;        rt->depth=depth;        rt->fa=f;        return;    }    if(rt->val>val) insert(rt->ls,rt,val,depth+1);    else if(rt->val<val) insert(rt->rs,rt,val,depth+1);}Node* find(Node* rt,int val){       if(rt==NULL) return NULL;    if(rt->val>val) return find(rt->ls,val);    else if(rt->val==val) return rt;    else if(rt->val<val) return find(rt->rs,val);}int main(){       Node* root=NULL;    scanf("%d",&n);    for(int i=1; i<=n; ++i)    {           int x;        scanf("%d",&x);        insert(root,NULL,x,0);    }    scanf("%d",&m);    getchar();    while(m--)    {           int x,y;        string op;        getline(cin,op);        if(op.find("root")!=-1)        {               sscanf(op.c_str(),"%d is the root",&x);            if(root!=NULL&&root->val==x) puts("Yes");            else puts("No");        }        else if(op.find("siblings")!=-1)        {               sscanf(op.c_str(),"%d and %d are siblings",&x,&y);            Node* p=find(root,x);            Node* q=find(root,y);            if(p!=NULL&&q!=NULL&&p->fa==q->fa) puts("Yes");            else puts("No");        }        else if(op.find("parent")!=-1)        {               sscanf(op.c_str(),"%d is the parent of %d",&x,&y);            Node* p=find(root,x);            Node* q=find(root,y);            if(p!=NULL&&q!=NULL&&p==q->fa) puts("Yes");            else puts("No");        }        else if(op.find("left")!=-1)        {               sscanf(op.c_str(),"%d is the left child of %d",&x,&y);            Node* p=find(root,x);            Node* q=find(root,y);            if(p!=NULL&&q!=NULL&p==q->ls) puts("Yes");            else puts("No");        }        else if(op.find("right")!=-1)        {               sscanf(op.c_str(),"%d is the right child of %d",&x,&y);            Node* p=find(root,x);            Node* q=find(root,y);            if(p!=NULL&&q!=NULL&p==q->rs) puts("Yes");            else puts("No");        }        else if(op.find("same")!=-1)        {               sscanf(op.c_str(),"%d and %d are on the same level",&x,&y);            Node* p=find(root,x);            Node* q=find(root,y);            if(p!=NULL&&q!=NULL&p->depth==q->depth) puts("Yes");            else puts("No");        }    }    return 0;}

L3-017 森森快递 (30分)

题意：有 n 座城市在一条直线上，第 i 座城市和第 i + 1 座城市之间道路的载重量为 $c_i$ 。现有 m 条线路，第 i 条线路在城市 $l_i$ 和 $r_i$ 之间发货。假设可以无限发货，但发货时间不确定。问最多能够运输多少的货物。

思路：先按右端点升序、再按左端点降序排。

• 当右端点固定的时候，显然左端点越大越优，也就是被包含的区间越优。
• 当两个区间重叠的时候，任意取就好了。因为重叠部分贡献是固定的，被哪里取完都行。
• 总而言之，被包含的区间更优，其他情况而任意取

#include <bits/stdc++.h>#define ls (rt<<1)#define rs (rt<<1|1)#define ll long longusing namespace std;const int maxn=1e5+5,inf=2e9;int n,m,a[maxn];int st[maxn<<2],lazy[maxn<<2];struct Node{       int l,r;    bool operator<(const Node& b) const    {           if(r==b.r) return l>b.l;        return r<b.r;    }} p[maxn];void pushDown(int rt){       if(lazy[rt])    {           st[ls]-=lazy[rt];        st[rs]-=lazy[rt];        lazy[ls]+=lazy[rt];        lazy[rs]+=lazy[rt];        lazy[rt]=0;    }}void build(int rt,int L,int R){       if(L==R)    {           st[rt]=a[L];        return;    }    int mid=(L+R)>>1;    build(ls,L,mid);    build(rs,mid+1,R);    st[rt]=min(st[ls],st[rs]);}void update(int rt,int l,int r,int L,int R,int val){       if(l<=L&&R<=r)    {           st[rt]-=val;        lazy[rt]+=val;        return;    }    pushDown(rt);    int mid=(L+R)>>1;    if(l<=mid) update(ls,l,r,L,mid,val);    if(r>mid) update(rs,l,r,mid+1,R,val);    st[rt]=min(st[ls],st[rs]);}int query(int rt,int l,int r,int L,int R){       if(l<=L&&R<=r) return st[rt];    pushDown(rt);    int mid=(L+R)>>1;    int ans=inf;    if(l<=mid) ans=min(ans,query(ls,l,r,L,mid));    if(r>mid) ans=min(ans,query(rs,l,r,mid+1,R));    st[rt]=min(st[ls],st[rs]);    return ans;}int main(){       scanf("%d%d",&n,&m);    for(int i=1; i<=n-1; ++i) scanf("%d",&a[i]);    build(1,1,n-1);    for(int i=1; i<=m; ++i)    {           int l,r;        scanf("%d%d",&l,&r);        if(l>r) swap(l,r);        p[i]= {   l,r};    }    sort(p+1,p+1+m);    ll ans=0;    for(int i=1; i<=m; ++i)    {           int l=p[i].l,r=p[i].r;        if(l==p[i-1].l) continue;        ll mi=query(1,l+1,r,1,n-1);        if(mi>0) ans+=mi,update(1,l+1,r,1,n-1,mi);    }    printf("%lld\n",ans);    return 0;}

L3-018 森森美图 (30分)

题意：给定一个 $n\times m$ 的图，在图上选择两点 A、B形成一条直线，在直线两端分别寻找两条不经过直线上点且从 A 到 B 的最短路，求它们的和。（具体权值见原题）
思路：通过叉积计算出图上可以行走的点，然后 bfs 暴力跑最短路。

dijstra

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=100+5;const double r=sqrt(2.0)-1;int n,m;int sx,sy,ex,ey;int dx[]= {   0,0,1,-1,1,1,-1,-1};int dy[]= {   1,-1,0,0,1,-1,1,-1};double cost[]= {   0,0,0,0,r,r,r,r};int val[maxn][maxn],mp[maxn][maxn],visit[maxn][maxn];double dis[maxn][maxn];int ok;int calc(int x,int y){       int val=(x-sx)*(ey-sy)-(y-sy)*(ex-sx);    if(val) val=val/abs(val);    return val;}struct Node{       int x,y;    double d;    bool operator<(const Node& b) const    {           return d>b.d;    }};double bfs(){       for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            dis[i][j]=9e18,visit[i][j]=0;    dis[sx][sy]=val[sx][sy];    priority_queue<Node> pq;    pq.push({   sx,sy,val[sx][sy]});    while(!pq.empty())    {           Node t=pq.top();        pq.pop();        int x=t.x,y=t.y;        if(visit[x][y]) continue;        visit[x][y]=1;        for(int i=0; i<8; ++i)        {               int nx=x+dx[i];            int ny=y+dy[i];            if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]!=ok) continue;            double w=val[nx][ny]+cost[i]*(val[nx][ny]+val[x][y]);            if(dis[nx][ny]>dis[x][y]+w) dis[nx][ny]=dis[x][y]+w,pq.push({   nx,ny,dis[nx][ny]});        }    }    return dis[ex][ey];}int main(){       scanf("%d%d",&n,&m);    for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            scanf("%d",&val[i][j]);    scanf("%d%d%d%d",&sy,&sx,&ey,&ex);    sy++,sx++,ey++,ex++;    for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            mp[i][j]=calc(i,j);    double ans=-val[sx][sy]-val[ex][ey];    mp[sx][sy]=mp[ex][ey]=1;    ok=1;    ans+=bfs();    mp[sx][sy]=mp[ex][ey]=-1;    ok=-1;    ans+=bfs();    printf("%.2lf\n",ans);    return 0;}

BFS

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=100+5;const double r=sqrt(2.0)-1;int n,m;int sx,sy,ex,ey;int dx[]= {   0,0,1,-1,1,1,-1,-1};int dy[]= {   1,-1,0,0,1,-1,1,-1};double cost[]= {   0,0,0,0,r,r,r,r};int val[maxn][maxn],mp[maxn][maxn];double dis[maxn][maxn];int ok;int calc(int x,int y){       int val=(x-sx)*(ey-sy)-(y-sy)*(ex-sx);    if(val) val=val/abs(val);    return val;}struct Node{       int x,y;};double bfs(){       for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            dis[i][j]=9e18;    dis[sx][sy]=val[sx][sy];    queue<Node> q;    q.push({   sx,sy});    while(!q.empty())    {           Node t=q.front();        q.pop();        int x=t.x,y=t.y;        for(int i=0; i<8; ++i)        {               int nx=x+dx[i];            int ny=y+dy[i];            if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]!=ok) continue;            double w=val[nx][ny]+cost[i]*(val[nx][ny]+val[x][y]);            if(dis[nx][ny]>dis[x][y]+w) dis[nx][ny]=dis[x][y]+w,q.push({   nx,ny});        }    }    return dis[ex][ey];}int main(){       scanf("%d%d",&n,&m);    for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            scanf("%d",&val[i][j]);    scanf("%d%d%d%d",&sy,&sx,&ey,&ex);    sy++,sx++,ey++,ex++;    for(int i=1; i<=n; ++i)        for(int j=1; j<=m; ++j)            mp[i][j]=calc(i,j);    double ans=-val[sx][sy]-val[ex][ey];    mp[sx][sy]=mp[ex][ey]=1;    ok=1;    ans+=bfs();    mp[sx][sy]=mp[ex][ey]=-1;    ok=-1;    ans+=bfs();    printf("%.2lf\n",ans);    return 0;}

L3-020 至多删三个字符 (30分)

题意：给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？

思路：设 $dp[i][j]$ 表示前 i 个字符串选择了 j 个字符串组成的不同字符串的方案数。

• 对于第 i 个字符串选或者不选两种决策：$dp[i][j]=dp[i-1][j]+dp[i-1][j-1]$
• 这里产生重复的点在于：在 abcdefd 中删去 def 和删去 efd 是一样的。那么就只需要保留其中一个 d 产生的方案数计数就好了
• 考虑一个比较好计数的方法：在计数 $dp[i][j]$ 时，第 i 位和前面第 k 位字符相同，那么其中选择第 k 位的方案被计数了两次，减去一次就好了。而选择第 k 位的方案数为：$dp[k-1][j-(i-k)]$

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e6+5;string s;ll dp[maxn][4],last[30];int main(){       cin>>s;    int n=s.size();    s='0'+s;    dp[0][0]=1;    for(int i=1; i<=n; ++i)    {           for(int j=0; j<=3; ++j)        {               dp[i][j]=dp[i-1][j];            if(j>=1) dp[i][j]+=dp[i-1][j-1];            int k=last[s[i]-'a'+1];            if(k!=0&&j-(i-k)>=0) dp[i][j]-=dp[k-1][j-(i-k)];        }        last[s[i]-'a'+1]=i;    }    ll ans=0;    for(int i=0; i<=3; ++i) ans+=dp[n][i];    cout<<ans<<"\n";    return 0;}

L3-021 神坛 (30分)

题意：给定 n 个点，请你选择 3 个点组成一个面积最小的三角形，输出个最小的面积

思路：枚举每个点作为极点，做极角排序，最小的三角形面积出现在相邻的两个向量构成的三角形中

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=1e5+5;int n;struct Point{       ll x,y;} p[maxn],q[maxn];ll cross(Point a,Point b){       return a.x*b.y-a.y*b.x;}bool cmp(Point a,Point b){       return cross(a,b)>0;}int main(){       scanf("%d",&n);    for(int i=1; i<=n; ++i) scanf("%lld%lld",&p[i].x,&p[i].y);    double ans=9e18;    for(int i=1; i<=n; ++i)    {           int cnt=0;        for(int j=1; j<=n; ++j)        {               if(i==j) continue;            q[++cnt]= {   p[j].x-p[i].x,p[j].y-p[i].y};        }        sort(q+1,q+1+cnt,cmp);        for(int j=1; j<=cnt-1; ++j)            ans=min(ans,fabs(cross(q[j],q[j+1]))*0.5);    }    printf("%.3lf\n",ans);    return 0;}

L3-022 地铁一日游 (30分)

题意：地铁计费价格的方式是：2 元起步，每增加 k 公里加 1 元。森森在地铁的每个站能够到达的地点是：同价格中距离最远的站，或者是地铁线路末端终点。给定一个起点，问他能够到达哪些站点。

思路：处理出每个点能够到达的点建图，然后 dfs 即可。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=210,inf=1e9;int n,m,k,q;int dis[maxn][maxn],mp[maxn][maxn];vector<int> e[maxn];int visit[maxn],sta[maxn];void floyd(){       memcpy(dis,mp,sizeof(mp));    for(int k=1; k<=n; ++k)        for(int i=1; i<=n; ++i)            for(int j=1; j<=n; ++j)                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}void dfs(int u){       visit[u]=1;    for(auto v: e[u])    {           if(visit[v]) continue;        dfs(v);    }}int main(){       scanf("%d%d%d",&n,&m,&k);    for(int i=1; i<=n; ++i)        for(int j=1; j<=n; ++j)            mp[i][j]=inf;    for(int i=1; i<=n; ++i) mp[i][i]=0;    for(int i=1; i<=m; ++i)    {           int u,v,w;        scanf("%d",&u);        sta[u]=1;        while(1)        {               char c=getchar();            if(c=='\n') break;            scanf("%d%d",&w,&v);            if(w<mp[u][v]) mp[u][v]=mp[v][u]=w;            u=v;        }        sta[u]=1;    }    floyd();    for(int i=1; i<=n; ++i)    {           map<int,int> d;        for(int j=1; j<=n; ++j)        {               if(i==j) continue;            int cost=(dis[i][j])/k+2;            if(dis[i][j]!=inf) d[cost]=max(d[cost],dis[i][j]);        }        for(int j=1; j<=n; ++j)        {               if(i==j) continue;            int cost=(dis[i][j])/k+2;            if(sta[j]&&dis[i][j]!=inf||dis[i][j]==d[cost]&&dis[i][j]!=inf)                e[i].push_back(j);        }    }    scanf("%d",&q);    while(q--)    {           int rt;        scanf("%d",&rt);        memset(visit,0,sizeof(visit));        dfs(rt);        vector<int> ans;        for(int i=1; i<=n; ++i)            if(visit[i]) ans.push_back(i);        int m=ans.size();        for(int i=1; i<=m; ++i) printf("%d%c",ans[i-1],i==m?'\n':' ');    }    return 0;}

L3-023 计算图 (30分)

题意：给定一个计算图，计算式子的最终结果，并对每个变量求偏导。

思路：处理出每个点的 函数值 $f[i]$ 和导数值 $g[i]$。把每个与之相连的点都看做一个函数，然后根据导数求导规则求解。

#include <bits/stdc++.h>#define ll long longusing namespace std;const int maxn=5e4+5;int n,op[maxn];double f[maxn],g[maxn],val[maxn];bool visit[maxn];vector<int> vec;int in[maxn],x;vector<int> e[maxn];void dfs(int u){       if(visit[u]) return;    visit[u]=1;    if(op[u]==0) f[u]=val[u],g[u]=(x==u?1:0);    else if(op[u]==1)    {           int v1=e[u][0],v2=e[u][1];        dfs(v1),dfs(v2);        f[u]=f[v1]+f[v2];        g[u]=g[v1]+g[v2];    }    else if(op[u]==2)    {           int v1=e[u][0],v2=e[u][1];        dfs(v1),dfs(v2);        f[u]=f[v1]-f[v2];        g[u]=g[v1]-g[v2];    }    else if(op[u]==3)    {           int v1=e[u][0],v2=e[u][1];        dfs(v1),dfs(v2);        f[u]=f[v1]*f[v2];        g[u]=f[v1]*g[v2]+g[v1]*f[v2];    }    else if(op[u]==4)    {           int v1=e[u][0];        dfs(v1);        f[u]=exp(f[v1]);        g[u]=exp(f[v1])*g[v1];    }    else if(op[u]==5)    {           int v1=e[u][0];        dfs(v1);        f[u]=log(f[v1]);        g[u]=g[v1]/f[v1];    }    else if(op[u]==6)    {           int v1=e[u][0];        dfs(v1);        f[u]=sin(f[v1]);        g[u]=cos(f[v1])*g[v1];    }}int main(){       scanf("%d",&n);    for(int i=0; i<n; ++i)    {           int x,y;        scanf("%d",&op[i]);        if(op[i]==0)        {               scanf("%lf",&val[i]);            vec.push_back(i);        }        else if(op[i]>=1&&op[i]<=3)        {               scanf("%d%d",&x,&y);            e[i].push_back(x);            e[i].push_back(y);            in[x]++,in[y]++;        }        else if(op[i]>=4&&op[i]<=6)        {               scanf("%d",&x);            e[i].push_back(x);            in[x]++;        }    }    int rt=0;    for(int i=0; i<n; ++i)        if(in[i]==0) rt=i;    vector<double> ans;    for(auto i: vec)    {           x=i;        memset(visit,0,sizeof(visit));        dfs(rt);        ans.push_back(g[rt]);    }    printf("%.3lf\n",f[rt]);    int m=ans.size();    for(int i=1; i<=m; ++i) printf("%.3lf%c",ans[i-1],i==m?'\n':' ');    return 0;}