大连大学2024.4校赛题解

Problem A 更爱吃面包的东百王

输出和即可

#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。因此直接选取长度为的区间即可。

#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 双倍字符串

记为字符串的最长双倍字符串长度，用记录第字母的上一次出现的位置

转移为

即为答案

#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和r把数组a分成了五个部分，易得交换操作对l前边和r后边的部分不会产生新的逆序对，也不会删除旧的逆序对，所以每次交换对结果产生影响的只有这一段。

对于内的，比小、与相等、比大的元素个数分别记为、、，比小、与相等、比大的元素个数分别记为、、，令为交换前整个数组逆序对的个数，为交换后整个数组逆序对的个数。

则易得，同时，。

所以，即。

Problem G 寰宇蝗灾

出题人博客

Problem H Highest Common Factor

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

为了保证，区间的所有元素需要相同。直接遍历数组找到所有元素相同的最长子区间即可。

#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 最大公因数

题目要找的的最长区间，若令，那么满足条件的区间一定满足：该段区间内有且区间内其他元素为的倍数。

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

由于本题，所以可以开一个vector<pair<int,int>>p[N]数组，p[i]内的pair存储满足是的倍数的的下标和是否等于。

Problem J 假回文串

哈希做法

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

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

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

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

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

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

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

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

我们分别去枚举通配符为 和 时得到的贡献减去多出来的贡献（通配符为 时能得到的贡献 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 排座

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

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