大连大学程序设计竞赛（2024.04）正式赛题解 – 大连大学ACM程序设计工作室

题目链接：http://dluacm.cn/wp-content/uploads/2024/05/202404zhengshi.pdf

补题链接：https://ac.nowcoder.com/acm/contest/81545

Problem A 更爱吃面包的东百王

输出 $n * 32$ 和 $n * 20$ 即可

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    cout<<n*32<<' '<<n*20<<endl;
}

Problem B 大四喜

大四喜：判断四种风牌是否数量都是三张以及是否有两张相同的牌作将牌。

小四喜：判断是否有三种风牌数量为三张，另一种风牌为两张，以及另外三张相同的牌即可。

Problem C 盒子

模拟即可。

记录每个盒子中的每一个物品下面的物品序号，以及是否在盒子顶部，在取出时判断物品是否在盒子顶部，并修改下面物品在盒子顶部。

Problem D Greatest Common Divisor

由于给出的数组为一个长度大于等于1的排列，故一定存在元素1。因此直接选取长度为 $n$ 的区间即可。

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i){
        int t;cin>>t;
    }
    cout<<n<<endl;
}
int main(){
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
}

Problem E 双倍字符串

记 $dp[i]$ 为字符串 $S_{1…i}$ 的最长双倍字符串长度，用 $lst[c]$ 记录第字母 $c$ 的上一次出现的位置

转移为 $dp[i] = max(dp[i - 1], dp[lst[c] - 1] + 2)$

$dp[|S|]$ 即为答案

#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;
const int mod = 998244353, N = 5e7 + 5 ;

int n ; 
int f[N], lst[26] ;

void solve()
{
    string s ; cin >> s ;
    f[0] = 0 ; n = (int)s.length() ; s = "_" + s ;
    for(int i = 1; i <= n; ++ i)
    {
        f[i] = f[i - 1] ;
        int c = s[i] - 'a' ;
        if(lst[c]) f[i] = max(f[i], f[lst[c] - 1] + 2) ;
        lst[c] = i ;
    }
    cout << f[n] << '\n' ;
}

int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    int T = 1 ; // cin >> T ;
    while(T --) solve() ;
    return 0 ;
}

Problem F 逆序对

对于数组a，令 $l=min(x,y)$ ， $r=max(x,y)$ ，则l和r把数组a分成了五个部分，易得交换操作对l前边和r后边的部分不会产生新的逆序对，也不会删除旧的逆序对，所以每次交换对结果产生影响的只有 $[l,r]$ 这一段。

对于 $i\in(l,r)$ 内的 $a_i$ ，比 $a_{l}$ 小、与 $a_{l}$ 相等、比 $a_{l}$ 大的元素个数分别记为 $cnt_{l1}$ 、 $cnt_{l2}$ 、 $cnt_{l3}$ ，比 $a_{r}$ 小、与 $a_{r}$ 相等、比 $a_{r}$ 大的元素个数分别记为 $cnt_{r1}$ 、 $cnt_{r2}$ 、 $cnt_{r3}$ ，令 $res_{0}$ 为交换前整个数组逆序对的个数， $res$ 为交换后整个数组逆序对的个数。

则易得$ res \mod 2=(res_0 – cnt_{r3} + cnt_{r1} – cnt_{l1} + cnt_{l3} +(a_{l} a_{r})) \mod 2 $，同时$ (r-l-1)-cnt_{l2}=cnt_{l1}+cnt_{l3} $，$ (r-l-1)-cnt_{r2}=cnt_{r1}+cnt_{r3} $。

所以$ res \mod 2=(res_{0}+(r-l-1)-cnt_{l2}+(r-l-1)-cnt_{r2} + (a_{l} a_{r})) \mod 2 $，即$ res \mod 2(res_{0}+cnt_{l2}+cnt_{r2}+(a_{l}a_{r})) \mod 2 $。

Problem G 寰宇蝗灾

出题人博客

G题作为本场校赛的压轴题，通过人数比较少。

赛前测试的时候，std在牛客的评测机上大概时间为2s左右，遂开了1.5倍时限，可能有点卡常。但std本身没有做多余剪枝，正常的写法只要常数不太大应该都能通过。

空间限制 $512M$ 是为了看看有没有其他神秘做法，根据赛中情况来看好像没有。

贴一张std运行时间，牛客神机还是跑的很快的

简要题意：

给一棵 $n$ 个节点的树，每个节点有一个持续时间 $a_i$ （代表在第 $a_i$ 秒的开始塌陷），第 $i$ 秒可以进行两个操作的其中之一

$1\ x\ t$ ，对于所有与 $x$ 距离 $\le 2$ 的节点 $y_i$ ，若 $y_i$ 未塌陷，则将 $y_i$ 的持续时间 $a_{y_i}$ 与 $i+t$ 比较，若后者更大，则把 $a_{y_i}$ 的值修改为 $i+t$

$2\ x$ ，询问节点 $x$ 是否塌陷

塌陷的节点不会恢复

solution：

考虑对距离 $\le 2$ 的节点进行维护。因为每次修改均涉及的是相邻节点，这启发我们使用BFS序+高级数据结构维护

在BFS序中，一个节点的儿子的下标是连续的，所以我们可以把距离 $\le 2$ 的所有点拆分为不超过 $6$ 个区间：

$x$的儿子
$x$的孙子（因为$x$的儿子在BFS序中连续，所以$x$的孙子也在BFS序中连续）
$x$的兄弟
$x$自身
$x$的父亲
$x$的爷爷

进行区间分割后，我们可以通过一次DFS来求出对于所有节点距离 $\le 2$ 的区间集合。

接下来考虑对区间的维护：

发现本质上是区间取 $max$ ，可以使用带懒标记的线段树来维护，对于在每一秒开始要塌陷的节点，我们直接暴力递归到叶子，开一个数组 $deled[x]$ 记录 $x$ 是否塌陷，并把 $x$ 的持续时长改为 $1e9$ （一个很大的数），对于操作 $1$ ，修改所有区间，对于操作 $2$ ，直接根据 $deled$ 数组的值来判断。

暴力递归部分的次数不会超过 $n$ 次，总体时间复杂度为 $O((n+m)logn)$

std

#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;
using pii = pair<int, int> ;
const int N = 2e5 + 5, INF = 1e9 ;

int n, m ;
vector<int> g[N] ;
int lst[N] ;
int dfn[N], fa[N], rev[N], num ;
bool vis[N], deled[N] ;
int ld1[N], rd1[N], ld2[N], rd2[N] ;
struct SegmentTree
{
    int l, r ;
    int minv, lazy_max ;
} t[N << 2] ;

void chmax(int &x, int y) { if(x < y) x = y ; }

void pushup(int p)
{
    t[p].minv = min(t[p << 1].minv, t[p << 1 | 1].minv) ;
}

void pushdown(int p)
{
    if(t[p].lazy_max)
    {
        chmax(t[p << 1].minv, t[p].lazy_max) ;
        chmax(t[p << 1 | 1].minv, t[p].lazy_max) ;
        chmax(t[p << 1].lazy_max, t[p].lazy_max) ;
        chmax(t[p << 1 | 1].lazy_max, t[p].lazy_max) ;
        t[p].lazy_max = 0 ;
    }
}

void build(int p, int l, int r)
{
    t[p].l = l ; t[p].r = r ; 
    t[p].minv = INF ; t[p].lazy_max = 0 ;
    if(l == r)
    {
        t[p].minv = lst[rev[l]] ;
        return ;
    }
    int mid = (t[p].l + t[p].r) >> 1 ;
    build(p << 1, l, mid) ; build(p << 1 | 1, mid + 1, r) ;
    pushup(p) ;
}

void delNodes(int p, int v)
{
    if(t[p].minv > v) return ;
    if(t[p].l == t[p].r)
    {
        deled[rev[t[p].l]] = 1 ;
        t[p].minv = INF ;
        return ;
    }
    pushdown(p) ;
    delNodes(p << 1, v) ;
    delNodes(p << 1 | 1, v) ;
    pushup(p) ;
}

void rangeMax(int p, int l, int r, int d)
{
    if(l <= t[p].l && t[p].r <= r)
    {
        chmax(t[p].lazy_max, d) ;
        chmax(t[p].minv, d) ;
        return ;
    }
    pushdown(p) ;
    int mid = (t[p].l + t[p].r) >> 1 ;
    if(l <= mid) rangeMax(p << 1, l, r, d) ;
    if(r > mid) rangeMax(p << 1 | 1, l, r, d) ;
    pushup(p) ;
}

void dfs(int x, int f)
{
    ld1[x] = ld2[x] = INF ;
    rd1[x] = rd2[x] = -INF ;
    fa[x] = f ;
    for(auto y : g[x]) if(y != f)
    {
        dfs(y, x) ;
        ld1[x] = min(ld1[x], dfn[y]) ;
        rd1[x] = max(rd1[x], dfn[y]) ;
        ld2[x] = min(ld2[x], ld1[y]) ;
        rd2[x] = max(rd2[x], rd1[y]) ;
    }
}

void getRanges(int x, vector<pii> &vec)
{
    int y = fa[x], z = fa[y] ;
    vec.push_back({dfn[x], dfn[x]}) ; // x
    vec.push_back({ld1[x], rd1[x]}) ; // son[x]
    vec.push_back({ld2[x], rd2[x]}) ; // son_son[x]
    if(y)
    {
        vec.push_back({ld1[y], rd1[y]}) ; // brother[x]
        vec.push_back({dfn[y], dfn[y]}) ; // fa[x]
        if(z) vec.push_back({dfn[z], dfn[z]}) ; // fa_fa[x]
    }
}

void solve()
{
    cin >> n >> m ;
    for(int i = 1; i <= n; ++ i)
    {
        g[i].clear() ;
        vis[i] = 0 ;
        deled[i] = 0 ;
    }
    for(int i = 1; i < n; ++ i)
    {
        int x, y ; cin >> x >> y ;
        g[x].push_back(y) ;
        g[y].push_back(x) ;
    }
    for(int i = 1; i <= n; ++ i) cin >> lst[i] ;
    num = 0 ;

    queue<int> q ; q.push(1) ;
    while(!q.empty())
    {
        int x = q.front() ; q.pop() ;
        vis[x] = 1 ;
        dfn[x] = ++ num ;
        rev[num] = x ;
        for(auto y : g[x])
            if(!vis[y]) q.push(y) ;
    }
    dfs(1, 0) ;
    build(1, 1, n) ;

    for(int i = 1; i <= m; ++ i)
    {
        delNodes(1, i) ;
        int opt ; cin >> opt ;
        if(opt == 1)
        {
            int x, t ; cin >> x >> t ;
            vector<pii> vec ;
            getRanges(x, vec) ;
            for(auto [l, r] : vec)
                if(l <= r) rangeMax(1, l, r, i + t) ;
        }
        else
        {
            int x ; cin >> x ;
            cout << (deled[x] ? "YES" : "NO") << '\n' ;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T ; cin >> T ;
    while(T --) solve() ;
    return 0 ;
}

Problem H Highest Common Factor

往一个集合中加入一个数，集合的 $max$ 非单调递减，集合的 $gcd$ 非单调递增。

为了保证 $min(a_l,a_{l+1},…,a_r)=gcd(a_l,a_{l+1},…,a_r)$ ，区间 $(l,r)$ 的所有元素需要相同。直接遍历数组找到所有元素相同的最长子区间即可。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int a[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    int last=-1,len=0;
    int ans=0;
    for(int i=1;i<=n;++i){
        if(a[i]!=last){
            len=1;
            last=a[i];
        }
        else len++;
        ans=max(ans,len);
    }
    cout<<ans<<endl;
}
int main(){
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
}

Problem I 最大公因数

题目要找的 $min(a_l,a_{l+1},…,a_r)=gcd(a_l,a_{l+1},…,a_r)$ 的最长区间，若令 $min(a_l,a_{l+1},…,a_r)=gcd(a_l,a_{l+1},…,a_r)=x$ ，那么满足条件的区间一定满足：该段区间内有 $x$ 且区间内其他元素为 $x$ 的倍数。

所以只需对数组内所有元素分解因数，之后枚举 $x$ ，选择最长长度。

由于本题 $a_i \leq 10^6$ ，所以可以开一个vector<pair<int,int>>p[N]数组，p[i]内的pair存储满足 $a_{j}$ 是 $i$ 的倍数的 $a_{j}$ 的下标 $j$ 和 $a_{j}$ 是否等于 $i$ 。

Problem J 假回文串

哈希做法

首先考虑没有通配符时我们应该怎么做

由题目定义知道形如 $AbBa$ 这样的串是假回文串

对哈希判断回文串，翻转整个串后判断两串之间是否相等是很常用的的技巧

例如对回文串 $abba$ 反转后依然是 $abba$

但是对于本题，可以发现 $AbBa$ 翻转后变成 $aBbA$ 两串之间不同处就是大小写是反转过来的，那么对于这题我们不止是去翻转串，还要把大小写翻转过来

这时假回文串 $AbBa$ 再通过在这样翻转后就变成 $AbBa$ 这时我们就可以用哈希判断一个串是否是假回文串了（这时原串中某个位置 $pos$ 对应翻转串中位置 $|S| + 1 - pos$ ）

我们枚举每个点作为回文中心能得到的偶数回文串最大回文半径，该点最大回文半径就是该点对于答案的贡献

当有通配符时我们只需要去枚举通配符是什么即可

我们分别去枚举通配符为 $a - z$ 和 $A-Z$ 时得到的贡献减去多出来的贡献（通配符为 $*$ 时能得到的贡献 $\times$ 51）就是最终答案

不枚举通配符依然是可以用二分+哈希做的，本题解不讨论此做法

#include <bits/stdc++.h>
using namespace std ;
using ll = long long ;
using pii = pair<int, int> ;
const int N = 1e6 + 5 ;

struct Hash
{
    vector<int> hs1, hs2, pn1, pn2 ;
    int length, base = 131, p1 = 1222827239, p2 = 1610612741 ;
public:
    explicit Hash(const string& s)
    {
        length = (int)s.length() - 1 ;
        hs1.resize(length + 1) ;
        hs2.resize(length + 1) ;
        pn1.resize(length + 1) ;
        pn2.resize(length + 1) ;
        pn1[0] = pn2[0] = 1 ;
        for(int i = 1; i <= length; ++ i)
        {
            hs1[i] = (hs1[i - 1] * 1ll * base + s[i]) % p1 ;
            hs2[i] = (hs2[i - 1] * 1ll * base + s[i]) % p2 ;
            pn1[i] = pn1[i - 1] * 1ll * base % p1 ;
            pn2[i] = pn2[i - 1] * 1ll * base % p2 ;
        }
    }
    int gethash1(int l, int r)
    {
        if(l > r) return 0 ;
        return (hs1[r] - hs1[l - 1] * 1ll * pn1[r - l + 1] % p1 + p1) % p1 ;
    }
    int gethash2(int l, int r)
    {
        if(l > r) return 0 ;
        return (hs2[r] - hs2[l - 1] * 1ll * pn2[r - l + 1] % p2 + p2) % p2 ;
    }
};


int main()
{
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;

    string s, t ; cin >> s ;
    t = s ;
    reverse(t.begin(), t.end()) ;
    int pos = s.find("*") + 1, n = (int)s.length() ;
    t = "_" + t ;
    s = "_" + s ;
    for(int i = 1; i <= n; ++ i) t[i] ^= 32 ;

    ll ans = 0 ;
    for(int i = 0; i < 52; ++ i)
    {
        if(i < 26) s[pos] = 'a' + i ;
        else s[pos] = 'A' + i - 26 ;
        t[n - pos + 1] = s[pos] ^ 32 ;
        Hash hs = Hash(s), ht = Hash(t) ;
        for(int p = 1; p < n; ++ p)
        {
            int l = 0, r = min(p, n - p) ;
            while(l < r)
            {
                int mid = (l + r + 1) >> 1 ;
                int pl = p - mid + 1, pr = p + mid ;
                if(hs.gethash1(pl, p) == ht.gethash1(n - pr + 1, n - p) &&
                    hs.gethash2(pl, p) == ht.gethash2(n - pr + 1, n - p))
                        l = mid ;
                else r = mid - 1 ;
            }
            ans += l ;
        }
    }
    s[pos] = t[n - pos + 1] = '*' ;
    Hash hs = Hash(s), ht = Hash(t) ;
    for(int p = 1; p < n; ++ p)
    {
        int l = 0, r = min(p, n - p) ;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1 ;
            int pl = p - mid + 1, pr = p + mid ;
            if(hs.gethash1(pl, p) == ht.gethash1(n - pr + 1, n - p) &&
                hs.gethash2(pl, p) == ht.gethash2(n - pr + 1, n - p))
                    l = mid ;
            else r = mid - 1 ;
        }
        ans -= l * 51 ;
    }
    cout << ans << '\n' ;
    return 0 ;
}

马拉车做法

也可以直接魔改马拉车, 做法参考这题 POI2010 ANT-Antisymmetry

和哈希做法差不多，枚举通配符马拉车计算回文半径，算出贡献即可。

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
typedef long long ll;

const int N = 1e5 + 100;

struct Manacher {
    int lc[N * 2], len;
    char ch[N * 2];
    Manacher(char *s) {init(s); manacher();}
    /* s 1 bas */
    void init(char *s) {
        int n = strlen(s + 1);
        ch[n * 2 + 1] = '#';
        ch[0] = '@';
        ch[n * 2 + 2] = '\0';
        for (int i = n; i >= 1; i--) {
            ch[i * 2] = s[i]; ch[i * 2 - 1] = '#';
        }
        len = 2 * n + 1;
    }
    // lc[i] - 1 就是该点整个回文长度
    void manacher() {
        lc[1] = 1;  int k = 1;
        for (int i = 2; i <= len; i++) {
            int p = k + lc[k] - 1;
            if (i <= p) lc[i] = min(lc[2 * k - i], p - i + 1);
            else lc[i] = i % 2;
            while (((ch[i + lc[i]] == '#') && (ch[i + lc[i]] == ch[i - lc[i]])) || ( (ch[i + lc[i]] != '#') && (32 ^ ch[i + lc[i]]) == ch[i - lc[i]])) lc[i]++;
            if (i + lc[i] > k + lc[k]) k = i;
        }
    }
};

char s[N];
void solve() {
    cin >> (s + 1);
    int n = strlen(s + 1), pos = -1;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '*') pos = i;
    }

    int ans = 0, sum = 0;

    auto check = [&](char * str) {
        Manacher manacher(str);
        auto &len = manacher.len;
        auto &lc = manacher.lc;
        for (int i = 1; i <= len; i += 2) {
            ans += (lc[i] - 1) / 2;
        }
        ans -= sum;
    };

    check(s);
    sum = ans;

    // 小写
    for (int i = 0; i < 26; i++) {
        s[pos] = 'a' + i;
        check(s);
    }

    // 大写
    for (int i = 0; i < 26; i++) {
        s[pos] = 'A' + i;
        check(s);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

Problem K z1x的qq

z1xQQ

简单对比即可。

Problem L 排座

可以注意到 $n$ 范围很小，暴力枚举输出满足条件的位置即可

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= 9; j++) {
            cnt++;
            if (j & 1) cout << cnt << ' '; 
        }
    }
    return 0;
}