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

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

时间：2024-09-20 17:03:15浏览次数：10  
标签：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 的非空真后缀，将 b 和 Z 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，其中 c 为 a + b 的前缀，比如 N abcdefgh 就与 N abc H 相匹配，在正串 trie 上求根到 a + b 的路径点权和；

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

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

  • 当复制串形如 N Z b，为了不重复计算，只有形如 N Z d，其中 d 为 b 的真后缀时才匹配，在反串 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就......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99