NewOJ Week 9题解

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

题意：

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< 
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< 
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;
vectorG[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< 
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> G(N, vector(N));
    vector> 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 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(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;
  }
}