codeforces 7.22 E Permutation Shift

codeforces 7.22 E Permutation Shift

给出一个1到n的排列,每次可以交换两个数,问在交换最多m次(m <= n/3)之后能不能得到由1 2 3 … n循环右移所得到的的排列,输出所有能得到的排列和循环右移的次数。
数据范围:n <= 3e5

有点脑洞的一道题。

由于最多交换m次,那么最多会有2m个数交换位置,而剩下的n - 2m个数是在原位置不变的。也即是,在循环右移k位之后,有至少n - 2m个数是与给出的排列对应位置的数相同的。

而在循环右移的过程中,对于每一位的数,只存在一个k使得让这一位的数与给出的排列在同一位置是一样的。这就代表着,在循环右移n-1次之后,每一次两个排列相同的位数之和加起来是n。而要满足条件的话,在循环右移k次之后,至少有n - 2m个数是相同的,n - 2m >= n / 3。也就是说最多存在三个k满足条件。所以我们计数统计k,最多三次 O ( n ) O(n) O(n)计算最少交换次数。总复杂度为 O ( n ) O(n) O(n).

const int N = 3e5 + 10;
int a[N], cnt[N], pos[N], b[N];
bool vis[N];

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);

	int T = 1;
	T = read();
	while (T --)
	{
		int n = read(), m = read();

		for (int i = 0; i < n; i ++)
			cnt[i] = 0;
		for (int i = 0; i < n; i ++)
		{
			a[i] = read();
			-- a[i];
			pos[a[i]] = i;
			int k = (i - a[i] + n) % n;
			cnt[k] ++; 
		}

		queue <int> q;
		for (int i = 0; i < n; i ++)
		{
			if (cnt[i] < n - 2 * m) continue;
			for (int j = 0; j < n; j ++)
			{
				vis[j] = 0;
				b[(j + i) % n] = j;
			}

			int tot = 0;
			for (int j = 0; j < n; j ++)
			{
				if (!vis[j])
				{
					++ tot;
					vis[j] = 1;
					int p = j;
					while (!vis[pos[b[p]]])
					{
						vis[pos[b[p]]] = 1;
						p = pos[b[p]];
					}
				}
			}

			tot = n - tot;
			if (tot <= m)
				q.push(i);
		}
		cout << q.size();
		while (!q.empty())
		{
			int now = q.front(); q.pop();
			cout << " " << now;
		}
		cout << endl;
	}
	return 0;
}
上一篇:模拟简单 LeetCode1486. 数组异或操作


下一篇:2021牛客暑期多校训练营2 K. Stack(拓扑排序)