Educational Codeforces Round 102 (Rated for Div. 2)

比赛地址

A（水题）

题目：

给出一个数组\(a\)并能进行一个操作使得数组元素更改为数组任意其他两元素之和，问是否可以让数组元素全部小于等于\(d\)

解析：

排序后判断最大值是否小于等于\(d\)或者最小的两个值是否小于等于\(d\)即可

#include<bits/stdc++.h>

using namespace std;

const int maxn = 105;

int n, dat[maxn];

int main() {

	int T;

	scanf("%d", &T);

	while (T--) {

		int n, d;

		dat[1] = 0;

		scanf("%d%d", &n, &d);

		for (int i = 0; i < n; ++i)

			scanf("%d", &dat[i]);

		sort(dat, dat + n);

		printf("%s\n", dat[n - 1] <= d || dat[0] + dat[1] <= d ? "YES" : "NO");

	}

}

B（思维）

题目链接

题目：

给出两个字符串，定义\(LCM(S_1,S_2)\)是由这两个串作为循环节的最小长度串，问\(LCM(S_1,S_2)\)是什么，如果不存在则输出\(-1\)

解析：

如果\(LCM\)存在，则它的长度一定是\(LCM(len_1,len_2)\)，那么已知最终串的长度，就可以算出每个循环节的循环次数，判断循环倍增后的串是否相同即可

#include<bits/stdc++.h>

using namespace std;

string str[2];

string repeat(const string& a, int x) {

	string t;

	while (x--)

		t += a;

	return t;

}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	int T;

	cin >> T;

	while (T--) {

		cin >> str[0] >> str[1];

		int d = gcd(str[0].length(), str[1].length());

		string t[2] = { repeat(str[0],str[1].length() / d),repeat(str[1],str[0].length() / d) };

		cout << (t[0] == t[1] ? t[0] : "-1") << endl;

	}

}

C（找规律）

题目链接

题目：

给出\(n\)与\(k\)，以及对应的数组\(a=1,2,\dots,k-1,k,k-1,k-2,\dots,k-(n-k)\)，现在假定有一个长度为\(k\)的排列\(p\)，依照他构造出数组\(b\)，使得\(b[i]=p[a[i]]\)，问使得\(b\)中逆序对数不超过\(a\)的话，p中满足要求的且为最大字典序的排列是什么

解析：

这样的变换可以理解为\(a\)为索引下表，\(b\)为对应值

o(￣▽￣)ブ找规律可以发现，将原本\(k,k-1,k-2,\dots,k-(n-k)\)进行倒序排列，逆序对数不会改变，且可以让字典序增加，但除此之外的序列仍然需要服从正序排列\(1\dots n-(n-k+1)\)

#include<bits/stdc++.h>

using namespace std;

int n, k;

int main() {

	int T;

	scanf("%d", &T);

	while (T--) {

		scanf("%d%d", &n, &k);

		int a = n - k;

		int b = k - a;

		for (int i = 1; i < b; ++i)

			printf("%d ", i);

		for (int j = 0; j <= a; ++j)

			printf("%d ", k - j);

		printf("\n");

	}

}

D（思维）

题目链接

题目：

解析：

E（）

题目链接

题目：

解析：

巴特西

Educational Codeforces Round 102 (Rated for Div. 2)

A（水题）

B（思维）

C（找规律）

D（思维）

E（）

最新文章

热门文章