T1

https://bs.daimayuan.top/p/350

T2

https://bs.daimayuan.top/p/356

T3

https://bs.daimayuan.top/p/351

T4

https://bs.daimayuan.top/p/337

T1

https://codeforces.com/contest/2225/problem/D

给定两个整数 $n$ 和 $x$。在序列 $[1, 2, 3, \dots, n]$ 中，你需要求出满足以下条件的子区间 $[l, r]$ 的个数：

1. 区间必须包含 $x$，即 $1 \le l \le x \le r \le n$。
2. 区间内所有元素的异或和为 $0$，即 $l \oplus (l+1) \oplus \dots \oplus r = 0$。

答案可能会很大，需要对 $998244353$ 取模。

数据范围：

$1 \le x \le n \le 10^{18}$，$t \le 2 \cdot 10^5$。

T2

https://codeforces.com/contest/2219/problem/A

Roger 有 $p$ 个单位长度（长度为 1）的线段，以及 $q$ 个 L 型拼图（每个 L 型拼图由 2 个单位长度的线段成直角连接而成）。 他希望恰好用完这 $p$ 个线段和 $q$ 个 L 型拼图，拼出一个完整的 $n \times m$ 的网格。 如果可以拼出，输出任意满足条件的 $n$ 和 $m$；如果无论如何都拼不出，则输出 $-1$。

数据范围：

$1 \le t \le 100, 1 \le p, q \le 10^8$

T3

https://bs.daimayuan.top/p/358

$T$ 组询问，每次给一个整数 $n$。

求正整数三元组 ${x, y, z}$ 的数量：

• 取值范围：$1 \le x, y, z \le n$。
• 特殊性质：$x^2 - y^2 = z^3$。

数据范围：

• 20pts：$T \le 10, n \le 1000$
• 40pts: $T \le 10, n \le 10^5$
• 100pts：$T \le 10^5, n \le 10^6$

T4

https://codeforces.com/contest/2216/problem/C

给定一个长度为$n$的数组$a$，以及一个长度限制$k$和两个取模参数$p$与$q$（保证$p<q$）。 你可以执行任意次操作：每次选择一个长度**至少为$k$**的区间，将区间内的所有元素对$p$或对$q$取模。 求在执行任意次操作后，整个数组元素总和的最小值。

数据范围：

• $1 \le t \le 10^4$
• $1 \le k \le n \le 10^5, 1 \le p < q \le 10^9$
• $1 \le a_i \le 10^9$

T5

https://bs.daimayuan.top/p/364

给定一个长度为偶数 $n$ 的排列 $a$。你每次可以进行如下操作：

1. 将序列分为左半部分 $l$ ($a_1 \dots a_{n/2}$) 和右半部分 $r$ ($a_{n/2+1} \dots a_n$)。
2. 构造一个长度为 $n$ 的操作字符串，其中包含 $n/2$ 个 'l' 和 $n/2$ 个 'r'。
3. 按照字符串的指示，依次从 $l$ 或 $r$ 的队首弹出元素放入新数组 $b$。
4. 将 $a$ 更新为 $b$。

目标是在 $2n$ 次操作内，使 $a$ 变为单调递增序列 $1, 2, \dots, n$。

数据范围：

• 20pts：$a = [1, 3, 5, \dots, 2, 4, 6 \dots]$，$n \le 1000, k \le 2n$。
• 100pts：$n \le 1000, k \le 2n$**。

T6

https://bs.daimayuan.top/p/365

给定一个包含 n 个城市的有向图，城市编号为 0 到 n-1。对于任意城市 i，存在两条出边（传送门）：

• A 类边：指向 2i mod n
• B 类边：指向 (2i+1) mod n

目标：判断图中是否存在一条从 0 出发、恰好经过所有城市一次并回到 0 的回路（即哈密顿回路）。若存在，输出任意一种合法的传送门选择序列。

数据范围：

• 40pts：$n \le 20$
• 100pts：$n \le 10^6$

20260319

参考题解：https://oj.33dai.cn/paste/show/GhQxWtMBTRqw4zyq

abc447_c

给你由大写英文字母组成的字符串 $S$ 和 $T$ 。

您可以按任意顺序执行以下两种类型的运算任意次数（可能为零）：

• 在 $S$ 的任意位置（可能是开头或结尾）插入一个字符 A。
• 在 $S$ 中选择一个字符 A 并删除。其余字符按原来的顺序连接。

判断是否有可能使 $S$ 等于 $T$ ，如果有可能，求所需运算的最小总数。

https://atcoder.jp/contests/abc447/tasks/abc447_c

abc447_d

可以在一个字符串中删除一个子序列 ABC，问最多可以删除几次

https://atcoder.jp/contests/abc447/tasks/abc447_d

abc447_e

给你一个简单相连的无向图 $G$ ，其中有 $N$ 个顶点和 $M$ 条边。这里是 $N \geq 2$ 。顶点的编号为 $1$ 至 $N$ ，边的编号为 $1$ 至 $M$ ；每条边都有一个称为成本的值，边 $i$ 的成本为 $2^i$ 。

现在，您要删除 $G$ 中的一些边，这样 $G$ 的连通部分的数目就会正好变为 $2$ 。可以证明，在本问题的约束条件下，这总是可以实现的。

求删除的边的成本总和的最小值，模数为 $998244353$ 。

https://atcoder.jp/contests/abc447/tasks/abc447_e

abc448_c

$n$ 个数 $a_1\sim a_n$。$q$ 次询问。

每次需要求出去掉 $k(k\le 5)$ 个数后，剩下数的最小值。

https://atcoder.jp/contests/abc448/tasks/abc448_c

代码源 R51D

https://bs.daimayuan.top/p/318

ABC449E

给你一个整数 $N, M$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$ ，其中每个元素都介于 $1$ 和 $M$ 之间（含）。

对这个整数序列 $A$ 执行以下操作 $10^{100}$ 次：

• 设 $v$ 是 $1$ 和 $M$ 之间的整数，包括 $1$ 和 $M$ ，在 $A$ 中出现次数最少的整数。如果有多个这样的 $v$ ，取其中最小的一个。然后，将 $v$ 追加到 $A$ 的末尾。

您将得到 $Q$ 个查询。 $i$ -th 查询给出了一个整数 $X_i$ ，那么在执行 $10^{100}$ 次操作后，求出 $A_{X_i}$ 的值。

https://atcoder.jp/contests/abc449/tasks/abc449_e

ABC447F

https://atcoder.jp/contests/abc447/tasks/abc447_f

给你一棵树 $T$ ，其中有 $N$ 个顶点，编号为 $1$ 至 $N$ 。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$ 。

对于正整数 $k$ ，将 "长度为 $k$ 的蜈蚣图 "定义为通过以下步骤得到的具有 $3k$ 个顶点的图：

• 准备一个有 $k$ 个顶点的路径图。**个顶点。
• 为路径图中的每个顶点 $v$ 添加两个仅与 $v$ 相邻的新顶点。

求 "长度为 $x$ 的蜈蚣图 "作为树 $T$ 的子图所包含的最大值 $x$ 。

给出了 $Q$ 个测试用例，请逐一求解。

代码源 R51D

https://bs.daimayuan.top/p/318

省选 D1T1

https://www.luogu.com.cn/problem/P15649

abc447_c

给你由大写英文字母组成的字符串 $S$ 和 $T$ 。

您可以按任意顺序执行以下两种类型的运算任意次数（可能为零）：

• 在 $S$ 的任意位置（可能是开头或结尾）插入一个字符 A。
• 在 $S$ 中选择一个字符 A 并删除。其余字符按原来的顺序连接。

判断是否有可能使 $S$ 等于 $T$ ，如果有可能，求所需运算的最小总数。

https://atcoder.jp/contests/abc447/tasks/abc447_c

abc447_d

可以在一个字符串中删除一个子序列 ABC，问最多可以删除几次

https://atcoder.jp/contests/abc447/tasks/abc447_d

abc447_e

给你一个简单相连的无向图 $G$ ，其中有 $N$ 个顶点和 $M$ 条边。这里是 $N \geq 2$ 。顶点的编号为 $1$ 至 $N$ ，边的编号为 $1$ 至 $M$ ；每条边都有一个称为成本的值，边 $i$ 的成本为 $2^i$ 。

现在，您要删除 $G$ 中的一些边，这样 $G$ 的连通部分的数目就会正好变为 $2$ 。可以证明，在本问题的约束条件下，这总是可以实现的。

求删除的边的成本总和的最小值，模数为 $998244353$ 。

https://atcoder.jp/contests/abc447/tasks/abc447_e

abc448_c

$n$ 个数 $a_1\sim a_n$。$q$ 次询问。

每次需要求出去掉 $k(k\le 5)$ 个数后，剩下数的最小值。

https://atcoder.jp/contests/abc448/tasks/abc448_c

代码源 R51D

https://bs.daimayuan.top/p/318

#include <bits/stdc++.h>
using namespace std;
int n,P1,P2,P3,T1,T2;
int l[105],r[105];
bool t[1441];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>P1>>P2>>P3>>T1>>T2;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        for(int j=l[i];j<r[i];j++)
            t[j]=true;
    }
    // 状态  时间 精力 
    // 拼豆1  ~    P1
    // 保持2  T1   P1
    // 冥想3  T2   P2
    // 放松4  ~    P3
    int now=1;//状态
    int tim=0;//状态持续时间
    int ans=0;//总精力消耗
    for(int i=l[1];i<r[n];i++)
    {
        if(t[i])
        {
            //拼豆
            now=1;
            ans+=P1;
        }
        else if(!t[i]&&t[i-1])
        {
            //拼豆->保持
            now=2;
            tim=1;
            ans+=P1;
        }
        else if(now==2&&tim<T1)
        {
            // 保持
            tim++;
            ans+=P1;
        }
        else if(now==2&&tim==T1)
        {
            //保持->冥想
            now=3;
            tim=1;
            ans+=P2;
        }
        else if(now==3&&tim<T2)
        {
            // 冥想
            tim++;
            ans+=P2;
        }
        else
        {
            // 放松
            ans+=P3;
        }
    }
    cout<<ans<<"\n";
    return 0;
}

https://bs.daimayuan.top/p/300

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 500000;
int n, m, k; // 节点数量、变异数量、需要拿的果子数量
vector<int> e[MAXN + 5];
bool huai[MAXN + 5]; // huai[i] 为真表示坏果子
int num[MAXN + 5];   // 每个节点果子数量
// 前 D 层能否拿满 k 个果子
// f[i][0/1] 子树 i 在前 D 层最多拿几个果子（0 不拿节点 i，1 拿节点 i）
int f[MAXN + 5][2];
void dfs(int u, int fa, int d, int D)
{
    if (d > D)
        return;
    f[u][0] = 0;
    f[u][1] = num[u];
    for (int i = 0; i < e[u].size(); i++)
    {
        int v = e[u][i];
        if (v == fa)
            continue;
        dfs(v, u, d + 1, D);
        f[u][0] += max(f[v][0], f[v][1]);
        if (huai[u] || huai[v]) // u,v 有一个坏果子就不能选 v
            f[u][1] += f[v][0];
        else
            f[u][1] += max(f[v][0], f[v][1]);
    }
}
bool check(int D)
{
    for (int i = 1; i <= n; i++)
        f[i][0] = f[i][1] = 0;
    dfs(1, 0, 1, D);
    return max(f[1][0], f[1][1]) >= k;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n - 1; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        cin >> num[i];
    for (int i = 1; i <= m; i++)
    {
        int pos;
        cin >> pos;
        huai[pos] = true;
    }
    int l = 1;
    int r = n;
    int ans = -1;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
    }
    cout << ans;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
int n;
string s[105];
string ans;
void connect(string &a, string &b){
    int len = 0;
    for(int i = min(a.size(),b.size());i >= 0;i--)
    {
        // 检查 a 的最后 i 个字符和 b 的开头 i 个字符是否一样
        // a[a.size()-i ~ a.size()-1] ~ b[0 ~ i-1]
        bool flag = true;
        for(int j=0;j<=i-1;j++)
            if(a[(int)a.size()-i+j]!=b[0+j])
            {
                flag=false;
                break;
            }
        if(flag)
        {
            len = i;
            break;
        }
    }
    // b 跳过前 len 个字符
    for(int i=len;i<=(int)b.size()-1;i++)
        a+=b[i];
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    ans=s[1];
    for(int i=2;i<=n;i++)
        connect(ans,s[i]);
    cout<<ans;
    return 0;
}

https://htoj.com.cn/cpp/oj/problem/detail?pid=22635142801280&cid=22635299396992

#include <bits/stdc++.h>
using namespace std;
int n,m;
char x;
char g[105][105];
map<char,bool> s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x;
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++)
            g[i][j]='.';
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            if(g[i][j]!=x)
                continue;
            s[g[i+1][j]]=true;
            s[g[i-1][j]]=true;
            s[g[i][j-1]]=true;
            s[g[i][j+1]]=true;
        }
    s[x] = false;
    int ans = 0;
    for(char i='A';i<='Z';i++)
        ans+=s[i];
    cout<<ans;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
string s;
char g[205][205];
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
queue<pair<int,int>> q;
int dis[205][205];
bool vis[205][205];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    // (1,1)~(201,201)
    for (int i = 0; i <= 202; i++)
        for (int j = 0; j <= 202; j++)
            g[i][j] = '#';
    // 走路
    int sx,sy,ex,ey;
    sx=101,sy=101;
    ex=101,ey=101;
    g[ex][ey]='.';
    for(int i=0;i<s.size();i++){
        if(s[i]=='U')
            ex--;
        if(s[i]=='D')
            ex++;
        if(s[i]=='L')
            ey--;
        if(s[i]=='R')
            ey++;
        g[ex][ey]='.';
    }
    // 计算 sx,sy -> ex,ey 的最短路
    q.push({sx,sy});
    dis[sx][sy]=0;
    vis[sx][sy]=true;
    while(!q.empty()){
        pair<int,int> now=q.front();
        q.pop();
        int x = now.first;
        int y = now.second;
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(!vis[nx][ny]&&g[nx][ny]!='#')
            {
                dis[nx][ny]=dis[x][y]+1;
                vis[nx][ny]=true;
                q.push({nx,ny});
            }
        }
    }
    if(dis[ex][ey] == s.size())
        cout<<"yes";
    else
        cout<<"no";
    return 0;
}

[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;
}

[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;
}

[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;
}