[C++知识库]AtCoder Beginner Contest 254 A~E 题解

待更……

A - Last Two Digits

题目大意

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

输入格式

$N$

输出格式

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

样例

分析

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

代码

#include <cstdio>
using namespace std;

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

B - Practical Computing

题目大意

输出$N$个整数序列$A_0,\dots ,A_{N?1}$。它们按如下定义：

• $A_i$的长为$i+1$。
• $A_i$的第$j+1$个元素记为$a_{i,j}$（$0\le j\le i<N$），即：
  • 当$j=0$或$j=i$时，$a_{i,j}=1$；
  • 否则，$a_{i,j}=a_{i?1,j?1}+a_{i?1,j}$。

$1\le N\le 30$

输入格式

$N$

输出格式

输出$N$行。第$i$行上有$A_{i?1}$中的$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$正序）依次计算即可。时间复杂度$\mathcal{O}(n^2)$，空间复杂度$\mathcal{O}(n)$或$\mathcal{O}(n^2)$。详见代码$1,2$。

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

代码

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

  #include <iostream>
  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$（普通方法+滚动表+scanf/printf，$6\text{ms}1656\text{KB}$）
  时间：$\mathcal{O}(n^2)$
  空间：$\mathcal{O}(n)$
  难度：中低

  #include <cstdio>
  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 <cstdio>
#include <set>
#include <algorithm>
#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 <cstdio>
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\le k\le 3$，且顶点度数$\le 3$，因此根据乘法原理，一次查询最大符合条件的顶点数为$3^3+1=28$个。因此，使用简单的暴力$\text{BFS}$即可通过。详见代码。

代码

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

#include <cstdio>
#include <queue>
#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;
}

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系