首页 > 其他分享 >题解 NOD2207C【不降序列】

题解 NOD2207C【不降序列】

时间:2023-06-10 17:01:04浏览次数:43  
标签:fa 不降 题解 NOD2207C solution int 数组 include deg

problem

给出 n 个数组 A1​ 到 An​ ,数组中的元素为 1 到 M 之间的数字。

数组之间也存在字典序,即从第一个数开始逐位比较,一旦某个数字大于另一个,则数组的字典序大于另一个,如果某一个是另一个的前缀,则前缀的字典序更小。

你可以选择一些大于 0 的数字执行减法操作,一旦选中某个数字 k ,则从 A1​ 到 An​ 中,所有的数字 k 都要被减掉 M,即变成 k−M,并且只能对于正数执行减法操作。

问能否通过这样的操作,使得这 n 个数组的字典序是不下降的(可以相等)。

solution

以下是显然无解的情况,请特判:

[1 2 3]
[1 2]

观察一些性质:

  • 如果 \(A_{11}>A_{21}\),那么必然是 \(A_{11}\) 被减而 \(A_{21}\) 不被减。
  • 如果 \(A_{11}<A_{21}\),除了 \(+A_{11}\land -A_{21}\) 外其他都行。

以下就有很多种做法:

solution 1:2-sat

每个点拆成两个点表示被减(\(-x\)) 和不被减(\(+x\)),除此之外还有超级源 \(S\)。

对于两个相邻的数组,找到第一个不相同的,记为 \(u,v\)。

  • 如果 \(u<v\) 那么 \(+u\to +v,-v\to -u\)。
  • 如果 \(u>v\) 那么 \(S\to-u,S\to+v\)。

建出来一个图。我们强制选 \(S\),看一下 \(S\) 能选到的有没有矛盾(即同时选到 \(-x\) 和 \(+x\))。如果有就无解。

否则,\(S\) 所指示的数字该减就减,该加就加,和 \(S\) 不联通的直接不管。

solution 2:建 DAG

对于两个相邻的数组,找到第一个不相同的,记为 \(u,v\)。然后 \(u\to v\)。

如果建出来的图有环,无解。

注意到对于一条 DAG 上的链,我们把这些数字的符号拿出来,那么就是说 \(u>v\) 时符号必须由负变为正,\(u<v\) 时符号不能减少。

也就是 \(u>v\) 的边,要满足 \(v\) 以后全是正数,\(u\) 往上全是负数。其他没提到的点默认为负。

solution 3:随机化

我们放弃图论。按列考虑这些数组,有个结论是:删除的必然是一段前缀(否则必然不满足条件)。所以有两个大于号的就无解。

考虑第二列,按照 \(A_{i1}\) 相同的分开,继续处理。

问题是如果 \(A{i1}\) 合法,那么不知道删什么。

随机化:继续往下,每次到要删除的时机,退回到 \(A_{i1}\) 从头来过。

听说 100 次能过。

code

solution 2
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr,##__VA_ARGS__)
#else
#define debug(...) void(0)
#endif
typedef long long LL;
template<int N> struct dsu{
	int fa[N+10],siz[N+10],cnt;
	dsu(int n=N):cnt(n){iota(fa+1,fa+n+1,1),fill(siz+1,siz+n+1,1);}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	void merge(int x,int y){if(x=find(x),y=find(y),x!=y) cnt--,siz[x]<siz[y]&&(swap(x,y),0),siz[fa[y]=x]+=siz[y];}
};
int n,m,deg[1<<16],S,col[1<<16],key[1<<16],f[1<<16];
vector<int> a[1<<16],g[1<<16];
queue<int> q;
dsu<1<<17> s;
bool toposort(){
	for(int i=1;i<=m;i++) for(int v:g[i]) deg[v]++;
	for(int i=1;i<=m;i++) if(!deg[i]) q.push(i);
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int v:g[u]){
			//u 是正数,u+n 是负数
			if(u>v) col[v]=1,key[u]=1;
			else col[v]|=col[u];
			if(--deg[v]==0) q.push(v);
		}
	}
	return *min_element(deg+1,deg+m+1)||*max_element(deg+1,deg+m+1);
}
bool kly=0;
bool dfs(int u){
	if(~f[u]) return f[u];
	f[u]=key[u];
	for(int v:g[u]) f[u]|=dfs(v);
	if(f[u]) kly|=col[u];
	return f[u];
}
int main(){
	#ifdef LOCAL
	 //	freopen("22.in","r",stdin);
	 //	freopen("log.out","w",stderr);
	#endif
	scanf("%d%d",&n,&m),S=m<<1|1;
	for(int i=1,k;i<=n;i++){
		scanf("%d",&k);
		a[i]=vector<int>(k);
		for(int&x:a[i]) scanf("%d",&x);
	}
	for(int i=2;i<=n;i++){
		int j=0,lim=min(a[i-1].size(),a[i].size());
		while(j<lim&&a[i-1][j]==a[i][j]) j++;
		//最多两倍时间
		if(j<lim) g[a[i-1][j]].push_back(a[i][j]);
		else if(a[i-1].size()>a[i].size()) return puts("No"),0;
	}
	for(int i=1;i<=m;i++){
		for(int v:g[i]) debug("%d %d\n",i,v);
	}
	if(toposort()) return debug("fuck"),puts("No"),0;
	memset(f,-1,sizeof f);
	for(int i=1;i<=m;i++) dfs(i);
	if(kly) return debug("sewoifhqoigiwueg"),puts("No"),0;
	puts("Yes");
	vector<int> dest;
	for(int i=1;i<=m;i++) if(!col[i]) dest.push_back(i);
#ifdef LOCAL
	for(int i=1;i<=m;i++){
		for(int v:g[i]) assert(i-!col[i]*m<v-!col[v]*m);
	}
#endif
	printf("%zu\n",dest.size());
	for(int x:dest) printf("%d ",x); puts("");
	return 0;
}

标签:fa,不降,题解,NOD2207C,solution,int,数组,include,deg
From: https://www.cnblogs.com/caijianhong/p/solution-NOD2207C.html

相关文章

  • 题解 NOD2207D【电报】
    前置知识:高斯消元已知\(n\)元线性一次方程组。关于\(x_1,x_2,\cdots,x_n\)。\[\begin{cases}a_{1,1}x_1+a_{1,2}x_2+\cdots+a_{1,n}x_n=b_1\\a_{2,1}x_1+a_{2,2}x_2+\cdots+a_{2,n}x_n=b_2\\\cdots\\a_{n,1}x_1+a_{n,2}x_2+\cdots......
  • [SHOI2011]双倍回文 题解
    [SHOI2011]双倍回文题解看了一些写回文自动机的大佬的代码,我深感敬畏,于是我转身向Manacher走去现在荣登最优解第一页……说实话,这个方法的复杂度是很玄学的,但是加了一些优化之后,就几乎不可能被卡到\(O(n^2)\)了。具体思路如下:预处理字符串部分就略过吧我们预先跑一......
  • P7959 [COCI2014-2015#6] WTF 题解
    P7959[COCI2014-2015#6]WTF题解呃,是一道DP题说实话,原题实际上是不要输出一种方法的……但是似乎放这道题的人想增加一点难度?这里有两种做法,但都是DP。预备观察我们首先观察一些性质,以方便解题。循环不变:我们可以观察到,在\(n\)次变换后,序列会还原。也就是说,两个......
  • 题解 BZOJ4399 魔法少女LJJ
    前言XXX:你瞅你长得那个B样,俺老孙就(氧化钙)......这魔法(J8)少女能不能去死啊啊啊啊啊啊啊啊啊啊......正文"LJJ你是来搞笑的吧"你说得对,但是这数据就是骗人的.首先看题面:然后看样例:最后看数据范围:我惊奇的发现\(c\le7\)!家人们我真难绷qaq...问题分析显......
  • [AGC055B] ABC Supremacy 题解
    [AGC055B]ABCSupremacy题解题目描述给定两个长度为 \(n\) 的字符串 \(a\),\(b\)。你可以进行若干次以下操作:若 \(a\) 中的一个子串为 ABC,BCA 或 CAB,那么可以将这个子串替换为 ABC,BCA 或 CAB。求能否将 \(a\) 变成 \(b\),输出 YES 或 NO。解析不难发现,......
  • chrome 跨域问题解决
    1.后端设置了跨域,https下可以,http不可以高版本chrome配置了策略,如果访问私有网络,会出现禁止跨域chrome://flags/#block-insecure-private-network-requestsBlockinsecureprivatenetworkrequests.......
  • JAVA面试题解惑系列(六)——字符串(String)杂谈
    关键字:java面试题字符串string作者:臧圩人(zangweiren)网址:http://zangweiren.javaeye.com上一次我们已经一起回顾了面试题中常考的到底创建了几个String对象的相关知识,这一次我们以几个常见面试题为引子,来回顾一下String对象相关的其它一些方面。String的l......
  • quickfix协议当有中文时校验位错误问题解决
    quickfix校验位计算都是根据ISO-8859-1编码计算,知道这个规则后续我们处理中文就很好处理了。但是如果用ISO-8859-1编码有中文会出现乱码,如果将CharsetSupport.setCharset设置为UTF-8或者GBK时,在发送数据时会报java.nio.bufferoverflowexception:null,或者校验位失败。1、往step网......
  • JSOI2018 部分题解
    目录潜入行动防御网络列队潜入行动一眼直接DP。设\(f_{i,j,0/1,0/1}\)表示\(i\)子树内放了\(j\)个监听设备,\(i\)是否被子结点覆盖,\(i\)是否放了监听设备,\(i\)子树内除了\(i\)都被覆盖的方案数。转移是一个树形背包,时间复杂度\(\mathcal{O}(nk)\),只是常数有点大。......
  • Competitive Programmer 题解
    题目传送门一道模拟题。纯模拟肯定不行,考虑优化。\(60=2^2\times3\times5\),也就是说我们判断组合后的数字能否被\(2\),\(3\),\(10\)整除即可。如果这个数能被\(2\)整除,那么原数一定会存在偶数;如果这个数能被\(3\)整除,那么它的数字和应该也能被\(3\)整除;如果这个数......