校内比赛10.25总结&题解

· · 个人记录

今天又打了一场校内赛

A. 小O的珠子

小O有一些很漂亮的珠子，根据小O对珠子的喜欢程度，编号为a到z。

珠子们之间用魔力相互吸引，排列成一条线。

有一天，小Y乱丢法术，一不小心把某些珠子之间的魔力消除了，珠子们断成了n条。

现在，小O想知道，将断开的n条珠子们重新排列，能得到的字典序最小的序列是什么。

题解:

比赛时想简单了，以为直接排序就可以了，结果含泪爆零

比如下面这个样例

2
ab
aba

发现如果按正常排序的话是 ababa

但实际上最小的是 abaab

为啥呢，因为字符串的长度不同，如果是两个长度一样的字符串，那么肯定是正常排序就可以了

于是应该把排序函数改写一下

对于相邻两个字符串s1,s2，如果s1s2字典序比s2s1小，我们定义这样为s1<s2

那么显然，如果s1>s2，交换s1,s2更优

Code

#include<bits/stdc++.h>
using namespace std;
int n;
string st[200005];
bool cmp(string a,string)
{
    string c=a+b;
    string d=b+a;
    return c<d;
}
int main()
{
    freopen("bead.in","r",stdin);
    freopen("bead.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>st[i];
    }
    sort(st+1,st+n+1,cmp);
    for(int i=1;i<=n;i++)
    cout<<st[i];
    return 0;
}

B. 王国的传送门

一个王国有 N 个城镇，编号为 1 到 N ,城镇 1 是首都。

王国中的每个城镇都有一个单向传送门，可以将人从一个城镇快速传送到另一个城镇

城镇 i 的传送目标是城镇 a[i] (1\leq a[i]\leq N)

通过多次使用传送门，可以保证从任何城镇到达首都。

因为国王洛浔喜欢整数 K ,所以洛浔想要调整一些传送门的目的地（出发地不变）

以便从任何城镇开始，使用传送门恰好K次后将可以到达首都。

并且，洛浔允许这 K 次中重复使用任意传送门。

请你帮洛浔找到需要调整的传送门的最小数量（允许存在自环）。

题解:

通过观察样例可以发现，这是一个有着 N 个点，N 条边的有向图

题目又保证了每个点都能到 1 号点，所以不难发现这个图去掉 1 号点连出去的那条边后就是一棵树，

因为要保证每个点跑 K 次到了 1 号点，如果这是一棵树，怎么会有这么好的事，所以 1 号点肯定要连边到自己

然后当某一个点跑到 1 后就不停的跟自己绕圈就可以了

那那些跟 1 号点的距离比 K 大的点呢?

他们可不能通过绕圈达成目的

于是他们就要连边到 1 号点，或者等其他点连边后到 1 的最短距离 \leq K

那这个问题就变成了 树上 K 覆盖问题了，可以参考

P2279 [HNOI2003]消防局的设立

树形 dp 也行，不过像这里的 K 覆盖问题就不适用了，时间空间都会炸

于是考虑另一种做法，利用贪心的思路，每次选出最深的点，然后把他的 k-1 级父亲连边到 1 号点

比赛时我打了优先队列，AC了，代码如下

Code

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
struct node{int x,y,next;}p[400005];
struct node1
{
    int dep,id;
    friend bool operator<(const node1 &x,const node1 &y)
    {
        return x.dep<y.dep;
    };
};
int n,dep[200005],ans=1,useless,k,maxx=-1e9;
int len=0,last[200005];
//int f[100005][2];//1:自己连一条到首都，0:自己不连 
int s[200005],slen=0;
//vector<int>v;
int fak[200005];
bool v[200005];
priority_queue<node1>que;
void ins(int x,int y)
{
    p[++len]={x,y,last[x]};
    last[x]=len;
}
void dfs(int now,int faa)
{
    dep[now]=dep[faa]+1;
    maxx=max(maxx,dep[now]);
    if(dep[now]<=k)v[now]=1;
    for(int i=last[now];i;i=p[i].next)
    {
        int y=p[i].y;
        dfs(y,now);
    }
}
void dfs1(int now,int faa)
{
    s[++slen]=now;
    fak[now]=s[max(slen-k+1,1)];
    que.push((node1){dep[now],now});
    for(int i=last[now];i;i=p[i].next) 
    {
        int y=p[i].y;
        dfs1(y,now);
    }
    slen--;
}
void dfs3(int now,int faa)
{
    dep[now]=dep[faa]+1;
    if(dep[now]<=k)v[now]=1;else return;
    for(int i=last[now];i;i=p[i].next)
    {
        int y=p[i].y;
        dfs3(y,now);
    }
}
int main()
{
    freopen("gate.in","r",stdin);
    freopen("gate.out","w",stdout);
    scanf("%d%d",&n,&k);
    scanf("%d",&useless);
    for(int i=2;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        ins(x,i);
    }
    if(useless==1)ans--;
    dep[0]=-1;
    dfs(1,0);
    dfs1(1,0);
    while(!que.empty())
    {
        node1 now1=que.top();
        que.pop();
        if(v[now1.id])continue;
        dfs3(fak[now1.id],1);
//      printf("%d\n",fak[now1.id]);
        ans++;
    }
    printf("%d",ans);
    return 0;
}

而下面是题解的做法

直接一遍 dfs

如果 dfs 下去最远的儿子等于 K-1 了，而且当前点的父节点还不是 1

那么他就需要吧自己连向 1 ，然后此时他的 dep 变成0，他原本的父节点就不算他了

可恶的std竟然只写了26行

std

#include<bits/stdc++.h>
using namespace std;
vector<int>v[109990];
int n, k, a, y, i = 1;
int s(int x, int p = 0) 
{
    int r = 0;
    for (auto to : v[x])
    r = max(r, s(to, x));
    if (++r >= k && p)
    a++, r = 0;
    return r;
}
int main() 
{
    ios::sync_with_stdio(false);
    cin>>n>>k>>y;
    if (y!=1)a++;
    for (;i<n;i++) 
    {
        cin>>y;
        v[y-1].push_back(i);
    }
    s(0);
    cout<<a<<endl;
}