haue20221008

A. 6男

题目大意 ：

给定一个字符串 $S$，求最长的连续的 $6$ 的子串的长度。
- $$S$$ 可能含有空格。

思想：

签到题。
- 读入时注意空格。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){
    int res = 0;
    string s; getline(cin, s);
    for(int i = 0; i < s.size(); i ++){
        int cnt = 0;
        while(s[i] == '6'){
            cnt ++;
            if(i < s.size()) i ++;
            res = max(res, cnt);
        }
    }
    cout << res << endl;
}

int main(){
    IOS;
    int _ = 1;
    // cin >> _;
    while(_ --){
        solve();
    }
    return 0;
}

B. 我要拿最多的Money2.0

原题链接

题目大意 ：

给定 $n$ 行 $m$ 列的矩阵，和 $q$ 个坐标。
- 以这些 $$q$$ 个坐标为中心的点，曼哈顿距离小于等于 $$2$$ 的点的金币无法得到。
- 求剩余可以得到的点的金币的最大值。

思想：

签到题。
- 通过偏移量数组枚举所有无法得到金币的坐标。
- 除掉这些坐标后扫一遍，维护最值即可。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

const int N = 110;

int mp[N][N];

int n, m, q;

bool check(int l, int r){
    if(l >= 0 && l < n && r >= 0 && r < m) return 1;
    return 0;
}

int dx[] = {-2, -1, -1, -1, 0, 0, 0, 0, 0, 1, 1, 1, 2};
int dy[] = {0, -1, 0, 1, -2, -1, 0, 1, 2, -1, 0, 1, 0};

void st(int l, int r){
    for(int i = 0; i < 13; i ++){
        int x = l + dx[i], y = r + dy[i];
        if(check(x, y)) mp[x][y] = 0;  
    }
}

void solve(){

    cin >> n >> m >> q;
    for(re int i = 0; i < n; i ++){
        for(re int j = 0; j < m; j ++){
            cin >> mp[i][j];
        }
    }

    while(q --){
        int l, r;
        cin >> l >> r;
        st(l, r);
    }

    int ans = 0;
    for(re int i = 0; i < n; i ++){
        for(re int j = 0; j < m; j ++){
            ans = max(ans, mp[i][j]);
        }
    }

    if(ans == 0) cout << -1 << endl;
    else cout << ans << endl;

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

C. 极致到完美的AK

原题链接

题目大意 ：

给定一个只包含 $0,2,5$ 的字符串 $S$。
- 对应若为 $$0$$ 输出 $$5$$ ，若为 $$2$$ 输出 $$0$$ ，若为 $$5$$ 输出 $$2$$ 。

思想：

签到题。
- 判断输出。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

const int N = 110;

void solve(){

    string s; cin >> s;
    for(int i = 0; i < s.size(); i ++){
        if(s[i] == '5') cout << 2;
        else if(s[i] == '2') cout << 0;
        else if(s[i] == '0') cout << 5;
    }

    return ;

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;
}

D. 吃豆人

原题链接

题目大意：

给定起始和终点坐标、矩阵的大小及障碍的坐标。
- 判断在可以打破"空气墙"的情况下，能否到达终点。
- "空气墙"的定义为非实心的连续块。

思想：

思维题。
- 只要起点和终点的上下左右四个方向上有一处不存在障碍，就可以不断满足空气墙的条件，进而不断地打破墙。
- 故只需要判断起点和终点的四个方向上的状态即可，另外注意起点和终点重合的情况。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

int n, m;
int sx, sy, ex, ey;

const int N = 100;

char mp[N][N];
int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

bool check(int l, int r){
    if(l >= 0 && l < n && r >= 0 && r < m && mp[l][r] != '*') return true;
    return false;
}

void solve(){
    cin >> sx >> sy >> ex >> ey;
    cin >> n >> m;

    for(int i = 0; i < n; i ++){
        for(int j = 0; j < m; j ++){
            mp[i][j] = '.';
        }
    }

    for(int i = 0; i < m; i ++){
        int x, y;
        cin >> x >> y;
        mp[x][y] = '*';
    }

    int vis1 = 0, vis2 = 0;

    for(int i = 0; i < 4; i ++){
        int x = sx + dx[i], y = sy + dy[i];
        if(check(x, y)){
            if(mp[x][y] == '.'){
                vis1 = 1; break;
            }
        }
    }

    for(int i = 0; i < 4; i ++){
        int x = ex + dx[i], y = ey + dy[i];
        if(check(x, y)){
            if(mp[x][y] == '.'){
                vis2 = 1; break;
            }
        }
    }

    if(vis1 && vis2 || (sx == ex && sy == ey)) cout << "Yes!" << endl;
    else cout << "No!" << endl;

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

E. 胡辣汤啊胡辣汤

原题链接

题目大意 ：

给定矩形范围的左上角和右下角的坐标。
- 判断若干点到该矩形边界的最短距离，输出最短距离的点的编号。

思想：

思维题。
- 对于一个点，可以暴力枚举其到四条边的直线距离和到四个顶点的直线距离，取最小值即可。
- 也可以通过粗略判断点的坐标关系，减少枚举和计算不必要的距离。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

const int N = 110;

int n;

double X1, X2, Y1, Y2, cnt = 1e8;

bool check(int l, int r) {
    double t = 1e8;
    if (l >= X1 && l <= X2) t = min(fabs(r - Y1), fabs(r - Y2));
    else if (r >= Y1 && r <= Y2) t = min(fabs(l - X1), fabs(l - X2));
    double p = min(min(sqrt((l - X1) * (l - X1) + (r - Y2) * (r - Y2)), sqrt((l - X1) * (l - X1) + (r - Y1) * (r - Y1))), min(sqrt((l - X2) * (l - X2) + (r - Y1) * (r - Y1)), sqrt((l - X2) * (l - X2) + (r - Y2) * (r - Y2))));
    if (cnt > min(t, p)) {
        cnt = min(t, p);
        return 1;
    }
    return 0;
}

void solve() {
    cin >> n;
    cin >> X1 >> Y1 >> X2 >> Y2;

    int num = INF;
    double res = 1e8;
    int flag = 0;

    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        if (check(l, r)) {
            flag = i;
            res = cnt;
        }
    }

    cout << flag << endl;
}

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

    int _ = 1;
    // cin >> _;

    while (_--) {
        solve();
    }

    return 0;
}

F. HF波那契数列

原题链接

题目大意：

类似斐波那契数列，构造 (HF) 波那契数列： $G_n = G_{n - 1} + G_{n - 2}$ 其中 (G_0 = 1, G_1 = t (0 < t))。
给定 (i) 和 (G_i)，求满足条件的 (G_i \mod 19960515) 的值。
若不存在，则输出 (-1)。

思想：

思维题：

列出部分 $G$ 波那契数列：
- $G_0, G_1, G_2, G_3, G_4, G_5 \dots$
- $1, t, t+1, 2t+1, 3t+2, 5t+3 \dots$
设 $G_i = x_i \cdot t + y_i$，其中 $x_i$ 和 $y_i$ 为系数。从 $i=0$ 开始观察可知：
- $$x_i$$ 满足： $0, 1, 1, 2, 3, 5 \dots$ ，即 $$x$$ 从 $$i=1$$ 开始构成斐波那契数列。
- $$y_i$$ 满足： $0, 0, 1, 1, 2, 3 \dots$ ，即 $$y$$ 从 $$i=2$$ 开始构成斐波那契数列。
因此，对于给定的 $$G_i$$ 值 $$g$$ ，我们可以由 $$t = (g - y_i) / x_i$$ 求得对应的 $$t$$ 值（需满足 $$t>0$$ 且整除）。
由于数据范围可能很大，但斐波那契数列增长极快，我们只需预处理出前几十项（例如 90 项以内，因为之后数值将超出常用整数范围）的原始斐波那契数列，即可直接查询 $$x_i$$ 和 $$y_i$$ ，而无需递推。
注意：最终输出结果需要对 $$19960515$$ 取模。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int MOD = 19960515;
const int MAX_PRE = 90; // 预处理长度，斐波那契数列第90项已远超1e18

LL fib[MAX_PRE]; // 存储原始斐波那契数列，fib[0]=0, fib[1]=1, fib[2]=1, ...

void init() {
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i < MAX_PRE; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
        // 注意：此处不取模，保留原始值用于计算t
    }
}

void solve() {
    LL i, g, j;
    cin >> i >> g >> j;

    // 检查i和j是否在预处理范围内，并且x_i (fib[i]) 不为0
    if (i >= MAX_PRE || i < 1 || fib[i] == 0 || j >= MAX_PRE || j < 1) {
        cout << -1 << endl;
        return;
    }

    LL x_i = fib[i];
    LL y_i = fib[i - 1]; // 根据规律，y_i = x_{i-1}

    // 检查(g - y_i)是否能被x_i整除，并且得到的t为正整数
    if ((g - y_i) % x_i != 0) {
        cout << -1 << endl;
        return;
    }
    LL t = (g - y_i) / x_i;
    if (t <= 0) {
        cout << -1 << endl;
        return;
    }

    // 计算G_j = x_j * t + y_j，并对MOD取模
    LL x_j = fib[j];
    LL y_j = fib[j - 1];
    // 先对乘法部分取模，防止溢出（虽然t和x_j可能很大，但取模后计算）
    LL res = ((x_j % MOD) * (t % MOD)) % MOD;
    res = (res + (y_j % MOD)) % MOD;

    cout << res << endl;
}

int main() {
    IOS;

    init(); // 预处理原始斐波那契数列

    int _ = 1;
    cin >> _;

    while (_--) {
        solve();
    }

    return 0;
}

G. 解析密码

原题链接

题目大意 ：

给定一串数字，输出其反转后不含前导零的形式。
- 若为负数，则负号无需翻转，且 $$-0$$ 翻转后仍为 $$-0$$ 。

思想：

模拟题。
- 读入为字符串的形式，判断首元素是否为 -。
- 然后翻转该字符串，去除掉第一个非 $$0$$ 数出现之前的前导 $$0$$ ，若所有的数全为 $$0$$ ，则只保留一个。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve(){

    string s; cin >> s;

    int flag = 0;

    if(s[0] == '-'){
        cout << '-';
        for(int i = 1; i < s.size(); i ++){
            if(s[i] != '0'){
                flag = i;
                break;
            }
        }
        if(flag == 0){
            cout << 0 << endl;
            return ;
        }
    }
    else{
        bool vis = 0;
        for(int i = 0; i < s.size(); i ++){
            if(s[i] != '0'){
                flag = i;
                vis = 1; break;
            }
        }
        if(!vis){
            cout << 0 << endl;
            return;
        }
    }

    reverse(s.begin(), s.end());

    for(int i = 0; i < s.size() - flag; i ++){
        if(i == 0) while(s[i] == '0') i ++;
        cout << s[i];
    }

}

int main(){

    IOS;

    int _ = 1;

    // cin >> _;

    while(_ --){
        solve();
    }

    return 0;

}

H. 苦命的毅哥

原题链接

题目大意 ：

给定 $n$ 个字符串，统计字符串 "我ZY就喜欢这个" 和 "我ZY实名邀请您于圣源二楼就餐" 出现的次数。
- 分别输出对应次数，两者之和大于 $$3$$ 时额外输出 $$6$$ 。

思想：

签到题。
- 读入判断统计次数。
- 注意直接复制题面的字符串即可。

代码：

cpp

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define IOS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define re register
#define fi first
#define se second
#define endl '\n'

typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

const int N = 1e6 + 3;
const int INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-6, PI = acos(-1);

void solve() {
    int t; cin >> t;
    int cnt1 = 0, cnt2 = 0;
    while (t--) {
        string s; cin >> s;
        if (s == "我ZY就喜欢这个") cnt1++;
        if (s == "我ZY实名邀请您于圣源二楼就餐") cnt2++;
    }
    cout << cnt1 << " " << cnt2 << endl;
    if (cnt1 + cnt2 > 3) cout << 6 << endl;
}

int main() {
    IOS;
    int _ = 1;
    // cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}

5. 动态规划

6. 学校培训

动态规划

搜索

数学

贪心

字符串

图论

力扣

其他

Acwing

Codeforces

Atcoder

CCPC

LeetCode

haue20221008

A. 6男

B. 我要拿最多的Money2.0

C. 极致到完美的AK

D. 吃豆人

E. 胡辣汤啊胡辣汤

F. HF波那契数列

G. 解析密码

H. 苦命的毅哥

haue20221008 ​

A. 6男 ​

B. 我要拿最多的Money2.0 ​

C. 极致到完美的AK ​

D. 吃豆人 ​

E. 胡辣汤啊胡辣汤 ​

F. HF波那契数列 ​

G. 解析密码 ​

H. 苦命的毅哥 ​

haue20221008

A. 6男

B. 我要拿最多的Money2.0

C. 极致到完美的AK

D. 吃豆人

E. 胡辣汤啊胡辣汤

F. HF波那契数列

G. 解析密码

H. 苦命的毅哥