大连大学2024.4校赛题解

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∈(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\%2=(res_{0}-cnt_{r3} cnt_{r1}-cnt_{l1} cnt_{l3} (a_{l}==a_{r}))\%2$ ，同时 $(r-l-1)-cnt_{l2}=cnt_{l1} cnt_{l3}$ ， $(r-l-1)-cnt_{r2}=cnt_{r1} cnt_{r3}$ 。

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

Problem G 寰宇蝗灾

出题人博客

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

简单对比即可。

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;
}