「Codeforces」寒假训练 2023 #4

A. Coprime

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n, ans;
map<int, int> mp;
int gcd(int u, int v)
{
	return v == 0 ? u : gcd(v, u % v);
}
int main()
{
	cin >> t;
	while(t--)
	{
		ans = 0;
		mp.clear();
		cin >> n;
		for(int i = 1; i <= n; i++) 
		{
			int x;
			scanf("%d", &x);
			mp[x] = i;
		}
		for(int i = 1; i <= 1000; i++)
		{
			for(int j = 1; j <= 1000; j++)
			{
				int _gcd = gcd(i, j);
				if(_gcd == 1 && mp.count(i) && mp.count(j)) ans = max(ans, mp[i] + mp[j]);
			}
		}
		if(ans == 0) ans = -1;
		cout << ans << endl;
	}
	return 0;
}

B. Run For Your Prize

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6;
int n, ans;
int main()
{
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		ans = max(ans, min(x - 1, N - x));
	}
	cout << ans << endl;
	return 0;
}

C. Vasya and Robot

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, l, r, ql, qr, ans = 2e9;
int w[N], s[N];
int main()
{
	cin >> n >> l >> r >> ql >> qr;
	for(int i = 1; i <= n; i++)
	{
		scanf("%d", w + i);
		s[i] = s[i - 1] + w[i];
	}
	for(int i = 1; i <= n + 1; i++)
	{
		int res = 0;
		int minus = (n - i + 1) - (i - 1);
		if(minus > 0) res += (abs(minus) - 1) * qr;	
		else if(minus < 0) res += (abs(minus) - 1) * ql;
		res += (s[i - 1] - s[0]) * l + (s[n] - s[i - 1]) * r;
		ans = min(ans, res);
	}
	cout << ans << endl;
	return 0;
}

D. Alternating Subsequence

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
int t, n;
int main()
{
	cin >> t;
	while(t--)
	{
		scanf("%d", &n);
		ll sum = 0;
		ll pos = -2e9, neg = -2e9;
		int sign = 0;
		for(int i = 0; i < n; i++)
		{
			ll x;
			scanf("%lld", &x);
			if(x > 0)
			{
				if(sign == -1)
				{
					pos = -2e9;
					sum += neg;
				}
				sign = 1;
				pos = max(pos, x);
			}
			else if(x < 0)
			{
				if(sign == 1)
				{
					neg = -2e9;
					sum += pos;
				}
				sign = -1;
				neg = max(neg, x);
			}
		}
		if(sign == 1) sum += pos;
		else if(sign == -1) sum += neg;
		printf("%lld\n", sum);
	}
	return 0;
}

E. Move and Turn

原题链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, p;
int main()
{
	cin >> n;
	p = n / 2;
	if(n % 2) cout << 2 * (p + 1) * (p + 2) << endl;
	else cout << (p + 1) * (p + 1) << endl;
	return 0;
}