[C++知识库]The 2022 ICPC Asia Regionals Online Contest (I) （2022ICPC网络赛第一场）题解ACGHJL

A.01 Sequence

题意：对于一个长度为 $3$ 的倍数的，元素只有01的环，你每次可以选择一个 $1$ 删除以这个 $1$ 为中心的相邻三个元素。你可以选择将环当中的部分 $0$ 变成 $1$ ，求最少的选择数字数量使得你能够将这个环删除完毕。
给定一个长度为 $n$ 的01序列，$q$ 次询问，每次询问一个区间。每次询问一个区间，表示询问的环。$（3\le n\le 1e6,1\le q\le 1e6）$

题解：题意显然可以转换成 $len/3?环上选择至多的互不相邻的1的数量$。通过线段树维护这个值，直接区间查询即可。
注意，题目询问是个环 ，最后得到的答案应该满足，不同时选左右端点的1，且上述式子可能求出来负数，要和 $0$ 取 $max$。
复杂度： $O(n+qlogn)$

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N =1000005;
string str;
namespace SegTree{
    #define ls rt << 1
    #define rs rt << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r
    struct Info{
        int lmax, rmax, lrin, lrout;
        friend Info operator+ (Info a, Info b){
            return {
                max(a.lmax+max(b.lmax,b.lrout),a.lrin+b.lrout),
                max(max(a.rmax,a.lrout)+b.rmax,a.lrout+b.lrin),
                max({a.lmax+b.rmax,a.lrin+b.rmax,a.lmax+b.lrin}),
                max({a.rmax+b.lrout,a.lrout+b.lrout,a.lrout+b.lmax})
            };
        }
    }tr[N << 2];
    void push_up(int rt){ tr[rt] = tr[ls] + tr[rs]; }
    void build(int rt, int l, int r){
        if(l == r){
            if(str[l-1]=='1'){
                tr[rt]={0,0,1,0};
            }
            return;
        }
        int mid = l + r >> 1;
        build(lson), build(rson);
        push_up(rt);
    }
    Info query(int rt, int l, int r, int L, int R){
        if(l >= L && r <= R) return tr[rt];
        int mid = l + r >> 1;
        if(mid >= R) return query(lson, L, R);
        if(mid < L) return query(rson, L, R);
        return query(lson, L, R) + query(rson, L, R);
    }
}
using SegTree::build;
using SegTree::query;
inline void solve(){
    int n, q; cin >> n >> q >> str;
    build(1, 1, n);
    for(int i = 1; i <= q; i++){
        int l, r; cin >> l >> r;
        auto res = query(1, 1, n, l, r);
        cout << max((r-l+1)/3-max({res.lmax, res.rmax,res.lrout}),0ll)<< endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; // cin >> t;
    while(t--) solve();
    return 0;
}

C.Delete the Tree

给一个树，你可以选择两种操作

删除：删除一个点以及所有与他相邻的边
收缩：将一个有两条边的结点与他有的边删除，并连接两个本来与他相连的结点。

求最少的删除操作删除整棵树。

题解：签到题，对于每个度数大于等于 $2$ 的结点在删除过程中都可能使得度数等于 $2$ ，所以答案就是度数小于等于 $1$ 的节点数目。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1e6 + 10; 
int d[N],ans;
inline void solve(){
    int n; cin >> n; ans = 0;
    memset(d, 0, (n + 2) * sizeof(int));
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        d[u]++;d[v]++;
    }
    for(int i = 1; i <= n; i++){
        if(d[i] <= 1) ans++;
    }
    cout << ans << endl;
}
signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    int t = 1; cin >> t;
    while(t--) solve();
    return 0;
}

G.Read the Documentation

题意：给定一个数字 $n$ 表示按照顺序有 $n$个物品，每个物品有一个权值 $w_i$，有费用 $t$。
对于选择物品要求有

不能选择连续的五个物品
作为连续的第 $i$ 个物品需要花费 $x_i$ 的费用

求获得的权值最大是多少。$(1\le n\le 100,1\le q\le 1e9)$
题解：简单背包。
令 $dp[i][j][k][l][z]$ 表示,前 $i$ 个数,$j$ 个 $1$ , $k$ 个$2$ ,$l$ 个$3$ ,$z$ 个 $4$ 的方案的最大值
满足 $j?2+k?3+l?4+m?5<=i+1\&\&su{m}_1?j+su{m}_2?k+su{m}_3?l+su{m}_4?m\le t$
暴力转移即可(转移式子可见代码)。
复杂度$O(\frac{n^5}{120})$

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t,ans;
int x[10],a[105];
int dp[102][55][35][27][22];
void solve(){
    cin>>n>>t;
    for(int i=1;i<=4;i++){
        cin>>x[i];
        x[i]+=x[i-1];
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=0,sum1=0,res1=0;res1<=t&&sum1<=i+1&&j<=50;j++,sum1+=2,res1+=x[1]){
            for(int k=0,sum2=sum1,res2=res1;res2<=t&&sum2<=i+1&&k<=33;k++,sum2+=3,res2+=x[2]){
                for(int l=0,sum3=sum2,res3=res2;res3<=t&&sum3<=i+1&&l<=25;l++,sum3+=4,res3+=x[3]){
                    for(int m=0,sum4=sum3,res4=res3;res4<=t&&sum4<=i+1&&m<=20;m++,sum4+=5,res4+=x[4]){
                        dp[i][j][k][l][m]=dp[i-1][j][k][l][m];
                        if(j){
                            dp[i][j][k][l][m]=max(dp[i][j][k][l][m],dp[max(0ll,i-2)][j-1][k][l][m]+a[i]-a[i-1]);
                        }
                        if(k){
                            dp[i][j][k][l][m]=max(dp[i][j][k][l][m],dp[max(0ll,i-3)][j][k-1][l][m]+a[i]-a[i-2]);
                        }
                        if(l){
                            dp[i][j][k][l][m]=max(dp[i][j][k][l][m],dp[max(0ll,i-4)][j][k][l-1][m]+a[i]-a[i-3]);
                        }
                        if(m){
                            dp[i][j][k][l][m]=max(dp[i][j][k][l][m],dp[max(0ll,i-5)][j][k][l][m-1]+a[i]-a[i-4]);
                        }
                        ans=max(ans,dp[i][j][k][l][m]);
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}

H

题意：忘光了
题解：按照题意模拟dfs过程即可，我是被队友嘴巴操纵写的代码。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=20220911;
string s;
int dfs(){
    int res=0,w;
    string s;
    while(cin>>s){
        if(s=="for")return res;
        else if(s=="repeat"){
            int now=dfs();
            cin>>w>>s;
            (res+=now*w)%=mod;
        }
        else if(s=="library")res=(res+1)%mod;
        else if(s=="fin")return res;
    }
    return res;
}
signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout<<dfs()%mod;
}

J.Gachapon

题意：一个抽卡游戏，玩家想要抽中某张卡，一旦抽中立刻停止抽奖。
给定两个整数 $X，Y$ 表示进行 $X$ 轮抽卡，结束游戏的轮数期望是 $Y$ 。你需要构造一组包含 $X$ 个数的数组 $p$ 。其中 $p_i$ 表示在第 $i$ 轮游戏抽中卡的概率，满足 $p_X==1$ 且 $?1\le i<x,0<p_i<1$ 。对于所有的 $p_i$ 以最简分数形式输出，保证输出的最简分数 $a/b$ 满足 $a,b\le 10000$。

令 $q_i$ 表示进行 $i$ 轮游戏结束的概率,考虑将题意用公式写出则有

$$\begin{array}{rl}\sum q_i& =1\\ \sum i?q_i& =Y\end{array}$$
我们需要构造序列 $q$ 满足以上两个方程。假设所有 $q_i$ 的最简分数。令分母的最小公倍数为 $n$ , $a_i$ 表示分母为 $n$ 时候的 $q_i$ 的分子，则有，$su{m}_i$ 为 $a$ 数组前 $i$ 项和。对于任何一个合法的 $q$ 序列，对应有 $p_i=\frac{a_i}{n?su{m}_{i?1}}$,发现每一轮的 $p_i$ 的分母小于等于 $n$，为满足题意要求可令 $n=10000$,随后即有
$$\begin{array}{rl}\sum a_i& =10000\\ \sum i?a_i& =10000?Y\end{array}$$
考虑构造一个满足题意的解序列 $a$ ，首先找到满足上式，对应期望最小值，则为 $a_1=10001?x$， 其余为 $1$ ，然后在每次 $a_{i?1}?1,a_i+1$ 过程中，期望增加一，循环即可找到一个解，随后输出即可。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int x,y,ex,p[1005];
void solve(){
    cin>>x>>y;
    ex=p[1]=10001-x;
    for(int i=2;i<=x;i++){
        p[i]=1;
        ex+=i;
    }
    for(;ex<y*10000;){
        for(int i=1;ex<y*10000&&i<x;i++){
            p[i]--,p[i+1]++;
            ex++;
        }
    }
    for(int i=1,fenmu=10000;i<=x;i++){
        int d=__gcd(p[i],fenmu);
        cout<<p[i]/d<<" "<<fenmu/d<<endl;
        fenmu-=p[i];
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}

L.LCS-like Problem

题意：给定两个字符串 $s,t$ 求从 $s$ 的最长子序列满足该子序列和 $t$ 的最长公共子序列小于等于 $1$ 。

题解：DP,对 $s$ 中字母分出现在 $t$ 中和没出现在 $t$ 中考虑。对于没出现过的字母，贪心选择即可。对于出现在 $t$ 中的字母，我们可以建立一个矩阵 $c{k}_{i,j}$ 表示字母 $i$ 后面能否添加 $j$。然后直接 $26n$ 求最大值即可。

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
string s,t;
int n,m;
int ck[30][30],tot[26];
int dp[30];
void solve(){
    cin>>s>>t;
    n=s.size();m=t.size();
    s=" "+s;t=" "+t;
    for(int i=m;i;i--){
        int k=t[i]-'a';
        for(int j=0;j<26;j++){
            ck[k][j]=tot[j];
        }
        tot[k]++;
    }
    int res=0,ans=0;
    for(int i=1;i<=n;i++){
        int k=s[i]-'a';
        if(tot[k]==0){
            res++;continue;
        }
        if(!ck[k][k])dp[k]=dp[k]+1;
        for(int j=0;j<26;j++){
            if(j!=k&&ck[j][k]==0){
                dp[k]=max(dp[k],dp[j]+1);
            }
        }
    }
    for(int i=0;i<26;i++){
        ans=max(ans,dp[i]);
    }
    cout<<ans+res;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	solve();
}