AtCoder Beginner Contest 341

A - Print 341

问题陈述

给定一个正整数 \(N\)，打印一个由 \(N\) 个 0 和 \(N+1\) 个 1 组成的字符串，其中 0 和 1 交替出现。

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>
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 >= ni--)
void solve()
{
int n;
cin>>n;
rep(i,1,n)
{
    cout<<"10";
}
cout<<1;
}
int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
}
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;

void solve()
{
    int n;
    cin >> n;
    int c = 1;
    for (int i = 0; i < 2 * n + 1; i++, c ^= 1)
        cout << c;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;

    while (T--)
        solve();

    return 0;
}

B - Foreign Exchange

问题陈述

有\(N\)个国家，编号为\(1\)至\(N\)。对于每个\(i = 1, 2, \ldots, N\)，高桥有\(A_i\)个单位的\(i\)国货币。

高桥可以重复下面的操作任意多次，可能为零：

  • 首先，在\(1\)和\(N-1\)之间选择一个整数\(i\)。
  • 然后，如果高桥至少有 \(S_i\) 个单位的 \(i\) 国货币，他就执行一次下面的操作：
    • 支付\(S_i\)个单位的\(i\)国货币，获得\(T_i\)个单位的\((i+1)\)国货币。

打印高桥最终可能拥有的\(N\)国货币的最大单位数。

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
// 由于只枚举到N-1的S[] T[] 我们只要从第一个开始一个个遍历过去使得A[N]最大 坑点数据范围
// 注意long long
#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 >= ni--)
const int N=2e5+100;
using ll=long long;
ll a[N];
int main()
{
ll n;
cin>>n;
rep(i,1,n)
{
cin>>a[i];
}
rep(i,1,n-1)
{
    ll x,y;
    cin>>x>>y;
    if(a[i]>=x)
    {
        a[i+1]+=(a[i]/x)*y;
    }
}
cout<<a[n];
}
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
//STL马蜂
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

void solve()
{
    int n;
    cin >> n;

    vector<LL> a(n), s(n - 1), t(n - 1);
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    for (int i = 0; i < n - 1; i ++ )
        cin >> s[i] >> t[i];

    for (int i = 0; i < n - 1; i ++ )
        a[i + 1] += a[i] / s[i] * t[i];

    cout << a[n - 1] << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T = 1;
    
    while (T -- ) solve();

    return 0;
}

C - Takahashi Gets Lost

问题陈述

有一个网格，网格中有 \(H\) 行和 \(W\) 列。

网格中的每个单元格都是陆地或海洋，由长度为\(W\)的\(H\)字符串\(S_1, S_2, \ldots, S_H\)表示。让\((i, j)\)表示从顶部起第\(i\)行和从左侧起第\(j\)列的单元格，如果\(S_i\)的第\(j\)个字符是.，则\((i, j)\)是陆地，如果该字符是#，则\((i, j)\)是海洋。

这些约束条件保证了网格周边的所有单元格（即满足 \(i = 1\)、\(i = H\)、\(j = 1\)、\(j = W\) 中至少一个条件的单元格 \((i, j)\)）都是海域。

高桥的飞船坠落在网格中的一个单元格上。之后，他按照长度为 \(N\) 的字符串 \(T\) 所代表的指令在网格中移动了 \(N\) 次，该字符串由 L、R、U 和 D 组成。对于\(i = 1, 2, \ldots, N\)，\(T\)的\(i\)个字符描述了\(i\)次移动，具体如下：

  • L "表示向左移动一格。也就是说，如果他在移动之前位于\((i, j)\)，那么移动之后他将位于\((i, j-1)\)。
  • R "表示向右移动一格。也就是说，如果移动前他位于\((i, j)\)，移动后他将位于\((i, j+1)\)。
  • U "表示向上移动一格。也就是说，如果移动前他位于\((i, j)\)，移动后他将位于\((i-1, j)\)。
  • D "表示向下移动一格。也就是说，如果移动前他位于\((i, j)\)，移动后他将位于\((i+1, j)\)。

已知他移动路径上的所有单元格（包括他坠落的单元格和当前所在的单元格）都不是海。请打印可能是他当前位置的单元格数。

很水的模拟

数据很小，直接走就可以了

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
#include <bits/stdc++.h>

using namespace std;

void solve()
{
    int n, m, k;
    string T;
    cin >> n >> m >> k >> T;

    vector<string> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i];

    int res = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (s[i][j] == '.')
            {
                bool ok = true;
                int x = i, y = j;
                for (auto c : T)
                {
                    if (c == 'L')
                        y--;
                    else if (c == 'R')
                        y++;
                    else if (c == 'U')
                        x--;
                    else
                        x++;
                    if (s[x][y] == '#')
                    {
                        ok = false;
                        break;
                    }
                }

                if (ok)
                    res++;
            }

    cout << res << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;

    while (T--)
        solve();

    return 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
59
// 按照题意首先观察数据很小所以遍历每一个点即可
#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--)
const int N = 550;
using ll = long long;
int n,m,k;
string s;
int ans;
int main()
{
    char a[N][N];
    cin>>n>>m>>k;
    cin>>s;
    s=" "+s;
    rep(i,1,n)
    {
        rep(j,1,m)
        {
            cin>>a[i][j];
        }
    }
    rep(i,1,n)
    {
rep(j,1,m)
{
bool flag=1;
int x = i, y = j;

rep(l,1,k)
{
    if(a[x][y]=='#')
    {
        flag = 0;
        break;
    }
    if (s[l] == 'L')
        y--;
    else if (s[l] == 'R')
        y++;
    else if (s[l] == 'U')
        x--;
    else
        x++;
    if (a[x][y]== '#')
    {
        flag = 0;
        break;
    }
}
if(flag)
{
    ans++;
}
}
    }
    cout<<ans;
}

D - Only one of two

问题陈述

给你三个正整数 \(N\)、\(M\) 和 \(K\)。这里，\(N\)和\(M\)是不同的。
请列出能被\(N\)和\(M\)中的1个整数整除的\(K\)个最小正整数。

考虑二分

![image-20240305175109213]/images/image-20240305175109213.png)

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
#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--)
const int N = 550;
using ll = long long;
ll n,m,k;
ll ans;
int main()
{
cin>>n>>m>>k;
ll lcm=n/__gcd(n,m)*m;
ll l=0;
ll r=1e18;
while(l<=r)
{
    ll mid=(l+r)>>1;
    if(mid/n+mid/m-mid/lcm*2>=k)
    {
        ans = mid;
        r = mid-1 ;
    }
    else
    {
        l=mid+1;
    }
}
cout<<ans;


}

大佬二分和题解二分

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 main()
{
    ll N, M, K;
    cin >> N >> M >> K;

    ll left = 0, right = 1e18, ans = 0;

    auto lcm = [&](ll a, ll b)
    {
        return a / __gcd(a, b) * b;
    };

    auto check = [&](ll mid)
    {
        return mid / N + mid / M - mid / lcm(N, M) * 2;
    };

    while (left <= right)
    {
        ll mid = (left + right) >> 1;
        if (check(mid) >= K)
        {
            ans = mid;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    cout << ans << '\n';
    return 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
//官方题解（也许也可以康康）
#include <bits/stdc++.h>
using namespace std;

long long gcd(long long x, long long y)
{
    if (x > y)
        swap(x, y);
    if (y % x == 0)
        return x;
    return gcd(y % x, x);
}

int main()
{
    long long n, m, x, k;
    cin >> n >> m >> k;
    x = (n * m) / gcd(n, m);
    long long l = 0, r = (long long)2e+18, mid, y;
    while ((l + 1) < r)
    {
        mid = (l + r) / 2;
        y = (mid / n) + (mid / m) - 2 * (mid / x);
        if (y < k)
            l = mid;
        else
            r = mid;
    }
    cout << r << endl;
    return 0;
}

E - Alternating String

问题陈述

由 0 和 1 组成的字符串，如果其中两个连续字符总是不同，则称为好字符串。
给你一个长度为 \(N\) 的字符串 \(S\) ，由 0 和 1 组成。将给出 \(Q\) 个查询，必须按顺序处理。
查询有两种类型：

  • 1 L R：翻转\(S\)中\(L\)/-th到\(R\)/th的每个字符。也就是说，对于每个满足\(L\leq i\leq R\)的整数\(i\)，如果\(S\)的\(i\)个字符是 "1"，则将其改为 "0"，反之亦然。

  • 2 L R：假设 \(S'\) 是通过提取 \(S\) 的 \(L\)-th 到 \(R\)-th 字符（不改变顺序）得到的长度为 \((R-L+1)\) 的字符串。如果\(S'\)是一个好字符串，则打印 "是"，否则打印 "否"。

    0-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
//采取差分的思想
//存取的是每个数与前面的数字相等吗
//翻转的时候
//由于翻转内的数字是不会改变所谓的相等次序的
//但是翻转的两端实际上是会改变的
//因此只需要查看有没有两端在
//有就删除，没有就加进来
//而对于查询，只需要知道下标中有没有落在我们的询问范围即可
#include <bits/stdc++.h>
using namespace std;
set<int> st; 
int main()
{
    int N, Q;
    string S;
    cin >> N >> Q >> S;
    for (int i = 1; i < N; i++)
    {
        if (S[i] == S[i - 1])
        {
            st.insert(i);
        }
    }
    st.insert(N);
    while (Q--)
    {
        int x, L, R;
        cin >> x >> L >> R;
        L--;
        if (x == 1)
        { 
            for (auto val : {L, R})
            {
                auto it = st.find(val);
                if (it == st.end())
                {
                    st.insert(val);
                }
                else
                {
                    st.erase(it);
                }
            }
        }
        else
        {
            auto it = *st.upper_bound(L);
            //二分查找下标
            cout << (it >= R ? "Yes\n" : "No\n");
        }
    }
    return 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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//线段树也可以差分
//差分后就变成单点修改和区间查询了
#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--)
const int N = 550;
using ll = long long;
int n, m;
bool s[N];
struct Tree
{
    int l, r, s;
} w[N << 2];
//普通的建树
void pushup(int u)
{
    w[u].s = w[u*2].s + w[u*2+1].s;
}
void build(int u, int l, int r)
{
    w[u] = {l, r};
    if (l == r)
        w[u].s = s[l] != s[l + 1];
    else
    {
        int mid = l + r >> 1;
        build(u*2, l, mid), build(u*2+1, mid + 1, r);
        pushup(u);
    }
    return;
}
//单点修改
void modify(int u, int x)
{
    if (w[u].l == w[u].r)
        w[u].s ^= 1;
    else
    {
        int mid = w[u].l + w[u].r >> 1;
        if (x <= mid)
            modify(u*2, x);
        else
            modify(u*2+1, x);
        pushup(u);
    }
}
//区间查询和
int query(int u, int l, int r)
{
    if (w[u].l >= l && w[u].r <= r)
        return w[u].s;
    int mid = w[u].l + w[u].r >> 1, res = 0;
    if (l <= mid)
        res = query(u*2, l, r);
    if (r > mid)
        res += query(u*2+1, l, r);
    return res;
}
//输入
int main()
{
    cin>>n>>m;
    rep(i, 1, n)
    {
        char c;
        cin >> c;
        s[i] = c == '1';
    }
    if (n == 1)
    {
        while (m--)
        {
           int op,l,r;
           cin>>op>>l>>r;
            if (op == 2)
              cout<<"Yes"<<'\n';
        }
        return 0;
    }
    build(1, 1, n - 1);
    while (m--)
    {
       int op,l,r;
       cin>>op>>l>>r;
        if (op == 1)
        {
            if (l != 1)
                modify(1, l - 1);
            if (r != n)
                modify(1, r);
        }
        else
        {
            if (l == r || query(1, l, r - 1) == r - l)
                cout << "Yes" << '\n';
            else
                cout<<"No"<<'\n';
        }
    }
    return 0;
}