首页 > 其他分享 >题解:洛谷P9934 [NFLSPC #6] 绝不能忘记的事……

题解:洛谷P9934 [NFLSPC #6] 绝不能忘记的事……

时间:2024-09-20 17:03:15浏览次数:9  
标签:map 洛谷 ty int 题解 s1 P9934 复制 串形

题目链接:洛谷P9934 [NFLSPC #6] 绝不能忘记的事……

hatelove大力分讨。

这道题先分三种大情况:N 在左边,N 在中间,N 在右边。

声明:以下分类讨论中,a, b, c, d 均为记住的字符串。

记录操作

N 在左边

  • 当复制串形如 N a b,可以用 map <string, int> 记录。

  • 当复制串形如 N a H,那么 a 就是 a H 的非空真前缀,可以将 a 顺序加入正串 trie 中。

  • 当复制串形如 N Z b,那么 b 就是 Z b 的非空真后缀,将 bZ b 都首尾颠倒后 b 就是 Z b 的非空真前缀,可以将 b 倒序加入反串 trie 中。

  • 当复制串形如 N Z H,那么每个 N 在左边的复制串都可以与它匹配,直接累加答案。

N 在右边

我们发现只要将整个字符串颠倒一下,如果有 H,将 H 变为 Q,就可以按照 N 在左边的方式处理字符串。

N 在中间

  • 当复制串形如 a N b,可以用 map <pair <string, string>, int> 记录。

  • 当复制串形如 Q N b,可以用 map <string, int> 记录。

  • 当复制串形如 a N H,可以用 map <string,int>记录。

  • 当复制串形如 Q N H,那么每个 N 在中间的复制串都可以与它匹配,直接累加答案。

统计操作

将所有的复制串枚举一遍。

N 在左边

  • 当复制串形如 N a b,那么以下三种情况可以与其匹配:
  1. N c d,其中 a + b = c + d,直接累加 map[a + b]

  2. N c H,其中 ca + b 的前缀,比如 N abcdefgh 就与 N abc H 相匹配,在正串 trie 上求根到 a + b 的路径点权和;

  3. N Z d,其中 da + b 的后缀,比如 N abcdefgh 就与 N Z defgh 相匹配,在反串 trie 上求根到 a + b 的路径点权和。

  • 当复制串形如 N a H,为了不重复计算,只有形如 N c H,其中 ca 的真前缀时才匹配,在正串 trie 上求根到 a 的路径点权和。

  • 当复制串形如 N Z b,为了不重复计算,只有形如 N Z d,其中 db 的真后缀时才匹配,在反串 trie 上求根到 b 的路径点权和。

答案取第一种情况匹配数、第二三种情况匹配数和的最大值加上一开始统计的 N Z H 的个数。

N 在右边

与记录操作一样,颠倒后按 N 在左边一样统计。

N 在中间

  • 当复制串形如 a N b,那么以下三种情况可以与其匹配:
  1. a N b,直接累加 map[pair(a, b)]

  2. a N H,直接累加 map[a]

  3. Q N b,直接累加 map[b]

  • 当复制串形如 Q N b,直接累加 map[b]

  • 当复制串形如 a N H,直接累加 map[a]

答案取第一种情况匹配数、第二三种情况匹配数和的最大值加上一开始统计的 Q N H 的个数。

这样就分类讨论完了所有情况。

完整代码是真的长

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 9;
int ch[5][N][26], red[5][N], tot[5], ans[5], n;
map <string, int> mp, mp5, mp2, mp3;//mp s1 = "N", mp5 s3 = "N", mp3, mp4, mp5 s2 == "N"
map <pair <string, string>, int> mp4;
string tmp, s1, s2, s3;
int num(char c){
	return c - 'a' + 1;
}
void insert(int ty){
	int u = 1, len = tmp.length();
	for(int i = 0; i < len; i++){
		int x = num(tmp[i]);
		if(ch[ty][u][x] == 0){
			ch[ty][u][x] = ++tot[ty];
			u = tot[ty];
		}
		else
			u = ch[ty][u][x];
	}
	red[ty][u]++;
}
int query(int ty){
	int u = 1, ans = 0, len = tmp.length();
	for(int i = 0; i < len; i++){
		int x = num(tmp[i]);
		if(ch[ty][u][x]){
			ans += red[ty][ch[ty][u][x]];
			u = ch[ty][u][x];
		} else
			break;
	}
	return ans;
}
/*
ty = 1 : s1 == "N",正串;
ty = 2 : s1 == "N",反串;
ty = 3 : s3 == "N",正串;
ty = 4 : s3 == "N",反串
*/
struct Store{
	string t1, t2, t3;
} st[5][N];
int cnt[5];
signed main(){
	for(int i = 0; i <= 8; i++)
		tot[i] = 1;
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++){
		cin >> s1 >> s2 >> s3;
		if(s1 == "N")
			st[1][++cnt[1]] = Store{s1, s2, s3};
		else if(s2 == "N")
			st[2][++cnt[2]] = Store{s1, s2, s3};
		else
			st[3][++cnt[3]] = Store{s1, s2, s3};
	}
	for(int i = 1; i <= 3; i++){
		int w = 0, cnta = 0, cntb = 0;
		if(i == 1){
			for(int j = 1; j <= cnt[i]; j++){
				s1 = st[i][j].t1;
				s2 = st[i][j].t2;
				s3 = st[i][j].t3;
				if(s2 != "Z" && s3 != "H"){
					tmp = s2 + s3;
					mp[tmp]++;
				} else if(s2 == "Z" && s3 != "H"){
					tmp = s3;
					reverse(tmp.begin(), tmp.end());
					insert(2);
				} else if(s2 != "Z" && s3 == "H"){
					tmp = s2;
					insert(1);
				} else
					w++;
			}
			for(int j = 1; j <= cnt[i]; j++){
				s1 = st[i][j].t1;
				s2 = st[i][j].t2;
				s3 = st[i][j].t3;
				if(s2 != "Z" && s3 != "H"){
					int sum = mp[s2 + s3];
					tmp = s2 + s3;
					tmp.pop_back();
					sum += query(1);
					tmp = s2 + s3;
					reverse(tmp.begin(), tmp.end());
					tmp.pop_back();
					sum += query(2);
					ans[i] = max(ans[i], sum);
				} else if(s2 == "Z" && s3 != "H"){
					tmp = s3;
					reverse(tmp.begin(), tmp.end());
					cntb = max(cntb, query(2));
				} else if(s2 != "Z" && s3 == "H"){
					tmp = s2;
					cnta = max(cnta, query(1));
				}
			}
			ans[i] = max(ans[i], cnta + cntb) + w;
		} else if(i == 2){
			for(int j = 1; j <= cnt[i]; j++){
				s1 = st[i][j].t1;
				s2 = st[i][j].t2;
				s3 = st[i][j].t3;
				if(s1 != "Q" && s3 != "H")
					mp4[make_pair(s1, s3)]++;
				else if(s1 == "Q" && s3 != "H")
					mp3[s3]++;
				else if(s1 != "Q" && s3 == "H")
					mp2[s1]++;
				else
					w++;
			}
			for(int j = 1; j <= cnt[i]; j++){
				s1 = st[i][j].t1;
				s2 = st[i][j].t2;
				s3 = st[i][j].t3;
				if(s1 != "Q" && s3 != "H")
					ans[i] = max(ans[i], mp2[s1] + mp3[s3] + mp4[make_pair(s1, s3)]);
				else if(s1 == "Q" && s3 != "H")
					cntb = max(cntb, mp3[s3]);
				else if(s1 != "Q" && s3 == "H")
					cnta = max(cnta, mp2[s1]);
			}
			ans[i] = max(ans[i], cnta + cntb) + w;
		} else {
			for(int j = 1; j <= cnt[i]; j++){
				s1 = st[i][j].t1;
				s2 = st[i][j].t2;
				s3 = st[i][j].t3;
				if(s1 == "Q")
					s1 = "H";
				reverse(s1.begin(), s1.end());
				reverse(s2.begin(), s2.end());
				string fk = s1;
				s1 = s2;
				s2 = fk;
				st[i][j].t1 = s1;
				st[i][j].t2 = s2;
				if(s1 != "Z" && s2 != "H"){
					tmp = s1 + s2;
					mp[tmp]++;
				} else if(s1 == "Z" && s2 != "H"){
					tmp = s2;
					reverse(tmp.begin(), tmp.end());
					insert(4);
				} else if(s1 != "Z" && s2 == "H"){
					tmp = s1;
					insert(3);
				} else
					w++;
			}
			for(int j = 1; j <= cnt[i]; j++){
				s1 = st[i][j].t1;
				s2 = st[i][j].t2;
				s3 = st[i][j].t3;
				if(s1 != "Z" && s2 != "H"){
					int sum = mp[s1 + s2];
					tmp = s1 + s2;
					tmp.pop_back();
					sum += query(3);
					tmp = s1 + s2;
					reverse(tmp.begin(), tmp.end());
					tmp.pop_back();
					sum += query(4);
					ans[i] = max(ans[i], sum);
				} else if(s1 == "Z" && s2 != "H"){
					tmp = s2;
					reverse(tmp.begin(), tmp.end());
					cntb = max(cntb, query(4));
				} else if(s1 != "Z" && s2 == "H"){
					tmp = s1;
					cnta = max(cnta, query(3));
				}
			}
			ans[i] = max(ans[i], cnta + cntb) + w;
		}	
	}
	printf("%lld", max(max(ans[1], ans[2]), ans[3]));
	return 0;
}

标签:map,洛谷,ty,int,题解,s1,P9934,复制,串形
From: https://www.cnblogs.com/JPGOJCZX/p/18422853

相关文章

  • 快速幂模板/洛谷P1226【模板】快速幂
    ​本题是CSP-J组的第四题。题意:给出一个有向图,当前在1号点,初始在时间0,必须在k的倍数的时间出发,且到终点的时间也必须是k的倍数。每条边有一个边权,只有在当前时间≥时才可以通过,且不能在原地不动,即每一个时间点必须走一条边。问从11号点出发到nn号时最早的时刻。(没......
  • 【问题解决】Web在线办公系统-数据爬取结果乱码
    问题描述在【热门电影】模块,通过jsoup爬虫并解析网页数据时,执行代码,出现“中文乱码”问题。解决方法由于网页自带的编码方式与后端开发中jsoup解析的编码方式不匹配,需要修改后端解析网页的编码方式。//设置爬取网页的地址Stringurl="https://movie.douban.com/......
  • Gradio离线部署到内网,资源加载失败问题(Gradio离线部署问题解决方法)
    问题描述Gradio作为一个快速构建一个演示或Web应用的开源Python包,被广泛使用,最近在用这个包进行AI应用构建,打包部署到内网Docker的时候发现有些资源无法使用。网页加载不出来。即使加载出来了也是没有样式无法点击的。一般出现这个问题的多半是低版本的gradio,高版本中已经解决......
  • CF1526F Median Queries 题解
    Description本题是一道交互题。给定\(n\),你需要猜测一个长度为\(n\)的排列\(p\)(即\(p\)包含所有\(1\)到\(n\)的整数各一次)。已知\(p\)满足\(p_1<p_2\)。当然,你可以进行询问,每次询问你需要给定三个互不相同的整数\(a,b,c\),交互器会返回\(|p_a-p_b|,|p_b-p_c|,|p_......
  • P9705 「TFOI R1」Unknown Graph题解
    思路题目给出了每个点的初度和入度,由于图是无重边无自环的有向图。要求满足限制的图有多少条边与建图方案。我们可以考虑使用网络流中的最大流。我们知道这是一道网络流后,题目的难点就转移到网络流的建模以及输出方案的办法。网络流的建模:题目所给的条件没有源点汇点并指出......
  • P5979 [PA2014] Druzyny 题解
    对于一个固定的右端点\(r\),左端点\(l\)合法当且仅当\(\max(d_l,d_{l+1},\dotsd_r)\ler-l+1\le\min(c_l,c_{l+1},\dots,c_r)\)。容易得到一个很朴素的dp:记\(f_i\)表示前\(i\)个位置可以分成的组的数目的最大值,\(g_i\)表示有多少种分组方案能达到最大值,直接枚举左端点......
  • CF2004G 题解
    题意定义关于数字串\(s\)的函数\(f(s)\)表示将\(t\)切分为\(m\)段,要求\(m\)是偶数,假设这些字符串分别为\(t_1,t_2,\ldots,t_m\),有\(s=t_1+t_2+\ldots+t_m\)。定义\(A^x\)表示\(\underbrace{AA\ldotsAA}_{x~\text{times}}\),求一种划分方式,使得\(t_2^......
  • P1108 低价购买 题解
    这题在求最长下降子序列的基础上加了一个求方案数的要求,这就让这道题目变难了很多。我们考虑我们在求最长下降子序列的时候,总是从这一位,要么重新开始计数,要么只和前面的有关,所以前面的信息完全丢失了,无法判断有多少方案,所以我们就要针对前面的方案数设计一个dp来统计。可以称之......
  • 题解:CF1906F Maximize The Value
    可以在cnblog中阅读。见这种题比较少,写篇题解加深印象。如果直接上数据结构维护数组,似乎没有好的办法处理操作序列的一个子段。那不妨转变思路,对操作序列上数据结构维护。假设顺序进行每个修改操作,我们用时间表示修改操作的编号,位置表示数组的下标,则常见的维护序列的数据结构......
  • 蓝桥杯十五届软件赛C++B组题解
    最近蓝桥杯官网已经把十五届题目上架了,我会尽快的将题解发出来,没有发的过段时间再补。​​​​​​​数字接龙一个很鹅心的搜索题,一不注意就会写错,比赛的时候写不来,题目上架后也WA了两个样例才过。题目大意:也就是说从(1,1)开始 ,下一步路的数据总是要比当前数据大1,超过k就......