当前位置:网站首页>AtCoder Beginner Contest 258「ABCDEFG」
AtCoder Beginner Contest 258「ABCDEFG」
2022-07-05 09:48:00 【Chels.】
A - When?
题目描述:
问从
21:00
开始k
分钟后是什么时候
思路:
随便写写就行
#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)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
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;
if(n < 60){
printf("21:%02d\n", n);
}
else{
n %= 60;
printf("22:%02d\n", n);
}
}
int main(){
io;
work();
return 0;
}
B - Number Box
题目描述:
给你
n * n
的矩阵,每个点位都有一个数字,这个矩阵的上界和下界、左界和右界是连起来的,你可以选择任意一个起点,然后固定一个方向,方向有上下左右左上左下右上右下共8个方向,问走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)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
char tr[15][15];
int dx[] = {
1, 0, -1, 0, -1, -1, 1, 1};
int dy[] = {
0, 1, 0, -1, -1, 1, -1, 1};
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
cin >> tr[i][j];
}
}
vector<string>v;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
for(int k = 0; k < 8; ++k){
int num = 0;
string s = "";
while(num < n){
int x = (i + dx[k] * num - 1 + n * n) % n + 1;
int y = (j + dy[k] * num - 1 + n * n) % n + 1;
s += tr[x][y];
++num;
}
v.push_back(s);
}
}
}
sort(v.begin(), v.end());
cout << v.back() << endl;
}
int main(){
io;
work();
return 0;
}
C - Rotation
题目描述:
给定一个长度为n的字符串,进行Q次操作,两种操作,具体如下:
op = 1
: 删除后面x个字符,并放到前面去op = 2
: 输出第x个字符是什么
思路:
我们可以把字符串看成一个首尾相接的一个串,我们只需要记录起点即可,而操作1实际上使得起点往左移动了x位,我们只需要合理取模即可维护,操作2也是通过我们的起点和x想加取模后输出对应位置的字符即可
#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)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 500000 + 50
int n, m, k, x, op;
char tr[MAX];
void work(){
cin >> n >> m;
for(int i = 0; i < n; ++i)cin >> tr[i];
int fi = 0;
while(m--){
cin >> op >> x;
if(op == 1){
fi = (fi - x + 2 * n) % n;
}
else{
cout << tr[(fi + x - 1) % n] << endl;
}
}
}
int main(){
io;
work();
return 0;
}
D - Trophy
题目描述:
有n个关卡,每个关卡都有一个入场动画以及关卡通关所需时间,而每次进入一个新的关卡是必须看完入场动画且通关这个关卡后才能解锁下一个关卡,且通关后的关卡再次选择时则不需要看入场动画,只需要通关即可,你现在在关卡1门口,你必须通关x个关卡,这x个关卡可以存在重复的关卡,问最小花费的时间是多少
思路:
简单的贪心
注意最大值要取大一点,因为极限数据其实会超过1e18,我就因为这个原因硬生生wa了20分钟(裂开
#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)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n, m, k, x;
ll ar[MAX], br[MAX];
void work(){
cin >> n >> x;
ll minx = 8e18;
ll ans = 0;
for(int i = 1; i <= n; ++i){
cin >> ar[i] >> br[i];
ans += ar[i] + br[i];
minx = min(minx, ans + (max(0ll, x - 1)) * br[i]);
--x;
}
cout << minx << endl;
}
int main(){
io;
work();
return 0;
}
E - Packing Potatoes
题目描述:
n个物品,每个物品都有一个重量
w[i]
,n个物品按照顺序依次排列,n个物品完了后面继续无限重复这n个物品,现在有无数个箱子想打包这些物品,规则是:如果加入当前物品后箱子的重量大于等于K
,则封装该箱子,换下一个空箱子去装物品,否则就继续装现在给你Q次询问,每次询问都问你第
X[i]
个箱子里面装了几个物品
思路:
第一眼就觉得是找循环节
因为物品顺序已经确定了,且
K
也确定,所以如果又一次遇到以i
物品为一个空箱子的起始物品,那一定开始产生循环了所以我们可以通过某种方法计算出以第
i
个物品为空箱子的起始物品时,下一个空箱子的起始物品的下标为id[i]
方法是在前缀和的基础上去二分,并记录以
i
物品为空箱子起始物品所能装的物品的数量这里二分分两种情况:
- 当
sum[n] - sum[i - 1] >= K
,则直接二分就行- 否则,我们先把
K
减去sum[n] - sum[i - 1]
,后变成以物品1
为起始物品,然后对sum[n]
进行取模,再二分二分出来以后,我们去模拟这个过程,用一个数组记录上一次出现
i
为空箱子的起始物品的箱子下标,如果之前出现过了,就说明出现了循环,大概是这样的图:
我们对于每次询问,我们就根据下标先减去前面的头,再去循环节里面找就行
这个题写起来细节很多,特别是二分和下标那块,我就是因为二分的起点下标写错了wa了半天
#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)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
ll n, m, k, x;
ll tr[MAX];
ll sum[MAX];
ll fuck[MAX];
ll num[1000005];
ll id[MAX];
ll vis_id[MAX];
void work(){
cin >> n >> m >> x;
for(int i = 1; i <= n; ++i){
cin >> tr[i];
sum[i] = sum[i - 1] + tr[i];
}
for(int i = 1; i <= n; ++i){
ll p = x;
if(sum[n] - sum[i - 1] >= x){
id[i] = (lower_bound(sum + i, sum + 1 + n, x + sum[i - 1]) - sum);
fuck[i] = id[i] + 1 - i;
id[i] = id[i] % n + 1;
}
else{
p = p - (sum[n] - sum[i - 1]);
fuck[i] = n - i + 1 + n * (p / sum[n]);
p %= sum[n];
id[i] = (lower_bound(sum + 1, sum + 1 + n, p) - sum);
fuck[i] = fuck[i] + id[i];
id[i] = id[i] % n + 1;
}
}
ll idd = 1;
ll len = 0;
ll r = 1;
for(int i = 1; i <= 1000000; ++i){
if(vis_id[idd]){
len = i - vis_id[idd];
r = vis_id[idd] - 1;
break;
}
vis_id[idd] = i;
num[i] = fuck[idd];
idd = id[idd];
}
while(m--){
cin >> x;
if(x <= r)cout << num[x] << endl;
else{
x -= r;
x = (x - 1) % len + 1;
cout << num[r + x] << endl;
}
}
}
int main(){
io;
work();
return 0;
}
F - Main Street
题目描述:
输入B,K,在一个二维平面上,存在无数条平行于x轴和y轴的直线,
x = n, y = n
,这些是小道路,其中,x = Bn, y = Bn
的这些直线是大路,人在大路上行走时,两个相邻的点之间的花费是1
,而在小路上走时,相邻两个点之间的花费是K
,问从(Sx, Sy)
出发到(Gx, Gy)
的最小花费是多少
思路:
显然,我们要尽可能走大路,而对于每个点,一定属于一个
B*B
的方块中,那这个点到方格的四个边界做垂线一定存在4个垂足(可能重合),这就是这个点到达大路的四种方法,我们用双重for
循环来枚举着两个点到达大路的方法,也就是4 * 4 = 16
种方案,再需要知道两个在大路上的点之间的最短距离是什么这里如果两个点不在同一个
B*B
的方块里面,或者在同一个块,但不在互相平行的对边上,则花费就是二者之间的曼哈顿距离,如果在同一个块里面且两个点是位于对边上,则需要进行讨论,讨论是在上下的对边还是在左右的对边,在此基础上,两个点的最小距离也要分如下三种情况取最小值来做
存在三条路径,我们取这三条路径的最小值,紫色那条是先走大路再走小路,所以计算的时候小路一定要乘
K
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <ll, ll> pii;
#define y1 y114514
#define MAX 300000 + 50
ll b, k, sx, sy, gx, gy;
vector<pii>ar, br;
void cal(ll x, ll y, vector<pii>&ar){
ar.push_back(m_p(x - x % b, y));
ar.push_back(m_p(x, y - y % b));
ar.push_back(m_p(x, y + b - y % b));
ar.push_back(m_p(x + b - x % b, y));
}
ll getans(ll x1, ll y1, ll x2, ll y2){
ll ans = (abs(x1 - sx) + abs(y1 - sy) + abs(x2 - gx) + abs(y2 - gy)) * k;
if(x1 % b == 0 && x2 % b == 0 && y1 / b == y2 / b){
ans += min({
abs(x1 - x2) * k + abs(y1 - y2), abs(x1 - x2) + 2 * b - y1 % b - y2 % b, abs(x1 - x2) + y1 % b + y2 % b});
}
else if(y1 % b == 0 && y2 % b == 0 && x1 / b == x2 / b){
ans += min({
abs(y1 - y2) * k + abs(x1 - x2), abs(y1 - y2) + x1 % b + x2 % b, 2 * b - x1 % b - x2 % b + abs(y1 - y2)});
}
else {
ans += abs(x1 - x2) + abs(y1 - y2);
}
return ans;
}
void work(){
cin >> b >> k >> sx >> sy >> gx >> gy;
ar.clear();br.clear();
cal(sx, sy, ar);
cal(gx, gy, br);
ll ans = 8e18;
ans = min(ans, (abs(sx - gx) + abs(sy - gy)) * k);
for(int i = 0; i < ar.size(); ++i){
for(int j = 0; j < br.size(); ++j){
ans = min(ans, getans(ar[i].first, ar[i].second, br[j].first, br[j].second));
}
}
cout << ans << endl;
}
int main(){
io;
int tt;cin>>tt;
for(int _t = 1; _t <= tt; ++_t){
work();
}
return 0;
}
G - Triangle
题目描述:
问存在多少个三元组
(i, j, k)
,满足i<j<k
且i
和j
之间有边,j
和k
之间有边,i
和k
之间有边
思路:
我们枚举
i
和j
,用bitset取&
来优化,求k
的数量注意
bitset
存的是倒着的字符串其实,我们需要先reverse
一下
#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)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;
#define MAX 300000 + 50
int n, m, k, x;
bitset<3005>b[3005];
string s;
void work(){
cin >> n;
for(int i = 1; i <= n; ++i){
cin >> s;
reverse(s.begin(), s.end());
b[i] = bitset<3005>(s);
}
ll ans = 0;
for(int i = 1; i <= n; ++i){
for(int j = i + 1; j <= n; ++j){
if(b[i][j - 1] == 1){
ans += (b[i] & b[j]).count();
}
}
}
cout << ans / 3 << endl;
}
int main(){
io;
work();
return 0;
}
边栏推荐
- uniapp + uniCloud+unipay 实现微信小程序支付功能
- Apache DolphinScheduler 入门(一篇就够了)
- Livedata interview question bank and answers -- 7 consecutive questions in livedata interview~
- How to get the STW (pause) time of GC (garbage collector)?
- Matrix processing practice
- Swift saves an array of class objects with userdefaults and nssecurecoding
- Unity粒子特效系列-毒液喷射预制体做好了,unitypackage包直接用 -下
- Kotlin Compose 多个条目滚动
- 天龙八部TLBB系列 - 单体技能群伤
- 学习笔记5--高精地图解决方案
猜你喜欢
[C language] the use of dynamic memory development "malloc"
字节跳动面试官:一张图片占据的内存大小是如何计算
ConstraintLayout的流式布局Flow
宝塔面板MySQL无法启动
美图炒币半年亏了3个亿,华为被曝在俄罗斯扩招,AlphaGo的同类又刷爆一种棋,今日更多大新闻在此...
A high density 256 channel electrode cap for dry EEG
Cent7 Oracle database installation error
如何写出高质量的代码?
一种用于干式脑电图的高密度256通道电极帽
Comment obtenir le temps STW du GC (collecteur d'ordures)?
随机推荐
RMS TO EAP通过MQTT简单实现
Application of data modeling based on wide table
天龙八部TLBB系列 - 关于技能冷却和攻击范围数量的问题
苹果 5G 芯片研发失败?想要摆脱高通为时过早
The comparison of every() and some() in JS uses a power storage plan
Wechat applet - simple diet recommendation (4)
Kotlin compose multiple item scrolling
剪掉ImageNet 20%数据量,模型性能不下降!Meta斯坦福等提出新方法,用知识蒸馏给数据集瘦身...
Energy momentum: how to achieve carbon neutralization in the power industry?
leetcode:1200. 最小绝对差
Single chip microcomputer principle and Interface Technology (esp8266/esp32) machine human draft
一个程序员的职业生涯到底该怎么规划?
Cut off 20% of Imagenet data volume, and the performance of the model will not decline! Meta Stanford et al. Proposed a new method, using knowledge distillation to slim down the data set
Applet image height adaptation and setting text line height
Interview: is bitmap pixel memory allocated in heap memory or native
View Slide
oracle和mysql批量Merge对比
[app packaging error] to proceed, either fix the issues identified by lint, or modify your build script as follow
天龙八部TLBB系列 - 关于包裹掉落的物品
Design and Simulation of fuzzy PID control system for liquid level of double tank (matlab/simulink)