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}\)可组成的方案个数为:
-
当第二个点位于第\(j\)列上,第三个点位于第\(i\)行上时:
第二个点的方案数\(\times\)第三个点的方案数即
(col[j] - 1) * c[i][j+1] -
当第二个点位于\(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;
}