首页 > 其他分享 >洛谷 P6681 [CCO2019] Bad Codes

洛谷 P6681 [CCO2019] Bad Codes

时间:2024-01-25 13:55:06浏览次数:34  
标签:typedef Codes const nm P6681 long int Bad define

洛谷传送门

QOJ 传送门

QOJ1193 Ambiguous Encoding 撞了。

考虑直接 dp,设 \(f_{i, j}\) 为较长的串未被较短的串覆盖的部分是第 \(i\) 个字符串的长为 \(j\) 的后缀。转移考虑枚举接在较短的串后面是第 \(k\) 个串,然后讨论一下 \(j\) 和第 \(k\) 个字符串的大小关系就可以确定转移到哪。

发现转移成环,考虑建图用最短路转移。这里 \(|E| = n^2m, |V| = nm\),复杂度看似是 \(O(|E| \log |V|) = O(n^2m \log nm)\) 的。但是 Dijkstra 最短路复杂度中的 \(|E|\) 实际上是松弛次数,但是这题考虑最大边权 \(\le m\) 所以任意时刻队列距离的极差 \(\le m\),所以每个点松弛次数 \(\le m\),所以复杂度其实是 \(O(n^2m + nm^2 \log nm)\)。这可以解释为什么 QOJ1193 Ambiguous Encoding 跑得那么快。

code
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))

using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<int, int> pii;

const int maxn = 55;
const int maxm = 2510;

int n, id[maxn][maxn], nt, f[maxm];
bool vis[maxm];
vector<pii> G[maxm];
string s[maxn];

struct node {
	int u, d;
	node(int a = 0, int b = 0) : u(a), d(b) {}
};

inline bool operator < (const node &a, const node &b) {
	return a.d > b.d;
}

priority_queue<node> pq;

void solve() {
	scanf("%d%*d", &n);
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		for (int j = 0; j < (int)s[i].size(); ++j) {
			id[i][j] = ++nt;
		}
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j < (int)s[i].size(); ++j) {
			for (int k = 1; k <= n; ++k) {
				int t = min(j, (int)s[k].size());
				if (s[k].substr(0, t) == s[i].substr((int)s[i].size() - j, t)) {
					if (t == (int)s[k].size()) {
						G[id[i][j]].pb(id[i][j - t], t);
					} else {
						G[id[i][j]].pb(id[k][(int)s[k].size() - j], t);
					}
				}
			}
		}
	}
	mems(f, 0x3f);
	set<string> S;
	for (int i = 1; i <= n; ++i) {
		S.insert(s[i]);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j < (int)s[i].size(); ++j) {
			string t = s[i].substr(0, j);
			if (S.find(t) != S.end()) {
				f[id[i][(int)s[i].size() - j]] = j;
				pq.emplace(id[i][(int)s[i].size() - j], j);
			}
		}
	}
	while (pq.size()) {
		int u = pq.top().u;
		pq.pop();
		if (vis[u]) {
			continue;
		}
		vis[u] = 1;
		for (pii p : G[u]) {
			int v = p.fst, d = p.scd;
			if (f[v] > f[u] + d) {
				f[v] = f[u] + d;
				if (!vis[v]) {
					pq.emplace(v, f[v]);
				}
			}
		}
	}
	int ans = 2e9;
	for (int i = 1; i <= n; ++i) {
		ans = min(ans, f[id[i][0]]);
	}
	printf("%d\n", ans > 1e9 ? -1 : ans);
}

int main() {
	int T = 1;
	// scanf("%d", &T);
	while (T--) {
		solve();
	}
	return 0;
}

标签:typedef,Codes,const,nm,P6681,long,int,Bad,define
From: https://www.cnblogs.com/zltzlt-blog/p/17986997

相关文章

  • xrandr: error BadMatch (invalid parameter attributes) 无法设置自定义分辨率刷新率
    我的环境ManjaroKDENvidia显卡前言前几天在创建虚拟显示屏让iPad成为副屏时,我打算使用xrandr给虚拟显示屏自定义分辨率以及144hz的刷新率(为了与主屏幕同步)但是当进行了如下操作后发生了RT报错:❯cvt19201080144#1920x1080143.88Hz(CVT)hsync:169.35kH......
  • ABC337 E Bad Juice 题解
    QuestionABC337EBadJuice交互题\(n\)瓶果汁中有\(1\)瓶是坏的,现在需要把这些果汁分给\(m\)个人,每个人可以喝任意瓶,然后通过\(m\)个人的回复判断哪一瓶是坏的需要输出最小的\(m\)以及坏果汁的编号Solution\(m\)返回的结果由\(01\)构成,自然而然想到二进制,考虑......
  • 解析 terminating with uncaught exception of type std::bad_cast: std::bad_cast
    解析"terminatingwithuncaughtexceptionoftypestd::bad_cast:std::bad_cast"简介在C++编程中,我们有时会遇到异常(exception),这些异常可能是由于程序运行时出现意外情况而引发的错误。其中,"terminatingwithuncaughtexceptionoftypestd::bad_cast:std::bad_cast"是一种......
  • vite构建的react+ts项目中使用arcodesign组件的问题
    今天在react项目中使用arcodesign组件库,引入的图标巨大无比,调样式也不起作用,如下图。网上找了也没看到类似的问题,去官网文档里看,发现是没有引入组件的样式。在我这个vite构建的react+ts项目中找到两个解决办法:第一个是直接引入全部样式import"@arco-design/web-react/dist/cs......
  • STM32+Codesys工业软件PLC解决方案
    工业控制系统在现代制造和自动化领域扮演着关键角色,基于IEC61131-3标准的控制器编程开发软件平台CODESYS,适用于多种行业的控制系统的开发,使用户方便快捷地对自动化工程进行编程和配置,完成项目开发、软件测试和应用调试。本次STM32联合合作伙伴CODESYS带您深入了解如何利用STM3......
  • CODESYS 仿真运行
    这是一篇关于CODESYS开发环境的小白教程,没有任何多余的步骤和解释,会玩的看到这里可以闪了......
  • 初中英语优秀范文100篇-043Is Television Good or Bad?看电视是好是坏?
    PDF格式公众号回复关键字:SHCZFW043记忆树1Moreandmorepeoplelikewatchingtelevision.翻译越来越多的人喜欢看电视简化记忆电视句子结构1"Moreandmorepeople"是主语,表示越来越多的人。2"like"是谓语,表示喜欢或愿意。3"watchingtelevision"是宾语,表示......
  • CRC-Aided Sparse Regression Codes for Unsourced Random Access
    一、摘要随记仅用于个人对论文的分析、初步复现。1.1文件夹介绍随机包含了一篇论文的仿真结果的源代码,该论文的标题是"CRC-aidedSpareRegressionCodesforUnsourcedRandomAccess"。源代码CRC-aided_SPARCs_for_URA-main,一共包括三个文件夹:"CRC-BMSTcodesforst......
  • Java8之函数式接口@FunctionalInterface和lambada表达式
    跟着孙哥学Spring,b站:https://www.bilibili.com/video/BV185411477k/?spm_id_from=333.337.search-card.all.click在Java中,函数式接口和Lambda表达式是一种常见的编程模式,主要用于简化代码和提高代码的可读性。函数式接口(FunctionalInterface)函数式接口是Java8中引入的一个......
  • nignx多域名多站点的配置,502 Bad Gateway解决方法
    本文以ubuntu为例,其他Linux系统类似1、先建立两个放网站的目录mkdir/datamkdir/data/ding1commkdir/data/ding2com2、查看nginx.conf可知放入位置sites-enabled文件夹内所有文件都生效cd/etc/nginxcp-rsites-enabledsites-enabled.bak#修改前先备份cdsites-enabled多域名......