T1 转圈圈
题目大意：给你一个只含有一个\(1\)的\(01\)串\(S\) 每次你可以翻转一段区间为\(k\)的子串 且给出\(m\)个禁止位置 必须保证\(1\)在任何时刻都不能出现在静止位置上
对于每个位置\(i\) 给出旋转到\(i\)位置时的最小次数 无法旋转到这个位置时输出\(-1\)
思考：原题要求我们每次枚举一段区间翻转 我们可以判断\(k\)的奇偶然后暴力 BFS 来搞 这样子可以保证最小次数 时间复杂度\(O(nk)\) 期望得分 56pts
继续探究：
为什么会\(TLE\)？我们重复访问了一个区间的点太多次了！怎么优化呢？开个 set 就行了 时间复杂度降至\(O(nlogn)\) 期望得分 100pts
注意：set并不能动态删点 所以要开一个栈或者队列存下要删的点统一删
56pts Code:
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,k,m,s;
int a[N],w[N],vis[N];
int q[N],l,r;
void bfs()
{
q[++r]=s;
vis[s]=1;
w[s]=0;
while(l<r)
{
int x=q[++l];
if(k&1)
{
for(int i=max(1,x-k+1);i<=x;i++)
{
int mid=(i+i+k-1)/2;
int pos=mid-(x-mid);
if(a[pos]) continue;
if(i+k-1>n) break;
if(vis[pos]) continue;
q[++r]=pos;
vis[pos]=1;
w[pos]=w[x]+1;
}
}
else
{
for(int i=max(1,x-k);i<=x;i++)
{
int mid=(i+i+k-1)/2;
int pos=mid-(x-mid)+1;
if(i+k-1>n) break;
if(a[pos]) continue;
if(vis[pos]) continue;
q[++r]=pos;
vis[pos]=1;
w[pos]=w[x]+1;
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&k,&m,&s);
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
a[x]=1;
}
bfs();
for(int i=1;i<=n;i++)
{
if(vis[i])printf("%d ",w[i]);
else printf("-1 ");
}
return 0;
}
AC code
#include<bits/stdc++.h>
#define N 200005
using namespace std;
int n,k,m,st;
int a[N],w[N],vis[N];
int q[N],l,r;
int del[N],len;
set<int> s[2];
void bfs()
{
fill(w+1,w+1+n,-1);
q[++r]=st;
w[st]=0;
while(l<r)
{
int x=q[++l];
if(k&1)
{
int mid=(max(1,x-k+1)*2+k-1)/2;
int pos=mid*2-x-2;
int times=min(x,n+1-k)-max(1,x-k+1)+1;
int lpos=pos+2,rpos=pos+times*2;
set<int>::iterator ls=s[x&1].lower_bound(lpos),rs=s[x&1].upper_bound(rpos);
len=0;
for(set<int>::iterator it=ls;it!=rs;it++)
{
pos=*it;
del[++len]=pos;
q[++r]=pos;
w[pos]=w[x]+1;
}
for(int i=1;i<=len;i++)
s[x&1].erase(del[i]);
}
else
{
int mid=(max(1,x-k)*2+k-1)/2;
int pos=mid*2-x+1-2;
int times=min(x,n+1-k)-max(1,x-k)+1;
int lpos=pos+2,rpos=pos+times*2;
set<int>::iterator ls=s[pos&1].lower_bound(lpos),rs=s[pos&1].upper_bound(rpos);
len=0;
for(set<int>::iterator it=ls;it!=rs;it++)
{
pos=*it;
del[++len]=pos;
q[++r]=pos;
w[pos]=w[x]+1;
}
for(int i=1;i<=len;i++)
s[pos&1].erase(del[i]);
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&k,&m,&st);
for(int i=1;i<=m;i++)
{
int x;
scanf("%d",&x);
a[x]=1;
}
for(int i=1;i<=n;i++)
if(i!=st&&!a[i]) s[i&1].insert(i);
bfs();
for(int i=1;i<=n;i++)
printf("%d ",w[i]);
return 0;
}
T2 扌舌 口丂 匚儿 酉己
疑云顶针 鉴定为纯纯迷惑
思考：
部分分1
先想全为?的10pts部分分 发现只要区间长度为偶数即合法
那么容易发现公式为：
\(\left\lfloor \frac{n}{2} \right\rfloor \cdot \left\lceil \frac{n}{2} \right\rceil\)
期望得分10pts
部分分2
考虑\(O(n^3)\)的做法
怎么才能匹配一段括号呢？
- 1.区间长度为偶数
- 2.如果将所有
?替换成(将(看为1)看为-1 那么在\(l\to r\)这段区间中 所有前缀和\(\ge0\) - 2.如果将所有
?替换成)将(看为-1)看为1 那么在\(l\to r\)这段区间中 所有后缀和\(\ge0\)
如果同时满足三个区间 明显为匹配区间
为什么？
\(2,3\)可以保证左右不会出现左右括号无法匹配的情况
那么其实可以保证构造出一种方案 使得这段串合法
我们可以预处理整个前后缀数组 然后其实
\(a_i-a_j>0 \to a_i>a_j\)
根据以上推导 我们可以推导出\(O(n^3)\)的做法：
通过\(O(n^2)\)枚举区间 然后暴力\(O(n)\)判断
期望得分20pts
Code
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
string s;
ll ans,s1[N],s2[N];
int main()
{
cin>>s;
for(int i=1;i<=s.size();i++)
s1[i]=s1[i-1]+(s[i-1]==')' ? -1:1);
for(int i=s.size();i>=1;i--)
s2[i]=s2[i+1]+(s[i-1]=='('?-1:1);
for(int i=1;i<=s.size();i++)
{
for(int j=1;j<i;j++)//枚举 j~i
{
int p=1;
if((j-i+1)&1) continue;
for(int k=j;k<=i;k++)
if(s1[k]<s1[j-1]||s2[k]<2[i+1]) p=0;
ans+=p;
}
}
cout<<ans;
return 0;
}
部分分3
考虑优化\(O(n^3)\)做法
\(O(n^3)\)很暴力 先退而求其次 想想\(O(n^2)\)的做法
容易发现代码
for(int k=j;k<=i;k++)
if(s1[k]<s1[j-1]||s2[k]<2[i+1]) p=0;
其实就是在求
从\(j\)开始往后第一个比\(s1_{j-1}\)小的位置的下标 和
从\(i\)开始往前第一个比\(s2_{i+1}\)小的位置的小标中两个下标的闭区间中 是否包含\((i,j)\) 包含就统计答案
可以使用单调栈优化 时间复杂度\(O(n^2)\) 期望得分40pts
Code
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
string s;
ll ans,s1[N],s2[N];
ll a[N],b[N],q[N],l;
int main()
{
cin>>s;
for(int i=1;i<=s.size();i++)
s1[i]=s1[i-1]+(s[i-1]==')' ? -1:1);
for(int i=s.size();i>=1;i--)
s2[i]=s2[i+1]+(s[i-1]=='(' ? -1:1);
for(int i=0;i<=s.size();i++)
{
a[i]=s.size()+1;
while(l&&s1[i]<s1[q[l]])
a[q[l--]]=i;
q[++l]=i;
}
l=0;
for(int i=s.size()+1;i>=1;i--)
{
b[i]=0;
while(l&&s2[i]<s2[q[l]])
b[q[l--]]=i;
q[++l]=i;
}
for(int i=1;i<=s.size();i++)
{
for(int j=1;j<i;j++)//枚举 j~i
{
int p=1;
if((j-i+1)&1) continue;
int r1=a[j-1],l2=b[i+1];
if(i<r1&&j>l2) ans++;
}
}
cout<<ans;
return 0;
}
正解
\(O(n^2)\)对于题目的数据还是太勉强了
我们要优化整个程序 必须先魔改一下原程序
将第二重枚举改成这样：
for(int i=1;i<=s.size();i++)
{
for(int j=b[i+1];j<=i-2;j++)//枚举 j~i
{
if((j-i)&1) continue;
if(a[j]>i) ans++;
}
}
容易发现$(j-i)\operatorname{and} 1=0 \to j \operatorname{and}1=i \operatorname{and} 1 $
这样子 可以分类讨论去掉一句话
然后看下一句
if(a[j]>i) ans++;
这不就是求一段区间内有多少个数比当前的数大吗？考虑主席树
可能会想到主席树 可以维护\(n\)棵的权值线段树 查询就在主席树上作差
但是仔细想想会发现 实际上\(i\)是单调递增的
那么我们可以考虑把\((i,a_i)\)打包丢进优先队列里面 然后每次看看堆顶的\(a_x\)的值是不是小于等于当前是数 是的话就把它弹出优先队列 然后让对应点的数减少 弹出堆即可
单点修改，区间查询 鉴定为树状数组
时间复杂度\(O(nlogn)\) 期望得分100pts
Code
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
string s;
ll ans;
int s1[N],s2[N];
int a[N],b[N],q[N],l;
ll tr[2][N];
struct node{
int x,v;
};
bool operator < (node a,node b)
{
return a.v>b.v;
}
priority_queue<node> p[2];
void add(int p,int x,int v)
{
x+=3;
while(x<=s.size()+3)
{
tr[p][x]+=v;
x+=x&-x;
}
}
ll ask(int p,int x)
{
x+=3;
ll sum=0;
while(x)
{
sum+=tr[p][x];
x-=x&-x;
}
return sum;
}
int main()
{
cin>>s;
for(int i=1;i<=s.size();i++)
s1[i]=s1[i-1]+(s[i-1]==')' ? -1:1);
for(int i=s.size();i>=1;i--)
s2[i]=s2[i+1]+(s[i-1]=='(' ? -1:1);
for(int i=0;i<=s.size();i++)
{
a[i]=s.size()+1;
while(l&&s1[i]<s1[q[l]])
a[q[l--]]=i;
q[++l]=i;
}
l=0;
for(int i=s.size()+1;i>=1;i--)
{
b[i]=0;
while(l&&s2[i]<s2[q[l]])
b[q[l--]]=i;
q[++l]=i;
}
for(int i=0;i<=s.size();i++)
{
while(!p[i&1].empty()&&p[i&1].top().v<=i)
{
add(i&1,p[i&1].top().x,-1);
p[i&1].pop();
}
ans+=ask(i&1,i-2)-ask(i&1,b[i+1]-1);
if(a[i]>i) add(i&1,i,1),p[i&1].push((node){i,a[i]});
}
cout<<ans;
return 0;
}
T3 米哈游内战 USACO
我现在要点名一款????二字游戏
简要题意：给你一个字符串 只能交换相邻两个字符 求出让每个子串变成回文串的最小步数的和 变不了贡献就为\(-1\) 最后输出即可
思考：
怎样才是最小步数呢？
把原串抽象成\(01\)串
因为你只能交换相邻的字符 如果相邻字符相同后交换等于没有交换 一定不优
举个例子：\(110001001\)
交换第\(1,2\)个\(1\)是绝对不对的
因此 如果\(1\)的位置在\(p_1,p_2,p_3,…p_k\)
那么一定是 \(p_i\to p_{k-i+1}\) 两两对称
现在分析怎么才能两两对称
定义中点为\(mid\)
如果当前两点中点在\(mid\)左边 那么把右边的点右移 否则就把左边的点左移
最终点对一定是\([x,len-x+1]\)
需要移动的步数为\(|mid-p_i+mid-p_{k-i+1}|\)
等价于\(|l+r-p_i-p_{k-i+1}|\)
所以答案就是
\[\sum\limits_{(l-r+1)and 1=1}|\frac{(l+r)}{2}-p_{\frac{k+1}{2}}|+\sum\limits_{i=1}^{k/2}|l+r-p_i-p_{k-i+1}| \]前面的东西直接预处理了 后面的把\(p_i+p_{k-i+1}\)打包看成一个东西
这样\(l+r\)动态枚举 后面的东西打包好了 然后开两棵树状数组存一下个数和和就行了
枚举答案的方法就是枚举中间点 然后向两边扩展即可
时间复杂度\(O(n^2\log n)\)
code
#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define N 7505
#define ll long long
using namespace std;
int n;
ll ans;
int cnt,c[N];
string s;
struct tree{
int tr[N*2];
void clear(int n)
{
for(int i=1;i<=n*2;i++)
tr[i]=0;
return ;
}
void add(int x,int v)
{
while(x<=n*2)
{
tr[x]+=v;
x+=x&-x;
}
return;
}
int ask(int x)
{
int sum=0;
while(x)
{
sum+=tr[x];
x-=x&-x;
}
return sum;
}
}tr[2];
int main()
{
cin>>s;
n=s.size();
s=" "+s;
for(int l=1;l<=n;l++)
{
for(int r=l;r<=n;r++)
{
if(s[r]=='G') c[++cnt]=r;
if(cnt&1 &&(r-l)&1) ans--;
else if(cnt&1) ans+=abs((l+r)/2-c[cnt/2+1]);
}
cnt=0;
}
for(int i=1;i<=n;i++)
if(s[i]=='G') c[++cnt]=i;
c[cnt+1]=n+1;
for(int i=1;i<=cnt;i++)//以c[i]为中点
{
tr[0].clear(n),tr[1].clear(n);
int sum=0;
for(int j=1;i-j>=1&&i+j<=cnt;j++)
{
int p=c[i-j]+c[i+j];
tr[0].add(p,1);
tr[1].add(p,p);
sum+=p;
for(int l=c[i-j-1]+1;l<=c[i-j];l++)
for(int r=c[i+j];r<=c[i+j+1]-1;r++)
{
if((r-l)&1) continue;
int s1=tr[0].ask(l+r),s2=tr[1].ask(l+r);
ans+=1ll*s1*(l+r)-s2;
ans+=(sum-s2)-1ll*(j-s1)*(l+r);
}
}
}
for(int i=1;i<=cnt;i++)
{
tr[0].clear(n);
tr[1].clear(n);
int sum=0;
for(int j=0;i-j>=1&&i+j+1<=n;j++)
{
int p=c[i-j]+c[i+j+1];
tr[0].add(p,1);
tr[1].add(p,p);
sum+=p;
for(int l=c[i-j-1]+1;l<=c[i-j];l++)
for(int r=c[i+j+1];r<=c[i+j+1+1]-1;r++)
{
int s1=tr[0].ask(l+r),s2=tr[1].ask(l+r);
ans+=1ll*(l+r)*s1-s2;
ans+=1ll*(sum-s2)-1ll*(l+r)*(j+1-s1);
}
}
}
cout<<ans;
return 0;
}
T4 抽卡 原题
摆(