Codeforces round (div.2)

Codeforces Round #613 (Div. 2)

[A.Mezo Playing Zoma]

[general idea]
Give a string consisting of L and R. l means shift left, R means shift right, initially at position 0. Each time you can choose to move or not to move, ask how many different positions you may have in the end

[solutions]
In extreme cases, if all l's are not executed and all R's are not executed, it will reach the rightmost and leftmost, so all positions in the middle are possible, so the answer is (numsof(L) + numsof(R) + 1)

[AC code]

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define Rep(i, n) for(register int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
inline int read()
{
	register int X = 0, w = 0; register char ch = 0;
	while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
	while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
	return w ? -X : X;
}
inline void write(register ll x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int main() {
	int l;
	l = read();
	string s;
	cin >> s;
	write(l + 1);
	return 0;
}

[B.Just Eat It!]

[general idea]
Give you n numbers, A will choose [l, R] ([l, R]! = [1, n]) numbers in the interval, B will choose [1, n], and ask whether no matter how A chooses your b numbers and is it strictly greater than A's selected numbers and

[solutions]
For B, sumB = a[1] + a[2] + + a[n]

For A, handle the maximum interval sum

Note that A cannot select [1, n]

[AC code]

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define Rep(i, n) for(register int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
inline int read()
{
	register int X = 0, w = 0; register char ch = 0;
	while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
	while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
	return w ? -X : X;
}
inline void write(register ll x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
int main() {
	int t;
	t = read();
	while (t--) {
		int n;
		n = read();
		ll sum = 0; //sumB
		ll ans = 0; //sumA
		ll temp = 0; //Record interval and
		int l = 1;
		int ansl = 1, ansr = 1; //Record the selection interval of A
		for (int i = 1; i <= n; ++i) {
			int x;
			x = read();
			sum += x;
			temp += x;
			if (temp <= 0) { //Once temp < = 0, we directly set the left end of the interval to i+1
				temp = 0;
				l = i + 1;
				continue;
			}
			if (ans < temp) { //To update
				ans = temp;
				ansl = l;
				ansr = i;
			}
		}
		if (sum > ans) puts("yes");
		else if (sum < ans) puts("no");
		else {
			if (ansl == 1 && ansr == n) {
				puts("yes");
			}
			else puts("no");
		}
	}
	return 0;
}

[C.Fadi and LCM]

[general idea]
Given an x, find a, b to make
1.max(a, b) min
2.lcm(a, b) = x

[solutions]
For condition one, to minimize a and b, it is obvious to make a and b as close as possible. Then consider taking the root sign of x, traversing from the back to the front, and finding a number divided by x

Then consider condition 2, lcm(a, b) = x, that is, a * b / gcd(a, b) = x. to make a, B as small as possible, then gcd(a, b) is obviously equal to 1, otherwise smaller a or B must be found to satisfy the condition
For example: 24 = lcm(6, 8) = lcm(3, 8)

[AC code]

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define Rep(i, n) for(register int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
inline int read()
{
	register int X = 0, w = 0; register char ch = 0;
	while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
	while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
	return w ? -X : X;
}
inline void write(register ll x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
inline ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	ll x;
	scanf("%lld", &x);
	if (x == 1) {
		printf("1 1\n");
		return 0;
	}
	ll k = sqrt(x);
	if (k * k == x) --k;
	for (ll i = k; i >= 1; --i) {
		if (x % i == 0) {
			if (gcd(x / i, i) == 1) {
				printf("%lld %lld\n", i, x / i);
				return 0;
			}
		}
	}
	return 0;
}

[D.Dr. Evil Underscores]

[general idea]
Given n numbers, find the minimum number x to minimize the exclusive or value of N numbers

[solutions]
Consider posi with binary answers. If ai has only 1 or 0 in posi, then ans posi = 0 or 1

If AI posi has both 1 and 0, recursively find the minimum value of 1 or 0

Reference: https://www.cnblogs.com/cadcadcadcadcad/p/12179509.html

[AC code]

#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define Rep(i, n) for(register int i = 1; i <= (n); ++i)
using namespace std;
typedef long long ll;
inline int read()
{
	register int X = 0, w = 0; register char ch = 0;
	while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
	while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
	return w ? -X : X;
}
inline void write(register ll x)
{
	if (x < 0) putchar('-'), x = -x;
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
vector<ll> a;
inline ll dfs(register int pos, register vector<ll>& v) {
	if (pos < 0) return 0;
	register vector<ll> v0, v1;
	for (auto& it : v) {
		if ((it >> pos) & 1) v1.push_back(it);
		else v0.push_back(it);
	}
	if (v0.size() == 0) return dfs(pos - 1, v1); //Only 1
	if (v1.size() == 0) return dfs(pos - 1, v0); //Only 0
	ll a = dfs(pos - 1, v0);
	ll b = dfs(pos - 1, v1);
	return min(a, b) +(1 << pos); //Otherwise, find the minimum value of 1 or 0
}
int main() {
	register int n;
	n = read();
	Rep(i, n) {
		register ll x;
		scanf("%lld", &x);
		a.push_back(x);
	}
	write(dfs(30, a));
	return 0;
}
Published 8 original articles, praised 0, visited 65
Private letter follow

Posted on Sat, 11 Jan 2020 05:42:28 -0800 by xterra