本文最后更新于 849 天前,其中的信息可能已经有所发展或是发生改变。
A - A Recursive Function
题目大意:
- 求 f(k) 如下:
- f(0)=1;
- f(k)=k×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 改为一个与 10i 的倍数相差最小的数字。
思想:
- 模拟。
- 每次操作找到与 ⌊10ix⌋x 和 ⌈10ix⌉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=A1,A2,…,An。
- 对于 k=0,1,2,…,N−1:
- 在序列 A 中存在多少个大于 Ai 的数正好有 ki 个 。
思想:
- 记录不同的 Ai 的数量,并从大到小排序。
- 二分找到小于等于当前的 Ai 的位置,则该位置下标即为大于 Ai 的数的数量,将其存储。
代码:
#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×w 的矩阵,起始点为 (rs,cs)。
- 给定 n 个 (ri,ci) 的坐标表示为墙。
- 给定 q 次操作,对于 qi 给出行进方向 di 和次数 li。
- 遇到边界或者墙则停止操作。
- 对于每次操作,输出执行完毕后的位置。
思想:
- 二分,模拟。
- 朝着某一方向走 li 步,我们需要快速定位到在其方向上最近的墙的位置或者边界的位置。
- 考虑二分,同时我们需要存储每一个行对应的列坐标,每一个列对应的行坐标。
- 由于坐标范围很大,所以我们考虑
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; }