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()即可

代码:

#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;
}

热门相关:离婚合约:前妻的秘密   厨道仙途   龙印战神   全天下都知道太子爱她   觅仙道