其他OJ题解

5 comments

  • @ 2026-1-18 16:18:31

    [R46D]四元组

    #include <bits/stdc++.h>
using namespace std;
int n;
int a[2000 + 5];
// 右边的每种和出现了几次
int cnt[2000 + 2000 + 5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    // 初始所有数都在右边
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            cnt[a[i] + a[j]]++;
    // 枚举 a[i] 丢到左边带来的新贡献
    long long ans = 0;
    for (int i = 1; i <= n; i++)
    {
        // 把 a[i] 对右边 cnt 的贡献消除
        for (int j = i + 1; j <= n; j++)
            cnt[a[i] + a[j]]--;
        // 用 a[i] 与左边的元素组合，统计产生的贡献
        for (int j = 1; j <= i - 1; j++)
            ans += cnt[a[i] + a[j]];
    }
    cout << ans;
    return 0;
}
    • @ 2026-1-18 15:34:17
      Edited

      [R46E]机器

      没有调用机器，直接差分数组维护所有区间修改

      #include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200000;
const int MOD = 1'000'000'000 + 7;
int n, m, q;
struct Mac
{
    int typ, l, r, x;
};
Mac mac[MAXN + 5];
int cnt[MAXN + 5]; // 每台机器被调用的次数
int num[MAXN + 5]; // 每个盒子的糖果数量
int d[MAXN + 5];   // 差分数组
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        cin >> mac[i].typ;
        if (mac[i].typ == 1)
            cin >> mac[i].l >> mac[i].r >> mac[i].x;
        if (mac[i].typ == 2)
            cin >> mac[i].l >> mac[i].r;
    }
    // q 次直接调用
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        d[l]++, d[r + 1]--;
    }
    // 还原出每台机器被直接调用的次数
    for (int i = 1; i <= m; i++)
        cnt[i] = cnt[i - 1] + d[i];
    // 清空差分数组
    for (int i = 1; i <= m + 1; i++)
        d[i] = 0;
    // 子任务 1，每台机器的使用次数已经确定
    for (int i = 1; i <= m; i++)
    {
        if (mac[i].typ == 2)
            continue;
        d[mac[i].l] = (d[mac[i].l] + mac[i].x * cnt[i] % MOD) % MOD;
        d[mac[i].r + 1] = (d[mac[i].r + 1] - mac[i].x * cnt[i] % MOD) % MOD;
    }
    for (int i = 1; i <= n; i++)
        num[i] = ((num[i - 1] + d[i]) % MOD + MOD) % MOD;
    for (int i = 1; i <= n; i++)
        cout << num[i] << " ";
    cout << "\n";
    return 0;
}

      用树状数组维护机器之间的调用

      实际上倒着做差分数组也可以。

      #include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 200000;
const int MOD = 1'000'000'000 + 7;
int n, m, q;
struct Mac
{
    int typ, l, r, x;
};
Mac mac[MAXN + 5];
int cnt[MAXN + 5]; // 每台机器被调用的次数
int num[MAXN + 5]; // 每个盒子的糖果数量
int d[MAXN + 5];   // 差分数组
// 树状数组来实现机器的调用次数
int lowbit(int x)
{
    return x & -x;
}
int t[MAXN + 5];
void update(int x, int y)
{
    for (int i = x; i <= m; i += lowbit(i))
        t[i] = (t[i] + y) % MOD;
}
int query(int x)
{
    int res = 0;
    for (int i = x; i >= 1; i -= lowbit(i))
        res = (res + t[i]) % MOD;
    return res;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)
    {
        cin >> mac[i].typ;
        if (mac[i].typ == 1)
            cin >> mac[i].l >> mac[i].r >> mac[i].x;
        if (mac[i].typ == 2)
            cin >> mac[i].l >> mac[i].r;
    }
    // q 次直接调用
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        update(l, 1);
        update(r + 1, -1);
    }
    // 处理机器之间的调用
    for (int i = m; i >= 1; i--)
    {
        cnt[i] = query(i);
        if (mac[i].typ == 2)
        {
            update(mac[i].l, cnt[i]);
            update(mac[i].r + 1, -cnt[i]);
        }
    }
    // 清空差分数组
    for (int i = 1; i <= m + 1; i++)
        d[i] = 0;
    // 子任务 1，每台机器的使用次数已经确定
    for (int i = 1; i <= m; i++)
    {
        if (mac[i].typ == 2)
            continue;
        d[mac[i].l] = (d[mac[i].l] + mac[i].x * cnt[i] % MOD) % MOD;
        d[mac[i].r + 1] = (d[mac[i].r + 1] - mac[i].x * cnt[i] % MOD) % MOD;
    }
    for (int i = 1; i <= n; i++)
        num[i] = ((num[i - 1] + d[i]) % MOD + MOD) % MOD;
    for (int i = 1; i <= n; i++)
        cout << num[i] << " ";
    cout << "\n";
    return 0;
}
      • @ 2026-1-2 16:53:43

        [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;
}
        • @ 2025-12-20 10:51:28
          Edited

          [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;
}
          • @ 2025-12-11 14:16:37
            Edited

            【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;
}
            • 1
            1126
            Accepted
            0
            Solutions Liked
            1. Judging Queue
            2. Service Status
            3. Legacy mode
            4. Theme
            2. 陕ICP备2024054233号
            3. Worker 0, 15ms
            4. Powered by Hydro v5.0.0-beta.16 Community, Modified by 33DAI