Educational Codeforces Round 155 (Rated for Div. 2)

Dashboard - Educational Codeforces Round 155 (Rated for Div. 2) - Codeforces

A. Rigged!

只要后面有选手大于或等于第一个选手的力量和耐力就会获胜或者平局，故这种情况判为-1，其余情况以第一位选手的力量为重量可以取到最优解

#include
using namespace std;
typedef long long ll;
void solve()
{
	ll n, x, y, s, e;
	ll flag = 0;
	cin >> n;
	cin >> x >> y;
	for(int i = 2; i <= n; i ++)
	{
		cin >> s >> e;
		if(s >= x && e >= y)flag = 1;
	}
	if(flag)cout << -1 << '\n';
	else cout << x << '\n';
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while(t --)
	{
		solve();	
	}
	return 0;
}

B. Chips on the Board

每行或每列都要选一个，对于每行选择每列代价最小的那个，对于每列列选择每行代价最小的那个，最终选取这两种方案的最小值即可

#include
using namespace std;
typedef long long ll;
const  int N = 3e5 + 10;
ll a[N], b[N];
void solve()
{
	ll n;
	cin >> n;
	ll s1 = 0, s2 = 0;
	for(int i = 1; i <= n; i ++)cin >> a[i];
	for(int i = 1; i <= n; i ++)cin >> b[i];
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + n);
	for(int i = 1; i <= n; i ++)
	{
		s1 += a[1] + b[i];
		s2 += b[1] + a[i];
	}
	cout << min(s1, s2) << '\n';
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t;
	cin >> t;
	while(t --)
	{
		solve();
	}
	return 0;
}

C. Make it Alternating

第一问：求删除数的个数，对于这题只需要减去重复的数即可，eg.1001111可以转化为1，2，4也就是相同的数就放在一起，然而对于每一个数不能有连续一样的，故每次删掉相同的数最后这几个数只剩下一个即可。

第二问：需要求两点：

1.重复元素有len个，我们需要删去len - 1个，故在这len个元素中挑出len - 1个元素即可，挑出这些数的方法有C（len,len-1）种

2.对于挑出的所有的数中又可以进行任意的组合，这些组合的方案数为挑出元素个数的阶乘

将1 * 2为所有的方案数

注意初始就使用init，算出阶乘

#include
using namespace std;
typedef long long ll;
const int M = 2e5 + 10, mod = 998244353, N = 2e5 + 10;;
ll p[N];
ll c(ll x, ll y)
{
	x *= y;
	return x % mod;
}
void init()
{
	p[0] = p[1] = 1;
	for(int i = 2; i < M; i ++)
	{
		p[i] = c(i, p[i - 1]);
	}
}
void solve()
{
	string s;
	ll num = 1, cur = 0, res = 1;
	cin >> s;
	ll n = s.size();
	for(int i = 0; i < n; i ++)
	{
		if(i && s[i] != s[i - 1])
		{
			num ++;
			res = c(res, cur);
			cur = 1;
		}	
		else cur ++;
	}	
	if(cur)res = c(res, cur);
	res = c(res, p[n - num]);
	cout << n - num << ' ' << res << '\n';
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	init();
	while(t --)
	{
		solve();
	}
	return 0;
}