A-Bridging the Gap 2

题意

在河岸的一侧有$n$个人，每个人有一个体力值$h_i$，有一艘船可以将人从一侧载到另一侧，每次航行需要至少$L$个人掌舵，每次掌舵会花费每个掌舵人的一点体力，当体力不足一点时，这个人不能再掌舵，船的容量最大是$R$，提问是否能够将这些人都运送到对岸。

数据范围

• $1\leq L\lt R\leq n\leq 5\times 10^5$​
• $1\leq h_i\leq 5\times 10^5$

思路

贪心的运输，从左岸运输的最小次数是$k=\lceil \frac{n-R}{R-L} \rceil$，计算每个人最多的来回次数$a_i$，假如满足$\sum_{i-1}^{n} min(k,a_i)\geq k\times L$，则可以将所有人都运输到对岸。

1001-循环位移

$(709/3775)$

题意

将字符串$S=S_0+S_1+S_2+…+S_{n-1}$循环位移$k$次后得到$S(k)=S_{k\bmod n }+…+S_{n-1}+S+0+…+S_{(k-1)\bmod n}$。

定义$[A]={A(k),k\in N}$。给出$T$组串$A,B$，询问$B$有多少个子串在$[A]$​中。

数据范围

• $|A|\leq |B|$
• $\sum|B|\leq 1048576$

思路

思路1：字符串哈希

记字符串$A$的长度是$n$，将字符串$A$转变为首尾相连的样子（$A=A+A.substr(1,n-1)$），并计算其中每个长度为$n$的哈希值，用map存值，再对字符串$B$进行哈希，同样也对长度为$n$的子串计算哈希值，若有符合的则计数。

代码

代码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

ll ha[maxn], hb[maxn];
ll pwr[maxn];

void solve() {
    string a, b;cin >> a >> b;
    ll n = a.size();
    a = a.substr(1, n - 1) + a;
    ll la = a.size(), lb = b.size();
    a = " " + a, b = " " + b;
    pwr[0] = 1;
    map<ll, bool>mp;
    for (ll i = 1;i <= la;i++) {
        ha[i] = ha[i - 1] * bas1 + a[i];
        pwr[i] = pwr[i - 1] * bas1;
        if (i - n >= 0) {
            ll x = ha[i] - ha[i - n] * pwr[n];
            mp[x] = true;
        }
    }
    ll ans = 0;
    for (ll i = 1;i <= lb;i++) {
        hb[i] = hb[i - 1] * bas1 + b[i];
        if (i - n >= 0) {
            ll x = hb[i] - hb[i - n] * pwr[n];
            if (mp.count(x)) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

1002-星星

$(991/1659)$

A-Floor Tiles

题意

存在A型、B型两种砖：

现用这两种砖拼成$N\times M$的矩形，提问是否有恰好存在$K$条曲线的平铺方式，曲线如下：

数据范围

• $1\leq T\leq 10^5$
• $1\leq N,M\leq 800$
• $1\leq K \leq 2\times N\times M$

思路

边缘一圈的点所在的线一定不是一个环，所以最少的线数相当于都是A型或B型时的线数，也就是$N\times M$个，若要比$N\times M$个多，则多的部分只能是图形中环的数目，贪心的让所有的环最小，则能构造出最多的环，最小的环如例图中一样，当平铺的方式是 $$ AB\\BA $$ 时，形成的环是最小的。

A-Bit Common

题意

计算满足长度为$n$，每个元素小于$2^m$，且存在至少一个子序列满足按位$AND$后是$1$的序列的数量。

答案对正整数$q$取模。

数据范围

• $1\leq n,m\leq 5000$
• $1\leq q\leq 10^9$

思路

按位分析，对于一个长度为$n$的序列，序列中的数分为$k$个末尾是$1$的数和$n-k$个末尾是$0$的数。

• 末尾为$1$的数中，除末位以外的数位（$m-1$位），每一位的组合是$2^k-1$种（要除去全为1的情况）。
• 末尾为$0$的数中，除末位以外数位上的取值是任意的。
• 选择哪些数是末尾$1$需要考虑组合数。

所以，总方案数是： $$ \binom{n}{k}\times (2^k-1)^{m-1}\times (2^{n-k})^{(m-1)} = \binom{n}{k}\times (2^n-2^{n-k})^{m-1} $$ 最后对$q$取模即可。

前言

本篇记录利用 github action 实现自动化构建和部署的过程。

本站除了部署在 github page 上，还部署在本人的服务器上，懒惰的 ddl 直到现在才去上手实验，因此利用在 github action 中实现两种部署方式。

GYM地址：2024吉林省赛

题目顺序按照从易到难排序。

I. The Easiest Problem

题意

数一数

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
    string s = "Scan the QR code to sign in now.";
    ll cnt = 0;
    for (auto c : s) {
        if (c <= 'z' && c >= 'a')cnt++;
    }
    cout << cnt << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _ = 1;
    // cin >> _;cin.get();
    while(_--)
        solve();

    return 0;
}

L. Recharge

题意

有$x$次获得$1$格能量的机会，$y$次获得$2$格能量的机会，充满一个电池需要$k$格能量，溢出的能量会被浪费，问最多能充满多少电池。