首页 / 更多教程 / A. Suborrays(鸽巢原理)

A. Suborrays(鸽巢原理)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了A. Suborrays(鸽巢原理)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含735字，纯文字阅读大概需要2分钟。

内容图文

题意:给定一个序列，包含n个元素，每个元素都是[1, n]中唯一的元素。求是否存在一个序列满足，对于任意的(1 <= i <= j <= n)，[i, j]中的每个数异或起来大于j - i + 1，即这个区间的长度。

分析:一个事实:\(p_{i}orp_{i+1}orp_{i+2}\dots>=max(p_{i},p_{i+1},\dots)\)。那么我们只要证明对于任意长度len的子序列，存在一个元素>=len即可，根据鸽巢原理，如果存在一个长度为len的区间，里面的元素为[1, len - 1]，那么就会违反这是个序列每个数都只存在一次的性质，因此，对于任意一个长度为len的子序列，都会存在一个大于等于len的元素。所以，只要输出任意一个序列即可。

        #include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int t;
	cin >> t;

	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; ++i)
			cout << i << " ";

		cout << endl;
	}


	return 0;
}

原文：https://www.cnblogs.com/pixel-Teee/p/13467703.html

内容总结

以上是互联网集市为您收集整理的A. Suborrays(鸽巢原理)全部内容，希望文章能够帮你解决A. Suborrays(鸽巢原理)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1254230.html

来源：【匿名】