NewOJ Week 9题解

比赛链接：http://oj.ecustacm.cn/contest.php?cid=1024

题目总览

题目	TAG	难度	来源	补题链接
平均数组	构造	☆	C o d e C h e f CodeChef CodeChef	http://oj.ecustacm.cn/problem.php?id=1831
配对	贪心	☆☆	C o d e C h e f CodeChef CodeChef	http://oj.ecustacm.cn/problem.php?id=1832
可逆循环字符串	思维题	☆☆☆	P A C N W   2021 PACNW \ 2021 PACNW 2021	http://oj.ecustacm.cn/problem.php?id=1833
树与排列	暴力、 d f s dfs dfs、 l c a lca lca	☆☆☆	P A C N W   2021 PACNW \ 2021 PACNW 2021	http://oj.ecustacm.cn/problem.php?id=1834
跳房子游戏	动态规划	☆☆☆☆	P A C N W   2021 PACNW \ 2021 PACNW 2021	http://oj.ecustacm.cn/problem.php?id=1835

A 平均数组

题意：

Tag： 构造

难度： ☆

来源： C o d e C h e f CodeChef CodeChef

思路： 由于任意一组解即可，可以考虑以 X X X为中位数连续数组。

如果 N N N为偶数，则可以构造 [ X − N 2 , X − 1 ] ∪ [ X + 1 , X + N 2 ] [X-\frac{N}{2},X-1] \cup[X+1,X+\frac{N}{2}] [X−2N​,X−1]∪[X+1,X+2N​]。

如果 N N N为奇数，则可以构造 [ X − N 2 , X + N 2 ] [X-\frac{N}{2},X+\frac{N}{2}] [X−2N​,X+2N​]。

#include
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, x;
        cin >> n >> x;
        int length = n / 2;
        for(int i = x - length; i <= x - 1; i++)
            cout<<i<<" ";
        if(n & 1)cout<<x<<" ";
        for(int i = x + 1; i <= x + length; i++)
            cout<<i<<" ";
        cout<<endl;
    }
    return 0;
}

B 配对

题意：

Tag： 贪心

难度： ☆☆

来源： C o d e C h e f CodeChef CodeChef

思路： A [ i ] A[i] A[i]和 B [ j ] B[j] B[j]进行配对累计 N N N组，最小化 m a x A [ i ] + B [ j ] max{A[i]+B[j]} maxA[i]+B[j]。使用贪心的思想，想让最大的和最小化，相当于较大的数字和较小的数字配对，这样可以使得最大值尽可能小。

则想法为： A A A从小到大排序， B B B从小到大排序， A A A最小的和 B B B最大的配对。这样可以保证每个大的数字匹配到最小的数字，从而使得最大和最小化。

#include
using namespace std;
const int maxn = 2e4 + 10;
int a[maxn], b[maxn];
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n; i++)cin >> a[i];
        for(int i = 1; i <= n; i++)cin >> b[i];
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + n);
        int ans = 0;
        for(int i = 1; i <= n; i++)
            ans = max(ans, a[i] + b[n + 1 - i]);
        cout<<ans<<endl;
    }
    return 0;
}

C 可逆循环字符串

题意：

Tag： 思维题

难度： ☆☆☆

来源： P A C N W   2021 PACNW \ 2021 PACNW 2021

思路： 根据题意描述，要使得 s s s的所有子串的翻转结果均为 s s s的循环子串，等价于s翻转结果为 s s s的循环子串。

因为 s s s也是 s s s的子串，如果 s s s已经满足，则 s s s的子串一定满足，反之亦然。这是一个充要条件。

所以题目变成：给定字符串 s s s，判断 s s s的翻转结果是否为 s s s的循环子串。

循环子串的判定：直接把 s s s变成 s + s s+s s+s然后判断是否为 s + s s+s s+s的子串。

#include
using namespace std;
int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        string s;
        cin >> s;
        string ss = s + s;
        reverse(ss.begin(), ss.end());
        cout << (ss.find(s) != string::npos) << endl;
    }
    return 0;
}

D 树与排列

题意：

Tag： 暴力、 d f s dfs dfs、 l c a lca lca

难度： ☆☆☆

来源： P A C N W   2021 PACNW \ 2021 PACNW 2021

思路： 要求树上两个节点的距离，可以直接使用 L C A LCA LCA模板即可。

但是由于题目只需要判断距离是否小于等于 3 3 3，那么直接暴力即可。

类似 L C A LCA LCA，预处理每个点的深度 d e p t h depth depth和父节点 p r e pre pre。

对于相邻两个点 x x x和 y y y：

1、如果深度不同，则深度大的往上走，最多走 3 3 3步即可判断是否合法。

2、如果深度相同，则判断是否 x x x已经等于 y y y，如果不等， x x x和 y y y同时往上走 1 1 1步。

#include
using namespace std;
const int maxn = 1e5 + 10;
int n;
vector<int>G[maxn];
int a[maxn];
int depth[maxn];//depth[i]表示节点i的深度
int pre[maxn];  //pre[i]表示节点i的父节点

void dfs(int u, int fa, int d)
{
    pre[u] = fa;
    depth[u] = d;
    for(auto v : G[u])if(v != fa)
        dfs(v, u, d + 1);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            G[i].clear();
        for(int i = 1; i < n; i++)
        {
            int u, v;
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        dfs(1, -1, 0);
        int ok = 1;
        for(int i = 1; i + 1 <= n && ok; i++)
        {
            int x = a[i], y = a[i + 1], dis = 0;
            while(dis <= 3 && depth[x] > depth[y])x = pre[x], dis++;
            while(dis <= 3 && depth[y] > depth[x])y = pre[y], dis++;
            while(dis <= 3 && depth[x] && x != y)x = pre[x], y = pre[y], dis += 2;
            if(dis > 3)ok = 0;
        }
        cout<<ok<<endl;
    }
    return 0;
}

E 跳房子游戏

题意：

Tag： 动态规划

难度： ☆☆☆☆

来源： P A C N W   2021 PACNW \ 2021 PACNW 2021

思路： 每个格子的数字只能是 1 − K 1-K 1−K，只能从 1 1 1开始到 K K K结束。

每个格子有三个属性： x , y , n u m x,y,num x,y,num，表示第 x x x行第 y y y列数字为 n u m num num。

因为每次从 1 1 1开始到 K K K结束，所以按照数字大小排序。

数值 n n n按照从 1 1 1到 K K K枚举，记 c c [ x ] cc[x] cc[x]表示走到数值为 n − 1 n-1 n−1且到达第 x x x行的最短路径长度， r c [ y ] rc[y] rc[y]表示到达第 y y y列的最短路径长度，可以根据 r c , c c rc,cc rc,cc求出到达数值 n n n的最短路径长度 d d d。

对于每一个数值为 n n n的格子 ( x , y ) (x,y) (x,y)而言，可以更新 d d d，同时可以更新下一轮的 c c , r c cc,rc cc,rc数组，直到走到数值为 K K K停止。

时间复杂度 O ( N 3 ) O(N^3) O(N3)。

#include 
#include 
#include 
#include 
using namespace std;

int main() {
  int N, K;
  while (cin >> N >> K) {
    vector<vector<int>> G(N, vector<int>(N));
    vector<tuple<int, int, int>> v;
    for (int y = 0; y < N; y++)
    for (int x = 0; x < N; x++) {
      cin >> G[y][x];
      v.emplace_back(G[y][x], x, y);
    }
    sort(v.begin(), v.end());//按照数字大小排序

    vector<int64_t> rc(N), cc(N);
    int64_t ret = 1e18;
    for (int n = 1, i = 0; n <= K; n++) {//对于数值为n的格子
      auto orc = rc, occ = cc;
      rc = cc = vector<int64_t>(N, 1e18);
      for (; i < v.size(); i++) {//求出到达数值n的最小距离d
        auto [s, x, y] = v[i];
        if (s != n) break;       //只遍历数值为n的格子
        int64_t d = min(orc[y], occ[x]);
        if (s == K) ret = min(ret, d);
        for (int x2 = 0; x2 < N; x2++) cc[x2] = min(cc[x2], d + (x2-x)*(x2-x));
        for (int y2 = 0; y2 < N; y2++) rc[y2] = min(rc[y2], d + (y2-y)*(y2-y));
      }
    }
    cout << (ret == 1e18 ? -1 : ret) << endl;
  }
}