首页 > 其他分享 >P7086 题解

P7086 题解

时间:2024-02-27 18:26:49浏览次数:25  
标签:int 题解 vector maxn P7086 选中 type match

考虑把每个字符串的前 \(k\) 位和后 \(k\) 位看成点,字符串看成边,那么一个字符串前缀后缀至少有一个是相似群体的前缀后缀,看成这条边的两个端点至少有一个被选中。

那么这就变成了一个最小点覆盖问题。

考虑匈牙利算法算出答案,然后考虑如何构造答案。

考虑右边没有被匹配的点,选中这些点向左边连的点,因此这个点本身就不用被选中,考虑左边刚刚被选中的点,它们在右边匹配的点就不用选了,那么它们在右边匹配的点就进入右边没有被匹配的点相同的流程,如此递归下去,那么左边便利到的点就会被选中,右边被遍历到的点就不会被选中。

如此便可以构造出选中的点,然后再分配字符串到集合即可。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;

const int maxn = 1e6+114;
const int base = 1145141;
int vis[maxn],match[maxn];
vector<int> edge[maxn],fedge[maxn];
map<int,int> road[2][maxn];
int ans;
int fm[maxn];
bool hungary(int u){
	for(int v:edge[u]){
		if(vis[v]==1) continue;
		vis[v]=1;
		if(match[v]==0||hungary(match[v])==true){
			match[v]=u;
			fm[u]=v;
			return true;
		}
	}
	return false;
}

int pre[maxn],suf[maxn];

int n,k,cnt;
map<int,int> f;
map<int,int> p[2];
vector<int> chifan[2];
int use[maxn][2];

vector<int> answer[2];
map<int,int> pos[2];

int op[maxn][2];
vector<int> OUT[maxn][2];
void dfs(int u,int type){
	if(op[u][type]==1) return ;
	op[u][type]=1;
	if(type==0){
		dfs(fm[u],1);
	}
	else{
		for(int nxt:fedge[u]){
			if(nxt!=match[u]){
				dfs(nxt,0);
			}
		}
	}
}
signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<k;j++){
			pre[i]=pre[i]*base+s[j];
		}
		for(int j=s.size()-1;j>=s.size()-k&&j<s.size();j--){
			suf[i]=suf[i]*base+s[j];
		}
		if(f[pre[i]]==0){
			f[pre[i]]=++cnt;
		}
		if(p[0][f[pre[i]]]==0)
			chifan[0].push_back(f[pre[i]]),p[0][f[pre[i]]]=1;
		if(f[suf[i]]==0){
			f[suf[i]]=++cnt;
		}
		if(p[1][f[suf[i]]]==0)
			chifan[1].push_back(f[suf[i]]),p[1][f[suf[i]]]=1;
		edge[f[pre[i]]].push_back(f[suf[i]]),fedge[f[suf[i]]].push_back(f[pre[i]]);
	}
	for(int i:chifan[0]){
		memset(vis,0,sizeof(vis));
		if(hungary(i)==true) ans++;
	}
	for(int i:chifan[1]){
		if(match[i]==0){
			dfs(i,1);
		}
	}
	for(int i=1;i<=n;i++){
		if(op[f[pre[i]]][0]==1){
			OUT[f[pre[i]]][0].push_back(i);
		}
		else if(op[f[suf[i]]][1]==0){
			OUT[f[suf[i]]][1].push_back(i);
		}
	}
	cout<<ans<<'\n';
	for(int i:chifan[0]){
		if(op[i][0]==1){
			cout<<OUT[i][0].size()<<' ';
			for(int j:OUT[i][0]) cout<<j<<' ';
			cout<<'\n';
		}
	}
	for(int i:chifan[1]){
		if(op[i][1]==0){
			cout<<OUT[i][1].size()<<' ';
			for(int j:OUT[i][1]) cout<<j<<' ';
			cout<<'\n';
		}
	}
	return 0;
}

标签:int,题解,vector,maxn,P7086,选中,type,match
From: https://www.cnblogs.com/chifan-duck/p/17998350

相关文章

  • AT_abc317_f 题解
    调了一小时结果发现爆longlong了。考虑数位dp,具体来说,设计状态\(dp_{i,r_1,r_2,r_3,mx_1,mx_2,mx3_,c_1,c_2,c_3}\)表示当前考虑到第\(i\)位,\(x_1,x_2,x_3\)模\(a_1,a_2,a_3\)等于\(r_1,r_2,r_3\)三个数是否达到\(n\)的上界以及是否全部是\(0\)。然后从高到低枚......
  • AT_joisc2019_j 题解
    先考虑这个式子:\[\sum_{j=1}^{M}|C_{k_{j}}-C_{k_{j+1}}|\]一定是在\(C\)有序时取到,具体证明很简单各位读者自己证明。那么现在式子变成:\[\sum{V}+2\times({C_{\max}-C_{\min}})\]这个时候一个常见的技巧是将\(C\)排序。这个时候就可以定义状态:\[dp_{i,j}=\s......
  • CF1862G 题解
    首先这个查询操作很迷,考虑先化简查询操作。不难发现由于每次是加上一个逆的等差序列,因此一次操作完每个数与它的前驱之差一定会减少,因此加上等差序列的次数就等于全局每个数与它的前驱之差最大值。又因为会排序去重,所以最后剩下来的数一定是最开始的数一路加过来的,至此我们发现......
  • P5837 [USACO19DEC] Milk Pumping G 题解
    原题传送门思路只用堆每一个点跑一边最短路,在用当前点到点\(n\)的距离,再用当前点的\(f\)乘上\(10^6\)除以刚刚算出的值即可。代码#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<queue>usingnamespacestd;#defin......
  • P2350 [HAOI2012] 外星人 题解
    很巧妙的一道题。首先会发现如果最终\(\varphi(N)=1\)的话一定是通过很多次从\(2\)这个因子变到\(1\)的。而这个函数每迭代一次,就会有且仅有一个\(2\)的因子变为\(1\)。所以题目转化为了求\(N\)在函数迭代过程中一共会产生多少个\(2\)的因子。考虑\(\text{dp}\),设......
  • U332154 carbon 题解(期望)
    这题其实挺简单的......首先我们手模样例,对于第一组样例其实就是在1-n之间取一个数,求取到的数的期望。所以E(x)=\(\frac{1+n}{2}\)。对于第二组样例,我们首先将所有可能情况枚举出来:1010101010101010101099999999910888888889......
  • U329011 trie pi 题解
    花了2d打磨出来的题目,觉得很有意思。先讲点无关的,这道题有两版,但都是对要求的量进行改动。1.第一次要求的是y属性为a与y属性为b的两个节点的路径权值之和,对于要求的这个量,我们设v[i]为i到根节点的权值之和。那么我们先对a,b进行质因数分解,设dcg为a,b分解质因数后最长公共前缀的乘......
  • 时间戳时区问题解决方法
    在大家开发时会遇到这种情况:服务器是以东八时区为准(即中国标准时间),但是客户端会在不同地方,比如说雅典开罗(+2),格陵兰(-3),夏威夷(-10),当客户端选择某一个时间后,传递给服务器的时间戳,是以当地时区来解析的时间戳,这样就会出现一个时间差的问题,从而造成时间不准确。下面我们就来解决这种问......
  • [ABC314Ex] Disk and Segments题解(退火实现)
    一到比较水的退火题(虽然也调了3h)题意在平面直角坐标系中,有\(n\)条线段,第\(i\)条的端点是\((a_i,b_i)\)和$(c_i,d_i)$,任意线段不共点。(这里笔者为了方便会默认\(a_i<c_i\))你要在平面上画一个圆,使得任意一条线段都和圆周或圆内部有至少一个公共点,求满足条件的圆的最小......
  • P4666 [BalticOI 2011 Day1] Growing Trees题解(平衡树思想)
    自己第一道不看题解写出来的紫题,庆祝一下(没初始化种子导致调了30min)这是一个fhq-treap的题解思路来源:首先看题目,因为是序列上的问题,不难想到是一道数据结构题。首先看到操作C:对于这种操作,我们可以用平衡树解决,具体方法是,将树split成\(<min,min\lex\lemax,>max\)这......