Panasonic Programming Contest 2022(AtCoder Beginner Contest 273)
A – A Recursive Function
题目描述：
f(0)=1,f(k)=k*f(k-1)，求f(n)
思路：
诈骗题，其实是输出n的阶乘
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
void work(){
cin >> n;
tr[0] = 1;
for(int i= 1; i <= n; ++i){
tr[i] = i * tr[i - 1];
}
cout << tr[n] << endl;
}
int main(){
io;
work();
return 0;
}
B – Broken Rounding
题目描述：
给出数字
n，要求进行k次四舍五入，第i次四舍五入要把n向着10i进行四舍五入，即用x个10i来表示出离n最近的数字，用这个数字去替换n
思路：
诈骗题！
其实就是进行k次四舍五入，每次都对从后往前的第i位进行四舍五入
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n, k;
ll cal(ll n, ll i){
ll p = pow(10, i);
ll x = (n / p) * p;
ll y = x + p;
if(n-x < y-n)return x;
else return y;
}
void work(){
cin >> n >> k;
for(int i = 1; i <= k; ++i){
n = cal(n, i);
}
cout << n << endl;
}
int main(){
io;
work();
return 0;
}
C – (K+1)-th Largest Number
题目描述：
诈骗题！我也忘了题意什么意思了，反正晦涩难懂
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];
void work(){
cin >> n;
map<int, int>mp, ans, fuck;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
++mp[tr[i]];
}
int id = 0;
for(auto [x, y] : mp){
++id;
ans[x] = (int)mp.size() - id;
}
for(int i = 1; i <= n; ++i){
++fuck[ans[tr[i]]];
}
for(int i = 0; i < n; ++i){
cout << fuck[i] << endl;
}
}
int main(){
io;
work();
return 0;
}
D – LRUD Instructions
题目描述：
给定一个
n*m的矩形，其中有k个障碍物，你的起点为(x, y)，现在给你Q次操作， 每次操作都是进行一个固定方向固定距离的移动，如果前方遇到障碍物或边界则无法往前移动，每走一次输出当前位置
思路：
纯纯模拟，可以用
map<int,vector<int>>，但是我没有用，而是用个map<int,int>,vector<int>tr[MAX]来代替的对行和列分别进行处理，然后模拟就行，仔细点就完事了
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 500000 + 50
ll n, m, k, x, y, p;
vector<ll>ar[MAX], br[MAX];
struct ran{
ll x, y;
}tr[MAX];
bool cmp1(ran a, ran b){
if(a.x != b.x)return a.x < b.x;
else return a.y < b.y;
}
bool cmp2(ran a, ran b){
if(a.y != b.y)return a.y < b.y;
else return a.x < b.x;
}
void work(){
cin >> n >> m >> x >> y;
cin >> k;
for(int i = 1; i <= k; ++i){
cin >> tr[i].x >> tr[i].y;
}
sort(tr + 1, tr + 1 + k, cmp1);
ll h=0, l=0;
map<ll, ll>hang, lie;
for(int i = 1; i <= k;){
hang[tr[i].x] = ++h;
while(i + 1 <= k && tr[i+1].x==tr[i].x){
ar[h].push_back(tr[i].y);
++i;
}
ar[h].push_back(tr[i].y);
++i;
}
sort(tr+1, tr+1+k, cmp2);
for(int i = 1; i <= k;){
lie[tr[i].y] = ++l;
while(i+1<=k&&tr[i+1].y==tr[i].y){
br[l].push_back(tr[i].x);
++i;
}
br[l].push_back(tr[i].x);
++i;
}
cin >> p;
char op;
int len;
while(p--){
cin >> op >> len;
if(op == 'L'){
if(!hang.count(x)){
y = max(1ll, y-len);
}
else{
ll id = hang[x];
if(ar[id].front() > y){
y = max(1ll, y - len);
}
else{
ll pos = lower_bound(ar[id].begin(), ar[id].end(), y) - ar[id].begin()-1;
y = max(ar[id][pos]+1, y-len);
}
}
cout << x << ' ' << y << endl;
}
else if(op == 'U'){
if(!lie.count(y)){
x = max(1ll, x - len);
}
else{
ll id = lie[y];
if(br[id].front() > x){
x = max(1ll, x - len);
}
else{
ll pos = lower_bound(br[id].begin(), br[id].end(), x) - br[id].begin()-1;
x = max(br[id][pos]+1, x - len);
}
}
cout << x << ' ' << y << endl;
}
else if(op == 'R'){
if(!hang.count(x)){
y = min(m, y+len);
}
else{
ll id = hang[x];
if(ar[id].back() < y){
y = min(m, y + len);
}
else{
ll pos = lower_bound(ar[id].begin(), ar[id].end(), y) - ar[id].begin();
y = min(ar[id][pos]-1, y+len);
}
}
cout << x << ' ' << y << endl;
}
else{
if(!lie.count(y)){
x = min(n, x + len);
}
else{
ll id = lie[y];
if(br[id].back() < x){
x = min(n, x + len);
}
else{
ll pos = lower_bound(br[id].begin(), br[id].end(), x) - br[id].begin();
x = min(br[id][pos]-1, x+len);
}
}
cout << x << ' ' << y << endl;
}
}
}
int main(){
io;
work();
return 0;
}
E – Notebook
题目描述：
存在一个初始是空的时间机器，和一个序列A
Q次操作，四种操作
ADD x把x加入序列A的最后DELETE删除序列A的最后一个元素SAVE y将当前序列A覆盖在时间y对应的内容LOAD z读取时间z对应的A序列，把原来的序列给替换掉
思路：
链表模拟
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 500000 + 50
int n, m, k, x;
int tr[MAX];
int pre[MAX];
string s;
void work(){
cin >> m;
int now = 0;
tr[0] = -1;
map<int, int>mp;
while(m--){
cin >> s;
if(s[0] == 'A'){
cin >> x;
tr[++n] = x;
pre[n] = now;
now = n;
}
else if(s[0] == 'D'){
now = pre[now];
}
else if(s[0] == 'S'){
cin >> x;
mp[x] = now;
}
else{
cin >> x;
now = mp[x];
}
cout << tr[now] << ' ';
}
}
int main(){
io;
work();
return 0;
}
