D. Two Hundred Twenty One
题目描述
给定长度为 (n) 的序列 (a)，其中 (a_i={-1,1})，定义一个序列的权值为：
(q) 组询问，每组询问把区间 ([l,r]) 当成序列，问至少删除多少个数才能使序列权值为零，并给出方案。
(n,qleq 3cdot 10^5)
解法
比赛时候猜了个结论：答案不超过 (2)；然后用 ( t STL) 暴力操过了 ( t easy version)
其实这个结论还可以强化，我们考虑如果这个序列直接合法就输出 (0)；如果序列长度是奇数的话必须操作奇数次，并且操作次数至少是 (1)；如果序列长度是偶数的话必须操作偶数次，并且操作次数至少是 (2)
那么我们可以转证结论：任何长度为 (1) 的序列都可以通过一步删除合法
设 (b_i) 为序列删除第 (i) 个元素后所得到的序列权值，设 (f(l,r)) 为区间 ([l,r]) 的权值，先看两个性质。
性质一：(|b_{i}-b_{i+1}|=0/2)
如果 (a_i=a_{i+1}) 那么 (b_i=b_{i+1})；否则 (b_i=f(1,i-1)pm a_{i+1}mp f(i+2,n))，(b_{i+1}=f(1,i)mp f(i+2,n))，那么 (|b_i-b_{i+1}|=2)
性质二：(b_1cdot b_nleq 0)
因为 (b_1=-f(1,n)pm 1,b_n=f(1,n)pm 1)，显然它们要么异号要么有人等于零。
把 (b) 看成一个连续函数，因为两端点异号（非严格），所以一定有 (b_k=0) 在某一个 (k) 处取得。
那么算法流程是，对于奇数序列找到这个零点 (k)，对于偶数序列把 (l) 删掉之后转成奇数序列即可。
总结
对于求函数等于某值怎么取到的题，可以先证函数的连续性，再证端点的分布即可。
( t Freopen) 有言：猜了结论要继续深化，可能深化到了某一步之后才利于证明的进行。
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
using namespace std;
const int M = 300005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,m,q,f[M];char a[M];
map<int,int> mp;set<int> s[M];
int sig(int x) {return x%2?-1:1;}
void work()
{
n=read();q=read();m=0;
mp.clear();
for(int i=1;i<=n;i++) s[i].clear();
scanf("%s",a+1);f[n+1]=0;
for(int i=n;i>=1;i--)
{
if(a[i]=='+') f[i]=1;
else f[i]=-1;
f[i]=f[i]-f[i+1];
int x=sig(i)*(f[i]-f[i+1]);
if(!mp[x]) mp[x]=++m;
s[mp[x]].insert(i);
}
while(q--)
{
int l=read(),r=read();
if(f[l]==f[r+1]*sig(r-l+1))
{
puts("0");
continue;
}
int L=(r-l)%2==0?l:l+1;
int x=f[L]*sig(L)-f[r+1]*sig(r),y=mp[x];
set<int>::iterator it=s[y].lower_bound(l);
if(L==l+1)
printf("2
%d %d
",l,*it);
else
printf("1
%d
",*it);
}
}
signed main()
{
T=read();
while(T--) work();
}
E. Rescue Niwen!
题目描述
给定一个长度为 (n) 的字符串，把所有子串按照 [1,1],[1,2]...[1,n],[2,2]...[2,n]...[n,n] 的方式排成序列，定义小于号为字典序的小于，求出这个序列的最长上升子序列。
(nleq 5000)
Morning desert sun horizon 骄阳破晓
Rise above the sands of time... 照耀时之沙漠
解法
本题只能用 (O(n^2)) 做法，比赛时猜个结论直接过了~
暴力思路就是直接考虑每个子串结尾的最长上升子序列，首先有一个 ( t naive) 的 ( t observation)：答案只可能在 ([1,n],[2,n],[3,n]...) 这些地方取得，因为 (s[i,j]<s[i,j+1])，不在这里取得就还可以增加。
那么尝试只计算以这些点结尾的 (dp) 值，对后缀 (i) 转移的时候我们枚举后缀 (j)，找到它们的最长公共前缀 (x)，如果 (s[j+x]<s[i+x]) 那么把后缀 (i) 的一段后缀接到最长上升子序列后面即可。
上面做法的正确性基于结论：后缀 (i) 的有效转移是所有 (j<i) 的后缀 (j)
设 (x) 为后缀 (i) 中第一个满足 (s[j,k]<s[i,x]) 的位置 (x)，分这三种情况讨论：
- 如果同时满足 (s[j,k+1]<s[i,x])，那么显然从 (s[j,k+1]) 转移更优。
- 否则满足 (s[j,k+1]<s[i,x+1])，那么从两个点转移都一样优。
- 如果到 (k+1) 这里就已经找不到 (s[j,k+1]<s[i,y])，那么从两个点转移都不优。
那么显然靠后的点转移就优，所以只需要考虑后缀的转移。
写一个后缀数组求 ( t lcp)，时间复杂度 (O(n^2))
总结
考虑有效状态又多了一种思路：只求出跟答案相关的 (dp) 值即可，只用于转移的 (dp) 值可以考虑其性质。
推转移点的性质时，这样的思路也是成立的：某种情况某某优；某种情况一样优；某某情况都不优。这个很像凸包，足以说明某个转移点一定不优。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int M = 5005;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int T,n,lg[M],dp[M],ans;char s[M];
//init for suffix array
int x[M],y[M],c[M],sa[M],rk[M],hi[M][20];
void init()
{
int m=200;
memset(x,0,sizeof x);
memset(y,0,sizeof y);
memset(c,0,sizeof c);
memset(sa,0,sizeof sa);
memset(rk,0,sizeof rk);
for(int i=1;i<=n;i++) ++c[x[i]=s[i]];
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int num=0;
for(int i=n-k+1;i<=n;i++) y[++num]=i;
for(int i=1;i<=n;i++)
if(sa[i]>k) y[++num]=sa[i]-k;
for(int i=1;i<=m;i++) c[i]=0;
for(int i=1;i<=n;i++) ++c[x[i]];
for(int i=1;i<=m;i++) c[i]+=c[i-1];
for(int i=n;i>=1;i--) sa[c[x[y[i]]]--]=y[i];//mistake
swap(x,y);
x[sa[1]]=num=1;
for(int i=2;i<=n;i++)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]
&& y[sa[i]+k]==y[sa[i-1]+k])?num:++num;
if(m==n) break;
m=num;
}
int k=0;
for(int i=1;i<=n;i++) rk[sa[i]]=i;
for(int i=1;i<=n;i++)
{
if(rk[i]==1) continue;
if(k) k--;
int j=sa[rk[i]-1];
while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;
hi[rk[i]][0]=k;
}
for(int i=2;i<=n;i++)
lg[i]=lg[i>>1]+1;
for(int j=1;(1<<j)<=n;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
hi[i][j]=min(hi[i][j-1],hi[i+(1<<j-1)][j-1]);
}
int lcp(int l,int r)
{
l=rk[l];r=rk[r];
if(l>r) swap(l,r);l++;
int k=lg[r-l+1];
return min(hi[l][k],hi[r-(1<<k)+1][k]);
}
//my code
void work()
{
n=read();scanf("%s",s+1);
init();ans=0;
for(int i=1;i<=n;i++)
{
dp[i]=n-i+1;
for(int j=1;j<i;j++)
{
int x=lcp(i,j);
if(s[j+x]<s[i+x])
dp[i]=max(dp[i],dp[j]+n-i+1-x);
}
ans=max(ans,dp[i]);
}
printf("%d
",ans);
}
signed main()
{
T=read();
while(T--) work();
}