ABC330 A-E 题解

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

ABC330题解

AtCoder Beginner Contest 330

A - Counting Passes

思路:

枚举一遍,当前数大于\(L\)使\(ans+1\)即可.

代码:

#include<iostream>
#define int long long
using namespace std;
		
int n, l, ans;
int x;
		
signed main()
{
	cin >> n >> l;
	for(int i=1; i<=n; i++)
	{
		cin >> x;
		if(x >= l)
		{
			ans ++;
		}
	}
	cout << ans;
	return 0;
}

B - Minimize Abs 1

思路:

枚举一遍,当前数在\(L,R\)之间,结果就是它本身,小于\(L\)\(L\),大于\(R\)\(R\).

代码:

#include<iostream>
#define int long long
using namespace std;

int n, l, r;
int x;

signed main()
{
	cin >> n >> l >> r;
	for(int i=1; i<=n; i++)
	{
		cin >> x;
		if(x <= l)
		{
			cout << l << " ";
			continue;
		}
		if(x >= r)
		{
			cout << r << " ";
			continue;
		}
		cout << x << " ";
	}
	return 0;
}

C - Minimize Abs 2

思路:

枚举\(i:0\sim\sqrt{d}\)为第一个数,以\(1\)为左边界,\(\sqrt{d-i^2}+1\)为右边界,判定条件为\(mid^{2}\)\(d-i^2\)之间的大小关系,每次更新边界后\(ans=\min{ans, |d-i^2-mid^2|}\)为条件二分查找第二个数.

其中\(d-i^2\)为当前的\(i\)下剩余\(d\)的大小,\(mid\)为当前的第二个数\((mid > i)\)

特判:当\(mid^2=d-i^2\)时直接输出\(0\).

代码:

#include<iostream>
#include<cmath>
#define int long long
using namespace std;

int abss(int x)
{
	return x > -x ? x : -x;
}

int d, ans = 1e18;
int t, l, r, mid;

signed main()
{
	cin >> d;
	for(int i=0; i*i<d; i++)
	{
		t = d - i*i;
		l = 1;
		r = sqrt(t) + 1;
		while(l <= r)
		{
			mid = (l + r) >> 1;
			if(mid * mid < t)
			{
				l = mid + 1;
			}
			else if(mid * mid > t)
			{
				r = mid - 1;
			}
			else
			{
				cout << 0;
				return 0;
			}
			ans = min(ans, abss(t - mid * mid));
		}
	}
	cout << ans;
	return 0;
}

D - Counting Ls

思路:

由于元组的无序性,仅顺序不同的元组会被视为同一个元组,所以我们只统计每个\(\text{o}\)能和后面的\(\text{o}\)组成合法元组的个数.

只统计第2、3点在第1点右方、下方的方案,忽略左方、上方的点

设:
\(row_i\)表示第\(i\)\(\text{o}\)的个数
\(col_i\)表示第\(i\)\(\text{o}\)的个数
\(b_{i,j}\)表示第\(i\)行中第\(j\)列后每个\(\text{o}\)所在列在第\(i\)行往下\(\text{o}\)的个数总和
\(c_{i,j}\)表示第\(i\)行中第\(j\)列后\(\text{o}\)的个数总和

则第\(i\)行第\(j\)列的\(\text{o}\)可组成的方案个数为:

  1. 当第二个点位于第\(j\)列上,第三个点位于第\(i\)行上时:
    第二个点的方案数\(\times\)第三个点的方案数

    (col[j] - 1) * c[i][j+1]

  2. 当第二个点位于\(i,j_2\),第三个点位于第\(j_2\)列上时:
    每个第二个点所对应的第三个点的方案数总和

    b[i][j+1]

将它们加起来,最后输出即可

代码:

#include<iostream>
#define int long long
using namespace std;

int n, ans;
bool a[2010][2010];
int row[2010], col[2010];
int b[2010][2010]; //第i行第j列每列的o后缀和
int c[2010][2010]; //第i行第j列的o后缀和

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	char ch;
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			cin >> ch;
			a[i][j] = (ch == 'o');
			row[i] += a[i][j];
		}
	}
	for(int j=1; j<=n; j++)
	{
		for(int i=1; i<=n; i++)
		{
			col[j] += a[i][j];
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=n; j>=1; j--)
		{
			b[i][j] = b[i][j+1];
			c[i][j] = c[i][j+1];
			if(a[i][j])
			{
				b[i][j] += col[j] - 1;
				c[i][j] += 1;
			}
		}
	}
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(a[i][j])
			{
				ans += (col[j] - 1) * c[i][j+1];
				ans += b[i][j+1];
			}
		}
	}
	cout << ans;
	return 0;
}

E - Mex and Update

思路:

\(\large STL大法好\)

因为\(A\)数组最多有\(2\times10^5\)个数,所以输出的答案必定小于\(2\times10^5\)

所以\(Mex\)可以转化为:一个存储了\(1\sim2\times10^5\)所有数的数组,去掉\(A\)数组中的数,剩下数中的最小值

有序数组,无需插入,删除,\(\Theta(n\log{n})\),可以使用\(map\),先在\(map\)里存储\(1\sim2\times10^5\)所有数,再设\(cnt_i\)表示\(map\)去掉\(A\)之后剩下的每个数的数量(同样只需要存储\(1\sim2\times10^5\))

在输入时

  • cnt[y]--;,如果cnt[y] < 0,那么s.erase(y);
  • cnt[a[x]]++;,如果cnt[a[x]] >= 0,那么s.insert(a[x]);
  • a[x]=y;

再输出*s.begin()即可文章来源地址https://www.toymoban.com/news/detail-747207.html

代码:

#include<iostream>
#include<set>
#define int long long
using namespace std;

const int N = 200010;

int n, m;
int cnt[N], a[N];
set<int> s;

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i=0; i<=n; i++)
	{
		s.insert(i);
	}
	for(int i=1; i<=n; i++)
	{
		cin >> a[i];
		if(a[i] > N-10)
		{
			continue;
		}
		cnt[a[i]]--;
		s.erase(a[i]);
	}
	while (m--)
	{
		int x, y;
		cin >> x >> y;
		if(y <= 2e5)
		{
			cnt[y]--;
			if(cnt[y] < 0)
			{
				s.erase(y);
			}
		}
		if(a[x] <= 2e5)
		{
			cnt[a[x]]++;
			if(cnt[a[x]] >= 0) 
			{
				s.insert(a[x]);
			}
		}
		a[x] = y;
		cout << *s.begin() << '\n';
	}
	return 0;
}

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

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

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

相关文章

  • AtCoder Beginner Contest 292 (A - E) 记录第一场ABC

    本来晚上在打Acwing周赛,最后一题Trie想不出来咋写,看群里有人说ABC要开始了,想着没打过ABC就去报了一下,感觉难度大概是cf的Div3到Div4之间吧,总共写了五个题,E题想复杂了快结束才交过。总的来说手速很重要。 题意:给一个字符串,要求把小写字母改成大写。 分析:

    2023年04月19日
    浏览(32)
  • AtCoder Beginner Contest 317 题解 ABCDE | JorbanS

    题意 求权值和最大的一条路径 Tag dfs 题意 n × m n×m n × m 的迷宫, . 代表可以走, # 代表障碍物, ^v 代表射线,射线方向不能走,知道射线遇到非 . 的格子,求最短路 Tag bfs

    2024年02月10日
    浏览(36)
  • AtCoder Beginner Contest 336 C - Even Digits题解

    Time Limit: 2 sec / Memory Limit: 1024 MB Score: 300300 points Problem Statement A non-negative integer �n is called a  good integer  when it satisfies the following condition: All digits in the decimal notation of �n are even numbers (00, 22, 44, 66, and 88). For example, 00, 6868, and 20242024 are good integers. You are given an integer 

    2024年01月20日
    浏览(53)
  • AtCoder Beginner Contest 302 H. Ball Collector 题解

    为了更好的阅读体验,请单击这里 AtCoder Beginner Contest 302 H. Ball Collector 题意跳过。 可以视作将 (a_i, b_i) 之间连了一条边,然后 (a_i, b_i) 之间只能选一个等价于对于一条边只能选择其一个端点。那么对于只包含树的联通块而言,如果都选择儿子节点,那么会有一个根节点无

    2024年02月06日
    浏览(39)
  • Atcoder Beginner Contest 324 G Generate Arrays 题解-Treap

    为了更好的阅读体验,请点击这里 题目链接 套上平衡树板子就能做的很快的题,然后因为是指针存树,因此交换只需要把序列大小较小的挨个拿出来插到相应的地方即可。复杂度 (O(N log^2 N)) 。 但是一定要记住 不可以直接使用 std::swap 交换包含带有指针的类的实例(如代码

    2024年02月08日
    浏览(44)
  • Atcoder Beginner Contest 324 F Beautiful Path 题解-分数规划

    为了更好的阅读体验,请点击这里 分数规划小技巧: 尽可能将式子写成存在某种取值,使得不等式成立的形式。 不然可能需要绕几个弯才能想出来。 题目链接 题目大意:给出一个 DAG,每条边有一个 (b_i, c_i) ,保证从编号小的边向编号大的边连边,且 (1) 到 (n) 必有路径

    2024年02月08日
    浏览(39)
  • Atcoder beginner contest 336 -- E -- Digit Sum Divisible --- 题解(数位dp)

    目录   E -- Digit Sum Divisibl 题目大意: 思路解析: 代码实现: 给你一个整数n,让你找出小于等于n的数中一共有多少个好整数,并输出好整数的个数。对好整数的个数定义为如果一个数能被他的数位之和整除,则称这个数为好整数。例如 12 能被 3 整除。 n=10^14。 看到数位之和

    2024年01月16日
    浏览(65)
  • AtCoder Beginner Contest 302 H. Ball Collector 题解 可撤销并查集

    为了更好的阅读体验,请单击这里 AtCoder Beginner Contest 302 H. Ball Collector 题意跳过。 可以视作将 (a_i, b_i) 之间连了一条边,然后 (a_i, b_i) 之间只能选一个等价于对于一条边只能选择其一个端点。那么对于只包含树的联通块而言,如果都选择儿子节点,那么会有一个根节点无

    2024年02月06日
    浏览(35)
  • Atcoder Beginner Contest 321 G - Electric Circuit 题解 - 状压dp | 指定最低位

    为了更好的阅读体验,请点击这里 题目链接:G - Electric Circuit 看到了 (N) 的数据范围,因此是显然的状压 dp。 不妨设 (f_S) 为仅使用 (S) 集合中的所有点,能够连成恰好 (1) 个连通块的方案数。 (g_S) 为仅使用 (S) 集合中的所有点的方案数,其中 (cntr(S)) 在 (S) 中为

    2024年02月05日
    浏览(54)
  • AtCoder Beginner Contest 310

    感觉F又双叒叕写复杂了 点杯咖啡,要 (p) 元,但可以用一个优惠券,使得咖啡只要 (q) 元,但你需要额外购买 (n) 个商品中(价格为 (a_i) )的一个。 问点杯咖啡的最小价格。 考虑直接买还是使用优惠券,使用优惠券的话就选 (n) 个商品中价格最小的。 两种情况取最小

    2024年02月16日
    浏览(28)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包