Atcoder Beginner Contest 339

A

问题陈述

给你一个由小写英文字母和字符 . 组成的字符串 \(S\)。
当 \(S\) 被 .s 分割时，请打印最后一个子串。
换句话说，打印 \(S\) 中不包含.的最长后缀。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n;i--)
int main()
{
    char c;
    string ans="";
    while(cin>>c)
    {
        if(c=='.')
        {
            ans="";
        }
        else
        {
            ans+=c;
        }
    }
    cout<<ans;
}


//或者倒序枚举
void solve()
{
    string s;
    cin >> s;
    string ans = "";
    for (int i = s.size() - 1; i >= 0; i--)
    {
        if (s[i] == '.')
        {
            break;
        }
        else
        {
            ans = ans + s[i];
        }
    }
    for (int i = ans.size() - 1; i >= 0; i--)
    {
        cout << ans[i];
    }
}

B

问题陈述

有一个行数为 \(H\) 列数为 \(W\) 的网格，起初所有单元格都涂成白色。让 \((i, j)\) 表示从上往下第 \(i\) 行，从左往上第 \(j\) 列的单元格。

这个网格被认为是环形的。也就是说，每个\(1 \leq i \leq H\)的\((i, 1)\)在\((i, W)\)的右边，每个\(1 \leq j \leq W\)的\((1, j)\)在\((H, j)\)的下面。

高桥位于\((1, 1)\)，并且朝上。在高桥重复下面的操作 \(N\) 次后，打印出网格中每个单元格的颜色。

  • 如果当前单元格被涂成白色，则将其重新涂成黑色，顺时针旋转\(90^\circ\)，并沿着他所面对的方向向前移动一个单元格。否则，将当前单元格重新涂成白色，逆时针旋转 \(90^\circ\)，并沿着他所面对的方向向前移动一个单元格。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int x = 0, y = 0, dir = 0;
int tu[110][110];
int main()
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int h, w, n;
    cin >> h >> w >> n;
    while (n--)
    {
        tu[x][y] ^= 1;
        if (tu[x][y] == 0)
        {
            dir = (dir - 1 + 4) % 4;
        }
        else
        {
            dir = (dir + 1 + 4) % 4;
        }
        x = (x + dx[dir] + h) % h;
        y = (y + dy[dir] + w) % w;
    }
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
     {
               cout << (tu[i][j] ? '#' : '.');
     }
     cout<<'\n';
    }
        return 0;   
}

C

问题陈述

一辆公共汽车正在运营。公共汽车上的乘客人数总是一个非负整数。

在某一时刻，公交车上的乘客人数为零或更多，此后公交车停靠了 \(N\) 次。在第 \(i\) 个站点，乘客人数增加了 \(A_i\)。这里，\(A_i\)可以是负数，即乘客人数减少了\(-A_i\)。此外，除了停靠站点外，没有乘客上下车。

请找出与给定信息相符的当前公交车上乘客人数的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//维护最小值即可
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    ll minn = 0;
    ll sum = 0;
    while (n--)
    {
        int x;
        cin >> x;
        sum += x;
        minn = min(minn, sum);
    }
    ll ans = sum - minn;
    cout << ans << '\n';

    return 0;
}

D

问题陈述

有一个\(N \times N\)网格，其中每个单元格要么是空的，要么包含一个障碍物。让 \((i, j)\) 表示从上往下第 \(i\) 行和从左往上第 \(j\) 列的单元格。

网格中不同的空单元上也有两个玩家。每个单元格的信息以长度为 \(N\) 的 \(N\) 字符串 \(S_1, S_2, \ldots, S_N\) 的形式给出，格式如下：

  • 如果 \(S_i\) 的 \(j\) 个字符是 P，那么 \((i, j)\) 是一个空单元格，上面有一名棋手。

  • 如果 \(S_i\) 的 \(j\) 个字符是 .，那么 \((i, j)\) 是一个没有棋子的空格。

  • 如果 \(S_i\) 的 \(j\) 个字符是 #，那么 \((i, j)\) 包含一个障碍物。

重复下面的操作，找出将两位棋手带到同一格所需的最少步数。如果重复操作无法将两位棋手带到同一格，则打印 -1。

  • 从四个方向中选择一个：上、下、左或右。然后，每个玩家都会尝试移动到该方向的相邻单元格。如果目标单元格存在且为空，则每个玩家都会移动，否则不会移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//两个点跑bfs即可，弄一个数组记录
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 61;
char a[MAXN][MAXN];
int n;
bool vis[MAXN][MAXN][MAXN][MAXN];
struct node
{
    int a, b, c, d, step;
};
int tx1, tx2, ty1, ty2;

bool check(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= n && a[i][j] != '#';
}
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};
int bfs()
{
    queue<node> q;
    q.push({tx1, ty1, tx2, ty2, 0});
    vis[tx1][ty1][tx2][ty2] = 1;
    while (q.size())
    {
        auto [x1, y1, x2, y2, step] = q.front();
        q.pop();
        if (x1 == x2 && y1 == y2)
            return step;
        for (int t = 0; t < 4; ++t)
        {
            if (check(x1 + dx[t], y1 + dy[t]) || check(x2 + dx[t], y2 + dy[t]))
            {
                int tx1 = x1, ty1 = y1, tx2 = x2, ty2 = y2;
                if (check(x1 + dx[t], y1 + dy[t]))
                    tx1 += dx[t], ty1 += dy[t];
                if (check(x2 + dx[t], y2 + dy[t]))
                    tx2 += dx[t], ty2 += dy[t];
                if (!vis[tx1][ty1][tx2][ty2])
                {
                    vis[tx1][ty1][tx2][ty2] = 1;
                    q.push({tx1, ty1, tx2, ty2, step + 1});
                }
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
        {
            cin >> a[i][j];
            if (a[i][j] == 'P')
            {
                if (tx1)
                    tx2 = i, ty2 = j;
                else
                    tx1 = i, ty1 = j;
            }
        }
    cout << bfs();
}

还有一道ICPC也贴了

image-20240307004659518

思路大概是一定会移动少的，但是多出来那一部分就要考虑一下。

如果有一份是最大值最小值相等，多出来一部分就是0了

不然的话要计算那一部分

还有判ans=0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i, a, n) for (ll i = a; i <= n; i++)
#define frep(i, a, n) for (ll i = a; i >= n;i--)
string s;
ll ans=0;
ll temp=1e9;
bool x,y;
int main()
{
int n;
cin>>n;
rep(i,1,n)
{
cin>>s;
ll t=s.length();
ll sum_1=0;
ll sum_0=0;
rep(i,0,t-1)
{
if(s[i]=='1')
{
    sum_1++;
}
}
sum_0 = t - sum_1;
temp=min(temp,abs(sum_1-sum_0));
ans+=min(sum_1,sum_0);
if(sum_1>sum_0)
{
x=1;
}
else if(sum_1<sum_0)
{
    y=1;
}
else
{
    x=1;
    y=1;
}
}
if(ans==0)
{
    cout<<0;
    return 0;
}
if(x&&y)
{
    cout<<ans<<'\n';
}
else
{
    cout<<ans+temp<<'\n';
}
return 0;
}

E - Smooth Subsequence

问题陈述

给你一个长度为 \(N\) 的序列 \(A = (A_1, A_2, \ldots, A_N)\)。

求长度为 \(A\) 的子序列的最大长度，使得任意两个相邻项之间的绝对差最多为 \(D\)。

序列 \(A\) 的子序列是指从 \(A\) 中删除 0 个或多个元素，并将其余元素按原来的顺序排列后得到的序列。

线段树优化dp,维护转移范围内的最大值 \[ 我们设 dp [ i ] 为 以下标 i 结尾的符合要求的子序列最长是多少。那么我们枚举到位置 i ,就是找出 前 i 个数中的dp最大值，但是循环肯定是超时的。 那么就是找出这个区间内的最大值，所以用线段树维护即可。 \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10;
int n, D, ans = 1;
int d[N], a[N], dp[N];
void pushup(int u)
{
    d[u] = max(d[u << 1], d[u<<1|1]);
}
//单点修改
//注意Pushup
void update(int l, int r, int s, int t, int p, int change)
{
    if (l <= s && t <= r)
    {
        d[p] = max(d[p], change);
        return;
    }
    int mid = (s + t) >> 1;
    if (l <= mid)
        update(l, r, s, mid, p << 1, change);
    if (r > mid)
        update(l, r, mid + 1, t, p << 1 | 1, change);
 pushup(p);
}
//区间查询
int Query(int l, int r, int s, int t, int p)
{
    if (l <= s && t <= r)
        return d[p];
    int mid = (s + t) >> 1, ans = 0;
    if (l <= mid)
        ans = max(ans, Query(l, r, s, mid, p << 1));
    if (r > mid)
        ans = max(ans, Query(l, r, mid + 1, t, p << 1 | 1));
    return ans;
}
int main()
{
    cin >> n >> D;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        dp[i] = max(dp[i], Query(max(1, a[i] - D), min(a[i] + D, 500000), 1, 500000, 1)) + 1;
        update(a[i], a[i], 1, 500000, 1, dp[i]);
        ans = max(ans, dp[i]);
    }
    cout << ans << '\n';
}

F - Product Equality

问题陈述

给你 \(N\) 个整数 \(A_1, A_2, \dots, A_N\)。
求满足以下条件的整数 \((i, j, k)\) 的三元组数：

  • \(1 \le i, j, k \le N\)
  • \(A_i \times A_j = A_k\)

单哈希加奇怪模数（题解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define N 1005
#define int __int128
using ll=long long;
const int mod=(int)(1e18)+3;
using namespace std;
int a[N];
ll ans,n;
map<int,ll>m;
signed main(){
	cin>>n;
	for(int i=1;i<=n;++i){
		string s;
		cin>>s;
		for(int j=0;j<s.size();++j)a[i]=(a[i]*10+(s[j]-'0'))%mod;
		++m[a[i]];
	}
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)ans+=m[a[i]*a[j]%mod];
	}
	cout<<ans;
}