AtCoder Beginner Contest 273
A - A Recursive Function
Problem Statement
题意:给你一个函数\(f(x)\)
- \(f(0)=1\)
- 对于所有正整数\(k\),有\(f(k) = k*f(k-1)\)
找到\(f(N)\)
Solution
思路:数据范围只有\(10\),直接递归。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll n)
{
if(n==0)return 1;
return n*f(n-1);
}
int main()
{
ll n;
cin>>n;
cout<<f(n)<<endl;
return 0;
}
B - Broken Rounding
Problem Statement
题意:给你一个非负整数\(X\),求对\(X\)进行以下操作\(K\)次的结果
操作:对数字\(X\)按\(10^i\)进行四舍五入操作。
比如:\(273\)按照\(10^2\)四舍五入就是\(300\),\(273\)按\(10^1\)四舍五入就是\(270\)
Solution
思路:先变成小数,对其进行保留到整数位的四舍五入,在乘回来。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll x;
int k;
cin>>x>>k;
ll r = 1;
for(int i = 1;i<=k;i++)
{
r*=10;
x = round(x/(long double)r)*r;
}
cout<<x<<endl;
return 0;
}
C - (K+1)-th Largest Number
Problem Statement
题意:你有一个序列 \(A = (A_1, A_2 , \ ..., A_n)\) ,你需要求有多少个数满足 \(A\) 中有 \(k\) 个不同的数 \(\geq\) \(a_i\) \((i \in [1, n])\)
Solution
思路:sort+二分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
int a[N];
vector<int>v;
map<int,int>mp;
int main()
{
int n;
cin>>n;
for(int i = 1;i<=n;i++)
cin>>a[i],v.push_back(a[i]);
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
int m = v.size();
for(int i = 1;i<=n;i++)
{
int pos = lower_bound(v.begin(), v.end(),a[i])-v.begin();
mp[max(0,m-pos-1)]++;
}
for(int i = 0;i<n;i++)
cout<<mp[i]<<endl;
return 0;
}
D - LRUD Instructions
Problem Statement
题意:你有一个\(n\times m\) 的矩阵,矩阵上有 \(N\) 个障碍物,现在给你 \(Q\)次询问,问向 \(R_i\) 的方向走 \(C_i\)步到哪里了。 前一步能影响后一步,障碍物不能越过,不能走出边界。
Solution
思路:首先很明显直接模拟肯定T,那么我们对于一个点需要快速知道离每个方向它最近的的一个障碍物的位置,可以用\(map<ll,set<ll>>\)来快速查找。因为数据范围\(1e9\),需要离散化一下。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,x,y;
map<ll,set<ll>>dx,dy;
int main()
{
cin>>n>>m>>x>>y;
int N;
cin>>N;
for(int i = 1;i<=N;i++)
{
ll xx,yy;
cin>>xx>>yy;
dx[xx].insert(yy);
dy[yy].insert(xx);
}
for(auto &i:dx)
{
i.second.insert(0);
i.second.insert(m+1);
}
for(auto &i:dy)
{
i.second.insert(0);
i.second.insert(n+1);
}
int q;
cin>>q;
for(int i = 1;i<=q;i++)
{
char op;
ll k;
cin>>op>>k;
if(op=='L')
{
ll nxt_y = y-k;
if(dx.find(x)==dx.end())
y = max(nxt_y,1ll);
else
{
auto it = dx[x].lower_bound(y);
it = prev(it);
//cout<<"*it + 1 = "<<*it+1<<" nxt_y = "<<nxt_y<<endl;
y = max(*it+1,nxt_y);
}
}
else if(op=='R')
{
ll nxt_y = y+k;
if(dx.find(x)==dx.end())
y = min(nxt_y,(ll)m);
else
{
auto it = dx[x].lower_bound(y);
//cout<<"*it - 1 = "<<*it-1<<" nxt_y = "<<nxt_y<<endl;
y = min(*it-1,nxt_y);
}
}
else if(op=='U')
{
ll nxt_x = x-k;
if(dy.find(y)==dy.end())
x = max(nxt_x,1ll);
else
{
auto it = dy[y].lower_bound(x);
it = prev(it);
x = max(*it+1,nxt_x);
}
}
else
{
ll nxt_x = x+k;
if(dy.find(y)==dy.end())
x = min(nxt_x,(ll)n);
else
{
auto it = dy[y].lower_bound(x);
x = min(*it-1,nxt_x);
}
}
cout<<x<<" "<<y<<endl;
}
return 0;
}
- Beginner AtCoder Contest ABCD 273beginner atcoder contest abcd beginner atcoder contest 273 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 332 beginner atcoder contest 328