来自官方题解.md
星际联邦
做法比较多，可以直接用 Prim 来做，但最简单的做法仍然是考虑 Borůvka 算法，我们在每一轮需要找到这个点向外到另一个联通块内的最小边。注意到当 \(i\) 固定时，最小边要么是前缀 \([1, i)\) 的最大值取到的，要么是 \((i, n]\) 内的最小值取到的。我们只需要对每个前缀维护最大值，以及和最大值不在同一个联通块内的最大值，就可以快速求出该联通块向外的最小边。总的时间复杂度为 \(O(n \log n)\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=3e5+1;
const int INF=1e9;
int n, a[300005];
LL ans;
struct Node{
int val,id;
} s[300005];
bool cmp(Node a,Node b)
{
return a.val < b.val;
}
signed main() {
// freopen("a.in", "r", stdin);
freopen("star.in", "r", stdin);
freopen("star.out", "w", stdout);
cin>>n;
for (int i=1;i<=n;i++)cin>>a[i],s[i].id=i,s[i].val=a[i];
sort(s+1,s+1+n,cmp);
int j=0;
int maxn=-INF;
for(int i=1;i<=n;i++)
{
if(s[i].id<=j)
continue;
int dmax=-INF;
while(j<s[i].id)
{
j++;
if(j==s[i].id)
{
dmax=max(dmax,a[j]);break;
}
int del=min(s[i].val-a[j],a[j]-dmax);
if (del<a[j]-maxn)dmax=max(dmax,a[j]);
else maxn=max(maxn,a[j]),del=a[j]-maxn;
ans+=del;
}
if(i>=2)
ans+=s[i].val-maxn;
maxn=max(maxn,dmax);
}
printf("%lld\n",ans);
return 0;
}
和平精英
首先考虑枚举按位与和按位或的值，假设结果是 \(val\)，那么显然所有 \(a_i<val\) 都应该放到 or 集合里，所有 \(a_i>val\) 都应该放到 and 集合里，如果暴力 check 可以做到 \(O(nQV)\)。
考虑再发掘一些性质，考虑枚举 \(val\) 的 popcount，设为 \(p\)，那么显然所有 \(popcount(a_i)<p\) 都应该放到 or 集合里，所有 \(popcount(a_i)>p\) 都应该放到 and 集合里，\(popcount(a_i)=p\) 的把上面的结论拉下来发现这些数应当全部相等，如果暴力 check 可以做到 \(O(nQ \log v)\)，大概有 25pts。
然后考虑直接离线分治回答询问，可以轻松做到 \(O(n\log^2 n)\)，如果你不幸写了一个根号复杂度，也可以获得多于暴力的分数。
摆烂合唱
为了方便描述，下面的部分都在表达式树上进行。
分析一下：如果一个变量 \(i\)（叶结点）的取值影响到了整个表达式（根结点 1）的值，那么必然是 \(i\) 到 1 这条路径上每一个点的值都被影响，所以我们设 \(f(u, j)\) 表示当 \(u\) 的左/右（对应 \(j=0\) 或 \(j=1\)）子结点的值分别取 0,1 时 \(u\) 的值不同的概率，那么答案就应该是 \(i\) 到 1 这条链上 \(f(u, j)\) 的乘积。
令 \(g(i)\) 表示随机情况下 \(i\) 点的值为 1 的概率，以 and 型结点，\(j=0\) 为例，如果 \(r s_i\) 的值为 0，那么 \(l s_i\) 就不能影响 \(i\) 的取值（\(i\) 的值总是 0），否则就能影响，所以 \(f(i, 0)=g\left(r s_i\right)\)。
做 DP 过程中算出 \(g(i)\) 外顺带算出 \(f(i, 0)\)，最后 DFS 一次求出一个点到根节点链上的 \(f(u, j)\) 的积，即可快速得到答案。
时间复杂度为 \(O(n)\)。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5,mod=998244353,inv2=((mod+1)>>1);
struct Node{int typ,ch[2];}tr[N];
int get(char x)
{
if(x=='x')return 0;
if(x=='&')return 1;
if(x=='|')return 2;
if(x=='^')return 3;
assert(false);
}
int n,cnt=0,rt,f[N],g[N][2];char s[N<<1];
stack<int>st;stack<pair<int,int>>op;
void build() {
int len=strlen(s+1);
for(int i=1;i<=len;i++)
{
if(s[i]=='x')
st.push(++cnt);
if(s[i]=='|'||s[i]=='&'||s[i]=='^')
op.push({++cnt,get(s[i])});
if(s[i]==')')
{
int u=st.top();st.pop();
int v=st.top();st.pop();
pair<int,int>t=op.top();op.pop();
tr[t.first].ch[0]=v;tr[t.first].ch[1]=u;
tr[t.first].typ=t.second;st.push(t.first);
}
}
rt=st.top();return;
}
void dfs(int u)
{
if(!u)return;
if(tr[u].typ==0)
{
g[u][0]=g[u][1]=inv2;
return;
}
int v0=tr[u].ch[0],v1=tr[u].ch[1];
if(v0)dfs(v0);if(v1)dfs(v1);
if(tr[u].typ==1)
g[u][0]=(1-1ll*g[v0][1]*g[v1][1]%mod+mod)%mod;
if(tr[u].typ==2)
g[u][0]=1ll*g[v0][0]*g[v1][0]%mod;
if(tr[u].typ==3)
g[u][0]=(1ll*g[v0][0]*g[v1][0]%mod+1ll*g[v0][1]*g[v1][1]%mod)%mod;
g[u][1]=(1-g[u][0]+mod)%mod;return;
}
void getans(int u)
{
if(!u||tr[u].typ==0)return;
int v0=tr[u].ch[0],v1=tr[u].ch[1];
if(tr[u].typ==1)
{
f[v0]=1ll*f[u]*g[v1][1]%mod;
f[v1]=1ll*f[u]*g[v0][1]%mod;
}
if(tr[u].typ==2)
{
f[v0]=1ll*f[u]*g[v1][0]%mod;
f[v1]=1ll*f[u]*g[v0][0]%mod;
}
if(tr[u].typ==3)
{
f[v0]=f[v1]=f[u];
}
getans(v0);getans(v1);return;
}
int main()
{
freopen("binary.in","r",stdin);
freopen("binary.out","w",stdout);
scanf("%d %s",&n,s+1);build();
dfs(rt);f[rt]=1;getans(rt);
for(int i=1;i<=cnt;i++)
{
if(tr[i].typ==0)
printf("%d\n",f[i]);
}
return 0;
}
对称旅行者
考虑先求旅行者 \(i\) 的期望位置，设为 \(f_i\)，那么答案就为 \(f_i * 2^{m K}\)。
当旅行者 \(i\) 旅行时时，由于期望的线性性，\(f_i \longleftarrow \frac{1}{2}\left(2 f_{i-1}-f_i+2 f_{i+1}-f_i\right)=f_{i-1}+f_{i+1}-f_i\)，考虑其几何含义，发现是把 \(f_i\) 关于 \(f_{i-1}\) 和 \(f_{i+1}\) 的中点对称，如果设 \(g_i=f_{i+1}-f_i\)，那么跳第 \(i\) 枚棋子相当于交换 \(g_{i-1}\) 和 \(g_i\)。
因此一轮旅行就对应一个 \(1 \sim n-1\) 的置换，用类似快速幂的方法就可以求出 \(K\) 轮旅行后的 \(\left\{g_i\right\}\)，再注意到 \(f_1\) 始终不变，就可以求出所有棋子的期望位置，时间复杂度为 \(O(n \log K)\)。
标签：return,noip,int,tr,v0,v1,模拟,mod From： https://www.cnblogs.com/ccjjxx/p/18537930