AtCoder_abc333

比赛链接

A - Three Threes

题目描述

输入一个 \(N\) 输出 \(N\) 个 \(N\) 。

解题思路

（这个题但凡学过都能写出来吧）

Code

// Problem: A - Three Threes
// Contest: AtCoder - Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）
// URL: https://atcoder.jp/contests/abc333/tasks/abc333_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)
		cout<<n;
	return 0;
}

B - Pentagon

题目描述

现在有一个正五边形 \(ABCDE\) ，给出两条对角线，请判断他们是否等长，如果相等输出 Yes 否则输出 No 。

解题思路

判断是否等长其实就是判断他们两端点在正五边形上相隔的点的数是否相等。

这样我们就想到了初版思路： if(abs(a[0]-a[1])==abs(b[0]-b[1]))cout<<"Yes";

但这样有一个问题，在这个代码中 \(AE\) 的长就变成了 \(4\) ，而我们希望他是 \(1\)。

显然，我们应该让他的长度变成 \(5-4=1\) ，由特殊到一般，对于正五边形上的任两点，我们都可以将 \(\min( \text{abs}(l-r),5 - \text{abs}(l-r))\) 定义为这两点之间的距离。

Code

// Problem: B - Pentagon
// Contest: AtCoder - Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）
// URL: https://atcoder.jp/contests/abc333/tasks/abc333_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
	cin>>a>>b;
	if(min(abs(a[0]-a[1]),5-abs(a[0]-a[1]))==min(abs(b[0]-b[1]),5-abs(b[0]-b[1])))
		cout<<"Yes";
	else
		cout<<"No";
	return 0;
}

C - Repunit Trio

题目描述

这里有一些被称为 Repunit 的、由 \(1\) 组成的数，就像 \(1,11,111,1111,11111,111111 \cdots \cdots\)。

现在给出一个数 \(N\) ,请输出第 \(N\) 小的、可以被分成三个 Repunit 的整数。

解题思路

首先观察数据范围，我们可以发现 \(N \le 333\) 而且样例数据也给出了当 \(N = 333\) 时，输出的整数为 \(112222222233\) ，那么我们就可以知道，在这 \(333\) 个数中，涉及到的，最大的 Repunit 为 \(111111111111\) ，那么，我们就可以枚举这 \(12\) 个 Repunit ，把所有可能涉及到的整数都枚举出来，枚举的细节就写在代码注释里了。

Code

// Problem: C - Repunit Trio
// Contest: AtCoder - Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）
// URL: https://atcoder.jp/contests/abc333/tasks/abc333_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[15]={0,1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111};
//经典打表再放送
long long ans[10000],top;//记得开long long
int main(){
	cin>>n;
	for(int i=1;i<=12;i++)
		for(int j=1;j<=12;j++)
			for(int k=1;k<=12;k++)//枚举所有可能的三元组
				ans[++top]=a[i]+a[j]+a[k];//加起来
	sort(ans+1,ans+1+top);//枚举的时候不保证从小到大，所以记得先排序
	unique(ans+1,ans+1+top);//三重循环枚举只能保证不遗漏，不能保证不重复，所以要先进行去重
	cout<<ans[n];//因为已经进行了排序和去重，所以直接输出第N个就好了
	return 0;
}

D - Erase Leaves

题目描述

给出一颗有 \(N\) 个节点的树，每次操作都可以删除一个叶子节点^[1]和与他连接的边，请问最少用几次可以删除 \(1\) 号节点？

解题思路

这道题实际上就是找出节点 \(1\) 的最大子树，然后用总节点数减去这个最大子树的节点数即可。

为什么？读题可知，可以被我们删除的节点只与一条边相连，也就是说，我们要保留 \(1\) 节点的一颗子树。

要使删除次数最少自然就是要让保留下的最多，那么保留下最大子树就好了。

Code

// Problem: D - Erase Leaves
// Contest: AtCoder - Toyota Programming Contest 2023#8（AtCoder Beginner Contest 333）
// URL: https://atcoder.jp/contests/abc333/tasks/abc333_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
using namespace std;
struct edge{
	int u,v;
	int next;
}mp[30000005];//邻接表存树
int idx[30000005],top;
int n;
int ans=1;
int vis[300005];
void add(int u,int v){//加边
	mp[++top].u=u;
	mp[top].v=v;
	mp[top].next=idx[u];
	idx[u]=top;
}
int dfs(int k){//递归的判断每个子树的大小
	int ret=1;
	vis[k]=1;
	for(int i=idx[k];i!=0;i=mp[i].next)
		if(!vis[mp[i].v])
			ret+=dfs(mp[i].v);
	vis[k]=0;
	return ret;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v);
		add(v,u);//记得要建无向边！！！
	}
	int mad=0;//最大子树的大小
	vis[1]=1;//不能再返回来访问第一个点了
	for(int i=idx[1];i!=0;i=mp[i].next){//遍历每一棵树，因为要计算最大子树，所以不好放在递归里进行
		int t=dfs(mp[i].v);
		ans+=t;
		mad=max(mad,t);
	}
	cout<<ans-mad;//别忘了，ans初始值是1，因为删掉1节点本身也是1次操作
	return 0;
}