首页 > 其他分享 >CodeForces 1500C Matrix Sorting

CodeForces 1500C Matrix Sorting

时间:2024-01-15 21:36:40浏览次数:41  
标签:typedef Sorting 1500C int CodeForces long vc maxn ans

洛谷传送门

CF 传送门

做了好久。怎么会是呢。

题目的操作可以看成,求出一些关键字,使得 \(B\) 矩阵的行是由 \(A\) 按照这些第 \(1\) 关键字、第 \(2\) 关键字一直到第 \(k\) 关键字,最后还有一个原来所在行下标的关键字,从小到大排序。

肯定是从排好序的 \(B\) 矩阵入手。首先任意找到一个在 \(B\) 矩阵中已经排好序的列。然后把这一列极长的相等段拎出来,把 \([1, n]\) 分成了若干个区间 \([l_1, r_1], [l_2, r_2], \ldots, [l_k, r_k]\)。发现这是一个递归的过程,我们还要找到一个之前没选过的列,在这些区间分别是升序的。然后可以把这些区间分成一些更小的区间。可以把区间存下来,一轮一轮地判断。

终止条件就是,\([l_1, r_1] \sim [l_k, r_k]\) 都是 \(A\) 矩阵的子序列(因为最后一个排序的关键字是行的下标)。这个可以对每行哈希,然后建子序列自动机判断即可。

但是兴冲冲的写了一发,T 了。发现枚举每一列再判断在这些区间是否分别升序会使得复杂度退化至 \(O(n^3)\)。想起来有个东西叫 bitset。可以把第 \(i\) 行 \(B_{i, j} < B_{i + 1, j}\) 的所有列下标 \(j\) 开个 bitset 存起来,那么得到所有升序的行,只需把 \([l_1, r_1 - 1] \sim [l_k, r_k - 1]\) 的 bitset 与起来就行了。时间复杂度变为 \(O(\frac{n^3}{\omega})\)。

子序列自动机部分若开 vector 存位置然后每次二分就是 \(O(n^2 \log n)\)。但是也能过。跑得还不慢。

code
// Problem: C. Matrix Sorting
// Contest: Codeforces - Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)
// URL: https://codeforces.com/problemset/problem/1500/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#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<ll, ll> pii;

const int maxn = 1510;
const ll base = 131, mod1 = 998244853, mod2 = 1145141999;

int n, m, a[maxn][maxn], b[maxn][maxn], tot, c[maxn];
ll f1[maxn], g1[maxn], f2[maxn], g2[maxn];
bitset<maxn> f[maxn], g;
pii lsh[maxn];
vector<int> vc[maxn];
bool vis[maxn];

inline bool check(int l, int r) {
	int i = 1;
	for (int j = l; j <= r; ++j) {
		auto it = lower_bound(vc[c[j]].begin(), vc[c[j]].end(), i);
		if (it == vc[c[j]].end()) {
			return 0;
		}
		i = *it + 1;
	}
	return 1;
}

void solve() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &a[i][j]);
			f1[i] = (f1[i] * base + a[i][j]) % mod1;
			f2[i] = (f2[i] * base + a[i][j]) % mod2;
		}
		lsh[++tot] = mkp(f1[i], f2[i]);
	}
	sort(lsh + 1, lsh + tot + 1);
	tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	for (int i = 1; i <= n; ++i) {
		vc[lower_bound(lsh + 1, lsh + tot + 1, mkp(f1[i], f2[i])) - lsh].pb(i);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			scanf("%d", &b[i][j]);
			g1[i] = (g1[i] * base + b[i][j]) % mod1;
			g2[i] = (g2[i] * base + b[i][j]) % mod2;
		}
		c[i] = lower_bound(lsh + 1, lsh + tot + 1, mkp(g1[i], g2[i])) - lsh;
		if (lsh[c[i]] != mkp(g1[i], g2[i])) {
			puts("-1");
			return;
		}
	}
	for (int i = 1; i < n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (b[i][j] <= b[i + 1][j]) {
				f[i].set(j);
			}
		}
	}
	vector<int> ans;
	vector<pii> vc;
	vc.pb(1, n);
	while (1) {
		bool fl = 1;
		for (pii p : vc) {
			if (!check(p.fst, p.scd)) {
				fl = 0;
				break;
			}
		}
		if (fl) {
			printf("%d\n", (int)ans.size());
			reverse(ans.begin(), ans.end());
			for (int i : ans) {
				printf("%d ", i);
			}
			return;
		}
		bool t = 0;
		g.set();
		for (pii p : vc) {
			for (int j = p.fst; j < p.scd; ++j) {
				g &= f[j];
			}
		}
		for (int i = 1; i <= m; ++i) {
			if (vis[i] || !g.test(i)) {
				continue;
			}
			ans.pb(i);
			t = 1;
			vis[i] = 1;
			vector<pii> nv;
			for (pii p : vc) {
				int l = p.fst, r = p.scd;
				for (int j = l, k = l; j <= r; j = (++k)) {
					while (k < r && b[k + 1][i] == b[j][i]) {
						++k;
					}
					nv.pb(j, k);
				}
			}
			vc = nv;
			break;
		}
		if (!t) {
			puts("-1");
			return;
		}
	}
}

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

标签:typedef,Sorting,1500C,int,CodeForces,long,vc,maxn,ans
From: https://www.cnblogs.com/zltzlt-blog/p/17966381

相关文章

  • CodeForces 1266F Almost Same Distance
    洛谷传送门CF传送门好厉害。特判\(k=1\)。首先经过观察,我们可以按照\(k\)的奇偶性讨论:\(k\)为偶数,有一个中心点挂了若干条长度为\(\frac{k}{2}\)的链。\(k\)为偶数,有两个中心点,两边挂了若干条长度为\(\frac{k}{2}\)的链;\(k\)为奇数,有一个中心点挂了若干条长度......
  • hey_left 2 Codeforces Round 918 (Div. 4) 续
    题目链接F.常规的树状数组求逆序对需要注意的是,因为是下标与值的映射,所以数值不能为负数,也不能太大然后传参数的时候,参数是最大数值切记切记#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+10;template<typenameT>structTreeArray{vector<T>t......
  • Codeforces Round 919 (Div. 2)(A~D) 题解
    CodeforcesRound919(Div.2)(A~D)题解A.SatisfyingConstraints题意:给你一些条件让你求出满足条件的整数有多少个。模拟即可。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constllMAXN=2e5+5;llTex=1,n;voidAC(){ cin>>n; lll=......
  • Codeforces Round 919 (Div. 2)
    CodeforcesRound919(Div.2)A-SatisfyingConstraints#include<bits/stdc++.h>#defineendl'\n'#defineintlonglongusingnamespacestd;constintN=1e6+10;voidsolve(){ intn; intl=-1; intr=1e9+10; cin>>......
  • CodeForces 1920F2 Smooth Sailing (Hard Version)
    洛谷传送门CF传送门首先需要知道的一个trick:判断一个点是否在一个闭合回路内部,从这个点向任意方向引一条射线,若不考虑相切,那么和回路的交点为奇数时这个点在回路内部,否则在外部。那么这题要判断一个回路是否包含全部的island,可以找到任意一个island向右引一条射线。给每......
  • Hey left 1 Codeforces Round 918 (Div. 4)
    题目链接A.3个数,其中2个数相同,输出不相同的那个可以用ifelse判断,较为麻烦用的map,输出出现一次的#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;voidsolve(){map<int,int>mp;for(inti=0,x;i<3;i++){cin>>x;mp[x]++;......
  • CodeForces 1237H Balanced Reversals
    洛谷传送门CF传送门容易想到把\(s,t\)分成长度为\(2\)的段考虑。容易发现\(00,11\)的个数在操作过程中不会改变,所以若两串的\(00\)或\(11\)个数不相等则无解。考虑依次对\(i=2,4,\ldots,n\)构造\(s[1:i]=t[n-i+1:n]\)。对于\(s_{j-1}s_j=y......
  • Codeforces [Hello 2024]
    CodeforcesHello2024主打一个昏了头A.WalletExchange#include<bits/stdc++.h>#defineendl'\n'//#defineintlonglongusingnamespacestd;constintN=2e5+10;inta,b;voidsolve(){ cin>>a>>b; if((a+b)&1)cout<<......
  • CodeForces 1379E Inverse Genealogy
    洛谷传送门CF传送门\(n\)为偶数显然无解。否则我们可以构造一棵\(n\)个点的完全二叉树,当\(n+1\)是\(2\)的幂时满足\(m=1\),否则\(m=0\)。当\(n\ge5\)时可以递归至\((n-2,m-1)\),再挂一个叶子即可。但是可能会出现\(n+1\)不是\(2\)的幂,但\(n-......
  • codeforces比赛(3):codeforces good_bye_2023
    A、2023跳转原题点击此:A题地址1、题目大意  在一个乘积可能等于2023的数组a中去掉了k个数,得到新的长度为n的b数列。请你输出k个数,使得这k个数与b数列相乘为2023.如果不存在则输出No。2、题目解析  因为这道题的n和k都是不超过5,所以我们只需要算出b数组的乘积是否是2023的......