AtCoder Beginner Contest 273（A~D）
AtCoder Beginner Contest 273（A~D）
浪漫主义狗
发布于 2022-10-28 10:35:45
发布于 2022-10-28 10:35:45
文章被收录于专栏：HAUE_LYS'Blog
A - A Recursive Function
题目大意：
- 求 f(k) 如下： f(0) = 1; f(k) = k \times f(k - 1)
思想：
- 签到题。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
LL f(LL n){
if(n == 0) return 1;
else return n * f(n - 1);
}
void solve(){
LL n; cin >> n;
cout << f(n) << endl;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}B - Broken Rounding
题目大意：
- 给定一个整数 x，可以进行 k 次操作。
- 每次将 x 改为一个与 10^i 的倍数相差最小的数字。
思想：
- 模拟。
- 每次操作找到与 \lfloor \frac{x}{10^i} \rfloor x 和 \lceil \frac{x}{10^i} \rceil x 最接近的数，并取代即可。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
void solve(){
LL x; int k;
cin >> x >> k;
LL fac = 1;
for (int i = 1; i <= k; i ++) {
fac *= 10;
LL a = x / fac, b = ceil(1.0 * x / fac);
a *= fac; b *= fac;
if(abs(a - x) < abs(b - x)) x = a;
else x = b;
}
cout << x << endl;
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}C - (K+1)-th Largest Number
题目大意：
- 给定一个长度为 n 的整数序列 A={A_1,A_2,\dots,A_n}。
- 对于 k = 0,1,2,\dots,N-1： 在序列 A 中存在多少个大于 A_i 的数正好有 k_i 个 。
思想：
- 记录不同的 A_i 的数量，并从大到小排序。
- 二分找到小于等于当前的 A_i 的位置，则该位置下标即为大于 A_i 的数的数量，将其存储。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
LL a[N];
int idx;
LL b[N];
LL c[N];
map<LL,int> vis;
void solve(){
int n; cin >> n;
for(int i = 0; i < n; i ++) {
cin >> a[i];
if(vis[a[i]] == 0){
vis[a[i]] = 1;
b[idx ++] = a[i];
}
}
sort(b, b + n, greater<LL>());
for(int i = 0; i < n; i ++){
int t = lower_bound(b, b + idx, a[i], greater<LL>()) - b;
c[t] ++;
}
for(int i = 0; i < n; i ++){
cout << c[i] << endl;
}
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}D - LRUD Instructions
题目大意：
- 给定 h\times w 的矩阵，起始点为 (rs,cs)。
- 给定 n 个 (r_i,c_i) 的坐标表示为墙。
- 给定 q 次操作，对于 q_i 给出行进方向 d_i 和次数 l_i。
- 遇到边界或者墙则停止操作。
- 对于每次操作，输出执行完毕后的位置。
思想：
- 二分，模拟。
- 朝着某一方向走 l_i 步，我们需要快速定位到在其方向上最近的墙的位置或者边界的位置。
- 考虑二分，同时我们需要存储每一个行对应的列坐标，每一个列对应的行坐标。
- 由于坐标范围很大，所以我们考虑
map<LL, set<LL>>来快速查询。
代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);
map<LL, vector<LL>> dx, dy;
void solve(){
LL l, w, x, y; cin >> l >> w >> x >> y;
map<LL,set<LL>> dx, dy;
int n; cin >> n;
while(n --){
LL a, b;
cin >> a >> b;
dx[a].insert(b);
dy[b].insert(a);
}
for (auto &&i : dx){
i.second.insert(0);
i.second.insert(w + 1);
}
for (auto &&i : dy){
i.second.insert(0);
i.second.insert(l + 1);
}
int q; cin >> q;
while(q --> 0){
char op;
LL k;
cin >> op >> k;
if(op == 'L'){
LL ny = y - k;
if (dx.find(x) == dx.end()) {
y = max(ny, (LL)1);
}
else{
auto it = dx[x].lower_bound(y);
it = prev(it);
y = max(*it + 1, ny);
}
}
else if(op == 'R'){
LL ny = y + k;
if (dx.find(x) == dx.end()) {
y = min(ny, w);
}
else{
auto it = dx[x].lower_bound(y);
y = min(*it - 1, ny);
}
}
else if(op == 'U'){
LL nx = x - k;
if (dy.find(y) == dy.end()) {
x = max(nx, (LL)1);
}
else{
auto it = dy[y].lower_bound(x);
it = prev(it);
x = max(*it + 1, nx);
}
}
else{
LL nx = x + k;
if (dy.find(y) == dy.end()) {
x = min(nx, l);
}
else{
auto it = dy[y].lower_bound(x);
x = min(*it - 1, nx);
}
}
cout << x << ' ' << y << endl;
}
}
int main(){
IOS;
int _ = 1;
// cin >> _;
while(_ --){
solve();
}
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-10-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
