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