ABC341A-D题解

这篇具有很好参考价值的文章主要介绍了ABC341A-D题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

A

题目

这个没什么好说的,就先输出一个 1,再输出 n n n01就大功告成了。

AC Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cout << 1;
	for (int i = 1; i <= n; i ++) cout << "01";
	return 0;
}

B

题目

要获取更多 x x x 国货币,只能用 x − 1 x - 1 x1 国货币换。
所以我们可以从 1 1 1 国一直换到 n n n 国,输出,结束。

AC Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int n;
long long a[200100];
int s[200100], t[200100];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i ++) cin >> a[i];
	for (int i = 1; i < n; i ++) cin >> s[i] >> t[i];
	for (int i = 1; i < n; i ++) {
		a[i + 1] += t[i] * (a[i] / s[i]);
	}
	cout << a[n];
	return 0;
}

C

题目

你会发现, 50 0 3 < 2 ⋅ 1 0 8 500^3<2\cdot10^8 5003<2108,所以可以暴力枚举高桥所在的位置,如果他行进的过程中没有经过海洋就将答案加一。如果经过海洋了就直接枚举下一个点。

AC Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
int h, w, n;
char m[510][510];
string s;
map<char, int> dir;
int dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0};
int ans;
bool check(int x, int y) {
	for (int i = 0; i < n; i ++) {
		int nx = x + dx[dir[s[i]]], ny = y + dy[dir[s[i]]];
		if (nx > 0 && nx <= h && ny > 0 && ny <= w && m[nx][ny] == '.') {
			x = nx;
			y = ny;
		}
		else return 0;
	}
	return 1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> h >> w >> n;
	cin >> s;
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) cin >> m[i][j];
	}
	dir['L'] = 0, dir['R'] = 1, dir['U'] = 2, dir['D'] = 3;
	for (int i = 1; i <= h; i ++) {
		for (int j = 1; j <= w; j ++) {
			if (m[i][j] == '.') {
				ans += check(i, j);
			}
		}
	}
	cout << ans;
	return 0;
}

D

题目

这个题并不难,但是细节很多,仔细看!我因为一些零碎的细节卡了 40min!

首先,我们先讨论那些“有规律”的部分。我们发现,对于两个数 n n n m m m,在 n m nm nm 范围内有 n + m − 2 × gcd ⁡ ( n , m ) n + m - 2\times\gcd(n, m) n+m2×gcd(n,m) 个数满足只被 n n n m m m 中的一个数字整除。

这个结论怎么来的呢?

首先,对于可以被 n n n 整除的一共有 n m n \frac{nm}{n} nnm m m m 个,可以被 m m m 整除的一共有 n m m \frac{nm}{m} mnm n n n 个。

那么 − 2 × gcd ⁡ ( n , m ) -2\times\gcd(n, m) 2×gcd(n,m) 又是怎么来的呢?

首先, n m nm nm 范围内有 n m n m gcd ⁡ ( n , m ) \frac{nm}{\frac{nm}{\gcd(n, m)}} gcd(n,m)nmnm 个数即 gcd ⁡ ( n , m ) \gcd(n,m) gcd(n,m) 个数可以被 n n n m m m 整除。我们要在可以被 n n n 整除的部分减去它,还要在可以被 m m m 整除的部分减去它。所以是 − 2 × gcd ⁡ ( n , m ) -2\times\gcd(n,m) 2×gcd(n,m)

然后我们就可以将答案直接跳到 n m ( k / ( n + m − 2 gcd ⁡ ( n , m ) ) ) nm(k/(n + m - 2\gcd(n, m))) nm(k/(n+m2gcd(n,m))),此时 k k k 变成 k m o d    ( n + m − 2 gcd ⁡ ( n , m ) ) k \mod (n + m - 2\gcd(n, m)) kmod(n+m2gcd(n,m))

我们继续讨论,可以枚举,用 k 1 k1 k1 k 2 k2 k2 两个变量依次跳到答案。如果 k 1 k1 k1 跳的远就跳 k 2 k2 k2,否则跳 k 1 k1 k1。如果两个跳的一样远就都跳依次,这两次不算在跳的次数内。一共跳 k k k 次后,较大的就是满足条件的,加到答案上即可。

你以为这就完了?

如果减掉前面“有规律”的部分后,发现 k k k 等于 0 0 0 时,不加任何特判会输出一个 n m nm nm 的倍数的数。但是我们要的是最大的比上述不合法答案小的答案。此时如果我们把 k k k 设为 n + m − 2 gcd ⁡ ( n , m ) n+m-2\gcd(n, m) n+m2gcd(n,m),答案减去 n m nm nm 就可以解决这个问题。

还有一个很重要的东西:long long

时间复杂度分析:

按最坏情况来说, gcd ⁡ ( n , m ) = 1 \gcd(n, m)=1 gcd(n,m)=1,此时时间复杂度就是 n + m n+m n+m,而且跑不到这么多,所以执行次数不会超过 2 ⋅ 1 0 8 2\cdot10^8 2108,合格。

AC Code:

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <list>
#include <set>
#include <map>
using namespace std;
long long n, m, k;
long long gcd(long long x, long long y) {
	return x % y == 0ll ? y : gcd(y, x % y);
}
long long ans;
long long cnt;
long long cnt1;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k;
	long long g = gcd(n, m);
	ans = n * m * (k / (n + m - g * 2));
	k = k % (n + m - g * 2);
	if (k == 0) {
		ans -= n * m;
		k += n + m - g * 2;
	}
	long long k1 = 0ll, k2 = 0ll;
	cnt1 = 0ll;
	for (long long i = 1; i <= k; i ++) {
		if (k1 + n < k2 + m) {
			k1 += n;
		}
		else if (k1 + n > k2 + m) {
			k2 += m;
		}
		else {
			k1 += n;
			k2 += m;
			i--;
		}
	}
	ans += max(k1, k2);
	cout << ans;
	return 0;
}

E

什么,不是 A-D题解吗?怎么还有 E?

我才不会给出详细的解法的,我只给一个小小的提示:懒标线段树!文章来源地址https://www.toymoban.com/news/detail-826816.html

到了这里,关于ABC341A-D题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [AGC055A] ABC Identity 题解

    给定长度为 (3n (1 le n le 2e5)) 的序列,其中字母 A,B,C 各有 (n) 个。 一个合法序列 (T) 满足以下条件: 其长度为 (3k (1 le k le n)) 。 (T_1 = T_2 = ... = T_k) (T_{k + 1} = T_{k + 2} = ... = T_{2k}) (T_{2k + 1} = T_{2k + 2} = ... = T_{3k}) (T_1, T_{k + 1}, T_{2k + 1}) 互不相同。 求一个把这个序列分

    2024年02月08日
    浏览(49)
  • [AGC055B] ABC Supremacy 题解

    给定两个长度为  (n)  的字符串  (a) , (b) 。 你可以进行若干次以下操作: 若  (a)  中的一个 子串 为  ABC , BCA  或  CAB ,那么可以将这个子串替换为  ABC , BCA  或  CAB 。 求能否将  (a)  变成  (b) ,输出  YES  或  NO 。 不难发现,我们可以根据一些变换将 A

    2024年02月08日
    浏览(37)
  • [ABC318C] Blue Spring 题解

      主人公出去旅游要买票,共有若干天,每天要花不同钱。现在有“通行证”出售,通过购买通行证,可以在某一天直接用通行证,以此来省去当天原本需要花费的票价。通行证只能一套一套买,每套中有 (D) 个,买一套要花费 (P) 元。可以购买任意套数的通行证,求怎

    2024年02月10日
    浏览(41)
  • 题解:ABC320B - Longest Palindrome

    链接:Atcoder。 链接:洛谷。 算法难度:C。 思维难度:C。 调码难度:C。 综合评价:入门。 字符串处理。 通过双层循环分别枚举第一个字符和最后一个字符遍历每个子串,在分别判断是否为回文串,在所有是回文串的里面取长度最大值。 O(|s|2)。 字符串截取用substr函数。

    2024年02月07日
    浏览(41)
  • [ABC347C] Ideal Holidays题解

    原题传送门 原题传送门(洛谷) ​题意翻译: ​在 (AtCoder) 王国中,一个周有 (A+B) 天。其中在一周中, ([1,A]) 天是假日, ([A+1,B]) 天是工作日。 ​高桥有 (N) 个计划,第 (i) 个计划安排在 (i) 天后。他不知道今天是周几,但他想知道是否能将计划都安排在假期中;

    2024年04月08日
    浏览(45)
  • AtCoder abc336 A~D题解

    题目翻译: 对于正整数 X X X 级别的龙串, X X X 是长度为 ( X + 3 ) (X+3) ( X + 3 ) 的字符串,由按此顺序排列的 o 、 n 和 g 的一次 L 、 X X X 次出现形成。 你得到一个正整数 N N N 。打印 N N N 级的龙串。 分析 按题目要求做即可……,输出一个 L ,循环 X X X 次输出 o ,再输出 ng 。

    2024年01月15日
    浏览(39)
  • AT_abc344_d 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 你最开始有一个空字符串 (S) 。 你还有编号为 (1, 2, dots, N) 的袋子,每个袋子都包含一些字符串。 袋子 (i) 包含 (A_i) 个字符串 (S_{i,1}, S_{i,2}, dots, S_{i,A_i}) 。 对 (i = 1, 2, dots, N) 重复以下步骤 仅一次 (这里原题没有讲清楚

    2024年03月10日
    浏览(50)
  • AT_abc345_d 题解

    本文同步发表于洛谷。 是个逆天搜索。 最开始:爆搜,启动! 然后 TLE 到飞起。 赛后:我【数据删除】这么简单的吗?! dfs 每个位置,试着把没放过的块放到以这个位置为左上角的区域里面。 好了没了,就是这么简单! 对了记得这个块可以旋转!

    2024年03月21日
    浏览(44)
  • AT_abc344_e 题解

    本文同步发表于洛谷。 赌狗天天输的一集。 赛时各种【数据删除】原因导致没做出来。 给你一个长度为 (N) 的序列 (A=(A_1,ldots,A_N)) 。保证 (A) 中的元素是不同的。 你要处理 (Q) 个操作。每个操作是以下两种类型之一: 1 x y :在 (A) 中元素 (x) 后面紧接着插入 (y) 。

    2024年03月13日
    浏览(42)
  • [ABC318D] General Weighted Max Matching 题解

      给定无向有权完全图,求最大权匹配。   注意到 (n le 16) ,我考虑状压 DP。   设当前点集 (S) 中最大权匹配的答案是 (f_S) ,我们考虑 (S) 中“最后”一个点 (p) (这里的“最后”一个点是指,在状压表示状态的时候,最后一个 1 所代表的那个点,只需从这个点

    2024年02月10日
    浏览(33)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包