当前位置:网站首页>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;
}
边栏推荐
- Swift saves an array of class objects with userdefaults and nssecurecoding
- Kotlin compose and native nesting
- 【小技巧】獲取matlab中cdfplot函數的x軸,y軸的數值
- [NTIRE 2022]Residual Local Feature Network for Efficient Super-Resolution
- Unity粒子特效系列-毒液喷射预制体做好了,unitypackage包直接用 - 上
- NCP1342芯片替代料PN8213 65W氮化镓充电器方案
- Kotlin Compose 与原生 嵌套使用
- QT VT100 parser
- 卷起來,突破35歲焦慮,動畫演示CPU記錄函數調用過程
- Generics, generic defects and application scenarios that 90% of people don't understand
猜你喜欢
[C language] the use of dynamic memory development "malloc"
How to get the STW (pause) time of GC (garbage collector)?
把欧拉的创新带向世界 SUSE 要做那个引路人
Implementation of smart home project
Design and Simulation of fuzzy PID control system for liquid level of double tank (matlab/simulink)
The king of pirated Dall · e? 50000 images per day, crowded hugging face server, and openai ordered to change its name
QT realizes signal transmission and reception between two windows
Pagoda panel MySQL cannot be started
伪类元素--before和after
Usage differences between isempty and isblank
随机推荐
ThreadLocal source code learning
Single chip microcomputer principle and Interface Technology (esp8266/esp32) machine human draft
Personal website construction tutorial | local website environment construction | website production tutorial
MySQL字符类型学习笔记
Application of data modeling based on wide table
Generics, generic defects and application scenarios that 90% of people don't understand
把欧拉的创新带向世界 SUSE 要做那个引路人
C#函数返回多个值方法
B站大量虚拟主播被集体强制退款:收入蒸发,还倒欠B站;乔布斯被追授美国总统自由勋章;Grafana 9 发布|极客头条...
Uni app running to wechat development tool cannot Preview
横向滚动的RecycleView一屏显示五个半,低于五个平均分布
Unity粒子特效系列-毒液喷射预制体做好了,unitypackage包直接用 -下
Applet image height adaptation and setting text line height
Apache dolphin scheduler system architecture design
CSDN always jumps to other positions when editing articles_ CSDN sends articles without moving the mouse
Windows uses commands to run kotlin
[system design] index monitoring and alarm system
【系统设计】指标监控和告警系统
Coordinate system of view
学习笔记6--卫星定位技术(上)