ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年6月5日 369点热度 5人点赞 0条评论

比赛链接: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: atcoder C++ dfs 图论 思维 排序 数学 算法 算法竞赛 素数 贪心
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • A - Last Two Digits
    • 代码 / Code
  • B - Practical Computing 
    • 代码 / Code
  • C - K Swap
  • D - Together Square
    • 代码 / Code
  • E - Small d and k
    • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号