Educational Codeforces Round 112 (Rated for Div. 2) 个人题解

2024-03-23 08:44:16

A. PizzaForces

题意

有三种披萨制作方案：15分钟制作6片、20分钟制作8片和25分钟制作10片。

问制作出至少 n n n片披萨要多少分钟

分析

三种方案的效率都一样，都是每分钟制作0.4个披萨，也就是一片披萨要做2.5分钟，所以让溢出的时间尽可能少就可以了。

由于我们有 6 , 8 , 10 6,8,10 6,8,10这三个数，我们可以通过不同的方案凑出 12 , 14 , 16 , . . . 12,14,16,... 12,14,16,...，所有大于等于6的偶数。

所以如果小于6，输出15，否则如果是偶数就输出 2.5 n 2.5n 2.5n，是奇数输出 2.5 ( n + 1 ) 2.5(n+1) 2.5(n+1).

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
	// DDLC_ESCAPE_PLAN_FAILED;
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		scanf("%lld", &n);
		if(n <= 6) printf("15\n");
		else if(n & 1){
			printf("%lld\n", (int)((n + 1) * 2.5));
		}
		else printf("%lld\n",(int)( n * 2.5));
	}
	return 0;
}

B. Two Tables

题意

一个大矩形区域内有一张桌子，你要平移这张桌子（任意方向），使得能放下另一个 w × h w×h w×h的桌子。求最小移动距离

分析

看这张桌子的正上方。正上方的区域，长度肯定是满足，可以放下的。所以我们只需要将其垂直向下平移就可以得到一种方案。那么，对于其他3个方向也一样。所以沿着坐标轴平移肯定优于斜着来，因为长和宽里面总是有一个是不需要额外移动来满足的，而斜平移相对于垂直平移在另外一个方向上做了无用的移动。

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;

signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	int t;
	cin >> t;
	while(t--)
	{
		int W, H;
		int x1, x2, y1, y2, w, h;
		cin >> W >> H;
		cin >> x1 >> y1 >> x2 >> y2;
		cin >> w >> h;
		int ans = inf;
		int r = abs(w - x1);
		if(x1 >= w) r = 0;
		if(x2 + r <= W) ans = min(ans, r);
		int l = abs(x2 - W + w);
		if(x2 <= W - w) l = 0;
		if(x1 - l >= 0) ans = min(ans, l);
		int u = abs(y2 - H + h);
		if(y2 <= H - h) u = 0;
		if(y1 - u >= 0) ans = min(ans, u);
		int d = abs(y1 - h);
		if(y1 >= h) d = 0;
		if(y2 + d <= H) ans = min(ans, d);
		cout << (ans == inf ? -1 : ans) << endl;
	}
	return 0;
}

C. Coin Rows

题意

有一个两行 m m m列的矩阵，每个格子上有金币。 A l i c e Alice Alice和 B o b Bob Bob可以在矩阵中向下或者向右移动，但不能向其他方向移动。

A l i c e Alice Alice从 ( 1 , 1 ) (1,1) (1,1)出发，走到 ( 2 , m ) (2,m) (2,m)，并取走所有停留过的格子里的金币。

B o b Bob Bob同样从 ( 1 , 1 ) (1,1) (1,1)出发，走到 ( 2 , m ) (2,m) (2,m)，并取走所有停留过的格子里的金币（ A l i c e Alice Alice已经取走的 B o b Bob Bob取不到了）

A l i c e Alice Alice要让 B o b Bob Bob得到的金币尽可能少， B o b Bob Bob会让自己得的尽可能多。

问最终 B o b Bob Bob会得到多少金币？

分析

由于 A l i c e Alice Alice要走到 ( 2 , m ) (2,m) (2,m)，有且仅有一次向下移动。观察 m m m在 1 e 5 1e5 1e5的规模，枚举她向下移动发生的位置。然后，她拿走金币后，留下的金币只会分布在右上和左下两个地方，且 B o b Bob Bob只能选择其中一个地方的金币全部拿走，而不能同时拿2个地方的金币。所以对2个地方剩余的金币取 m a x max max就是答案。剩余金币的数量可以用前缀和处理。

时间复杂度 O ( m ) O(m) O(m).

代码

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
#define int long long
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 1e5 + 10;
int a[3][maxn];
int pre[maxn], lst[maxn]; // 第一行从前往后的和，第二行从后往前的和
int sum1, sum2;
signed main()
{
	DDLC_ESCAPE_PLAN_FAILED;
	int t;
	cin >> t;
	while(t--)
	{
		sum1 = sum2 = 0;

		int m;
		cin >> m;
		fors(i, 1, 2){
			fors(j, 1, m){
				cin >> a[i][j];
				if(i == 1) sum1 += a[i][j];
				else sum2 += a[i][j];
			}
		}
		pre[0] = lst[m + 1] = 0;
		fors(i, 1, m) pre[i] = pre[i - 1] + a[1][i];
		for(int i = m; i; --i) lst[i] = lst[i + 1] + a[2][i];
		int ans = inf;
		fors(i, 1, m){
			ans = min(ans, max(sum2 - lst[i], sum1 - pre[i]));
		}
		cout << ans << endl;
	}
	return 0;
}

D. Say No to Palindromes

题意

定义一个字符串是 b e a u t i f u l beautiful beautiful的，当且仅当：任选一个长度大于1的子串，其不是回文串。

现在给出一个只含有字母a,b,c的字符串 s s s，然后给出 m m m个询问，对每个询问，你需要回答下标 l l l到 r r r的子串如果要称为 b e a u t i f u l beautiful beautiful串，至少需要修改几次（只能用a,b,c修改）。

分析

考虑下面的情况：
对字符串 b a a baa baa：

b b b替换 a a a， b b a bba bba, b a b bab bab都含有回文子串，都不行
c c c替换 a a a, b a c , b c a bac,bca bac,bca都符合要求.
其他情况很显然不行

进一步总结规律，我们发现，一个字符串如果要变成非回文，其只能是形如 a b c a b c a b c a b c . . . abcabcabcabc... abcabcabcabc...或者 b c a b c a b c a . . . bcabcabca... bcabcabca...，其他的情况都会发生两个字符相邻一样，或者隔一个一样，因此都是会导致回文子串产生的。

因此我们只需要看当前子串转变为以上两种串任意一种的子串就可以了，然后取 m i n min min。

这样暴力的复杂度就是 O ( n 2 ) O(n^2) O(n2)了，但还不够，需要继续优化。

优化很简单，任意区间修改成对应串的最小次数显然可以用前缀和维护，复杂度降到 O ( n + m ) O(n+m) O(n+m).

当然你也可以用莫队分块 O ( m n ) O(m\sqrt n) O(mn )或者线段树 O ( m l o g n ) O(mlogn) O(mlogn)，但显然做复杂了（我属于是最近学了莫队就想用莫队，就当是练习了，差点超时，被很多Hacker盯上了QAQ，幸好没人叉掉）

代码（莫队）

#include <bits/stdc++.h>
#define fors(i, a, b) for(int i = (a); i <= (b); ++i)
#define lson k<<1
#define rson k<<1|1
#define pb push_back
#define lowbit(x) ((x)&(-(x)))
#define mem(a) memset(a, 0, sizeof(a))
#define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0)
const int inf = 0x3f3f3f3f;
const double dinf = 1e100;
typedef long long ll;
//const ll linf = 9223372036854775807LL;
// const ll linf = 1e18;
using namespace std;
const int maxn = 2e5 + 5;
string abc;
string bca;
string cab;
string cba;
string acb;
string bac;
struct query{
	int l, r;
	int ans, idx, blc;
}q[maxn];
string s;
bool cmp1(const query& x, const query& y){
	if(x.blc != y.blc) return x.blc < y.blc;
	return x.r < y.r;
}
bool rearr(const query& x, const query& y){
	return x.idx < y.idx;
}
signed main()
{
	for(int i = 0; i < maxn; ++i){
		abc += i % 3 + 'a';
		bca += (i + 1) % 3 + 'a';
		cab += (i + 2) % 3 + 'a';
		if(i % 3 == 0){
			acb += 'a';
			cba += 'c';
			bac += 'b';
		}
		else if(i % 3 == 1){
			acb += 'c';
			cba += 'b';
			bac += 'a';
		}
		else {
			acb += 'b';
			cba += 'a';
			bac += 'c';
		}
	}
	DDLC_ESCAPE_PLAN_FAILED;
	int t;
	t = 1;
	while(t--)
	{
		int n, m;
		cin >> n >> m;
		cin >> s;
		fors(i, 1, m){
			cin >> q[i].l >> q[i].r;
			q[i].l--, q[i].r--;
			q[i].idx = i;
			q[i].blc = (q[i].l - 1) / (int)sqrt(n) + 1;
		}
		sort(q + 1, q + 1 + m, cmp1);
		int l = 0, r = -1;
		int ans1 = 0, ans2 = 0, ans3 = 0, ans4 = 0, ans5 = 0, ans6 = 0;
		fors(i, 1, m){
			while(l > q[i].l){
				l--;
				if(s[l] != abc[l]) ans1++;
				if(s[l] != bca[l]) ans2++;
				if(s[l] != cab[l]) ans3++;
				if(s[l] != acb[l]) ans4++;
				if(s[l] != cba[l]) ans5++;
				if(s[l] != bac[l]) ans6++;
			}
			while(r < q[i].r){
				r++;
				if(s[r] != abc[r]) ans1++;
				if(s[r] != bca[r]) ans2++;
				if(s[r] != cab[r]) ans3++;
				if(s[r] != acb[r]) ans4++;
				if(s[r] != cba[r]) ans5++;
				if(s[r] != bac[r]) ans6++;
			}
			while(l < q[i].l){
				if(s[l] != abc[l]) ans1--;
				if(s[l] != bca[l]) ans2--;
				if(s[l] != cab[l]) ans3--;
				if(s[l] != acb[l]) ans4--;
				if(s[l] != cba[l]) ans5--;
				if(s[l] != bac[l]) ans6--;
				l++;
			}
			while(r > q[i].r){
				if(s[r] != abc[r]) ans1--;
				if(s[r] != bca[r]) ans2--;
				if(s[r] != cab[r]) ans3--;
				if(s[r] != acb[r]) ans4--;
				if(s[r] != cba[r]) ans5--;
				if(s[r] != bac[r]) ans6--;
				r--;
			}
			q[i].ans = min(min(ans1, min(ans2, ans3)), min(ans4, min(ans5, ans6)));
		}
		sort(q + 1, q + 1 + m, rearr);
		fors(i, 1, m) cout << q[i].ans << endl;
	}
	return 0;
}

代码（前缀和）

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int inf = 1e9 + 7;
int n, m;
int pre[6][maxn] = {0};
string s;
char check[6][4] = {"abc", "bca", "cab", "acb", "cba", "bac"};
int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	cin >> s;
	for(int i = 0; i < 6; ++i){
		if(s[0] != check[i][0]) pre[i][0] = 1;
		for(int j = 1; j < s.size(); ++j){
			if(s[j] != check[i][j % 3]) pre[i][j] = pre[i][j - 1] + 1;
			else pre[i][j] = pre[i][j - 1];
		}
	}
	for(int i = 0; i < m; ++i){
		int l, r; 
		cin >> l >> r;
		l--, r--;
		int ans = inf;
		for(int j = 0; j < 6; ++j){
			if(l != 0) ans = min(ans, pre[j][r] - pre[j][l - 1]);
			else ans = min(ans, pre[j][r]);
		}
		cout << ans << endl;
	}
	return 0;
}

显然前缀和好写多了，效率也快多了

码农公寓

A. PizzaForces

B. Two Tables

C. Coin Rows

D. Say No to Palindromes

相关文章