UVA11518 Dominos 2 题解

发表于 2023-07-30 分类于 solution

题目大意

一组多米诺骨牌，将用手推倒若干个，被推倒的多米诺骨牌可让后面的多米诺骨牌倒下，问有几个多米诺骨牌被推倒。

题目分析

可将多米诺骨牌视为一个有向图，要模拟推倒的过程，可用深度优先遍历方法。

考虑使用邻接表储存图，首先读入要存的边 $u,v$ ，随后将边存入 vector 里：

1	adj[u].push_back(v);

随后读入起始点 $z$ ，以 $z$ 为起点，对图进行 DFS 操作。

1 2	cin >> z; dfs(z);

然后将 DFS 函数补充完整。

void dfs(int u)
{
	vis[u] = true;
	int siz = adj[u].size();
	for(int i = 0; i < siz; ++i)
	{
		int now_point = adj[u][i];
		if(!vis[now_point]) dfs(now_point);
	}
}

最后，统计被访问过的点的个数，并输出。

1 2	for(int i = 1; i <= n; i++) ans += vis[i]; cout << ans << endl;

注意：因为有多组数据，所以应在每组数据处理之前清空邻接表以及标记数组。

完整代码

#include<bits/stdc++.h>
using namespace std;
const short MAXN = 10010;
vector<int> adj[MAXN];
bool vis[MAXN];
int n, m, l;
void dfs(int u)
{
	vis[u] = true;
	int siz = adj[u].size();
	for(int i = 0; i < siz; ++i)
	{
		int now_point = adj[u][i];
		if(!vis[now_point]) dfs(now_point);
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int u, v;
	int T;
	cin >> T;
	while(T--)
	{
		for(int i = 1; i <= n; i++) adj[i].clear();
		memset(vis, 0, sizeof vis);

		cin >> n >> m >> l;
		while(m--)
		{
			cin >> u >> v;
			adj[u].push_back(v);
		}
		int z;
		while(l--)
		{
			cin >> z;
			dfs(z);
		}
		int ans = 0;
		for(int i = 1; i <= n; i++) ans += vis[i];
		cout << ans << endl;
	}
	return 0;
}

题外话

这是本蒟蒻第一篇图论题题解。

本蒟蒻做此题时吃了 $9$ 发 WA：

在第十次终于 AC 了：https://www.luogu.com.cn/record/118131412

CF976B Lara Croft and the New Game 题解

发表于 2023-07-26 更新于 2023-07-27

前言

本文为本蒟蒻第一篇在洛谷题库过审的题解，写得不好请见谅。

题目简介

这是一道很考验思维的数学题。

题意

一个 $n \times m$ 的矩阵，从左上角 $(1,1)$ 出发，从上走到下之后按照蛇形方式走到终点 $(1,2)$ 。给定一个步数 $k$ ，求走 $k$ 步之后的坐标。

分析

通过数据量 $2\le n,m \le 10^9,0\le k \le n \cdot m$ 得知模拟小人走的路径是不可以的。因此，我们考虑常数时间复杂度的数学算法。

分析一下，可以得知小人走的路径分为两部分：从左上角走到左下角和从左下角走到终点两部分。

第一部分

走一步时，小人在 $(2,1)$ ；走两步时，小人在 $(3,1)$ ……走 $k(k<n)$ 步时，小人在 $(k+1,1)$ 。

所以我们可以得到第一部分的代码：

1	if(k<n) cout<<k+1<<" "<<1<<endl;

第二部分

第二部分的路径可以分为两种情况：从左往右走和从右往左走。设 $k_1=k-n$ ，那么 $k_1$ 即为第二部分走的步数。

通过分析 $k_1$ 我们可以得到一个规律：

当 $\left \lfloor \dfrac{k_1}{m-1} \right \rfloor$ 为偶数时，即为从左往右走，此时小人的坐标为 $(n-\dfrac{k_1}{m-1},k_1 \bmod (m-1)+2)$
当 $\left \lfloor \dfrac{k_1}{m-1} \right \rfloor$ 为奇数时，即为从右往左走，此时小人的坐标为 $(n-\dfrac{k_1}{m-1},m-k_1 \bmod (m-1))$

于是我们可以得到第二部分的代码：

1
2
3

long long k1=k-n;
if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl;
else cout<<n-k1/(m-1)<<" "<<k1%(m-1)+2<<endl;

完整代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	long long n,m,k;
	cin>>n>>m>>k;
	if(k<n) cout<<k+1<<" "<<1<<endl;
	else
	{
		long long k1=k-n;
		if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl;
		else cout<<n-k1/(m-1)<<" "<<k1%(m-1)+2<<endl;
	}
	return 0;
}

最后提醒：注意数据范围，此题需要开 long long！

后记

1 2	if((k1/(m-1))%2==1) cout<<n-k1/(m-1)<<" "<<m-k1%(m-1)<<endl; // ^ I even wrote this 1 as 0! What am I thinking??????

1	//I spent about two and a half hours on this question.

洛谷入门赛#12彩蛋

发表于 2023-05-12 更新于 2023-05-13

比赛链接

【LGR-138-Div.4】洛谷入门赛 #12

彩蛋

在上面说过，会有彩蛋。

点开 T335305 排排队，做游戏这一题，发现“样例2 解释”里说到：

1 2	前三个小朋友的学号分别是三个出题人的洛谷 UID。有人说学号是随机生成的，学号可不是随机生成的啊。

把四个学号分别带进去，可以得到四个用户，分别是：@览遍千秋，@一扶苏一，@Maxmilite，和一个特别的用户@EtILiMxam，这个用户主页写着“神秘网址”（一个问卷星页面），打开一看，就是彩蛋了。

不过这个彩蛋已经无效了，这是我成功领取到的截图：

Hello World

发表于 2023-04-29

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1	$ hexo new "My New Post"

More info: Writing

Run server

1	$ hexo server

More info: Server

Generate static files

1	$ hexo generate

More info: Generating

Deploy to remote sites

1	$ hexo deploy

More info: Deployment