首页 > 其他分享 >天津大学2024华为杯I.个大的大个 题解

天津大学2024华为杯I.个大的大个 题解

时间:2024-11-01 21:43:59浏览次数:4  
标签:int 题解 long 2024 maxn 天津大学 str 回文 define

原题链接https://acm.tju.edu.cn/problem/P2040
学校oj好像挂了,题解发不出去,又没有草稿功能,所以先存在这里了。

前言

华为杯时候对字符串不太熟,加上看错题了导致没做出这题,很可惜,苦练几个月,现在已经成为串串大师,回过头来秒一下这题发个题解泄恨。

题意

给定一个长为 \(n\) 的字符串, 求有多少对回文子串满足它们在原串中的位置不重叠。数据范围 \(n \leq 10^6\)

分析

既然是回文串对,那么肯定有一个在左,一个在右。那么先考虑一下对于左边的回文串,能跟他配对的回文串满足左端点大于该串右端点的回文串就都可以匹配上。发现我们只在乎每个回文串的左右端点位置,所以很显然的思路是,如果能够预处理出来这个字符串里,以每个位置作为结尾的回文串个数,和以每个位置作为开头的回文串个数,假设分别是数组 \(wei[N]\) 和数组 \(tou[N]\)。
那么答案显然就是 \(\sum_{i=1}^{n-1} wei[i] \times \sum_{j=i+1}^n tou[i]\)。也就是枚举每个位置作为左边串的结尾,能跟他匹配上的是所有开头大于该位置的所有回文串。问题就转化为求这两个数组,下面有两种方法。

马拉车(Manacher)

处理回文串的经典算法,无脑调用后,可以得到以每个点作为回文中心的最长回文半径。我们发现回文串是有单调性的,也就是求出每个点为中心的最大回文串后,两边同时去掉一个字母,依旧是回文串。所以用马拉车后直接配合差分前缀和,就可以得到这两个数组,过程中要注意一下马拉车添加字符后跟原先串的对应关系,代码如下:

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 2e6 + 10;
const int mod = 998244353;
int d[maxn];   
char s[maxn]; 
int maxpos;  
void init(string& str) {  
    maxpos = str.length() * 2;
    s[0] = '#';
    for (int i = 0; str[i]; i++) {
        s[2 * i + 1] = str[i];
        s[2 * i + 2] = '#';
    }
}
void manacher(string str) {
    init(str);
    for (int i = 0, l = 0, r = -1; i <= maxpos; i++) {
        int k = (i > r) ? 1 : min(d[l + r - i], r - i);
        while (i - k >= 0 && i + k <= maxpos && s[i - k] == s[i + k])
            k++;  // 调用朴素算法
        k--;
        d[i] = k;
        if (i + k > r) {
            r = i + k;
            l = i - k;
        }
    }
}
int wei[maxn], tou[maxn];
void solve() {
    int n; cin >> n;
    string str; cin >> str;
    manacher(str);
    for (int i = 0; i <= maxpos; i++) {
        if (d[i]) {
            if (i & 1) { //奇回文
                int pos = i / 2 + 1;
                wei[pos]++;
                wei[pos + d[i] / 2 + 1]--;
                tou[pos + 1]--;
                tou[pos - d[i] / 2]++;
            } else {
                int posl = i / 2; //偶回文串中心偏左
                wei[posl + 1]++;
                wei[posl + 1 + d[i] / 2]--;
                tou[posl + 1]--;
                tou[posl - d[i] / 2 + 1]++;
            }
        }
    }
    for (int i = 1; i <= n; i++)
        tou[i] += tou[i - 1], wei[i] += wei[i - 1];
    ll ans = 0, sum = 0;
    for (int i = n; i; i--)
        sum += tou[i];
    for (int i = 1; i < n; i++) {
        sum -= tou[i];
        ans += wei[i] * sum;
    }
    cout << ans << "\n";
}
signed main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

回文自动机(PAM)

其实主要是想写这个的,好不容易学了字符串科技怎么能不用呢?使用PAM可以很容易得到以每个点作为结尾的字符串个数,也就是在构建回文自动机过程extend时,lst指针在fail树上的深度,这个在构建的过程中很容易得到。那么想要以每个点作为开头,自然就是反着再建一个回文自动机,就得到所要的这两个数组了。基本上就是PAM的板子题。代码如下:

#include <bits/stdc++.h>
// #define int long long
#define inf 0x3f3f3f3f
#define ll long long
#define pii pair<int, int>
#define tii tuple<int, int, int>
#define db double
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 998244353;
struct PAM {
	int tot, last, fail[maxn], c[maxn][27], len[maxn], cnt[maxn];
	char s[maxn]; //下标从1开始的字符串
	PAM() { tot = last = fail[0] = 1, len[1] = -1;}	
	int getfail(int x, int i) {
		while (s[i - len[x] - 1] != s[i]) x = fail[x];
		return x;
	}
	void extend(char ch, int i) { //插入位置 i 的字符 ch
		s[i] = ch;
		int x = getfail(last, i), v = ch - 'a';
		if (!c[x][v]) {
			len[++tot] = len[x] + 2;
			int tem = getfail(fail[x], i);
			fail[tot] = c[tem][v];
			c[x][v] = tot; //必须放最后
            cnt[tot] = cnt[fail[tot]] + 1;
		}
		last = c[x][v];
	}
} pam1, pam2;
int wei[maxn];
ll tou[maxn];
void solve() {
    int n; cin >> n;
    string str; cin >> str;
    for (int i = 1; i <= n; i++) {
        pam1.extend(str[i - 1], i);
        wei[i] = pam1.cnt[pam1.last];
    }
    for (int i = n; i; i--) {
        pam2.extend(str[i - 1], n - i + 1);
        tou[i] = pam2.cnt[pam2.last];
        tou[i] += tou[i + 1];
    }
    ll ans = 0;
    for (int i = 1; i < n; i++)
        ans += 1ll * wei[i] * tou[i + 1];
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}

标签:int,题解,long,2024,maxn,天津大学,str,回文,define
From: https://www.cnblogs.com/TJUHuangTao/p/18521337

相关文章

  • OIFC未来共同体20241030noip模拟四
    T1我们发现\(1\)其实根本没有用,只和一个连通块里的\(0\)的个数有关,直接\(dfs\),判断即可。#include<iostream>#include<cstring>usingnamespacestd;inlineintread(){registerintx=0,f=1;registercharc=getchar();while(c<'0'||c>'......
  • 2024御网线上Pwn方向题解
    ASMChecksec检查保护基本上保护都关闭了64位ida逆向程序只有一段,并且返回地址就是输入的数据,看起来就是srop了,找一下可以用的gadget通过异或清空rax值,然后通过异或ecx和1,异或rax和rcx即可增加rax的值,同理左移一位同样可以增加rax的值,将rax增加到0xf然后打srop,程序还给出了......
  • 2024年10月文章一览
    2024年10月编程人总共更新了21篇文章:1.2024年9月文章一览2.《ProgrammingfromtheGroundUp》阅读笔记:p147-p1803.《ProgrammingfromtheGroundUp》阅读笔记:p181-p2164.《ProgrammingfromtheGroundUp》阅读笔记:p217-p2385.《ProgrammingfromtheGroundUp》读后感......
  • OIFC未来共同体20241028noip模拟三
    T1状压\(dp\),两两之间有相同的位,那一位就为\(1\),否则就为\(0\),考虑哪些选法不合法,要在\(0\)的位上为\(1\),即只在\(1\)上选和不选都是不可以的,于是状压\(dp\)即可。#include<iostream>#defineintlonglongusingnamespacestd;inlineintread(){registerintx......
  • CSP2024 游记
    \(\texttt{Thisarticlewaswrittenbyxxxalq.}\)\(2024.8.26\)开学第一天。\(2024.8.28\)来自浙江杭州的一位优秀OI选手Jasonshan10远赴\(800\text{km}\)来到郑州,晚上他和我跟武思源一起吃了饭,我们仨第一次见面还是在去年的杭师大,转眼都过去一年多了,此方也早已成为......
  • 2024网鼎杯线上赛REVERSE02(超详细)
    进入主函数分析代码发现了四段加密,一层一层进行解密第一步:打开进入main函数,然后分析代码第一个加密对dest的八个字节做了乘2加密,密文是s2伪代码下看不全在汇编下看第二步:第二块数据进行了异或加密异或key是XorrLord,然后写脚本进行解密拿到了第一段和第二......
  • 2024-2025-1 20241310 《计算机基础与程序设计》第6周学习总结
    2024-2025-120241310《计算机基础与程序设计》第6周学习总结作业信息这个作业属于哪个课程[2024-2025-1-计算机基础与程序设计](https://edu.cnblogs.com/campus/besti/2024-2025-1-CFAP)这个作业要求在哪里2024-2025-1计算机基础与程序设计第一周作业这个作业的......
  • 20241030 训练记录
    [TJOI2012]桥删边最短路模板。只需求出对于每条边,不经过这条边的最短路就做完了。考虑不在原\(1\)到\(n\)最短路上的边,它们的答案就为原本的最短路。对于原本就在最短路上的边,既然删掉了这条边,那么新的最短路一定会经过另外一条边,设这条边为\((u,v,w)\),\(dis(u,v)\)表......
  • 20222325 2024-2025-1 《网络与系统攻防技术》实验四实验报告
    1.实验内容一、恶意代码文件类型标识、脱壳与字符串提取对提供的rada恶意代码样本,进行文件类型识别,脱壳与字符串提取,以获得rada恶意代码的编写作者,具体操作如下:(1)使用文件格式和类型识别工具,给出rada恶意代码样本的文件格式、运行平台和加壳工具;(2)使用超级巡警脱壳机等脱壳软件,......
  • CodeForces Dora and C++ (2007C) 题解
    CodeForcesDoraandC++(2007C)题解题意给一个数组\(c_{1...n}\),定义数组的\(range\)是最大值减最小值,即极差。给出两个值\(a\)和\(b\),每步操作中,可给数组中任一一个数增大\(a\)或增大\(b\)。问任意步操作后(可以是\(0\)步),极差的最小值。思路(要直接看答案可以跳......