[R43E]听取蛙声一片1

#include <bits/stdc++.h>
using namespace std;
struct Node
{
    // 位置，是否有青蛙
    int x, y, z;
};
int n, m;
char g[1005][1005];
queue<Node> q;
int dis[1005][1005][2];
bool vis[1005][1005][2];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    q.push({1, 1, 0});
    dis[1][1][0] = 0;
    vis[1][1][0] = true;
    while (!q.empty())
    {
        Node now = q.front();
        q.pop();
        // 捡青蛙
        if (g[now.x][now.y] == 'F' && now.z == 0)
        {
            int x = now.x;
            int y = now.y;
            int z = 1;
            if (!vis[x][y][z])
            {
                q.push({x, y, z});
                vis[x][y][z] = true;
                dis[x][y][z] = dis[now.x][now.y][now.z] + 1;
            }
        }
        // 手拿青蛙在树上
        if (g[now.x][now.y] == '#' && now.z == 1)
        {
            int x = now.x;
            int y = now.y;
            int z = 0;
            if (!vis[x][y][z])
            {
                q.push({x, y, z});
                vis[x][y][z] = true;
                dis[x][y][z] = dis[now.x][now.y][now.z] + 1;
            }
            // 此时不能走四个方向
            continue;
        }
        // 四个方向走
        for (int i = 0; i < 4; i++)
        {
            int x = now.x + dx[i];
            int y = now.y + dy[i];
            int z = now.z;
            if (vis[x][y][z])
                continue;
            if (x < 1 || x > n ||
                y < 1 || y > m)
                continue;
            if (g[x][y] == '#' && z == 0)
                continue;
            q.push({x, y, z});
            vis[x][y][z] = true;
            dis[x][y][z] = dis[now.x][now.y][now.z] + 1;
        }
    }
    int ans;
    if (vis[n][m][0] && !vis[n][m][1])
        ans = dis[n][m][0];
    else if (!vis[n][m][0] && vis[n][m][1])
        ans = dis[n][m][1];
    else
        ans = min(dis[n][m][0], dis[n][m][1]);
    cout << ans << "\n";
    return 0;
}

[R42C]神奇宝箱

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int n;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    int l, r;
    l = r = 0;
    int now, num; // 当前等级，数量
    now = 1, num = 1;
    int ans = 0;
    while (r < n)
    {
        // 用不完 num 个的话，能用几个是几个
        if (r + num > n)
            num = n - r;
        l = r + 1;
        r = l + num - 1;
        // l~r 这些 now 等级的
        int sum; // l~r 的区间和
        if ((l + r) % 2 == 0)
            sum = ((l + r) / 2 % MOD) * (num % MOD) % MOD;
        else
            sum = ((l + r) % MOD) * ((num / 2) % MOD) % MOD;
        ans = (ans + now % MOD * sum % MOD) % MOD;
        // 换成下一个等级
        now++, num *= 2;
    }
    cout << ans * 2 % MOD << "\n";
    return 0;
}

[R42E]职位调整

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[4005], b[4005], p[4005];
int w[4005];
int dp[4005][4005];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    for (int i = 2; i <= n; i++)
        cin >> p[i];

    w[1] = 1;
    for (int i = 2; i <= n; i++)
        w[i] = w[p[i]] + i;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = 0;
            // 不替换 a[i]
            dp[i][j] = max(dp[i][j], dp[i - 1][j] + a[i] * w[i]);
            if (j == 0)
                continue;
            // 用 b[j] 替换 a[i]
            dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + b[j] * w[i]);
            // 用 b[<j] 替换 a[i]
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);
        }
    cout << dp[n][m];
    return 0;
}

【HT-089-Div.4】核桃新手组周赛

https://htoj.com.cn/cpp/oj/contest/detail?cid=22589816735488

P10983 替换

特殊性质 20 分

#include<bits/stdc++.h>
using namespace std;
int main(){
    int T;
    cin>>T;
    while(T--){
        string s,t;
        cin>>s>>t;
        if(s.size()<t.size())
            cout<<"NO\n";
        else
            cout<<"YES\n";
    }
    return 0;
}

子串性质，暴力枚举 40 分

#include<bits/stdc++.h>
using namespace std;
string s,t;
// 检查 s[l]~s[r] 是不是 t[0]~t[t.size()-1]
bool check(int l,int r){
    for(int i=l;i<=r;i++)
        if(s[i]!='?' && s[i]!=t[i-l])
            return false;
    return true;
}
void work(){
    cin>>s>>t;
    // 希望 t 是 s 的某个子串
    if(s.size()<t.size())
    {      
        cout<<"NO\n";
        return;
    }
    for(int i=0;i+t.size()-1<s.size();i++){
        // 如果 t 是 s[i]~s[i+t.size()-1] 就找到了
        if(check(i,i+t.size()-1))
        {
            cout<<"YES\n";
            return;
        }
    }
    cout<<"NO\n";
    return;
}
int main(){
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

正解

容易发现问号能用上就用，不然就浪费了。

#include<bits/stdc++.h>
using namespace std;
string s,t;
void work(){
    cin>>s>>t;
    // 希望 t 是 s 的某个子序列
    for(int i=0,j=0;i<t.size();i++){
        // 在 s[j]~末尾寻找 t[i]
        while(j+1<s.size() && s[j]!='?' && s[j]!=t[i])
            j++;
        // 1. 停在匹配的位置
        // 2. 找不到的时候停在最后一位
        if(s[j]=='?' || s[j]==t[i])
            j++;
        else
        {
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
    return;
}
int main(){
    int T;
    cin>>T;
    while(T--)
        work();
    return 0;
}

P10984 爱好

处理 R=1，意外拿到 40 分

#include<bits/stdc++.h>
using namespace std;
int r,c;
string s;
// cnt[i][1]: s[0]~s[i] 有几个 A
// cnt[i][2]: s[0]~s[i] 有几个 AB
// cnt[i][3]: s[0]~s[i] 有几个 ABC
long long cnt[1005][4];
int main(){
    cin>>r>>c;
    cin>>s;
    // 在 s 里面找 ABC
    cnt[0][1]=cnt[0][2]=cnt[0][3]=0;
    if(s[0]=='A')
        cnt[0][1]=1;
    for(int i=1;i<s.size();i++)
    {
        // 先继承之前的数量
        cnt[i][1]=cnt[i-1][1];
        cnt[i][2]=cnt[i-1][2];
        cnt[i][3]=cnt[i-1][3];
        // 看一下这一位多了几个
        if(s[i]=='A')
            cnt[i][1]++;
        // 之前几个 A 这里就有几个 AB
        if(s[i]=='B')
            cnt[i][2]+=cnt[i][1];
        // 之前几个 AB 这里就有几个 ABC
        if(s[i]=='C')
            cnt[i][3]+=cnt[i][2];
    }
    cout<<cnt[s.size()-1][3];
    return 0;
}

每一行每一列都按照40分的代码处理

#include<bits/stdc++.h>
using namespace std;
int r,c;
// cnt[i][1]: s[0]~s[i] 有几个 A
// cnt[i][2]: s[0]~s[i] 有几个 AB
// cnt[i][3]: s[0]~s[i] 有几个 ABC
string s;
long long cnt[1005][4];
// 返回字符串 s 里面有几个 ABC
int cal(){
    // 在 s 里面找 ABC
    cnt[0][1]=cnt[0][2]=cnt[0][3]=0;
    if(s[0]=='A')
        cnt[0][1]=1;
    for(int i=1;i<s.size();i++)
    {
        // 先继承之前的数量
        cnt[i][1]=cnt[i-1][1];
        cnt[i][2]=cnt[i-1][2];
        cnt[i][3]=cnt[i-1][3];
        // 看一下这一位多了几个
        if(s[i]=='A')
            cnt[i][1]++;
        // 之前几个 A 这里就有几个 AB
        if(s[i]=='B')
            cnt[i][2]+=cnt[i][1];
        // 之前几个 AB 这里就有几个 ABC
        if(s[i]=='C')
            cnt[i][3]+=cnt[i][2];
    }
    return cnt[s.size()-1][3];
}
char g[1005][1005];
int main(){
    cin>>r>>c;
    for(int i=1;i<=r;i++)
        for(int j=1;j<=c;j++)
            cin>>g[i][j];
    long long ans = 0;
    // 每一行算一下
    for(int i=1;i<=r;i++){
        s="";
        for(int j=1;j<=c;j++)
            s+=g[i][j];
        ans+=cal();
    }
    // 每一列算一下
    for(int j=1;j<=c;j++)
    {
        s="";
        for(int i=1;i<=r;i++)
            s+=g[i][j];
        ans+=cal();
    }
    cout<<ans;
    return 0;
}