AtCoder Beginner Contest 254 A~E 题解

待更……

ABC254 A~E

• [A - Last Two Digits](https://atcoder.jp/contests/abc254/tasks/abc254_a)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码
• [B - Practical Computing](https://atcoder.jp/contests/abc254/tasks/abc254_b)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • • 样例输入1
    • 样例输出1
    • 样例输入2
    • 样例输出2
  • 分析
  • 代码
• [C - K Swap](https://atcoder.jp/contests/abc254/tasks/abc254_c)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码
• [D - Together Square](https://atcoder.jp/contests/abc254/tasks/abc254_d)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码
• [E - Small d and k](https://atcoder.jp/contests/abc254/tasks/abc254_e)
• • 题目大意
  • 输入格式
  • 输出格式
  • 样例
  • 分析
  • 代码

A - Last Two Digits 题目大意

给定正整数 N N N，求 N N N的后两位。
100 ≤ N ≤ 999 100\le N\le 999 100≤N≤999

输入格式

N N N

输出格式

输出 N N N的后两位，注意输出可能有前导0。

样例

N N N	输出
254 254 254	54
101 101 101	01

分析

题目已经规定 N N N是三位数，因此无需使用整数输入，直接将输入看成字符串，输出后两位即可。

代码

#include 
using namespace std;

int main()
{
	getchar();
	putchar(getchar());
	putchar(getchar());
	return 0;
}

---

B - Practical Computing 题目大意

输出 N N N个整数序列 A 0 , … , A N − 1 A_0,\dots,A_{N-1} A0​,…,AN−1​。它们按如下定义：

• A i A_i Ai​的长为 i + 1 i+1 i+1。
• A i A_i Ai​的第 j + 1 j+1 j+1个元素记为 a i , j a_{i,j} ai,j​（ 0 ≤ j ≤ i < N 0\le j\le i0≤j≤i<N），即：
  • 当 j = 0 j=0 j=0或 j = i j=i j=i时， a i , j = 1 a_{i,j}=1 ai,j​=1；
  • 否则， a i , j = a i − 1 , j − 1 + a i − 1 , j a_{i,j}=a_{i-1,j-1}+a_{i-1,j} ai,j​=ai−1,j−1​+ai−1,j​。

1 ≤ N ≤ 30 1\le N\le 30 1≤N≤30

输入格式

N N N

输出格式

输出 N N N行。第 i i i行上有 A i − 1 A_{i-1} Ai−1​中的 i i i个数，用空格分隔。

样例 样例输入1

3

样例输出1

1
1 1
1 2 1

样例输入2

10

样例输出2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

分析

其实不用读题，看一眼样例，是不是很眼熟？没错，就是著名的杨辉三角。
不知道也没关系（不过应该也没人不知道），直接按题目要求（ i , j i,j i,j正序）依次计算即可。时间复杂度 O ( n 2 ) \mathcal O(n^2) O(n2)，空间复杂度 O ( n ) \mathcal O(n) O(n)或 O ( n 2 ) \mathcal O(n^2) O(n2)。详见代码 1 , 2 1,2 1,2。

继续考虑，杨辉三角中 a i , j = C j i a_{i,j}=C_j^i ai,j​=Cji​，所以可以用 O ( 1 ) \mathcal O(1) O(1)的空间计算，时间不变，代码待会补。

代码

• 代码 1 1 1（普通方法+无优化+cin/cout， 6 ms  1656 KB 6\text{ms}~1656\text{KB} 6ms 1656KB）
  时间： O ( n 2 ) \mathcal O(n^2) O(n2)
  空间： O ( n 2 ) \mathcal O(n^2) O(n2)
  难度：低

  #include 
  using namespace std;
  
  int arr[35][35];
  
  int main()
  {
     int n;
     cin >> n;
     for (int i = 0; i < n; i++)
     {
         arr[i][0] = 1;
         arr[i][i] = 1;
     }
     for (int i = 2; i < n; i++)
     {
         for (int j = 1; j < i; j++)
         {
             arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
         }
     }
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j <= i; j++)
         {
             cout << arr[i][j] << " ";
         }
         cout << endl;
     }
     return 0;
  }
  

• 代码 2 2 2（普通方法+滚动表+scanf/printf， 6 ms  1656 KB 6\text{ms}~1656\text{KB} 6ms 1656KB）
  时间： O ( n 2 ) \mathcal O(n^2) O(n2)
  空间： O ( n ) \mathcal O(n) O(n)
  难度：中低

  #include 
  using namespace std;
  
  int a[35];
  
  int main()
  {
     int n;
     scanf("%d", &n);
     a[0] = 1, puts("1");
     for(int i=1; i<n; i++)
     {
     	putchar('1');
     	for(int j=i-1; j>0; j--)
     		a[j] += a[j - 1];
     	for(int j=1; j<i; j++)
             printf(" %d", a[j]);
         a[i] = 1, puts(" 1");
     }
     return 0;
  }
  

---

C - K Swap 题目大意 输入格式 输出格式 样例 分析 代码

#include 
#include 
#include 
#define maxn 200005
using namespace std;

int a[maxn], b[maxn];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i=0; i<n; i++)
	{
		scanf("%d", a + i);
		b[i] = a[i];
	}
	sort(b, b + n);
	for(int i=0; i<k; i++)
	{
		multiset<int> s1, s2;
		for(int j=i; j<n; j+=k)
		{
			s1.insert(a[j]);
			s2.insert(b[j]);
		}
		if(s1 != s2)
		{
			puts("No");
			return 0;
		}
	}
	puts("Yes");
	return 0;
}

---

D - Together Square 题目大意 输入格式 输出格式 样例 分析 代码

#include 
using namespace std;

inline int gcd(int a, int b)
{
	while(b ^= a ^= b ^= a %= b);
	return a;
}

int main()
{
	int n = 0; char c;
	while((c = getchar()) != '\n')
		n = (n << 3) + (n << 1) + (c ^ 48);
	int t = __builtin_sqrt(n);
	long long ans = 0LL, x;
	for(int i=1; i<=t; i++)
		for(int j=i; j<=t; j++)
			if(gcd(i, j) == 1)
			{
				ans += (x = n / (i > j? i * i: j * j));
				if(i != j) ans += x;
			}
	printf("%lld\n", ans);
	return 0;
}

---

E - Small d and k 题目大意 输入格式 输出格式 样例 分析

注意这题数据范围，这是解体的关键，只有 0 ≤ k ≤ 3 0\le k\le 3 0≤k≤3，且顶点度数   ≤ 3 ~\le3  ≤3，因此根据乘法原理，一次查询最大符合条件的顶点数为 3 3 + 1 = 28 3^3+1=28 33+1=28个。因此，使用简单的暴力 BFS \text{BFS} BFS即可通过。详见代码。

代码

注意dis数组的清零 *** 作，无需全部清零，只需把刚刚改过的清零即可。

#include 
#include 
#define maxn 150005
using namespace std;

vector<int> G[maxn];
int dis[maxn];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int Q; scanf("%d", &Q);
	for(int i=1; i<=n; i++) dis[i] = -1;
	while(Q--)
	{
		int x, k;
		scanf("%d%d", &x, &k);
		vector<int> ans;
		queue<int> q;
		q.push(x);
		dis[x] = 0;
		while(!q.empty())
		{
			int v = q.front(); q.pop();
			int d = dis[v];
			if(d <= k) ans.push_back(v);
			if(++d > k) continue;
			for(int u: G[v])
				if(dis[u] == -1)
				{
					dis[u] = d;
					q.push(u);
				}
		}
		int res = 0;
		for(int v: ans)
			res += v, dis[v] = -1;
		printf("%d\n", res);
	}
	return 0;
}