Codeforces Round #741 (Div. 2)
D. Two Hundred Twenty One
题目描述
给定长度为 \(n\) 的序列 \(a\),其中 \(a_i=\{-1,1\}\),定义一个序列的权值为:
\[\sum_{i=1}^n(-1)^{i-1}a_i \]\(q\) 组询问,每组询问把区间 \([l,r]\) 当成序列,问至少删除多少个数才能使序列权值为零,并给出方案。
\(n,q\leq 3\cdot 10^5\)
解法
比赛时候猜了个结论:答案不超过 \(2\);然后用 \(\tt STL\) 暴力操过了 \(\tt 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_1\cdot b_n\leq 0\)
因为 \(b_1=-f(1,n)\pm 1,b_n=f(1,n)\pm 1\),显然它们要么异号要么有人等于零。
把 \(b\) 看成一个连续函数,因为两端点异号(非严格),所以一定有 \(b_k=0\) 在某一个 \(k\) 处取得。
那么算法流程是,对于奇数序列找到这个零点 \(k\),对于偶数序列把 \(l\) 删掉之后转成奇数序列即可。
总结
对于求函数等于某值怎么取到的题,可以先证函数的连续性,再证端点的分布即可。
\(\tt Freopen\) 有言:猜了结论要继续深化,可能深化到了某一步之后才利于证明的进行。
#include
#include
#include
#include
E. Rescue Niwen!
题目描述
点此看题
给定一个长度为 \(n\) 的字符串,把所有子串按照 [1,1],[1,2]...[1,n],[2,2]...[2,n]...[n,n]
的方式排成序列,定义小于号为字典序的小于,求出这个序列的最长上升子序列。
\(n\leq 5000\)
Morning desert sun horizon 骄阳破晓
Rise above the sands of time... 照耀时之沙漠
解法
本题只能用 \(O(n^2)\) 做法,比赛时猜个结论直接过了~
暴力思路就是直接考虑每个子串结尾的最长上升子序列,首先有一个 \(\tt naive\) 的 \(\tt observation\):答案只可能在 \([1,n],[2,n],[3,n]...\) 这些地方取得,因为 \(s[i,j],不在这里取得就还可以增加。
那么尝试只计算以这些点结尾的 \(dp\) 值,对后缀 \(i\) 转移的时候我们枚举后缀 \(j\),找到它们的最长公共前缀 \(x\),如果 \(s[j+x] 那么把后缀 \(i\) 的一段后缀接到最长上升子序列后面即可。
上面做法的正确性基于结论:后缀 \(i\) 的有效转移是所有 \(j 的后缀 \(j\)
设 \(x\) 为后缀 \(i\) 中第一个满足 \(s[j,k] 的位置 \(x\),分这三种情况讨论:
- 如果同时满足 \(s[j,k+1]
,那么显然从 \(s[j,k+1]\) 转移更优。 - 否则满足 \(s[j,k+1]
,那么从两个点转移都一样优。 - 如果到 \(k+1\) 这里就已经找不到 \(s[j,k+1]
,那么从两个点转移都不优。
那么显然靠后的点转移就优,所以只需要考虑后缀的转移。
写一个后缀数组求 \(\tt lcp\),时间复杂度 \(O(n^2)\)
总结
考虑有效状态又多了一种思路:只求出跟答案相关的 \(dp\) 值即可,只用于转移的 \(dp\) 值可以考虑其性质。
推转移点的性质时,这样的思路也是成立的:某种情况某某优;某种情况一样优;某某情况都不优。这个很像凸包,足以说明某个转移点一定不优。
#include
#include
#include
#include
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<r) swap(l,r);l++;
int k=lg[r-l+1];
return min(hi[l][k],hi[r-(1<