AtCoder Beginner Contest 258「ABCDEFG」

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;
}