题解:第二十届浙大宁波理工学院程序设计大赛

难度预期

A < B < C < I < J < D < E < F < G < H 其中,难度最低的 题是纯语法题,不涉及算法;后 题则是各种算法题,依次是:D.树上二分前缀和/离线处理树上前缀和。E.预处理状压DP,BFS/DFS转移状态。F.不存储的线段树。G.虚点建图/改初始化状态的最短路。H. 求解数列前 项和。

A Storious的小杨辉三角

输出杨辉三角形前五行中的某一行。 如果能观察到前五行都是 则可以轻松首A。 正常写 个if就可以轻松AC。 不想写if的话,开个二维数组for一遍小DP一下,直接输出也能轻松AC。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

void Main(void)
{
	ll n;
	cin >> n;
	cout << (ll)std::pow(11, n - 1) << '\n';
	return;
}

B Gray与坤变偶不变

把字符串中奇数位置的字母改变大小写后输出。 for一遍字符串改一下即可。 大部分语言都有写好的函数可以直接检测大小写和修改大小写,直接调用可以节省很多时间。 自己写下if也不会多花太多时间,也可以轻松AC。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

void Main(void)
{
	ll n;
	std::string s;
	cin >> n;
	cin >> s;
	for (ll i = 0; i < n; i += 2)
	{
		if (islower(s[i]))
			s[i] = toupper(s[i]);
		else if (isupper(s[i]))
			s[i] = tolower(s[i]);
	}
	cout << s << '\n';
	return;
}

C Gray与你好谢谢小笼包再见

给当前时间和闹钟时间,问下一次闹钟响起是多少小时多少分钟后。(注意特判当前时间和闹钟时间相同的情况。)

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

void Run(void)
{
	std::pair<ll, ll> now, bell;
	cin >> now.first >> now.second >> bell.first >> bell.second;
	if (bell == now)
	{
		cout << 24 << ' ' << 0 << '\n';
		return;
	}
	if (bell < now)
		bell.first += 24;
	std::pair<ll, ll> ans;
	ans.first = bell.first - now.first;
	ans.second = bell.second - now.second;
	if (ans.second < 0)
		--ans.first, ans.second += 60;
	cout << ans.first << ' ' << ans.second << '\n';
	return;
}
void Main(void)
{
	ll t;
	cin >> t;
	while (t--)
		Run();
	return;
}

D Gray与派对80

容易发现,参赛者之间的关系图是一个以 号为根的树,每个节点的深度意味着这个节点编号的参赛者是第几届参赛者。如果选择邀请一个节点,则他的祖先节点全部要被邀请,同时和他同深度的节点也要全部邀请。这意味着,选择的节点一定是某一届及之前的所有参赛者,才能满足条件。深度可以挑选心仪的遍历算法来得到,然后可以用前缀和来处理某届及以前共有多少人。随着届数的增加,选择的人数递增,具有单调性,可以二分处理每次查询,每次查询查前缀和数组中,小于等于 的数中的最大值。一共进行 轮查询,总复杂度 。 另一种做法是离线排序查询,然后滑动指针实现。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}
 
constexpr ll SZ = 1e5 + 5;
ll n;
ll a[SZ];
ll q;
ll b[SZ];
std::vector<ll> E[SZ];
ll mx;
ll c[SZ], s[SZ];
 
void DFS(ll x, ll dep)
{
	mx = std::max(mx, dep);
	++c[dep];
	for (const auto &son : E[x])
		DFS(son, dep + 1);
	return;
}
void Main(void)
{
	cin >> n;
	for (ll i = 1; i <= n; ++i)
		cin >> a[i];
	cin >> q;
	for (ll i = 1; i <= q; ++i)
		cin >> b[i];
	for (ll i = 2; i <= n; ++i)
		E[a[i]].push_back(i);
	mx = 1;
	DFS(1, 1);
	for (ll i = 1; i <= n; ++i)
		s[i] = s[i - 1] + c[i];
	for (ll i = 1; i <= q; ++i)
		cout << s[std::upper_bound(s + 1, s + mx + 1, b[i]) - s - 1] << '\n';
	return;
}

E Gray与XX启动

给当前状态和目标状态,问最少需要多少次操作,才能从当前状态到达目标状态。 状态可以压成长度为5的二进制,总共只有 种状态。 可以把每种状态作为初始状态BFS一次,就可以预处理出所有可能的询问的答案。 预处理复杂度 ,单次询问复杂度 ,总复杂度 。 用DFS同样可以实现。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

constexpr ll SZ = (1 << 5);
ll f[SZ][SZ];

void BFS(ll s)
{
	std::queue<ll> q;
	f[s][s] = 0;
	q.push(s);
	while (not q.empty())
	{
		ll now = q.front();
		q.pop();
		for (ll i = 0; i <= 4; ++i)
		{
			ll bit = (1 << i);
			if ((now & bit) != 0)
				continue;
			ll nxt = now + bit;
			bit = (1 << ((i + 2) % 5));
			if ((now & bit) != 0)
				nxt -= bit;
			else
				nxt += bit;
			bit = (1 << ((i + 3) % 5));
			if ((now & bit) != 0)
				nxt -= bit;
			else
				nxt += bit;
            
			if (f[s][nxt] != -1 )
				continue;
			f[s][nxt] = f[s][now] + 1;
			q.push(nxt);
		}
	}
	return;
}
void Init(void)
{
	memset(f, -1, sizeof(f));
	for (ll s = 0; s < SZ; ++s)
		BFS(s);
	return;
}
ll Read(void)
{
	ll res = 0;
	for (ll i = 0; i <= 4; ++i)
	{
		ll x;
		cin >> x;
		if (x == 1)
			res += (1 << i);
	}
	return res;
}
void Run(void)
{
	ll s = Read();
	ll t = Read();
	cout << f[s][t] << '\n';
	return;
}
void Main(void)
{
	Init();
	ll t;
	cin >> t;
	while (t--)
		Run();
	return;
}

F Gray与XX铁道

线段树结构的图上查询多源最短路。 从最长的那种路开始往短的路考虑,看此次查询的最短路是否经过这条路。 如果经过这条路,说明删除这条路后,查询的两个点一个和这条路的左端点连通,一个和这条路的右端点连通。那么查询结果就是:查询的一个点到这条路左端点的最短路距离+这条路的长度+查询的另一个点到这条路的右端点的最短路距离。可以像线段树一样用DFS轻松实现。复杂度

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

ll DFS(ll l, ll r, ll a, ll b)
{
	if (a == b)
		return 0;
	ll md = (l + r) >> 1;
	if (a <= md and b <= md)
		return DFS(l, md, a, b);
	if (md < a and md < b)
		return DFS(md + 1, r, a, b);
	return DFS(l, md, l, a) + DFS(md + 1, r, b, r) + r - l;
}
void Main(void)
{
	ll n, q;
	cin >> n >> q;
	ll tot = (1 << n);
	for (ll i = 1; i <= q; ++i)
	{
		ll a, b;
		cin >> a >> b;
		cout << DFS(1, tot, a, b) << '\n';
	}
	return;
}

G Gray与美了吗外卖

给一个有向图,不保证连通,可能存在重边,保证不存在自环。每个点有以下属性:颜色,本地生成费用。每个边有以下属性:通过收费站的基础费用,通过收费站需要的颜色转换费用。问给每个点一个蛋糕(本地生成或者其他点生成后运输过来)的最小费用。 额外加一个虚点,表示蛋糕生成的源头。虚点和图中每个点建个边(可以证明双向单向都正确),边权是在这个点生成蛋糕的费用。 再在图中修正边,如果一个边连接着 ,那么,如果不能把蛋糕的颜色从 点颜色转成 颜色, -> 的有向边就需要删除( -> 同理)。如果能够转换,则边权在收费站基础费用的基础上,再加上颜色转换的费用。 之后以虚点为源点跑一次有向图的单源最短路,到每个点的最短路距离就是让这个点得到一个蛋糕的最小费用。所有点的最短路距离和就是答案。 注意,颜色之间转换时,可以把其他颜色当成中转站,所以颜色转换也需要跑一次多源最短路。 如果了解单源最短路的原理,也可以通过跑最短路前,先在队列里加入 个点来替代建虚点的操作。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

#define VE std::vector
#define HEAP std::priority_queue
#define PLL std::pair<ll, ll>
#define fi first
#define se second
#define FOR(i, l, r) for (ll i = (l); i <= (r); ++i)
constexpr int inf = 0x3f3f3f3f;
constexpr ll INF = 0x3f3f3f3f3f3f3f3fLL;
template <ll V_SZ>
struct DIJ
{
public:
	static constexpr ll ERR = -1;
	ll v_sz;
	VE<PLL> E[V_SZ];
	ll dis[V_SZ];
	void Init(ll v_sz)
	{
		this->v_sz = v_sz;
		FOR(i, 0, v_sz)
		E[i].clear();
		return;
	}
	void Push(ll bg, ll ed, ll wt) { E[bg].push_back({ed, wt}); }
	void Build(ll s)
	{
		FOR(i, 0, v_sz)
		{
			dis[i] = INF;
			vis[i] = false;
		}
		dis[s] = 0;
		HEAP<PLL, VE<PLL>, std::greater<PLL>> he;
		he.push({0, s});
		while (not he.empty())
		{
			ll now = he.top().se;
			he.pop();
			if (vis[now])
				continue;
			vis[now] = true;
			for (auto &[aim, wt] : E[now])
			{
				if (vis[aim])
					continue;
				if (dis[aim] > dis[now] + wt)
				{
					dis[aim] = dis[now] + wt;
					he.push({dis[aim], aim});
				}
			}
		}
		return;
	}
	ll Qry(ll p)
	{
		if (p < 1 or p > v_sz or dis[p] == INF)
			return ERR;
		return dis[p];
	}

protected:
	bool vis[V_SZ];
};
constexpr ll C_SZ = 1e2 + 5;
constexpr ll SZ = 1e5 + 5;
ll c, k;
ll f[C_SZ][C_SZ];
ll n;
ll col[SZ];
ll cost[SZ];
ll m;
DIJ<SZ> G;

void Main(void)
{
	cin >> c >> k;
	memset(f, inf, sizeof(f));
	for (ll i = 1; i <= k; ++i)
	{
		ll x, y, z;
		cin >> x >> y >> z;
		f[x][y] = std::min(f[x][y], z);
	}
	for (ll i = 1; i <= c; ++i)
		f[i][i] = 0;
	for (ll i2 = 1; i2 <= c; ++i2)
		for (ll i1 = 1; i1 <= c; ++i1)
			for (ll i3 = 1; i3 <= c; ++i3)
				f[i1][i3] = std::min(f[i1][i3], f[i1][i2] + f[i2][i3]);
	cin >> n;
	for (ll i = 1; i <= n; ++i)
		cin >> col[i];
	for (ll i = 1; i <= n; ++i)
		cin >> cost[i];
	G.Init(n + 1);
	cin >> m;
	for (ll i = 1; i <= m; ++i)
	{
		ll u, v, w;
		cin >> u >> v >> w;
		if (f[col[u]][col[v]] != INF)
			G.Push(u, v, w + f[col[u]][col[v]]);
		if (f[col[v]][col[u]] != INF)
			G.Push(v, u, w + f[col[v]][col[u]]);
	}
	for (ll i = 1; i <= n; ++i)
		G.Push(n + 1, i, cost[i]);
	G.Build(n + 1);
	ll ans = 0;
	for (ll i = 1; i <= n; ++i)
		ans += G.Qry(i);
	cout << ans << '\n';
	return;
}

H Gray与原元源矩阵

给一个类似菱形的范围,查询范围内的和。 首先观察发现,查询的范围是一个类似菱形的范围。对于任意一个与选中的 点数字相同的点,以它为中心 选中同样的范围,得到的答案相同,所以可以先把 先分别对 取模,让实际查询的范围尽可能靠近原点。每一个点上的数字是 ,因此最终答案就是范围内的 。可以分开计算 。 以 为例,可以发现,每一列上的数字的 部分贡献是相同的,但每一列的数字出现的个数不同。先考虑 足够大,远大于 的情况。将需要计算的菱形范围分为左 和右 两个三角形区域,分别计算贡献。以左 为例,最左列的数字为 ,只出现一次,我们称之为 。则可以发现,左 每一列上的数字,从左到右,是对 在取模意义下以 为首项,公差为 的等差数列。但是答案计算并不是在取模意义下的,所以分开考虑 的部分和 的部分(如果 ,则忽略这部分)。以 的部分为例,先考虑最多端,完整的,长度为 的连续几列。定义 , , 代表第 列上的数字, 代表第 列的数字重复的次数, 代表第 列的贡献。则第一个完整的部分的贡献是 ,可以发现这部分是个二阶等差数列求和,可以 计算这一整个部分的贡献。如果不了解二阶等差数列求和的计算,也可以通过普通的运算律加上预处理来 处理这个部分: 其中 可以直接用公式计算,也可以提前预处理出来在之后的查询中使用。显然 不会超过 复杂度足够,也不会爆long long范围。 这样完整的,长度为 的部分会稳定出现 个,每个都可以视作二阶等差数列求和来 计算。对于最后可能出现的不完整部分,其长度为 。同样也是二阶等差数列求和,可 计算。当 较小,以至于没有完整部分时,直接 计算不完整部分即可。 部分同理,也是二阶等差数列,可以 计算。这样左 的部分的贡献就可以在 的复杂度内计算出来。但在最坏情况下,这样的总复杂度 会到达 ,复杂度还是不够,考虑进一步优化。 再次观察发现,对于完整的部分,其二阶等差数列只有 部分的首项 会发生变化。而因为中间距离相同,所以 的变化呈现为一阶等差数列,每隔一个区间, 会增加 。再观察二阶等差数列 ,可以把除了 以外的都看是确定的常量。定义 ,则 。所以 部分的左 部分的完整部分的 部分的贡献就是 ,其中 表示的是以 为首项, 为公差的等差数列的第 项。显然这是个一阶等差数列求和,可以直接 计算,既可以用公式直接计算,也可以像前面一样用运算律化出 ,然后用预处理的结果代入 完成等差数列求和的计算。对于不完整的部分,最多只计算一次二阶等差数列求和。其余 的部分同理,右 部分同理, 部分同理,最终就可以 得到所有的贡献。 很多部分的计算过程是非常接近的,可以用函数实现,从而减少码量。 综上,即使完全不了解等差数列,也可以利用预处理和基础的运算律 实现每次查询。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

// x对mod取模
ll Mod(ll x, ll mod) { return (x % mod + mod) % mod; }
// 首项为a1,公差为d的等差数列第i项的值
ll GetA(ll a1, ll d, ll i) { return a1 + (i - 1) * d; }
// 首项为a1,公差为d的等差数列前n项和
ll GetS1(ll a1, ll d, ll n)
{
	ll res = 0;
	res += n * a1;
	res += n * (n - 1) / 2 * d;
	return res;
}
// 首项为a1,公差为1的等差数列 乘上 首项为b1,公差为d的等差数列 得到的新的二阶等差数列 的前n项和
ll GetS2(ll a1, ll b1, ll d, ll n)
{
	ll res = 0;
	res += n * (n + 1) * (2 * n + 1) / 6 * d;
	res += n * (n + 1) / 2 * (b1 + a1 * d - 2 * d);
	res += n * (a1 * b1 + d - b1 - a1 * d);
	return res;
}
// 二阶等差数列求和公式转一阶等差求和数列时的系数计算
void GetKC(ll a1, ll d, ll n, ll &k, ll &c)
{
	k = n * (n + 1) / 2 + n * a1 - n;
	c = 0;
	c += n * (n + 1) * (2 * n + 1) / 6 * d;
	c += n * (n + 1) / 2 * (a1 * d - 2 * d);
	c += n * d - n * a1 * d;
	return;
}
// 以s为中心点,p为当前维度模数,共有cnt个此模式构成的整体,在第一个此模式的贡献次数的等差数列的首项是b1,公差是d,模式长度为len的整体部分贡献
ll GetBLK(ll s, ll p, ll cnt, ll b1, ll d, ll len)
{
	ll k, c;
	GetKC(s, d, len, k, c);
	ll a1 = k * b1 + c;
	ll step = k * d * p;
	return GetS1(a1, step, cnt);
}
// 以s点为中心点,p为当前维度模数,询问范围为r的区域,此维度的贡献
ll Qry(ll s, ll p, ll r)
{
	ll res = 0;
	ll a1, b1, cnt, len1, len2, tot, n;

	// 前r+1部分的整块部分的贡献
	a1 = Mod(s - r, p);
	cnt = (r + 1) / p;

	// 模式1 整块部分的贡献
	len1 = p - a1;
	b1 = GetA(1, 2, 1);
	res += GetBLK(a1, p, cnt, b1, 2, len1);

	// 模式2 整块部分的贡献
	len2 = p - len1;
	b1 = GetA(1, 2, len1 + 1);
	res += GetBLK(0, p, cnt, b1, 2, len2);

	// 前r+1部分的多余部分的贡献
	tot = cnt * p;
	n = std::min(p - a1, r + 1 - tot);

	// 模式1 多余部分的贡献
	b1 = GetA(1, 2, tot + 1);
	res += GetS2(a1, b1, 2, n);

	// 模式2 多余部分的贡献
	b1 = GetA(1, 2, tot + n + 1);
	res += GetS2(0, b1, 2, r + 1 - (tot + n));

	// 后r部分的整块部分的贡献
	a1 = Mod(s + 1, p);
	cnt = r / p;

	// 模式3 整块部分的贡献
	len1 = p - a1;
	b1 = GetA(2 * r - 1, -2, 1);
	res += GetBLK(a1, p, cnt, b1, -2, len1);

	// 模式4 整块部分的贡献
	len2 = p - len1;
	b1 = GetA(2 * r - 1, -2, len1 + 1);
	res += GetBLK(0, p, cnt, b1, -2, len2);

	// 后r部分的多余部分的贡献
	tot = cnt * p;
	n = std::min(p - a1, r - tot);

	// 模式3 多余部分的贡献
	b1 = GetA(2 * r - 1, -2, tot + 1);
	res += GetS2(a1, b1, -2, n);

	// 模式4 多余部分的贡献
	b1 = GetA(2 * r - 1, -2, tot + n + 1);
	res += GetS2(0, b1, -2, r - (tot + n));

	return res;
}
void Run(void)
{
	ll n, m, x, y, r;
	cin >> n >> m >> x >> y >> r;
	x = Mod(x, n);
	y = Mod(y, m);
	ll ans = m * Qry(x, n, r) + Qry(y, m, r);
	cout << ans << '\n';
	return;
}
void Main(void)
{
	ll t;
	cin >> t;
	while (t--)
		Run();
	return;
}

I Gevin的RGB区间和

二维for一下计算出R,B的区间和,用总区间和减去R,B的区间和即可得到G区间和。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

constexpr ll SZ = 1e3 + 3;
ll n;
ll a[SZ][SZ];

void Main(void)
{
	cin >> n;
	for (ll i = 1; i <= n; ++i)
		for (ll j = 1; j <= n; ++j)
			cin >> a[i][j];
	ll sum = 0;
	for (ll i = 1; i <= n; ++i)
		for (ll j = 1; j <= n; ++j)
			sum += a[i][j];
	ll r = 0, g = 0, b = 0;
	for (ll i = 1; i <= n / 2; ++i)
		for (ll j = 1; j <= n / 2 + 1 - i; ++j)
		{
			r += a[i][j];
			b += a[n + 1 - i][n + 1 - j];
		}
	g = sum - r - b;
	cout << r << ' ' << g << ' ' << b << '\n';
	return;
}

J Gevin的打印服饰

每个长度为 的线单独打印,可以重叠。一共12条线。都是水平/竖直/45度。

#include <bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
void Main(void);
int main(void)
{
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	Main();
	return 0;
}

constexpr ll SZ = 1e3 + 3;
ll n;
char a[SZ][SZ];

void Main(void)
{
	cin >> n;
	for (ll i = 1; i <= n * 2 - 1; ++i)
		for (ll j = 1; j <= n * 3 - 2; ++j)
			a[i][j] = ' ';
	for (ll i = 1; i <= n; ++i)
	{
		a[1][n + i - 1] = '*';
		a[i][n + i - 1] = '*';
		a[n + 1 - i][n + i - 1] = '*';
		a[n + 1 - i][i] = '*';
		a[i][n * 2 - 2 + i] = '*';
		a[n][i] = '*';
		a[n][n + n - 2 + i] = '*';
		a[n + 1][n - 1 + i] = '*';
		a[n * 2 - 1][n - 1 + i] = '*';
		a[n - 1 + i][n] = '*';
		a[n - 1 + i][n * 2 - 1] = '*';
		a[n * 2 - i][n - 1 + i] = '*';
	}
	for (ll i = 1; i <= n * 2 - 1; ++i)
	{
		for (ll j = 1; j <= n * 3 - 2; ++j)
			cout << a[i][j];
		cout << '\n';
	}
	return;
}
全部评论

相关推荐

能干的三文鱼刷了10...:公司可能有弄嵌入式需要会画pcb的需求,而且pcb能快速直观看出一个人某方面的实力。看看是否有面试资格。问你问题也能ai出来,pcb这东西能作假概率不高
点赞 评论 收藏
分享
评论
2
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务