发布时间：2024-04-23

E - Toward 0(期望dp)

题意：

给定一个 $N (1 \leq N \leq 10^{18})$ ， $X，Y，A(2 \leq A \leq 6)$

操作1：消耗 $X$ , $N= \lfloor \frac{N}{A} \rfloor$
操作2：消耗 $Y$ , $N= \lfloor \frac{N}{i} \rfloor， 1 \leq i \leq 6 ,i等概率出现$
问使N=0的期望次数

思路：

期望dp会有两种形式，一种可以通过移向推出转移方程，另一种则需要高斯消元，本题属于第一种

考虑记忆化搜索
首先对于第一种情况:
- $dp_N=min(dp_i,dp_{\frac{N}{A}}+X)$
第二种情况：
- $dp_N=\frac{1}{6} \sum_{i=1}^6 dp_{\frac{N}{i}}+Y$
- 移向可得 $dp_N=\frac{1}{5}\sum_{i=2}^6 dp_{\frac{N}{i}}+\frac{6}{5}Y$
二者取min值即可

cpp

map<int,double> f;
LL n,A,X,Y;
double dfs(LL x){
    if(x==0)return 0;
    if(f[x])return f[x];
    double ans=dfs(x/A)+X;
    double sum=0;
    for(int i=2;i<=6;i++)sum+=dfs(x/i);
    sum/=5;
    sum+=Y*6.0/5;
    f[x]=min(ans,sum);
    return f[x];
}
void solve(){
    cin>>n>>A>>X>>Y;
    cout<<setprecision(6)<<fixed;
    cout<<dfs(n)<<"\n";
}

F - Transpose(大模拟)

题意：

给定一个字符串(含有大小写字母和括号，括号合法)
每次选择括号的区间
先反转区间内的字符串，然后大写变小写，小写变大写
将括号删除
输出最后的字符串

思路：

发现如下规律：

对于一个字符串s,假设操作后的字符串为p
$((s))=s$
$(((s)))=(s)=p$
因此，若字符串被偶数倍的括号包围，则该字符串最终保持不变
否则(奇数),最终将是操作后的字符串
首先先预处理出配对的括号
用递归可以线性处理
- 首先从左到右扫
  - 若没遇到(,因为前面都没有括号存在，因此没遇到之前直接插入s[i]
  - 若遇到(，代表匹配括号内部应该反向，因此递归当前匹配子串，反向搜索
- 从右到左扫
  - 若没遇到)，则插入处理后的s[i]
  - 遇到)，代表此时匹配的括号不应该处理，继续递归，反向
- 实际上从右往左扫代表这些字符只有奇数个括号，需要反向并变换
- 从左往右扫的字符代表被偶数个括号包围，保持整体不变

cpp

string ans="",s;
int match[N];
char change(char c){
    if(c>='A'&&c<='Z')return c-'A'+'a';
    return c-'a'+'A';
}
void dfs(int l,int r,bool st){
    if(!st){
        for(int i=l;i<r;i++){
            if(s[i]=='('){
                dfs(i+1,match[i],1);
                i=match[i];
            }
            else ans+=s[i];
        }
    }
    else{
        for(int i=r-1;i>=l;i--){
            if(s[i]==')'){
                dfs(match[i]+1,i,0);
                i=match[i];
            }
            else ans+=change(s[i]);
        }
    }
} 
void solve(){
    cin>>s;
    int n=s.size();
    stack<int> st;
    for(int i=0;i<n;i++){
        if(s[i]=='(')st.push(i);
        else if(s[i]==')'){
            match[st.top()]=i;
            match[i]=st.top();
            st.pop();
        }
    }
    dfs(0,n,0);
    cout<<ans<<"\n";
}

G - Mediator(启发式合并)

题意

给定n个点，q次询问

1 x y:两点连一条边，保证之前未出现过
2 x y:查询两个点之间是否存在一个点同时与这两个点直接相连(即两点距离为2),输出这个点，不存在则输出0
保证一直是棵树

思路

启发式合并 $O(nlogn)$

小集合合并到大集合，小集合更新新的父节点，用并查集维护集合大小
具体只需要用fa数组判断，祖孙关系以及兄弟关系即可

cpp

void solve(){
    int n,m;
    cin>>n>>m;
    int last=0;
    vector<int> adj[n+1],par(n+1),siz(n+1),Fa(n+1);
    function<int(int)> find=[&](int x){
        if(par[x]==x)return x;
        siz[par[x]]+=siz[x];
        siz[x]=0;
        return par[x]=find(par[x]);
    };
    for(int i=1;i<=n;i++)par[i]=i,siz[i]=1;
    function<void(int,int)> dfs=[&](int u,int fa){
        Fa[u]=fa;
        for(auto v:adj[u]){
            if(v==fa)continue;
            dfs(v,u);
        }
    };
    function<void(int,int)> add=[&](int a,int b){
        int fa=find(a),fb=find(b);
        if(siz[fa]<siz[par[fb]])swap(a,b),swap(fa,fb);
        adj[a].push_back(b);
        adj[b].push_back(a);
        par[fb]=fa;
        siz[fa]+=siz[fb];
        siz[fb]=0;
        dfs(b,a);
    };
    while(m--){
        LL a,b,c;
        cin>>a>>b>>c;
        a=1+(((a*(last+1))%mod)%2);
        b=1+(((b*(last+1))%mod)%n);
        c=1+(((c*(last+1))%mod)%n);
        if(a==1)add(b,c);
        else{
			if(Fa[Fa[b]]==c||Fa[b]==Fa[c]&&Fa[b])last=Fa[b];
			else if(Fa[Fa[c]]==b)last=Fa[c];
			else last=0;
            cout<<last<<"\n";
        }
    }
}

E - Toward 0(期望dp) ​

题意： ​

思路： ​

F - Transpose(大模拟) ​

题意： ​

思路： ​

G - Mediator(启发式合并) ​

题意 ​

思路 ​

E - Toward 0(期望dp)

题意：

思路：

F - Transpose(大模拟)

题意：

思路：

G - Mediator(启发式合并)

题意

思路