C2020 2020.10.3测试

信息学——模拟赛

考试情况

考场上期望得分VS实际得分：

期望得分：

实际得分：

……（

T1 file

$1^o$ 分析

模拟题，模拟Trie树或直接画树模拟即可。

注意，不同文件目录下可能有相同的文件名，所以不能用map建树直接模拟。

#include<bits/stdc++.h>
using namespace std;
int n;
int tot;
char s[10005][1005];
string id[10005];
int edge[10005][1005];
bool vst[10005];
map <string,int> mapp;
inline bool cmp(int x,int y)
{
    return id[x]<id[y];
}
inline void search(int x,int dep)
{
    vst[x]=1;
    cout<<id[x]<<endl;
    sort(edge[x]+1,edge[x]+edge[x][0]+1,cmp);
    for (register int i=1;i<=edge[x][0];++i)
        if (!vst[edge[x][i]])
           {
           for (register int j=1;j<=dep;++j)
               printf("|    ");
           printf("|----");
           search(edge[x][i],dep+1);
           }
}
int main(){
    freopen("file.in","r",stdin);
    freopen("file.out","w",stdout);
    scanf("%d",&n);
    for(register int i=1;i<=n;++i)
       {
       scanf("%s",s[i]);
       int len=strlen(s[i]),pre_x=0;
       string c="",pre="";
       for (register int j=0;j<=len;pre+=s[i][j],++j)
           {
           if (s[i][j]=='/'||j==len)
              {
              int &x=mapp[pre];
              if (!x)
                 x=(++tot),id[x]=c;
              edge[pre_x][++edge[pre_x][0]]=x;
              pre_x=x;
              c="";
              }
           else
              c+=s[i][j];
           }
       }
    search(1,0);
    return 0;
}

$2^o$ 总结与反思

题面上没写的就是有可能！！！

T2 compile

$1^o$ 分析

乍一看感觉是DP，但是发现DP无论怎样都只能做到$O(nm)$，根据数据范围考虑贪心。

一个显然的贪心策略：每次取当前可取的最大数。但显然是错的。

hack数据：
4 2
9 8 1 8
贪心解：9+1=10
正解：8+8=16

问题就出在取了这点就不能取相邻点上，这样也许会漏失最优解。

这时候就有一个sao操作——反悔贪心。

其实反悔贪心就是当我们发现当前的最优解不是全局最优解时，撤销当前操作并执行正确操作。

显然所有贪心都可以做这样的反悔操作，只不过有些贪心反悔之后复杂度太高或是找不到如何执行正确操作。

此题是通过巧妙地计算差值来反悔。

假设我们现在取出的最优解（拿一个堆维护最大值）为$a_1$，前继为$a_2$，后继为$a_3$

则我们想要反悔，也就是撤销取$a_1$的操作，改为取$a_2$与$a_3$

那么我们考虑在堆中插入一个值为$a_2+a_3-a_1$的点，这样当我们把这个点取出就达到了撤销$a_1$的贡献加上$a_2+a_3$的贡献的操作。

这样连续操作$m$次就得到了答案。

#include<bits/stdc++.h>
#define mp make_pair
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m,ans;
int a[200005];
struct node{
    int pre,nex;
    int flag;
}edge[200005];
priority_queue < pair<int,int> > q;
inline void update(int x)
{
    edge[edge[x].nex].flag=1,edge[edge[edge[x].nex].nex].pre=x,edge[x].nex=edge[edge[x].nex].nex;
    edge[edge[x].pre].flag=1,edge[edge[edge[x].pre].pre].nex=x,edge[x].pre=edge[edge[x].pre].pre;
}
int main(){
    freopen("compile.in","r",stdin);
    freopen("compile.out","w",stdout);
    n=read(),m=read();
    if (m>n/2)
       {
       printf("Error!");
       return 0;
       }
    for (register int i=1;i<=n;++i)
        a[i]=read(),q.push(mp(a[i],i));
    edge[1].pre=n,edge[1].nex=2,edge[n].pre=n-1,edge[n].nex=1;
    for (register int i=2;i<n;++i)
        edge[i].pre=i-1,edge[i].nex=i+1;
    for (register int i=1;i<=m;++i)
        {
        int x;
        while (edge[(x=q.top().second)].flag)
              q.pop();
        ans+=q.top().first;
        q.pop(),a[x]=a[edge[x].pre]+a[edge[x].nex]-a[x],q.push(mp(a[x],x));
        update(x);
        }
    printf("%d",ans);
    return 0;
}

$2^o$ 总结与反思

带反悔的贪心一般分为反悔自动机和反悔堆，比较少见，但是似乎可以当做骗分技巧。

T3 cost

$1^o$ 分析

MST+LCA的经典套路题（可见luogu货车运输），这种题一般都会推出除MST上的边有用，其他边一定都不是最优解的边这种结论。

例如此题，费用为所有经过路径的最小值，而只要此图联通，那些较大的边一定不会被走（很显然吧不证明了）

而最小生成树就满足边最小且联通，所以我们先跑一遍MST，将图变成树，则在树上求距离就是LCA了。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n,m,q;
int father[100005];
struct Line{
    int u,v,w;
}line[200005];
struct node{
    int v,nex;
    int w;
}edge[200005];
int head[100005],len,tot;
int dep[100005],f[100005][25],maxx[100005][25];
inline bool operator <(Line x,Line y)
{
    return x.w<y.w;
}
inline void add(int u,int v,int w)
{
    tot++,line[tot].u=u,line[tot].v=v,line[tot].w=w;
}
inline void make_map(int u,int v,int w)
{
    len++;
    edge[len].nex=head[u];
    edge[len].v=v;
    edge[len].w=w;
    head[u]=len;
}
inline int Find(int x)
{
    if (father[x]!=x)
       return father[x]=Find(father[x]);
    return father[x];
}
inline void unnion(int f1,int f2)
{
    father[f2]=f1;
}
inline void get_MST()
{
    tot=0;
    for (register int i=1;i<=m;++i)
        {
        int u=line[i].u,v=line[i].v,w=line[i].w,f1=Find(u),f2=Find(v);
        if (f1!=f2)
           {
           tot++,unnion(f1,f2);
           make_map(u,v,w),make_map(v,u,w);
           if (tot==n-1)
              break;
           }
        }
}
inline void Deal_First(int x,int fa)
{
    dep[x]=dep[fa]+1;
    for (register int i=1;i<=20;++i)
        f[x][i]=f[f[x][i-1]][i-1],maxx[x][i]=max(maxx[x][i-1],maxx[f[x][i-1]][i-1]);
    for (register int i=head[x];i;i=edge[i].nex)
        {
        int y=edge[i].v,z=edge[i].w;
        if (y==fa)
           continue;
        f[y][0]=x,maxx[y][0]=z;
        Deal_First(y,x);
        }
}
inline int get_LCA(int x,int y)
{
    int ans=0;
    if (dep[x]<dep[y])
       swap(x,y);
    for (register int i=20;i>=0;--i)
        {
        if (dep[f[x][i]]>=dep[y])
           ans=max(ans,maxx[x][i]),x=f[x][i];
        if (x==y)
           return ans;
        }
    for (register int i=20;i>=0;--i)
        if (f[x][i]!=f[y][i])
           ans=max(ans,max(maxx[x][i],maxx[y][i])),x=f[x][i],y=f[y][i];
    return max(ans,max(maxx[x][0],maxx[y][0]));
}
int main(){
    freopen("cost.in","r",stdin);
    freopen("cost.out","w",stdout);
    n=read(),m=read();
    for (register int i=1;i<=n;++i)
        father[i]=i;
    for (register int i=1;i<=m;++i)
        {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        }
    sort(line+1,line+m+1);
    get_MST(),Deal_First(1,0);
    q=read();
    while (q--)
          {
          int u=read(),v=read();
          printf("%d\n",get_LCA(u,v));
          }
    return 0;
}

$2^o$ 总结与反思

经典套路，考场上LCA写挂了……