[AtCoder Beginner Contest 254] A - E（思维 + 数学 + 图论 + dfs）

比赛链接：AtCoder Beginner Contest 254 - AtCoder

各题题目请看原题链接。

A - Last Two Digits

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	int n;cin >> n;
	printf("%02lld\n", n % 100);
	return 0;
}

B - Practical Computing 

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;

int a[50];

signed main()
{
	int N;cin >> N;
	a[1] = 1;
	for(int i = 1; i <= N; ++ i)
	{
		for(int j = i;j >= 1; -- j)a[j] = a[j] + a[j - 1];
		for(int j = 1;j <= i; ++ j)printf("%lld ",a[j]);
		puts("");
	}
	
	return 0;
}

C - K Swap

因为每次只能交换间隔为K的，其实就可以将整个数组分为K个类（组），每个类都是“对K取模相等”的。

比如N = 7，K = 3，那么0 3 6为一组，1 4为一组，2 5为一组。

每一组中，可以按照任意顺序排列，因为可以任意交换位置。

用一点贪心的想法，为了使得整个序列不降序，那么也就是每一组都要不降序，如果当每一组都不降的时候，序列也不降，那么就可以被排列，反之则不行。

可以使用优先队列来维护每一组的最小值，当然你进行K次排序也可以，时间复杂度都一样。

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 2e5 + 9;
int a[maxn];

priority_queue<int, vector<int>, greater<int> > pq[maxn];

bool isok(int K,int N)
{
	for(int i = 0, last = 0;i < N; ++ i)
	{
		int x = pq[i % K].top();pq[i % K].pop();
		if(x < last)return 0;
		last = x;
	}
	return 1;
}

signed main()
{
	int N, K;scanf("%lld %lld", &N, &K);
	for(int i = 0;i < N; ++ i)
	{
		int x;scanf("%lld", &x);
		pq[i % K].push(x);
	}
	printf("%s\n", isok(K, N) ? "Yes" : "No");
	return 0;
}

D - Together Square

这道题卡了我好久。

在做题之前我们需要有个前置知识，假如L * R = 一个平方数，那么对L和R分别质因数分解，其中相同的质因数个数之和应该为偶数。借此，我们可以枚举L，算出最小的R，再算一下能把多少个平方数乘到R里面去，就有多少种方案。

因为一开始L和算出的R保证了相同质因数个数之和为偶数，那么再往R里面乘上平方数，也就是偶数个质因子，可以保证新产生的数字也是平方数，为了保证L,R<=N，所以乘上的平方数是有限的，可以用二分或者直接数学算出来。

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;

vector<int> v;//存放素数 
void initPrimes(int N)
{//求N以内所有素数 
	bitset<maxn> pri;
	pri[0] = pri[1] = 1;
	for(int i = 1;i <= N / i; ++ i)
		if(!pri[i])for(int j = i * i;j <= N; j += i)pri[j] = 1;
	for(int i = 1;i <= N; ++ i)if(!pri[i])v.push_back(i);
}

void solve(int N)
{
	initPrimes(N);
	int ans = 0;
	for(int L = 1;L <= N; ++ L)
	{
		int R = 1, tmp = L;
		for(auto &i : v)
		{
			if(i * i > tmp)break;
			int cnt = 0;
			while(tmp % i == 0)tmp /= i, cnt ^= 1;
			if(cnt & 1)R *= i;
		}
		R *= tmp;
		ans += (int)sqrt(N * 1.0/ R);
	}
	cout << ans << '\n';
}

signed main()
{
	int N;cin >> N;
	solve(N);
	return 0;
}

E - Small d and k

感觉这题比D简单，就是单纯地dfs，但是注意判重不能直接认为“走过的点就不走了”，因为可能出现环，然后导致走过的点后面可能还有可以走的点。

所以判重的规则是res = vis[x] ? 0 : x;

只是走过的点不再计算贡献，但是依然要往下拓展。

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e5 + 9;

vector<int> g[maxn];

int dfs(int dep, int x, int k, bitset<maxn>& vis)
{
	if(dep > k)return 0;
	int res = vis[x] ? 0 : x;//如果走过就不加贡献，但是要往下拓展 
	vis[x] = 1;
	for(auto &i : g[x])res += dfs(dep + 1, i, k, vis);
	return res;
}

signed main()
{
	int N, M;scanf("%d %d", &N, &M);
	while(M --)
	{
		int x, y;scanf("%d %d", &x, &y);
		g[x].pb(y), g[y].pb(x);
	}
	int Q;scanf("%d", &Q);
	while(Q --)
	{
		int x, k;scanf("%d %d", &x, &k);
		bitset<maxn> vis;//这里用vis.reset()也可以，速度也不慢 
		printf("%d\n",dfs(0, x, k, vis));
	}
	return 0;
}