题目总结
Angelstar
·
·
个人记录
首先：不妨令 v_1\ge v_2,k\in\mathbb N。两只青蛙在 L 的相遇情况只有：
-
相向而行：\frac{(2k+1)L}{v_1+v_2}\in[0,T]
-
追及而行：\frac{(2k'+1)L}{v_1-v_2}\in[0,T]
于是我们解两个方程，求出 k 的个数即可。
我们有
0\le(2k+1)L\le T(v_1+v_2)\Rightarrow
0\le2k+1\le\left\lfloor T(v_1+v_2)\div L\right\rfloor\Rightarrow
0\le k\le\left\lfloor(\left\lfloor T(v_1+v_2)\div L\right\rfloor-1)\div2\right\rfloor
同理有
0\le(2k'+1)L\le T(v_1-v_2)\Rightarrow
0\le2k'+1\le\left\lfloor T(v_1-v_2)\div L\right\rfloor\Rightarrow
0\le k'\le\left\lfloor(\left\lfloor T(v_1-v_2)\div L\right\rfloor-1)\div2\right\rfloor
那么问题来了，如果同时满足两个方程的 k，怎么算出它的个数呢？也就是在池塘端点相遇的情形。
引理：当且仅当 \frac {v_1} {\gcd(v_1,v_2)},\frac{v_2}{\gcd(v_1,v_2)} 奇偶性不同时，存在重叠的 k。这样的 k 有 \left\lceil\frac{T*\gcd(v_1,v_2)\div L}{2}\right\rceil 那么多个。
证明：谢谢 @CT_1024 大佬！！
设某一个 k 点的时间为 t，则有：
$∴t=k_1L/v_1=k_2L/v_2 (k_1,k_2∈N)
∴k_1/v_1=k_2/v_2
∴v_1/v_2=k_1/k_2
∴k_1=nv_1/\gcd(v_1,v_2),k2=nv_2/\gcd(v1,v2)
（k_1/k_2~约分后为~v_1/v_2）
（由上式可推导出 v_1/\gcd(v_1,v_2),v_2/\gcd(v_1,v_2) 奇偶性不同的原因（不然两只青蛙就不在同一个岸边了））
∵t\in[0,T]
∴k_1∈[0,Tv_1/L]
∴0\le nv_1/\gcd(v_1,v_2)\le Tv_1/L
∴0\le n\le T*\gcd(v_1,v_2)/L
又 ∵n~不能为偶数（不然~k1,k2~都为偶数）
∴n~共有~\left\lceil T*\gcd(v_1,v_2)\div(2L)\right\rceil~个
今天考试的警示：提防 `__int128` 用系统自带函数导致的CE，多测要清空！！！
先考虑链上的部分分。设 $f_{i,j}$ 为考虑 $1\sim i$ 的链，$i$ 前颜色为 $j$，的方案数。则有转移 $f_{i,j}=\sum\limits_{k\ne j} f_{i-1,k}=sum_{i-1}-f_{i-1,j}$（$1\le j\le a_i$）。考虑环的情形：断环成链。选 $a_i$ 最小的作为开头，然后容斥。总方案数减去开头结尾相同的方案数+开头和倒数两个都一样的方案数 $\cdots$。
不妨递推式的理解这个问题：设 $r_n$ 表示考虑上述构成的长 $n$ 环的方案数，则有
$$r_n=ch_n-r_{n-1}$$
$$r_{n-1}=ch_{n-1}-r_{n-2}$$
$$\ldots$$
$$r_1=a_1$$
于是问题得到解决但是时间会超时。我们考虑 $f$ 是怎么转移的：可以发现相当于每次将区间乘-1，然后加上区间和，再把外面的归零。那么就可以用线段树优化该过程了QwQ（我还没有实现出来awa）
```
【题目背景】
mty一个人走在大街上，突然感到一股恶臭的味道笼罩着他。 他一开始以为是某个人不讲武德用排遗物搞偷袭，结果往脚边一看，一个式子静静地躺在地上，散发着独属于它的芳香。 mty把式子捡了起来，他想要消除恶臭造福人类，你能帮帮他吗？
【题目描述】
这个序列包含三种东西，数字、运算符和括号。
运算符有三种：W、F、Y。
对于两个数x、y ，先把它们拆成二进制位，对于每个位满足以下运算规则：
W：0W0=0、0W1=0、1W0=0、1W1=1
F：0F0=0、0F1=1、1F0=1、1F1=1
Y：0Y0=0、0Y1=1、1Y0=1、1Y1=0
值得注意的是，这些运算符都是从左到右进行运算的，并且没有优先顺序。现在mty想要找到一个区间[l,r],使得这段区间所代表的式子的值最大。例如5W2Y3F4,截取2Y3,那么这个区间的值就是1。
请你输出这个最大的值。
注意：这个区间必须是合法的，即左右括号能够一一配对;保证给出的序列合法；字符串最长为n的4倍。
输入格式
先输入一个数n ，代表数的数量。
接着输入n个数，分别代表每一个数是多少。
最后输入一行一个字符串，包含字符()WFYx，其中除了字符x外意义都如题面描述，x从左到右分别与先前输入的n个数一一对应。
输出格式
一行一个数表示最大的值.
```
本题需要对 $\texttt{Trie}$ 树灵活应用，才能做出来。一道考察马力的大模拟题。
标算（by wh）：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=4e5+7,M=N*30,D=31;
int n,m;
int a[N],att;
char s[N*4];
void input() {
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cin>>(s+1);
}
int stk[N*4],tt=-1;
int rt[N*4];
int ans=0;
struct Node{
int opt;//0& 1| 2^
int x;
};
int root;
struct Trie{
int stk[M],tt=-1,tot;
int val[M],ls[M],rs[M];
int tag[M],h0[M],h1[M];
void del(int u) {
h0[u]=h1[u]=ls[u]=rs[u]=tag[u]=val[u]=0;
stk[++tt]=u;
}
void erase(int &u) {
if(u==0) return;
erase(ls[u]),erase(rs[u]);
del(u),u=0;
}
int node() {
if(tt>=0) return stk[tt--];
return ++tot;
}
void set_xor(int u,int v,int d) {
if(u==0 || d<0) return;
if((v>>d)&1) swap(ls[u],rs[u]);
int p=(h0[u]^h1[u])&v;
h0[u]^=p,h1[u]^=p;
tag[u]^=v;
}
void pushdown(int u,int d) {
if(tag[u]) {
set_xor(ls[u],tag[u],d-1);
set_xor(rs[u],tag[u],d-1);
tag[u]=0;
}
}
void pushup(int u,int d) {
val[u]=val[ls[u]]+val[rs[u]];
h0[u]=h0[ls[u]]|h0[rs[u]];
if(ls[u]) h0[u]|=(1<<d);
h1[u]=h1[ls[u]]|h1[rs[u]];
if(rs[u]) h1[u]|=(1<<d);
}
void insert(int &u,int x,int d) {
if(u==0) u=node();
if(d<0) {
val[u]=1;
return;
}
pushdown(u,d);
if((x>>d)&1)
insert(rs[u],x,d-1);
else
insert(ls[u],x,d-1);
pushup(u,d);
}
int merge(int x,int y,int d) {
if(x==0 || y==0) return x+y;
if(d<0) {
val[x]|=val[y];
del(y);
return x;
}
pushdown(x,d),pushdown(y,d);
ls[x]=merge(ls[x],ls[y],d-1);
rs[x]=merge(rs[x],rs[y],d-1);
pushup(x,d);
del(y);
return x;
}
void remove_and(int u,int k,int d) {
if(u==0 || ((h1[u]>>k)&1)==0) return;
if(((h0[u]>>k)&1)==0) {
set_xor(u,1<<k,d);
return;
}
pushdown(u,d);
if(d==k) {
ls[u]=merge(rs[u],ls[u],d-1);
rs[u]=0;
pushup(u,d);
return;
}
remove_and(ls[u],k,d-1);
remove_and(rs[u],k,d-1);
pushup(u,d);
}
void set_and(int x) {
for(int i=0;i<D;i++)
if(((x>>i)&1)==0) {
remove_and(root,i,D-1);
}
}
void remove_or(int u,int k,int d) {
if(u==0 || ((h0[u]>>k)&1)==0) return;
if(((h1[u]>>k)&1)==0) {
set_xor(u,1<<k,d);
return;
}
pushdown(u,d);
if(d==k) {
rs[u]=merge(rs[u],ls[u],d-1);
ls[u]=0;
pushup(u,d);
return;
}
remove_or(ls[u],k,d-1);
remove_or(rs[u],k,d-1);
pushup(u,d);
}
void set_or(int x) {
for(int i=0;i<D;i++)
if((x>>i)&1) {
remove_or(root,i,D-1);
}
}
int query(int u,int d) {
if(d<0) return 0;
pushdown(u,d);
if(rs[u] && val[rs[u]]) return query(rs[u],d-1)|(1<<d);
return query(ls[u],d-1);
}
}trie;
int calc(vector<Node> f) {
int len=f.size();
trie.erase(root);
for(int i=0;i<len;i++)
ans=max(ans,f[i].x);
trie.insert(root,f[0].x,D-1);
for(int i=1;i<len;i++) {
int opt=f[i].opt,x=f[i].x;
if(opt==0) trie.set_and(x);
if(opt==1) trie.set_or(x);
if(opt==2) trie.set_xor(root,x,D-1);
trie.insert(root,x,D-1);
ans=max(ans,trie.query(root,D-1));
}
int v=f[0].x;
for(int i=1;i<len;i++) {
int opt=f[i].opt;
int x=f[i].x;
if(opt==0) v&=x;
if(opt==1) v|=x;
if(opt==2) v^=x;
}
return v;
}
int solve(int l,int r) {
if(l==r) return a[++att];
if(s[l]=='(' && rt[l]==r) return solve(l+1,r-1);
vector<Node> f;
int pre=l;
f.push_back((Node){1,solve(pre,rt[pre])});
pre=rt[pre]+1;
while(pre<=r) {
int op;
if(s[pre]=='W') op=0;
if(s[pre]=='F') op=1;
if(s[pre]=='Y') op=2;
pre++;
f.push_back((Node){op,solve(pre,rt[pre])});
pre=rt[pre]+1;
}
int t=calc(f);
return t;
}
void work() {
m=strlen(s+1);
for(int i=1;i<=m;i++) {
if(s[i]=='(') stk[++tt]=i;
else if(s[i]==')') rt[stk[tt--]]=i;
else if(s[i]=='x') rt[i]=i;
}
solve(1,m);
cout<<ans;
}
int main() {
input();
work();
return 0;
}
```