Dytechlab Cup 2022

A. Ela Sorting Books

题目大意: 给定$n(1 \leq n \leq 200)$本书,每本书有一个首字符，要把这$n$本书放到$k$个书架上，每个书架上面按照字典序第一个没有出现过的字符加入集合中，问这个集合最大能够构成的字符是什么

解题思路: 模拟样例可以发现一件事情，假设我们当前还有若干个字符，那么从第一个字符按顺序放到最后一个可以连续放置的字符肯定是最优秀的放置方法。那么我们怎么写呢？我们可以枚举每个书架可以最终放入集合的字符是多少，然后$check$即可

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
typedef long long ll;
const int maxn = 1e6 + 10;
int a[maxn],n,k;
string str;
map<int,int> mp;
int check(int x)
{
	if(x > n / k) return 0;
	for(int i = 0;i <= x - 1;++i)
	{
		if(mp[i] <= 0) return 0; 
	}
	for(int i = 0;i <= x - 1;++i)
	{
		mp[i]--;
	}
	return 1;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> k;
		cin >> str;
		mp.clear();
		for(auto to:str)
		{
			int id = to - 'a';
			mp[id]++;
		}
		vector<char> ans;
		for(int i = 1;i <= k;++i)
		{
			for(int j = 25;j >= 0;--j)
			{
				if(check(j))
				{
					ans.push_back('a' + j);
					break;
				}
			}
		}
		sort(ans.begin(),ans.end());
		reverse(ans.begin(),ans.end());
		for(auto to:ans)
		{
			cout << to;
		}
		cout << "\n";
	}
}

B. Ela’s Fitness and the Luxury Number

题目大意: 给定$T (1 \leq T \leq 2e5)$组样例，每组两个数字分别是$l$ 以及$r(1 \leq l,r \leq 1e18)$ ，问在这个区间中美丽数字的个数是多少。美丽数字的定义是$x$可以被$x $ $mod$ $\lfloor\sqrt{x}\rfloor$ $ = 0$

解题思路: 发现数据范围实际上很大，然后我打了一下表发现了一个规律，就是根据每一个平方数去划分，可以以每个平方数划分成一个块，假设当前的平方数是$x$，当前的平方根是$y$，那么在这一个块中存在的数字分别是$x,x + y,x + 2 * y$

特别需要注意的是，$floor$存在的一定精度误差，因此在取的时候可以采取一些操作比如$–$来优化

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
typedef long long ll;
const int maxn = 1e6 + 10;
int a[maxn],n,k;
string str;
void get()
{
	for(int i = 1;i <= 20;++i)
	{
		int div = floor(sqrt(1.0 * i));
		if(i % div == 0)
		{
			cout << "i -> " << i << "\n";
		}
	}
}
int getans(int x)
{
	if(x == 0) return 0;
	int rd = (sqrt(1.0 * x));
	if(rd * rd > x) rd--;
	int haha = rd * rd;
	int ans = (rd - 1) * 3;
	if(x >= haha)
	{
		ans++;
	}
	if(x >= haha + rd)
	{
		ans++;
	}
	if(x >= haha + rd * 2)
	{
		ans++;
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		int l,r;
		cin >> l >> r;
		// cout << getans(l - 1) << "\n";
		// cout << l << " " << getans(l - 1) << " " << r << " " << getans(r) << "\n";
		cout << getans(r) - getans(l - 1) << "\n";
	}
}

C. Ela and Crickets

题目大意: 给定一个无限大的棋盘，给定一个$L$形状的棋子以及这个棋子刚开始的坐标，给定一个目标坐标，问这个棋子通过跳跃的方式能否到达这个目标点

解题思路: 既然在一个棋盘上面，我们可以先考虑本身这个棋盘所带来的性质，也就是考虑存在的$L$形状的奇偶性带来的影响。我们可以模拟样例，发现对于一个$L$形状来说，和那个空着的格子的横纵坐标奇偶性都一样的那么我们是不可达的；然后我们考虑特殊情况，如果那个小角在边缘的话，那么不管怎么样子也只能再这个边缘移动，然后这样子判断即可

#include <bits/stdc++.h>
using namespace std;
template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
#define int long long
typedef long long ll;
const int maxn = 1e2 + 10;
int r[maxn],n,k,c[maxn],x,y,sx,sy;
string str;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n;
		map<int,int> mpx,mpy;
		for(int i = 1;i <= 3;++i)
		{
			cin >> r[i] >> c[i];
			mpx[r[i]]++;
			mpy[c[i]]++;
		}
		cin >> x >> y;
		sx = sy = 0;
		for(auto [to,cs]:mpx)
		{
			if(cs == 2) sx = to;
		}
		for(auto [to,cs]:mpy)
		{
			if(cs == 2) sy = to;
		}
		//边缘
		if((sx == 1 || sx == n) && (sy == 1 || sy == n))
		{
			if(sx == x || sy == y) cout << "YES\n";
			else cout << "NO\n";
			continue;
		}
		if((sx - x + sy - y) % 2 == 1)
		{
			cout << "YES\n";
			continue;
		}
		if((sx - x) % 2 == 0) cout << "YES\n";
		else if((sy - y) % 2 == 0) cout << "YES\n";
		else cout << "NO\n";
	}
}

D. Ela and the Wiring Wizard

题目大意: 给定一张图，图有$n$个点$m$条边$(2 \leq n \leq 500,n - 1\leq m \leq 100000)$每次可以进行若干次操作，操作如下所示

选择两条边$(u,v)$和$(v,w)$删除$(u,v)$然后连接$(u,w)$，代价是$(u,v)$的边权

问从节点$1$到节点$n$最少需要多少次

解题思路: 刚开始拿到题目的时候发现没有任何思路，模拟样例可以发现一个性质，就是无论最后怎么样，最后只有一条从$1$到$n$的边使用

那么我们可以提出猜想，是否从$1$到$n$只需要连接一条路呢？

接下来的部分参考了$pzr$佬的

我们可以做出反证感性理解一下，假设我们有多条路到$n$，其中分别是$1 -> u_1 -> u_2 -> n$,设$u_1 ->u_2$的距离是$w_1$，另外一条从$1 -> u_1$权值是$w_2$

首先就放着这两条边，边权是$w_1 + w_2$

如果让我们把所有的边都变成$w_1$,那么就是$2w_1$

或者我们把所有边变成$w_2$，那么就是$2w_2$

那么进行修改后我们总能贪心取到最小的

分析样例之后，我们发现建边有成自环和非自环的情况

分析非自环的情况，那么对于一条边来说，就是去修改$dis(1,u) + dis(v,n)$的次数然后再加上$1$次走到的贡献

那么接下来考虑自环的情况，如果有自环的话最多可能存在几个自环呢？

我们可以把自环看成是一个点，设自环点是$x$,那么我们额外花费一个贡献连接$x$,从$1$到$x$再从$x$到$n$的距离相加然后乘贡献，这个$x$相当于中间的一个断点去更新整张图，因此实际上最多也就只有一个

那么对于这一种题目来说，分析完整道题目我们发现都是对边 这一个元素进行考虑

因为从一开始我们就在思考，从得出结论开始，再到实际上我去取哪条边最优

#define int long long
typedef long long ll;
const int maxn = 1e3 + 10;
const int inf = 1e9;
int dis[maxn][maxn],n,m;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int T;
	cin >> T;
	while(T--)
	{
		cin >> n >> m;
		vector<array<int,3>> edge;
		for(int i = 1;i <= n;++i)
		{
			for(int j = 1;j <= n;++j)
			{
				dis[i][j] = inf;
			}
		}
		for(int i = 1;i <= n;++i) dis[i][i] = 0;
		for(int i = 1,u,v,w;i <= m;++i)
		{
			cin >> u >> v >> w;
			edge.push_back({u,v,w});
			dis[u][v] = dis[v][u] = 1;
		}
		for(int k = 1;k <= n;++k)
		{
			for(int i = 1;i <= n;++i)
			{
				for(int j = 1;j <= n;++j)
				{
					chkmin(dis[i][j],dis[i][k] + dis[k][j]);
				}
			}
		}
		int ans = 1e18;
		for(auto [u,v,w]:edge)
		{
			chkmin(ans,(dis[1][u] + 1 + dis[v][n]) * w);
			chkmin(ans,(dis[1][v] + dis[u][n] + 1) * w);
			for(int x = 1;x <= n;++x)
			{
				chkmin(ans,(min(dis[u][x],dis[v][x]) + dis[1][x] + dis[x][n] + 2) * w);
			}
		}
		cout << ans << "\n";
	}
}