A题：
题面：
亲戚
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果 x，y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。
输入格式
第一行：三个整数 n,m,p，（n,m,p≤5000），分别表示有 n 个人，m 个亲戚关系，询问 p 对亲戚关系。
以下 m 行：每行两个数 Mi，Mj，1≤Mi, Mj≤N，表示 Mi 和 Mj 具有亲戚关系。
接下来 p 行：每行两个数 Pi,Pj，询问 Pi 和 Pj 是否具有亲戚关系。
输出格式
p 行，每行一个 Yes 或 No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。
样例 #1
样例输入 #1
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
样例输出 #1
Yes
Yes
No
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
int f[5005];
int father(int x)//查找父节点
{
if (x == f[x])
return x;
return f[x] = father(f[x]);
}
int main()
{
int a, b;
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; ++i)
f[i] = i;
for (int i = 1; i <= m; ++i)//化为同一父节点
{
scanf("%d%d", &a, &b);
f[father(a)] = father(b);
}
for (int j = 1; j <= p; ++j)//判断是否共同祖先
{
scanf("%d%d", &a, &b);
if (father(a) == father(b))
puts("Yes");
else
puts("No");
}
return 0;
}
B题:
题面：
[TJOI2007]路标设置
题目背景
B 市和 T 市之间有一条长长的高速公路，这条公路的某些地方设有路标，但是大家都感觉路标设得太少了，相邻两个路标之间往往隔着相当长的一段距离。为了便于研究这个问题，我们把公路上相邻路标的最大距离定义为该公路的“空旷指数”。
题目描述
现在政府决定在公路上增设一些路标，使得公路的“空旷指数”最小。他们请求你设计一个程序计算能达到的最小值是多少。请注意，公路的起点和终点保证已设有路标，公路的长度为整数，并且原有路标和新设路标都必须距起点整数个单位距离。
输入格式
第 1 行包括三个数 L,N,K，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。
第 2 行包括递增排列的 N 个整数，分别表示原有的 N 个路标的位置。路标的位置用距起点的距离表示，且一定位于区间 [0,L] 内。
输出格式
输出 1 行，包含一个整数，表示增设路标后能达到的最小“空旷指数”值。
样例 #1
样例输入 #1
101 2 1
0 101
样例输出 #1
51
提示
公路原来只在起点和终点处有两个路标，现在允许新增一个路标，应该把新路标设在距起点 50 或 51 个单位距离处，这样能达到最小的空旷指数 51。
50% 的数据中，2≤N≤100，0≤K≤100。
100% 的数据中，2≤N≤100000, 0≤K≤100000。
100% 的数据中，0<L≤10000000。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int L, n, k;
bool check(int len)//判断长度为len时可否满足
{
int now = arr[0], num = 0, i = 1;
while (now != L)
{
if ((now + len) >= arr[i])
{
now = arr[i];
i++;
}
else
{
now += len;
num++;
}
}
return num <= k;
}
int main()
{
cin >> L >> n >> k;//读取数据
for (int i = 0; i < n; i++) scanf("%d", &arr[i]);
int l = 1, r = L;//二分
while (l < r)
{
int mid = l + r >> 1;
if (check(mid)) r = mid;
else l = mid + 1;
}
cout << l << endl;
return 0;
}
c题：
题面：
芝士原子
题目背景
芝士世界的原子由电子和核子组成，芝士世界的恶霸浩浩想要研究第 n 号元素的电子排布。
电子排布在电子层中，第 i 个电子层有 i 个电子亚层，在本题的数据范围内，你只需要考虑每个电子层最多前 4 个电子亚层，我们命名为 s,p,d,f。每一个电子亚层用”电子层编号+电子亚层字母”来表示。
同时，每一个电子亚层都有一定的容量，每一个电子亚层中填充的电子数不能超过其容量，s 类电子亚层容量为 2，p 类电子亚层容量为 6，d 类电子亚层容量为 10，f 类电子亚层容量为 14。
例：第 3 个电子层的第 2 个电子亚层为 3p，其容量为 6，第 6 个电子层的第 4 个电子亚层为 6f，其容量为 14。
电子的填充有一定的顺序，如果前一个电子亚层还没有填充满，则不能将电子填入当前电子亚层。在本题数据范围内，电子填充电子亚层的顺序如下。
1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p
填充了电子的电子亚层我们以“电子亚层名称+电子数”的格式表示，例如 3p6 表示 3p 电子亚层填入了 6 个电子。
芝士世界有自己的规则，因此芝士世界原子的电子排布不必考虑洪特法则的特例，可参见输入输出样例第 4 组测试数据（对应元素为铜）。如果你不知道这句话的含义，可以忽略，这个不影响完成这道题目。
题目描述
你需要将 n 个电子填充在电子亚层中，每一个电子亚层有一定的容量，每一个电子亚层中填充的电子数不能超过其容量。
电子亚层的命名格式为 xc，其中 x 为一个在 1 至 7 之间的正整数，c 是一个字母，且只可能为 s,p,d,f中的某一个。s 类电子亚层容量为 2，p 类电子亚层容量为 6，d 类电子亚层容量为 10，f 类电子亚层容量为 14。
电子的填充有一定的顺序，如果前一个电子亚层还没有填充满，则不能将电子填入当前电子亚层，电子填充电子亚层的顺序如下。
1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p
填充了电子的电子亚层我们以 xcn 的格式表示，其中 xc 表示电子亚层名称，n 表示该电子亚层填入的电子个数。
你需要按照上面的格式输出这 n 个电子的排布，并要求优先输出电子层编号小的，电子层编号相同按照 s,p,d,f 的顺序输出。
输入格式
每个测试点中包含 T 组测试数据。
输入共 T+1 行。
输入的一行为一个正整数 T(1≤T≤200)，代表该测试点中测试数据的组数。
接下来 T 行，每行为一个正整数 n(1≤n≤118)，代表该组测试数据询问的元素为第 n 号元素
输出格式
输出共 T 行，每行输出所问元素的核外电子排布式。
要求优先输出电子层小的，电子层相同按照 spdf 的顺序输出。
样例 #1
样例输入 #1
5
1
11
21
29
87
样例输出 #1
1s1
1s2 2s2 2p6 3s1
1s2 2s2 2p6 3s2 3p6 3d1 4s2
1s2 2s2 2p6 3s2 3p6 3d9 4s2
1s2 2s2 2p6 3s2 3p6 3d10 4s2 4p6 4d10 4f14 5s2 5p6 5d10 6s2 6p6 7s1
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
//题意：按照 1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p 的顺序进行原子排列
//s类电子亚层容量为 2，p 类电子亚层容量为 6，d 类电子亚层容量为 10，f 类电子亚层容量为 14，排满了就放下一层。
//最后要按照数字升序，字母“spdf” 的顺序来排列。
string n[19] = { "1s","2s","2p","3s","3p","4s","3d","4p","5s","4d","5p","6s","4f","5d","6p","7s","5f","6d","7p" };
int a[19] = { 2,2,6,2,6,2,10,6,2,10,6,2,14,10,6,2,14,10,6 };
int b[19] = { 0,1,2,3,4,6,5,7,9,12,8,10,13,16,11,14,17,15,18 };
int d[19];
int main()
{
int t;
cin >> t;
while (t--) {
int num;
cin >> num;
for (int i = 0; i < 19; i++)
{
if (num >= a[i])
{
d[i] = a[i];
num -= a[i];
}
else if (num < a[i])
{
if (num == 0)
break;
else {
d[i] = num;
num = 0;
}
}
}
for (int i = 0; i < 19; i++)
{
int a = b[i];
if (d[a] == 0)
continue;
else
{
cout << n[a] << d[a] << " ";
}
}
cout << endl;
}
return 0;
//s类电子亚层容量为 2，p 类电子亚层容量为 6，d 类电子亚层容量为 10，f 类电子亚层容量为 14
//1s 2s 2p 3s 3p 4s 3d 4p 5s 4d 5p 6s 4f 5d 6p 7s 5f 6d 7p
return 0;
}
D题
题面：
[ABC006A] 世界のFizzBuzz
题面翻译
输入一个整数n,如果n能整除3，或者n的数位中有3，则输出“YES”，否则输出“NO”。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
bool is3(long long n)//判断n中有没有3
{
while (n)
{
if ((n % 10) == 3) return true;
n /= 10;
}
return false;
}
int main()
{
int n;
cin >> n;
if (!(n % 3) || is3(n)) puts("YES");//判断有没有3或是不是3的倍数
else puts("NO");
return 0;
}
E题：
题面：
[ABC006A] 世界のFizzBuzz
题面翻译
输入一个整数n,如果n能整除3，或者n的数位中有3，则输出“YES”，否则输出“NO”。
代码：
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <array>
#include <ctime>
#include <cstring>
#define endl "\n"
#define ture true;
#define flase false;
using namespace std;
typedef long long LL;
const LL N = 100008, mod = 1e9 + 7;
LL n, k, a[N], fac[N], ans = 0;
//a ^ k % p
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}
return res;
}
LL inv(LL x, LL p) //求x关于模p的逆元
{
return qmi(x, p - 2, p) % mod;
}
LL C(LL a, LL b)//直接用逆元求解组合数C(a, b)
{
return fac[a] * inv(fac[b], mod) % mod * inv(fac[a - b], mod) % mod;
}
int main()
{
scanf("%lld%lld", &n, &k);
for (LL i = 1; i <= n; i++) scanf("%lld", &a[i]);
fac[0] = 1;
for (LL i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
sort(a + 1, a + n + 1); //升序排序
for (LL i = k; i <= n; i++) //算一遍最大值
{
ans = (ans + a[i] * C(i - 1, k - 1) % mod) % mod;
}
for (LL i = 1; i <= n - k + 1; i++) //算一遍最小值
{
ans = (ans - a[i] * C(n - i, k - 1) % mod) % mod;
}
cout << (ans % mod + mod) % mod << endl;
return 0;
}
