526互联

Educational Codeforces Round 151 [div.2 #A-C] 赛后总结（contest/1845）

发布时间 2023-07-01 15:26:37作者: Zwjoey

\(\textcolor{52C41A}{A}-\textcolor{FADB14}{B}-\textcolor{FADB14}{C}-\textcolor{E74C3C}{D}-\textcolor{E74C3C}{E}-\color{E74C3C}{F}\)

A

给你一个数 n ，在给你一个数列 1~k，其中 x 不能用，然后用其他的数任意累加，如能得到 n ，输出所用数字数量和具体数列。

一眼分类。先分是否有 1，有 1 就皆大欢喜；

没 1，那就是可以用 2~k，此时就只要分两种情况：1. k=2，2. k>2 ;

为什么这样分？因为当 k>2 时，就可以用 2,3 组合成所有的数啦。 done.

#A code 
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int t, n, k, x; 
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 
	cin >> t;
	while (t --)
	{
		cin >> n >> k >> x;
		if (k == 1 && x == 1) { cout << "NO" << endl; continue; }
		
		if (x != 1) //1
		{
			cout << "YES" << endl << n << endl;
			for (int i = 1; i <= n; i ++) cout << 1 << ' ';
			cout << endl;
		}
		else 
		{
			if (k == 2) //2
			{
				if (n % 2 != 0) cout << "NO" <<endl;
				else
				{
					cout << "YES" << endl << n/2 << endl;
					for (int i = 1; i <= n/2; i ++) cout << 2 << ' ';
					cout << endl;
				}
			}
			else //2 or 3
			{
				cout << "YES" << endl;
				if (n % 2 == 0)
				{
					cout << n/2 <<endl;
					for (int i = 1; i <= n/2; i ++) cout << 2 << ' ';
				}
				else
				{
					n -= 3;
					cout << n/2+1 << endl;
					for (int i = 1; i <= n/2; i ++) cout << 2 << ' ';
					cout << 3 << endl;
				}
			}
		}
	}
 
	return 0;
}
B

在 Oxy 的 Ⅰ 象限，给出三个不同的点 A，B，C，规定 A 为起点，其余为两个终点，求分别从起点到终点的两条最短路径的最大重合长度。

一开始受上题影响，且一眼没思路，我就又开始分类讨论，分出了四五种情况，越分越复杂......

然后我Q了一下 syz 大佬，发现自己还是一比赛就降智 qwq

两点最短距离就是 xa-xb，xa-xc（y同理，这个就叫做『曼哈顿距离』），

接下来就是分类讨论

image

然后考虑 A 在 B，C任意位置（xb≠xc，yb≠yc）下不同位置的性质

image

可以发现，+1 是所有答案的共有性质，即肯定重合在 A 点，

那么就是判断 x，y 分别是否异号即可（用相乘判断，注意开 long long ，一直被劝告，永远在忘记） done.

#B code 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
struct node
{
	ll x, y;
}a, b, c;

ll count(ll & beg, ll & end)
{
	return beg - end;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t --)
	{
		cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
		ll lbx = count(a.x, b.x);
		ll lby = count(a.y, b.y);
		ll lcx = count(a.x, c.x);
		ll lcy = count(a.y, c.y);
		ll ans = 0;
		if ((lbx * lcx) > 0) ans += min(abs(lbx), abs(lcx));
		if ((lby * lcy) > 0) ans += min(abs(lby), abs(lcy));
		cout << ++ ans << endl;
    }
	return 0;
}
C

给一个由 0~9 组成的字串 s、一个数 m、两个长度为 m 的字串 l,r ，求是否存在一个数满足在 [l,r] 范围内且不是 s 的子串（不一定是连续的）

  • 首先想到肯定要枚举 l,r ，按从高到低数位 l -> r （不论是否连续，严格从左至右）
    那对于 l -> r 的每一个数位，又肯定要在 s 上查询，看看能否找到；

没找到，那就说明肯定不是它的子串；

  • 找到了，那就标记该位置，为什么嘞？其一是把 \(l[i] \rightarrow r[i]\) 中的所有被标记的位置找到，取其中的最大值，即最靠近 s 的尾巴，这样下一数位的数出现在 s 上的可能性就最小（别忘了严格从左至右，所以 s 标记处的左边就没有再遍历的意义了，所以我这样结论），这是一种贪心思想；
    其二是也从刚刚的话看得出来，标记最远位置 x 后，下一位数就可以直接从 x+1 位开始查询；

  • 那么答案就从最大值这里切入，若是它的子串，最大值撑死了就是 s 的长度。
    so，若不是子串，我们就可以给它赋一个极大值作为在 s 上找不到的标志（其实大于 s 的长度就可以。 done.

顺便提一嘴关于复杂度，Alex_Wei 大犇昨天在 帖子 里回答我说是 \(O(m*m*ls)\Rightarrow O(3*10^7)\) ，是我糊涂了吗（一定是）？，难道测试用例数量 t 不用算进去......

#C code 
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int t, m;
string s, l, r;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin >> t;
	while (t --)
	{
		cin >> s >> m >> l >> r;
		int ls = s.size(), check = -1;
		for (int i = 0; i < m ; i ++)
		{
			int k = check;
			for (char c = l[i]; c <= r[i]; c ++)
			{
				int tmp = inf;
				for (int j = check+1; j < ls; j ++)
				{
					if(s[j] == c)  
					{
						tmp = j;
						break;
					}
				}
				k = max(k, tmp);
			}
			check = k;
		}
		cout << (check == inf ? "YES" : "NO") << endl;
	}
	
	return 0;
}

剩下 D,E,F ，不用看了，我有自知之明，肯定不会做 qwq

总结：

这场比赛赛时实际上只过了 A ，但只花了 20min 左右，还是比较快的；

剩下的时间完全就耗在 B 上，思路蛮简单，但我的代码写得很......可以说凌乱，导致我一直能发现漏洞，一直调试，一直 wa ，不断堆砌代码，最后调不出来......

#B 凌乱的代码 
#include<bits/stdc++.h>
using namespace std;
int t;
struct node
{
	int x, y;
}a, b, c;

int count(int & beg, int & end)
{
	return beg - end;
}

bool check()
{
    if ((a.x >= b.x && a.x >= c.x && a.y >= b.y && a.y >= c.y) || (a.x <= b.x && a.x <= c.x && a.y <= b.y && a.y <= c.y)) return true;
    return false;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> t;
	while (t --)
	{
		cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
		int lbx = count(a.x, b.x);
		int lby = count(a.y, b.y);
		int lcx = count(a.x, c.x);
		int lcy = count(a.y, c.y);
		int ans = 0;
		bool ikun = false , IKUN = false;
		if ((lbx ^ lcx) < 0) ans += 1;
		else 
		{
			ans += min(abs(lbx), abs(lcx));
			if (check()) ikun = true;
		}
		if ((lby ^ lcy) < 0) ans += 1;
		else 
		{
			ans += min(abs(lby), abs(lcy));
			if (check()) IKUN = true;
		}
		if (ikun && IKUN) ans ++;
		cout << ans << endl;
	}

	return 0;
}

剩下没多少时间了，就懒得看 C 了。（直接开摆

但赛后看 C 还是蛮简单的。