AtCoder_abc330
A - Counting Passes
题目大意
给出$N$个数$a_1,a_2,a_3\cdots,a_N$，和一个正整数$L$。输出有几个$a_i \le L$.
解题思路
O(n)遍历一遍就好了
代码
// Problem: A - Counting Passes
// Contest: AtCoder - TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
// URL: https://atcoder.jp/contests/abc330/tasks/abc330_a
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
int n,l,cnt;
int main(){
cin>>n>>l;
for(int i=1;i<=n;i++){
int x;cin>>x;
if(x>=l)cnt++;
}
cout<<cnt;
return 0;
}
B - Minimize Abs 1
题目大意
给出一个长度为$N$的序列（$A=a_1,a_2,a_3,\cdots,a_N$）和两个数$L,R(L \le R)$。
对于每一个$i=1,2,3,N$，都找到一个$X_i$使其满足：
- $L \le X_i \le R$
- 对于每一个$Y(L \le Y \le R)$，都满足$|X_i-a_i| \le |Y-a_i|$
解题思路
题目实际上就是要求$L$~$R$之间与$a_i$差的最小值。分两种情况：
- 如果$L \le a_i \le R$,那么当$X_i$取$a_i$时，差有最小值$0$
- 否则如果$a_i \le L$，那么应该取$L$,如果$a_i \ge R$，那么应该取$R$
代码
// Problem: B - Minimize Abs 1
// Contest: AtCoder - TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
// URL: https://atcoder.jp/contests/abc330/tasks/abc330_b
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
int n,l,r,a;
int main(){
cin>>n>>l>>r;
for(int i=1;i<=n;i++){
cin>>a;
if(a>=l&&a<=r)
cout<<a<<" ";
else if(a<l)
cout<<l<<" ";
else cout<<r<<" ";
}
return 0;
}
C - Minimize Abs 2
题目大意
输入一个$D(1 \le D \le 2 \times 10{12})$，输出$|x2+y^2-D|$的最小值。
解题思路
既然是$x2+y2$,那么$x,y$一定是一个大一个小的(废话)，那么我们可以while()枚举那个较大的数，然后二分查找另一个数，使得当较大的数一定时$|x2+y2-D|$最小。最后输出所有结果中最小的那一个就好。
代码
// Problem: C - Minimize Abs 2
// Contest: AtCoder - TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
// URL: https://atcoder.jp/contests/abc330/tasks/abc330_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
long long d;
long long ans=2e12+1;
int main(){
cin>>d;
int i=0;
while(i*i<=d){
long long t=i+1;
long long l=0,r=i+1;
while(l+1!=r){
long long mid=(l+r)/2;
if(mid*mid+t*t<d)
l=mid;
else
r=mid;
}
ans=min(ans,min(abs(l*l+t*t-d),abs(r*r+t*t-d)));
i++;
}
cout<<ans;
return 0;
}
D - Counting Ls
题目大意
给出一个$N(2 \le N \le 2000)$和一个$N \times N$的，由ox组成的矩阵，求有多少三个一组的点满足以下几个要求：
- 三个点互不重合
- 三个点上都是o
- 其中两个点在同一行
- 其中两个点在同一列
解题思路
用$hang[],lie[]$记录下每一行，每一列各有多少个o，那么对于点$(i,j)$，以该点为顶点（另完两个点要么与其在同一行，要么与其在同一列），能组成的组数就为$(hang[i]-1)\cdot(lie[j]-1)$，-1是为了排除自己。
代码
// Problem: D - Counting Ls
// Contest: AtCoder - TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
// URL: https://atcoder.jp/contests/abc330/tasks/abc330_d
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
int n;
long long ans;
int h[2003],l[2003];
char mp[2003][2003];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>mp[i][j];
if(mp[i][j]=='o')
h[i]++,l[j]++;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(mp[i][j]=='o')
ans+=(h[i]-1)*(l[j]-1);
}
}
cout<<ans;
return 0;
}
E - Mex and Update
第一次做出E题留念
题目大意
给出一个长度为$N$的序列$A$,和$Q$次询问。第$k$次询问包括两个数：$i_k,x_k$，请把$a_{i_k}$改为$x_k$，执行完每次询问后，请输出最大的，不在序列中的非负整数
解题思路
因为$N \le 2 \times 10^5$，所以肯定无法完全覆盖$0$ ~ $2 \times 10^5+1$，这样一来就只需要记录这么多数就好了，然后用堆动态记录最小值。
代码
// Problem: E - Mex and Update
// Contest: AtCoder - TOYOTA SYSTEMS Programming Contest 2023(AtCoder Beginner Contest 330)
// URL: https://atcoder.jp/contests/abc330/tasks/abc330_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[300005];
int t[300010];
priority_queue<int,vector<int>,greater<int> >heap;
int main(){
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]<=300005)
t[a[i]]++;
}
for(int i=0;i<=300005;i++)
if(t[i]==0)
heap.push(i);
for(int i=1;i<=q;i++){
int s,x;cin>>s>>x;
if(a[s]<=300005){
t[a[s]]--;
if(t[a[s]]==0)
heap.push(a[s]);
}
a[s]=x;
if(x<=300005)
t[x]++;
while(t[heap.top()]>0)heap.pop();
cout<<heap.top()<<endl;
}
return 0;
}