2023 CCPC Henan Provincial Collegiate Programming Contest

https://codeforces.com/gym/104354

B. Art for Rest

题意

给定一个序列 aa。定义 aka_k 为将 aa 划分为 ⌈nk⌉\lceil\dfrac{n}{k}\rceil 段，每段升序排序后得到的序列。求有多少个 k∈[1,n]k\in [1,n] 满足 aka_k 单调不降。

题解

容易想到对每个 kk 进行检验。我们需要每一段的最大值不超过下一段的最小值，利用st表可以做到 O(nlog⁡n)O(n\log n)，但是跑不过去。

进一步，我们发现每一段的最大值就是前缀最大值，后一段的最小值就是后缀最小值，所以维护这两个东西就可以求解了，省去了预处理st表的开销。

代码

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
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,a[N],pre[N],suf[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    pre[0]=0;
    for(int i=1;i<=n;i++) pre[i]=max(pre[i-1],a[i]);
    suf[n+1]=0x3f3f3f3f;
    for(int i=n;i;i--) suf[i]=min(suf[i+1],a[i]);
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        bool ok=1;
        for(int j=i;j<=n;j+=i)
            if(pre[j]>suf[j+1]) ok=0;
        ans+=ok;
    }
    cout<<ans<<'\n';
    return 0;
}

C. Toxel 与随机数生成器

题意

有一个随机序列生成器，会等概率生成01。有另一个错误的随机序列生成器，每隔 lengthilength_i 个位置序列就会开始重复，保证 lengthi≥103length_i\geq 10^3。给出一个序列，要求判断生成器是正确的还是错误的。

题解

乱搞题。如果序列的前一千个字符组成的子串在后面出现了，那么说明生成器极大概率是错误的，否则就认为它是正确的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;cin>>s;
    string s1=s.substr(0,1000);
    s.erase(0,1000);
    if(s.find(s1)!=-1) cout<<"NO"<<'\n';
    else cout<<"YES"<<'\n';
    return 0;
}

E. 矩阵游戏

题意

在网格中从 (1,1)(1,1) 走到 (n,n)(n,n)，每次往下或往右。格子有 1,0,?1,0,? 三种，可以将至多 xx 个 ?? 修改为 11。求最多能获得多少分。

数据范围：1≤n,m≤500,0≤x≤1031\leq n,m\leq 500,0\leq x\leq 10^3。

题解

直接 O(nmx)O(nmx) 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
51
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

constexpr int N = 500;
constexpr int M = 1000;

int f[N + 1][M + 1];

void solve() {
    int n, m, x;
    cin >> n >> m >> x;

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

    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= x; j++) {
            f[i][j] = 0;
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = x; k >= 0; k--) {
                f[j + 1][k] = max(f[j + 1][k], f[j][k]) + (a[i][j] == '1');
                if (k && a[i][j] == '?') {
                    f[j + 1][k] = max(f[j + 1][k - 1], f[j][k - 1]) + 1;
                }
            }
        }
    }

    cout << f[m][x] << '\n';
}

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

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

G. Toxel 与字符画

题意

略。

题解

无聊的模拟题。

代码

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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include "bits/stdc++.h"

using namespace std;
using i64 = long long;
using i128 = __int128;

constexpr i64 inf = 1E18;

i64 mul(i64 a, i64 b) {
    i128 res = static_cast<i128>(a) * b;
    if (res > inf) {
        return inf + 1;
    }
    return res;
}

i64 power(i64 a, i64 b) {
    i64 res = 1;
    for (; b; b >>= 1, a = mul(a, a)) {
        if (b & 1) {
            res = mul(res, a);
        }
    }
    return res;
}

vector<string> a = {
    "................................................................................",
    "................................................................................",
    "0000000.......1.2222222.3333333.4.....4.5555555.6666666.7777777.8888888.9999999.",
    "0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
    "0.....0.......1.......2.......3.4.....4.5.......6.............7.8.....8.9.....9.",
    "0.....0.......1.2222222.3333333.4444444.5555555.6666666.......7.8888888.9999999.",
    "0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
    "0.....0.......1.2.............3.......4.......5.6.....6.......7.8.....8.......9.",
    "0000000.......1.2222222.3333333.......4.5555555.6666666.......7.8888888.9999999.",
    "................................................................................"
};

vector<string> b = {
    "............................................................",
    "00000.....1.22222.33333.4...4.55555.66666.77777.88888.99999.",
    "0...0.....1.....2.....3.4...4.5.....6.........7.8...8.9...9.",
    "0...0.....1.22222.33333.44444.55555.66666.....7.88888.99999.",
    "0...0.....1.2.........3.....4.....5.6...6.....7.8...8.....9.",
    "00000.....1.22222.33333.....4.55555.66666.....7.88888.99999.",
    "............................................................",
    "............................................................",
    "............................................................",
    "............................................................"
};


vector<string> c = {
    "................................",
    "................................",
    "........IIIIIII.N.....N.FFFFFFF.",
    "...........I....NN....N.F.......",
    "=======....I....N.N...N.F.......",
    "...........I....N..N..N.FFFFFFF.",
    "=======....I....N...N.N.F.......",
    "...........I....N....NN.F.......",
    "........IIIIIII.N.....N.F.......",
    "................................"
};

void solve() {
    i64 A, B;
    scanf("%lld^{%lld}", &A, &B);
    int N = 10;
    i64 res = power(A, B);
    vector<string> ans(N);
    for (int i = 0; i < N; i++) {
        ans[i] += ".";
    }
    auto get = [&](const int &l, const int &len, const vector<string> &s) {
        for (int i = 0; i < N; i++) {
            ans[i] += s[i].substr(l, len);
        }

    };

    string SA = to_string(A);
    string SB = to_string(B);
    for (auto &x : SA) {
        int y = x - '0';
        get(y * 8, 8, a);
    }
    for (auto &x : SB) {
        int y = x - '0';
        get(y * 6, 6, b);
    }
    get(0, 8, c);
    if (res > inf) {
        get(8, 24, c);
    } else {
        string t = to_string(res);
        for (auto &x : t) {
            int y = x - '0';
            get(y * 8, 8, a);
        }
    }
    for (auto &x : ans) {
        cout << x << '\n';
    }
}

int main() {

    int t;
    scanf("%d", &t);
    while (t--) {
        solve();
    }

    return 0;
}

J. Mocha 沉迷电子游戏

题意

给定起始点 PP 和线段 ABAB，保证三角形PABPAB 为等腰三角形。PP 以速度 vv 移动，至多移动 tt 秒，记最终位置为 QQ。求所有的三角形 QABQAB 的面积并。

题解

PP 的运动范围是个圆。分线段 ABAB 完全在圆内，部分在圆内和完全在圆外三种情况讨论就可以了。

代码

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 i64 = long long;

using Real = double;
using Point = complex<Real>;

const double Pi = acos(-1.0);

void solve() {
    int x, y;
    cin >> x >> y;
    Point p = Point(x, y);
    cin >> x >> y;
    Point a = Point(x, y);
    cin >> x >> y;
    Point b = Point(x, y);
    int v, t;
    cin >> v >> t;
    int r = v * t;
    Point c = (a + b) / 2.0;
    const double pa = abs(p - a);
    const double pc = abs(p - c);
    const double ab = abs(a - b);
    double ans = 0;
    const double ad = sqrt(pa * pa - 1LL * r * r);
    if (r > pa) {
        cout << Pi * r * r << '\n';
        return;
    }
    if (r <= pc) {   
        ans += ad * r;
        ans += pc * ab / 2;
        double ang = asin(ad / pa) + asin(ab / 2 / pa);
        ans += (Pi - ang) * r * r;
    } else {
        ans += ad * r * 2;
        double ang = asin(ad / pa);
        ans += (Pi - 2 * ang) * r * r;
    }
    cout << ans << '\n';
}

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

    cout << fixed << setprecision(15);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }   

    return 0;
}
ACM > 2023省赛
2023 CCPC Henan Provincial Collegiate Programming Contest
https://je3ter.github.io/2023/07/30/ACM/2023 CCPC Henan Provincial Collegiate Programming Contest/
作者
Je3ter
发布于
2023年7月30日
许可协议