Bronya19C 场。
转圈圈
一个长为 \(n\) 的 \(01\) 串 \(S\)，串中有且仅有一个 \(1\)，你可以操作若干次，每次可以将一个长为 \(k\) 的子串反转。
对每个 \(i\) 询问 \(1\) 至少几步可以翻转到位置 \(i\)，另外地，一些位置在操作的过程中不能有 \(1\).
对于 \(i\)，如果不存在这个最小步数，输出 \(-1\).
\(n\le 10^5\).
如果 \(i\) 能翻转到 \(j\)，那么有：
-
\(|i-j|<k\)
-
\(k+1\le i+j\le 2n-(k-1)\)
-
\(i-j\not\equiv k\space(\operatorname{mod}2)\)
每次能转移到的点一定为一段区间内的全体偶数或奇数。
拿两个 set 存未访问过的奇点和偶点，把取出的点用作下一次的 bfs.
写的时候 lower_bound 一下然后不断跳就行了。
这么简单的东西怎么没想出来。
时间复杂度 \(O(n\log n)\).
#include<bits/stdc++.h>
#define sit set<int>::iterator
#define N 100010
using namespace std;
int read(){
int x=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*w;
}
int n,k,m,s;
bool flag[N];
int ans[N];
set<int>s0,s1;
queue<int>q,del;
int main(){
n=read(),k=read(),m=read(),s=read();
for(int i=1;i<=m;i++)
flag[read()]=true;
if(k>n||k==1){
for(int i=1;i<=n;i++)
i==s?printf("0 "):printf("-1 ");
printf("\n");
return 0;
}
for(int i=1;i<=n;i++){
if(flag[i]||i==s)continue;
i&1?s1.insert(i):s0.insert(i);
}
memset(ans,-1,sizeof(ans)),ans[s]=0;
q.push(s);
while(!q.empty()){
int i=q.front();q.pop();
int L=max(1,k+1-i),R=min(n,2*n-(k-1)-i);
L=max(L,i-k+1),R=min(R,k+i-1);
if((i-k)&1){
sit it=s0.lower_bound(L);
for(;it!=s0.end()&&*it<=R;++it)
ans[*it]=ans[i]+1,del.push(*it),q.push(*it);
while(!del.empty())
s0.erase(del.front()),del.pop();
}
else{
sit it=s1.lower_bound(L);
for(;it!=s1.end()&&*it<=R;++it)
ans[*it]=ans[i]+1,del.push(*it),q.push(*it);
while(!del.empty())
s1.erase(del.front()),del.pop();
}
}
for(int i=1;i<=n;i++)
printf("%d ",ans[i]);
printf("\n");
return 0;
}
括号匹配
串 \(S\) 有左右括号和通配符 ?，问 \(S\) 的多少子串可以成为合法括号串。
\(|S|\le 10^6\).
Sub1：只有通配符，\(n\le 10^6\)
枚举为偶数的长度 \(len\) 即可。
Sub2：没有通配符，\(n\le 10^6\)
记 ( 为 \(1\)，) 为 \(-1\)，作前缀和。
枚举区间开始位置 \(i\)，对于结束位置 \(j\) 应有
\[\forall k\in[i,j],s_k\ge s_{i-1},s_j=s_{i-1} \]对于 \(s\) 跑一遍单调栈，这个相等的条件可以设一个偏移量 \(\Delta\)，然后放在 vector 里二分。
Sub3,4：\(n\le 2000\)
一个合法的括号串可以以如下方式拓展：
-
在两端添加一个合法的括号串
-
在左端添加
(，右端添加)
这样就容易写出一个 \(O(n^3)\) 的 dp，由于剪枝效率会比较高。
Sub5：\(n\le 10^6\)
一个区间合法当且仅当：
-
区间长度为偶数
-
令
(和?为 \(1\)，)为 \(-1\)，前缀和数组的每一项 \(\ge0\). -
令
)和?为 \(1\)，(为 \(-1\)，后缀和数组的每一项 \(\ge0\).
这样可以通过调整，使得前缀和数组非负且最后一项为 \(0\).
对于 \(l\)，可以预处理出 \(P_l\)，表示应有 \(l\le r\le P_l\).
对于 \(r\)，可以预处理出 \(Q_r\)，表示应有 \(Q_r\le l\le r\).
两者使用单调栈处理。
枚举 \(l\)，问有多少 \(r\in[l,P_l]\) 满足 \(Q_r\le l\).
容易将其转化为二维数点问题。开奇偶两个树状数组即可。
时间复杂度 \(O(n\log n)\).
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
using namespace std;
char c[N];int n;
int s[N],P[N],Q[N];
int st[N],top;
int tot;
struct query{
int l,x,flag,m2;
bool operator<(const query &t)const{
return l<t.l;
}
}q[N<<1];
#define lb(x) x&-x
int t1[N],t2[N];
void add(int *t,int x,int k){
for(;x<=n;x+=lb(x))t[x]+=k;
}
int qry(int *t,int x){
int ret=0;
for(;x;x-=lb(x))ret+=t[x];
return ret;
}
int main(){
scanf("%s",c+1),n=strlen(c+1);
for(int i=1;i<=n;i++)
s[i]=s[i-1]+(c[i]==')'?-1:1);
st[top=1]=0;
for(int i=1;i<=n;i++){
while(top&&s[st[top]]>s[i])
P[st[top--]+1]=i-1;
st[++top]=i;
}
while(top)P[st[top--]+1]=n;
for(int i=n;i;i--)
s[i]=s[i+1]+(c[i]=='('?-1:1);
st[top=1]=n+1;
for(int i=n;i;i--){
while(top&&s[st[top]]>s[i])
Q[st[top--]-1]=i+1;
st[++top]=i;
}
while(top)Q[st[top--]-1]=1;
for(int i=1;i<=n;i++){
if(i>P[i])continue;
q[++tot]=(query){P[i],i,1,i&1};
if(i>1)q[++tot]=(query){i-1,i,-1,i&1};
}
sort(q+1,q+1+tot);
ll ans=0;
for(int i=1,j=1;i<=n&&j<=tot;i++){
if(i>=Q[i])add(i&1?t1:t2,Q[i],1);
while(j<=tot&&q[j].l==i)
ans+=q[j].flag*qry(q[j].m2?t2:t1,q[j].x),j++;
}
printf("%lld\n",ans);
return 0;
}
崩原之战
你玩元神吗。
P8908 [USACO22DEC] Palindromes P
一个串的价值是不断交换串中的某两个相邻的字符，使其成为回文串的最小次数。如果其不能被重排为回文串，其价值为 \(-1\).
求 \(S\) 的所有子串的价值和。
\(|S|\in\{100,200,500,1000,2000,5000,7500\}\)，\(\Sigma=\{H,G\}\).
字符集也对上了。
先把字符串变成 \(01\) 串。
首先如果子串长度为偶数而 \(01\) 都有奇数个，答案显然为 \(-1\).
思考怎么操作能使得答案最小。
假设只考虑 \(1\)，不断将它们首尾配对，若剩下一个则放在正中间。
一定存在一种最优的方案使得两个 \(1\) 中至少一个不移动。
记共 \(m\) 个 \(1\)，第 \(i\) 个 \(1\) 的位置是 \(a_i\)，操作数为
\[[m\equiv1\space(\operatorname{mod}2)]|\frac{l+r}{2}-a_{\frac{m+1}{2}}|+\sum_{i=1}^{\lfloor\frac{m}{2}\rfloor}|a_i+a_{m-i+1}-l-r| \]前面一部分是对中心点的计算。时间复杂度 \(O(n^3)\).
考虑枚举 \(a_i,a_{m-i+1}\) 并计算它们配对产生的贡献。如果 \(a_i\) 和 \(a_j\) 配对，那么有
\[l\le a_i,r\ge a_j,j-i+1\equiv r-l+1\space(\operatorname{mod}2) \]\(i,j\) 的信息可以从 \(i-1,j+1\) 得来。从 \(a\) 的每段前缀和后缀出发，每次砍掉首尾两个元素，把新的 \([l,r]\) 扔进 DS 里，那么新产生的 \([l,r]\) 就是 \(l\in(a_{i-1},a_i]\)，\(r\in[a_j,a_{j+1})\) 对应的所有区间。
枚举 \(l+r\)，算一下这个东西的出现次数，一起扔进 DS 里。
最后想想这个 DS 要干什么。
维护一个可重集，查询 \(\le x\) 的元素之和和元素个数。\(x\) 的上界显然为 \(2n\)，开两个 BIT 即可。
时间复杂度 \(O(n^2\log n)\).
这个牛逼计数感性理解一下吧。
#include<bits/stdc++.h>
#define ll long long
#define N 7510
#define lb(x) x&-x
using namespace std;
char ch[N];int n,cnth,cntg;bool a[N];
int bit1[N<<1],cnt;ll bit2[N<<1],sum;
void add(int c,int k){
sum+=1ll*c*k,cnt+=c;
for(int x=k;x<=n*2;x+=lb(x))
bit1[x]+=c,bit2[x]+=1ll*c*k;
}
int qry1(int x){
int ret=0;
for(;x;x-=lb(x))ret+=bit1[x];
return ret;
}
ll qry2(int x){
ll ret=0;
for(;x;x-=lb(x))ret+=bit2[x];
return ret;
}
void work(int l,int r,int L,int R,bool fl){
r-=l,R-=L;
for(int i=0,_l,_r;i<=r+R;i++){
if(fl&&((i+l+L)&1))continue;
_l=max(0,i-R),_r=min(i,r);
add(_r-_l+1,i+l+L);
}
}
int c0[N],c1[N],pos[N],m;
ll ans;
void solve(int l,int r){
bool fl=(r-l+1)&1;
cnt=sum=0,memset(bit1,0,sizeof(bit1)),memset(bit2,0,sizeof(bit2));
while(l<=r){
work(pos[l-1]+1,pos[l],pos[r],pos[r+1]-1,fl);
int x=pos[l]+pos[r];
ll val=sum-2*qry2(x)+1ll*x*(2*qry1(x)-cnt);
ans+=(l==r)?val/2:val;
l++,r--;
}
}
int main(){
scanf("%s",ch+1),n=strlen(ch+1);
for(int i=1;i<=n;i++)
ch[i]=='H'?cnth++:cntg++;
for(int i=1;i<=n;i++){
a[i]=(ch[i]=='H')^(cnth>cntg);
if(a[i])pos[++m]=i;
c0[i]=c0[i-1]+!a[i];
c1[i]=c1[i-1]+a[i];
}
pos[m+1]=n+1;
for(int i=1;i<=m;i++)solve(1,i);
for(int i=2;i<=m;i++)solve(i,m);
for(int l=1,x,y;l<=n;l++)
for(int r=l;r<=n;r++){
x=c0[r]-c0[l-1],y=c1[r]-c1[l-1];
if((x&1)&&(y&1))ans--;
}
printf("%lld\n",ans);
return 0;
}
抽卡
上面那个词被 Cnblogs BAN 了。
极其好的期望题，也很难。
已知 \(n\) 个长为 \(l\) 的二进制数，每一次交互有 \(p_i\) 的概率得到第 \(i\) 位的二进制值。
对于每个数，求出能唯一确定这个二进制数的期望交互次数。答案对 \(998244353\) 取模。
多组测试数据。
\(T\le 10\)，\(l\le 15\)，\(n\le 2^l\)，\(\frac{p_i}{10^{-4}}\in[1,10^4]\cap\mathbb Z\)，\(n\) 个数两两不同。
求操作次数的期望有一个经典套路，就是根据期望的线性性，求出到达每个合法状态的概率 \(P_S\)，乘上停留在该状态的期望时间 \(t_S\)，然后求和。
设 \(P_S\) 为停留在状态 \(S\) 的概率，即 \(\displaystyle P_S=\prod_{s\in S}(1-p_s)\)，有 \(\displaystyle t_S=\frac{1}{1-P_S}\).
从 \(P_S\) 转移至 \(P_T\) 的系数是 \(\displaystyle\prod_{i\in T,i\not\in S}p_i\times\prod_{i\not\in T}(1-p_i)\times\frac{1}{1-P_S}\).
预处理 \(\prod p_i\) 和 \(\prod(1-p_i)\)，枚举 \(S\) 的超集 \(T\) 可做到 \(O(3^l)\).
对于串 \(s\) 记 \(T\) 为能唯一确定 \(s\) 的集合，那么答案为 \(\sum_{S\not\in T}P_St_S\).
容斥得 \(ans=\sum_{S}P_St_S-\sum_{S\in T}P_St_S\)
状态 \(S\) 每位的状态是 \(\{0,1,?\}\)，所以 \(S\) 的个数为 \(O(3^l)\)，易得 \(\sum|T|\le 3^l\).
求哪些状态可以唯一确定字符串。
记 \(f_S\) 为能确定的唯一字符串的编号，不存在则为 \(0\)，不唯一则为 \(-1\).
初始化 \(2^l\) 个已经确定 \(01\) 了的 \(f_S\)，记录为 \(id\) 或 \(0\).
主动转移的复杂度是 \(O(3^ll)\).
被动转移，考虑 \(S\) 有若干位 \(?\)，选择其中一个并填入 \(0/1\)，能够做到转移复杂度 \(O(1)\).
总复杂度 \(O(T3^l)\).
标签：10,le,int,top,st,2023.8,复杂度 From： https://www.cnblogs.com/SError0819/p/17612805.html