CF杂题题解

发表于 2022-09-26 更新于 2022-12-16 分类于题解

129B. Students and Shoelaces

题意：一个 $n$ 个点 $m$ 条边的无向图，每一轮删去所有度数为 $1$ 的点，问删几轮停止。

暴力模拟每一轮即可，每次删点更新邻居度数。

code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n , m;
int cnt[128];
int a[128][128];
int main() {
    int ans = 0;
    int q , w;
    scanf ( "%d%d" , &n , &m );
    while ( m -- ) {
        scanf ( "%d%d" , &q , &w );
        a[q][w] = a[w][q] = 1;
        ++ cnt[q]; ++ cnt[w];
    }
    while ( 1 ) {
        int i;
        vector < int > c;
        for (i = 1; i <= n; i++) {
            if ( cnt[i] == 1 ) {
                c.push_back ( i );
            }
        }
        if ( !(int)c.size() ) break;
        ++ ans;
        for (i = 0; i < (int)c.size(); i++) {
            cnt[ c[i] ] = 0;
            for (int j = 1; j <= n; j++) {
                if ( a[ c[i] ][j] == 1 ) {
                    -- cnt[j];
                    a[ c[i] ][j] = a[j][ c[i] ] = 0;
                }
            }
        }
    }
    printf ( "%d\n" , ans );
    return 0;
}

902B. Coloring a Tree

题意：一棵有根树，根结点为 $1$ ，初始每个节点的颜色为 $0$ ，每次操作可以将一个子树全部涂上一种颜色，问达到目标颜色状态的最小操作数。

做法 1

显然要从上往下涂色，dfs 时参数里传入子树目前的颜色，判断要不要更改。

code

By MForest

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define in(x); { for (auto &qwertyuiop : x) cin >> qwertyuiop; }
#define out(x); { for (auto qwertyuiop : x) cout << qwertyuiop << ' '; cout << endl; }
//#define int long long
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
vector <int> g[20000];
int c[20000];
int dfs(int v, int p, int uc) {
    int ans = 0;
    if (c[v] != uc) {
        uc = c[v];
        ans++;
    }
    for (int i : g[v]) {
        if (i != p) {
            ans += dfs(i, v, uc);
        }
    }
    return ans;
}
void solve() {
    int n; cin >> n;
    for (int i = 2; i <= n; i++) {
        int x; cin >> x;
        g[x].pb(i);
    }
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    cout << dfs(1, 0, 0);
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
}

做法 2

可以直接判断一个节点和其父亲的目标颜色是否相同，如果不同则一定需要一次操作。

code

By bhargav_0085

#include<bits/stdc++.h>
using namespace std;
int n,a[10010],fa[10100];
int main()
{
    int x,s=0;
    cin>>n;
    for (int i=2;i<=n;++i) cin>>x,fa[i]=x;
    for (int i=1;i<=n;++i) cin>>a[i],a[i]!=a[fa[i]]?++s:0;
    cout<<s;
}

893C. Rumor

题意：有一个 $n$ 个点 $m$ 条边的无向图，第 $i$ 个点有点权 $a_i$ 。每次可以花费 $a_i$ 的代价来将 $i$ 所在的连通块染色，求将整个图染色的最小代价。

显然对于每个连通块只需要 dfs 找到权值最小的点染色即可。

code

By Golovanov399

#include <bits/stdc++.h>
using namespace std;
inline int nxt() {
    int x;
    scanf("%d", &x);
    return x;
}
int main() {
    int n = nxt(), m = nxt();
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        c[i] = nxt();
    }
    vector<vector<int>> a(n);
    for (int i = 0; i < m; ++i) {
        int u = nxt() - 1, v = nxt() - 1;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    int mn;
    long long ans = 0;
    vector<char> used(n);
    function<void(int)> dfs = [&](int v) {
        if (used[v]) {
            return;
        }
        used[v] = 1;
        mn = min(mn, c[v]);
        for (int x : a[v]) {
            dfs(x);
        }
    };
    for (int i = 0; i < n; ++i) {
        if (!used[i]) {
            mn = 1e9 + 10;
            dfs(i);
            ans += mn;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

1661B. Getting Zero

题意：每次操作可以将一个数 $\times 2\% 32768$ 或 $(+1)\%32768$ ，不能出现非正数，问把 $n$ 变成 $0$ 的最小操作次数。

从 $32768$ 开始 BFS 即可。

code

By SSRS_

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i];
  }
  vector<int> d(32768, -1);
  d[0] = 0;
  queue<int> Q;
  Q.push(0);
  while (!Q.empty()){
    int x = Q.front();
    Q.pop();
    int p1 = (x + 32768 - 1) % 32768;
    if (d[p1] == -1){
      d[p1] = d[x] + 1;
      Q.push(p1);
    }
    if (x % 2 == 0){
      int p2 = x / 2;
      if (d[p2] == -1){
        d[p2] = d[x] + 1;
        Q.push(p2);
      }
      p2 += 32768 / 2;
      if (d[p2] == -1){
        d[p2] = d[x] + 1;
        Q.push(p2);
      }
    }
  }
  for (int i = 0; i < n; i++){
    cout << d[a[i]];
    if (i < n - 1){
      cout << ' ';
    }
  }
  cout << endl;
}

862B. Mahmoud and Ehab and the bipartiteness

题意：给你一棵树（显然是二分图），问最多能添加多少条边使得仍然保持二分图性质。

直接二分图染色，奇数层在一边，偶数层在另一边。得到两边的点数，相乘即为最多有多少条边，减去 $n-1$ 即可。

code

By Shik

const int N=1e5+10;
int n;
VI e[N];
LL c[2];
void dfs( int p, int f, int d ) {
    c[d]++;
    for ( int i:e[p] ) if ( i!=f ) dfs(i,p,d^1);
}
int main() {
    R(n);
    REP(i,n-1) {
        int a,b;
        R(a,b);
        e[a].PB(b);
        e[b].PB(a);
    }
    dfs(1,0,0);
    LL ans=c[0]*c[1]-(n-1);
    W(ans);
    return 0;
}

755C. PolandBall and Forest

题意：一个森林，给你每个点能到达的最远节点（如有相同则选编号最小的），判断森林有几棵树。

做法 1

显然一个点与到达的最远节点在同一棵树上，可以用并查集维护，因为一棵树的直径两端自然互为最远节点，而树上其他点的最远节点一定是直径的一端，所以在这颗树上当且仅当在同一并查集内。

code

By Izanagi

#include<bits/stdc++.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
int b[11000];
int UF[11000];
int FIND(int a){
    if(UF[a]<0)return a;
    return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
    a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int main(){
    int a;scanf("%d",&a);
    for(int i=0;i<a;i++){
        scanf("%d",b+i);b[i]--;
    }
    for(int i=0;i<a;i++)UF[i]=-1;
    for(int i=0;i<a;i++){
        UNION(b[i],i);
    }
    int ret=0;
    for(int i=0;i<a;i++)if(UF[i]<0)ret++;
    printf("%d\n",ret);
}

做法 2

可以直接开 $set$ 记录那些点被当作了最远节点。显然每棵树要么只有一个点、要么恰好有两个点被当作最远节点。对于第一种情况，该点的最远节点就是自己，否则一定为第二种情况。

code

By tourist

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  scanf("%d", &n);
  set <int> s;
  int ans = 0;
  for (int i = 1; i <= n; i++) {
    int foo;
    scanf("%d", &foo);
    if (foo == i) {
      ans++;
    } else {
      s.insert(foo);
    }
  }
  printf("%d\n", ans + (int) s.size() / 2);
  return 0;
}

1676G. White-Black Balanced Subtrees

题意：有根树上每个节点非黑即白，问有多少棵子树满足黑节点数量等于白节点数量。

DFS 即可，返回子树内黑白节点数量，递归往上合并。

code

By Joshc

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int, int>
#define f first
#define s second
const int MOD = 1000000007;
vector<int> edges[4005];
char c[4005];
int ans = 0;
int dfs(int v) {
    int cur = (c[v] == 'B' ? 1 : -1);
    for (int i : edges[v]) cur += dfs(i);
    ans += cur == 0;
    return cur;
}
void solve() {
    int n, x;
    scanf("%d", &n);
    for (int i=1; i<=n; i++) edges[i].clear();
    for (int i=2; i<=n; i++) {
        scanf("%d", &x);
        edges[x].push_back(i);
    }
    for (int i=1; i<=n; i++) scanf(" %c", &c[i]);
    ans = 0;
    dfs(1);
    printf("%d\n", ans);
}
int main() {
    int tests = 1;
    scanf("%d", &tests);
    while (tests--) solve();
}

520B. Two Buttons

题意：每次操作可以将一个数 $\times 2$ 或 $-1$ ，不能出现非正数，问将 $n$ 变成 $m$ 的最小操作次数。

从 $m$ 开始 BFS 即可。

code

By ZSH_ZSH

#include<bits/stdc++.h>
#define rep(i,a,b) for (register int i=(a);i<=(b);i++)
#define drep(i,a,b) for (register int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;
inline ll read()
{
    ll sum=0,f=0;char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) sum=(sum<<1)+(sum<<3)+(c^48),c=getchar();
    return f?-sum:sum;
}
const int N=1000010;
int s,t,dis[N];
queue<int>q;
signed main()
{
    s=read(),t=read(); dis[s]=1; q.push(s);
    while (q.size())
    {
        int u=q.front(); q.pop();
        int a=u<<1; if (a<=N-10&&a>0&&!dis[a]) dis[a]=dis[u]+1,q.push(a);
        int b=u-1; if (b<=N-10&&b>0&&!dis[b]) dis[b]=dis[u]+1,q.push(b);
    }
    cout<<dis[t]-1<<endl;
}

1167C. News Distribution

题意：有 $n$ 个点和 $m$ 个点集，每个点集中的点互相连边，对于每个点输出所在连通块大小。

每个点集建立一个虚点（或使用集合中第一个节点当根），并查集维护即可。

code

By bhargav_0085

#include<bits/stdc++.h>
using namespace std;
#define N 500001
int n,m,fa[N],k,x,y,s[N];
int Find(int x)
{
    return fa[x]==x?x:fa[x]=Find(fa[x]);
}
void Union(int x,int y)
{
    fa[Find(x)]=Find(y);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
     	fa[i]=i;
    while(m--)
    {
        scanf("%d",&k);
        if(!k)
          	continue;
        scanf("%d",&x);
        for(int i=2;i<=k;i++)
        {
          	scanf("%d",&y);
            Union(x,y);
        }
    }
    for(int i=1;i<=n;i++)
     	s[Find(i)]++;
    for(int i=1;i<=n;i++)
     	cout<<s[fa[i]]<<" ";
    cout<<endl;
    return 0;
}

1263D. Secret Passwords

题意：有 $n$ 个小写字母字符串，若有字母同时在两个字符串中出现，那么这两个字符串被认为是等价的。等价关系可以在这 $n$ 个字符串中传递。问有多少个本质不同的字符串。

所有包含 $\texttt{a}$ 的字符串都等价、所有包含 $\texttt{b}$ 的字符串都等价，以此类推，由于可以传递，并查集维护即可。

code

By wucstdio

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,pa[500005],last[26];
char s[105];
int find(int x)
{
    return x==pa[x]?x:pa[x]=find(pa[x]);
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)pa[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        int m=(int)strlen(s+1);
        for(int j=1;j<=m;j++)
        {
            if(last[s[j]-'a'])
            {
                int u=find(i);
                int v=find(last[s[j]-'a']);
                pa[u]=v;
            }
            last[s[j]-'a']=i;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
      if(find(i)==i)ans++;
    printf("%d\n",ans);
    return 0;
}

164A. Variable, or There and Back Again

题意：一个有向图由 0、1、2 三种点组成，对于每个点判断是否存在一条经过该点的路径（不一定是简单路径），满足起点为 1 型点、终点为 2 型点且中间没有 1 型点（可以有 2 型点）。

做法 1（正解）

转换一下题目要求：对于每个点判断是否存在一个 1 型点能到达此点且能“在不经过 1 型点的情况下”到达一个 2 型点。

对于前者，可以直接从每个 1 型点 DFS，将能到达的点打上标记；对于后者，再转换一下限制：存在一个 2 型点，能在不经过 1 型点的情况下到达该点。于是对于后者，在反向图上从每个 2 型点开始 DFS 打标记，遇到 1 型点时直接 return 即可。

code

By dzhulgakov

#define N 111000
int n,m,f[N];
bool mark[N],bmark[N];
VI adj[N],badj[N];

void dfs1(int v)
{
    if (mark[v]) return;
    mark[v] = true;
    REP(i,SZ(adj[v])) dfs1(adj[v][i]);
}

void dfs2(int v)
{
    if (bmark[v]) return;
    bmark[v] = true;
    if (f[v] == 1) return;
    REP(i,SZ(badj[v])) dfs2(badj[v][i]);
}

int main()
{
    scanf("%d%d",&n,&m);
    REP(i,n)
        scanf("%d",f+i);
    REP(i,m)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        --x;--y;
        adj[x].pb(y);
        badj[y].pb(x);
    }
    CLEAR(mark);
    CLEAR(bmark);
    REP(i,n) if (!mark[i] && f[i]==1) dfs1(i);
    REP(i,n) if (!bmark[i] && f[i]==2) dfs2(i);
    REP(i,n)
        printf(" %d"+(i==0),mark[i]&&bmark[i] ? 1 : 0);
    printf("\n");
    return 0;
}

做法 2（错解）

直接从每个 1 型点 DFS，碰到新的 1 型点时直接 return，如果有 2 型点则回溯的时候打上标记。

code

#include<bits/stdc++.h>
using namespace std;
int c[100010];
vector<int> a[100010];
bool vis[100010],ans[100010];
int root;
bool dfs(int now) {
    if(now!=root&&c[now]==1) return 0;
    if(vis[now]) return ans[now];
    vis[now]=1;
    if(c[now]==2) ans[now]=1;
    for(int v:a[now])
        ans[now]|=dfs(v);
    return ans[now];
}
signed main() {
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=1;i<=m;i++) {
        int u,v;
        cin>>u>>v;
        a[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
        if(c[i]==1)
            root=i,dfs(i);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
    return 0;
}

这样的做法错在哪里呢？

在上图的情况中，1 为 1 型点，5 为 2 型点，则显然的一条路径为 $1\to 2\to 3\to 4\to 5$ 。然而在 DFS 时，我们先搜到 2，打上了 $vis$ 标记，走完 3、4 再次到 2 时，由于已经有了 $vis$ 标记，程序认为它已经搜完了，于是直接返回了 0，认为 2 没法到达 2 型点。但实际上并不是没法到达，而是还没搜到。当我们回溯到 2 时，再向 5 搜，虽然可以找到 $1\to 2\to 5$ 这条路径，但 3 和 4 的答案就定在了“无法到达”上。做法 1 就完全不会遇到这种问题。

698B. Fix a Tree

题意：一棵树可以用一个序列 $p$ 表示。具体地，任选一个根 $x$ ，当 $i\ne x$ 时 $p_i$ 为 $i$ 节点的父亲，当 $i=x$ 时 $p_i=i$ 。一棵树转换成序列的方式并不唯一。定义一个序列是合法的，当且仅当存在一棵树可以表示成该序列。给定初始序列 $a$ ，问至少修改多少个元素使得该序列合法，并输出修改后的序列。

注意到，初始的 $a$ 序列如果按照 $i\to a_i$ 连边，会形成一个基环树森林。对于每个基环树，必然要选择环上一个点断掉一条环上的边，最后连接起来。如果存在一棵基环树的环为一个点的自环，则该点可以为树的根，无需修改。找环的操作可以用 DFS 完成，对于自环特判一下即可。

code

By MiracleFaFa

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int n,p[N],vis[N],rt,cnt,T;
int main() {
    scanf("%d",&n);
    rep(i,1,n+1) {
        scanf("%d",p+i);
        if (p[i]==i) rt=i;
    }
    rep(i,1,n+1) if (!vis[i]) {
        T++;
        int x=i;
        while (!vis[x]) {
            vis[x]=T;
            x=p[x];
        }
        if (vis[x]==T) {
            if (!rt) {
                rt=x; p[x]=x;
                cnt++;
            }
            if (x!=rt) {
                p[x]=rt;
                cnt++;
            }
        }
    }
    printf("%d\n",cnt);
    rep(i,1,n+1) printf("%d ",p[i]);
}

代码细节：使用循环代替了 DFS 找环的过程。

216B. Forming Teams

题意：有一个无向图（不一定连通），每个点的度数不超过 $2$ ，问最少删除多少个点，才能使得该图成为二分图且两边的点数相同。

由于每个点的度数不超过 $2$ ，图一定有若干个环和若干条链组成。对于长度为偶数的环和长度为偶数的链，本身满足条件，可以不用考虑。对于奇数环，必须删掉一个点转换成偶数链，此时直接 ans++。对于奇数链，本身是二分图但两侧节点数差 $1$ ，所以两个奇数链的差可以抵消。如果有奇数条奇数链，ans++，否则 ans 不变。环和链的判断可以 DFS 完成。

code

By dreamoon_love_AA

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>e[111];
int used[111],cnt,cnt2;
void dfs(int x){
    used[x]=1;
    cnt+=e[x].size();
    cnt2++;
    for(int i=0;i<e[x].size();i++)
        if(used[e[x][i]]==0)dfs(e[x][i]);
}
int main(){
    int i,j,k,n,m,stop=0;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        e[x].pb(y);
        e[y].pb(x);
    }
    for(i=1;i<=n;i++){
        if(!used[i]){
            cnt=0;
            cnt2=0;
            dfs(i);
            if(cnt2%2==1&&cnt2*2==cnt){
                stop++;
            }
        }
    }
    printf("%d\n",stop+(n-stop)%2);
    return 0;
}

代码细节：通过 $cnt$ 和 $cnt2$ 的记录巧妙地判断是环还是链。

1714G. Path Prefixes

题意：一棵以 $1$ 为根的有根树，每个边 $i$ 有两个边权 $a_i$ 和 $b_i$ 。对于每个点 $i$ ，令 $p_1\sim p_k$ 表示从根节点到 $i$ 的边的序列，求最长的 $r_i$ 使得 $\sum\limits_{j=1}^{r_i} b_{p_j}\le\sum\limits_{j=1}^k a_{p_j}$ 。

DFS 是维护根到当前点的 $a$ 边权总和以及 $b$ 边权前缀和 $s$ ，每次在 $s$ 中查找即可。

code

By tourist

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n;
    cin >> n;
    vector<vector<array<int, 3>>> g(n);
    for (int y = 1; y < n; y++) {
      int x, w0, w1;
      cin >> x >> w0 >> w1;
      --x;
      g[x].push_back({y, w0, w1});
      g[y].push_back({x, w0, w1});
    }
    vector<long long> seq(1, 0);
    vector<int> res(n);
    function<void(int, int, long long)> Dfs = [&](int v, int pr, long long s) {
      if (v > 0) {
        res[v] = (int) (lower_bound(seq.begin(), seq.end(), s + 1) - seq.begin()) - 1;
      }
      for (auto& p : g[v]) {
        int u = p[0];
        if (u == pr) {
          continue;
        }
        seq.push_back(seq.back() + p[2]);
        Dfs(u, v, s + p[1]);
        seq.pop_back();
      }
    };
    Dfs(0, -1, 0);
    for (int i = 1; i < n; i++) {
      cout << res[i] << " \n"[i == n - 1];
    }
  }
  return 0;
}

813C. The Tag Game

题意：Alice 和 Bob 在一棵树上博弈，初始时 Alice 在 $1$ 节点（根节点），Bob 在 $x$ 节点。二人轮流沿边走，Bob 先走，每回合可以不走。Alice 希望尽快抓到 Bob 而 Bob 相反。问最终的回合数。

显然 Alice 可以只由浅向深走而保证抓到 Bob，此时回合最少。所以 Bob 的任务为在保证不被抓到的前提下前往尽可能深的点待着不动。

做法 1

可以先跑两遍 DFS 得出每个点与 Alice 和 Bob 的距离（与 Alice 的距离即为深度）。每个与 Bob 距离比与 Alice 距离近的点都是 Bob 能够安全到达的，所以取这些点中深度最深的即可。

code

By Avason

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector <int> e[200005];
int depa[200005],depb[200005];
inline void dfsa(int u,int f)
{
    for(auto v:e[u])
        if(v!=f) depa[v]=depa[u]+1,dfsa(v,u);
}
inline void dfsb(int u,int f)
{
    for(auto v:e[u])
        if(v!=f) depb[v]=depb[u]+1,dfsb(v,u);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,B;
    cin >> n >> B;
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfsa(1,0);
    dfsb(B,0);
    int mx=0,ans=0;
    for(int i=1;i<=n;i++)
    {
        if(depa[i]>depb[i])
        {
            ans=max(ans,depa[i]*2);
        }
    }
    cout << ans;
    return 0;
}

做法 2

如果 Bob 在一个点没被抓到，那么他往下走也不会被抓到，所以在不被抓到的前提下，Bob 可以先尽可能地往上走获得后续的更多选择。找到能到达的最上面的点时，再找该子树下深度最深的点即可。

code

By fqw

vector<VI> es;
VI d, f, fat;
int n;

void dfs(int x, int fa, int dep) {
    d[x] = dep, f[x] = dep;
    fat[x] = fa;
    for(int y : es[x]) {
        if(y != fa) {
            dfs(y, x, dep + 1);
            setmax(f[x], f[y]);
        }
    }
}

int main() {
    int x;
    scanf("%d%d", &n, &x);
    --x;
    es.resize(n);
    d.resize(n);
    f.resize(n);
    fat.resize(n);
    repn(i, n - 1) {
        int a, b;
        scanf("%d%d", &a, &b);
        --a, --b;
        es[a].pb(b), es[b].pb(a);
    }
    dfs(0, -1, 0);
    int dt = d[x] / 2 + 1;
    while(d[x] > dt) x = fat[x];
    printf("%d\n", f[x] * 2);

    return 0;
}

691D. Swaps in Permutation

题意：有一个排列和 $m$ 个操作，每个操作 $(a_i,b_i)$ 表示交换排列的第 $a_i$ 个元素和第 $b_i$ 个元素。你可以以任意顺序进行操作任意多次，问操作后的最大字典序。

显然交换具有传递性，即若 $a_1,a_2$ 可以交换、 $a_2,a_3$ 可以交换，则 $a_1,a_2,a_3$ 可以任意排列。于是将每个 $(a_i,b_i)$ 连边，每个连通块内都可以任意排列，显然从大到小排列输出即可。

code

By I_love_Tanya_Romanova

int n, k, ar[N];
vector<int> vec[N];
int w[N];

int get(int x)
{
    if (w[x] == x)
        return x;
    return w[x] = get(w[x]);
}

void merge(int a, int b)
{
    a = get(a);
    b = get(b);
    w[a] = b;
}

int ans[N];

int main(){
    //freopen("fabro.in","r",stdin);
    //freopen("fabro.out","w",stdout);
    //freopen("F:/in.txt", "r", stdin);
    //freopen("F:/output.txt", "w", stdout);
    ios_base::sync_with_stdio(0);
    //cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> ar[i];
    }

    for (int i = 1; i <= n; i++)
        w[i] = i;

    for (int i = 1; i <= k; i++)
    {
        int a, b;
        cin >> a >> b;
        merge(a, b);
    }

    for (int i = 1; i <= n; i++)
    {
        int id = get(i);
        vec[id].push_back(ar[i]);
    }

    for (int i = 1; i <= n; i++)
        sort(vec[i].begin(), vec[i].end());

    for (int i = 1; i <= n; i++)
    {
        int id = get(i);
        int val = vec[id].back();
        vec[id].pop_back();
        ans[i] = val;
    }

    for (int i = 1; i <= n; i++)
    {
        if (i > 1)
            cout << " ";
        cout << ans[i];
    }
    cout << endl;

    cin.get(); cin.get();
    return 0;
}

1722F. L-shapes

题意：一个 $L$ 形如下所示
1
2
*.  .*  **  **
**  **  *.  .*
给你一个 $n\times m$ 的矩阵，问能否由若干个 $L$ 形拼成且每个 $L$ 形不相交、不共边、不共定点。

可以搜索得到八连通的连通块，如果块的大小不为 $3$ 则直接输出 No，如果为 $3$ 则判断是否为 $L$ 形。

code

By wtmoo: kevinyang, uwu

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
bool good(int x, int y){
    if(1<=x&&x<=n&&y>=1&&m>=y)return true;
    return false;
}
signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int t;
    cin >> t;
    while(t--){
        cin >> n >> m;
        vector<vector<char>>mp(n+1,vector<char>(m+1));
        for(int i = 1; i<=n; i++){
            string s;
            cin >> s;
            for(int j = 1; j<=m; j++){
                mp[i][j] = s[j-1];
            }
        }
        vector<int>dx = {-1,0,1,0,1,1,-1,-1};
        vector<int>dy = {0,1,0,-1,-1,1,1,-1};
        bool f = true;
        vector<vector<bool>>vis(n+1,vector<bool>(m+1));
        for(int i = 1; i<=n; i++){
            for(int j = 1; j<=m; j++){
                queue<pair<int,int>>q;
                if(vis[i][j])continue;
                if(mp[i][j]!='*')continue;
                q.push({i,j});
                vis[i][j] = true;
                set<int>sx;
                set<int>sy;
                sx.insert(i);
                sy.insert(j);
                int cnt = 1;
                while(q.size()){
                    pair<int,int>cur = q.front(); q.pop();
                    int x = cur.first; int y = cur.second;
                    for(int d = 0; d<8; d++){
                        int nx = x+dx[d];
                        int ny = y+dy[d];
                        if(!good(nx,ny))continue;
                        if(vis[nx][ny])continue;
                        if(mp[nx][ny]=='.')continue;
                        q.push({nx,ny});
                        sx.insert(nx); sy.insert(ny);
                        vis[nx][ny] = true;
                        cnt++;
                    }
                }
                if(cnt==3&&sx.size()==2&&sy.size()==2)continue;
                f = false;
            }
        }
        if(f)cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

29C. Mail Stamps

题意：有一个 $n$ 个点的链，给你 $n-1$ 条边，按顺序输出链上的点。点的下标在 $[1,10^9]$ 内。

离散化，暴力循环输出即可。

code

By Farhod_Farmon

#include <bits/stdc++.h>

#define fi first
#define se second
#define sc scanf
#define pr printf
#define pb push_back
#define mp make_pair
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const int N = 100100;

using namespace std;

int n;
vector < int > v[N], ans;
map < int, int > rv, us;

void dfs(int x, int p)
{
    ans.pb(x);
    for(int i = 0; i < v[x].size(); i++)
        if(v[x][i] != p)
            dfs(v[x][i], x);
}

int main()
{
    //fin("input.txt");
    //fout("output.txt");
    ios_base::sync_with_stdio(0);
    cin >> n;
    int g = 0;
    for(int i = 1; i <= n; i++){
        int x, y;
        cin >> x >> y;
        if(us.find(x) == us.end()){
            us[x] = ++g;
            rv[g] = x;
        }
        if(us.find(y) == us.end()){
            us[y] = ++g;
            rv[g] = y;
        }
        x = us[x];
        y = us[y];
        v[x].pb(y);
        v[y].pb(x);
    }
    int root = 1;
    for(int i = 1; i <= g; i++)
        if(v[i].size() == 1)
            root = i;
    dfs(root, -1);
    for(int i = 0; i < ans.size(); i++)
        cout << rv[ans[i]] << " ";
}

213A. Game

题意：有三个电脑和 $n$ 个游戏，第 $i$ 个游戏需要在第 $c_i$ 个电脑上完成，游戏之间有依赖关系但保证没有环。完成每个游戏需要一小时，在电脑之间移动 $1\to 2,2\to 3,3\to 1$ 需要一小时， $3\to 2,2\to 1,1\to 3$ 需要两小时。初始可以选择在任意电脑前，问完成全部游戏的最少时间。

注意到在电脑之间移动时， $+1 \mod 3$ 花费 $1$ 而 $-1 \mod 3$ 花费 $2$ ，所以一定不会出现 $-1 \mod 3$ （最差也可以用两次 $+1 \mod 3$ 代替）。所以只需要每次贪心地将当前电脑能玩的全部玩完再到下一个电脑即可。需要分类讨论初始位置。

code

By eddy1021

int n , c[ N ] , ind[ N ];
vector< int > v[ N ];
void init(){
  n = getint();
  for( int i = 1 ; i <= n ; i ++ )
    c[ i ] = getint() - 1;
  for( int i = 1 ; i <= n ; i ++ ){
    ind[ i ] = getint();
    for( int j = 0 ; j < ind[ i ] ; j ++ ){
      int fr = getint();
      v[ fr ].push_back( i );
    }
  }
}
vector<int> q[ 3 ];
int tind[ N ];
int go( int st , int nxt ){
  for( int i = 0 ; i < 3 ; i ++ )
    q[ i ].clear();
  for( int i = 1 ; i <= n ; i ++ ){
    tind[ i ] = ind[ i ];
    if( ind[ i ] == 0 )
      q[ c[ i ] ].push_back( i );
  }
  int gt = 0 , ret = 0;
  while( gt < n ){
    while( q[ st ].size() ){
      int who = q[ st ].back();
      q[ st ].pop_back();
      gt ++;
      ret ++;
      for( auto tmp : v[ who ] ){
        tind[ tmp ] --;
        if( tind[ tmp ] == 0 ){
          q[ c[ tmp ] ].push_back( tmp );
        }
      }
    }
    if( gt == n ) break;
    ret ++;
    st = ( st + nxt + 3 ) % 3;
  }
  return ret;
}
void solve(){
  int ans = N * N;
  for( int st = 0 ; st < 3 ; st ++ )
    ans = min( ans , go( st , 1 ) );
  printf( "%d\n" , ans );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}

408B. Garland

题意：有一些颜色的纸若干张，每张面积为 $1$ ，你需要拼成一定的彩带，要求每个位置的颜色对应。你可以将纸剪开，但不能拼起来。问最多能有多大面积或回答无法拼成。

显然对于每种颜色单独考虑。一种颜色如果纸比目标多，那一定是目标的面积。如果比目标少，则可以全部用上。所以答案为二者取 $\min$ 。