这次的题都是什么怪物！！！
Short Colorful Strip
因为 \(n=m\)，所以最终的形态一定是 \(n\) 的一个排列。
根据题意，发掘几个性质：
- 一个区间染色，一定最先对其中颜色最小的染色。
- 染色要求覆盖的点颜色完全相同。
对于第一次来说，先找到颜色为 \(1\) 的点，位置是 \(p\)。
染色的区间是 \([l,r]\)，\(l\le p\le r\)。
所以我们可以把答案分成四个区间 \([1,l]\)，\([l+1,p-1]\)，\([p+1,r]\)，\([r+1,n]\)
\(ans=\sum_{l=1}^{p-1}f_{1,l}\times f_{l+1,p-1}\times \sum_{r=p}^{n}f_{p+1,r}\times f_{r+1,n}\)
对于查询的每一个区间都可以用这种方法求得，所以做法就很显然了。
int n,m;
int a[N];
int f[505][505];
inline int dfs(int l,int r){
if(~f[l][r])return f[l][r];
if(l>=r)return f[l][r]=1;
int p=l;
up(i,l,r)if(a[i]<a[p])p=i;
int ans1=0,ans2=0;
up(i,l,p)ans1=(ans1+dfs(l,i-1)*dfs(i,p-1)%mod)%mod;
up(i,p,r)ans2=(ans2+dfs(p+1,i)*dfs(i+1,r)%mod)%mod;
return f[l][r]=ans1*ans2%mod;
}
signed main(){
memset(f,-1,sizeof f);
n=read();m=read();
up(i,1,m)a[i]=read();
cout<<dfs(1,m);
return 0;
}
Long Colorful Strip
似乎可以用同样的做法，对于每一种颜色，找出它 最左端的位置和最右端的位置，枚举 \(l,r\) 然后把当前区间分成五段，进行区间 dp。
然后一看， \(m\le 10^6\) ，当场去世。
那么有没有什么优化呢，我们考虑一下对于一段颜色相同的区间，我们可以选择把其压缩成一个点，但是这样似乎优化的很玄学，想一想有没有什么性质可以利用。
考虑一下，我们每一次染色，似乎最多增加两个 \(c_i!=c_{i+1}\)。
所以如果压缩后的 \(m\le 2n\)，可以直接判断不合法。
复杂度 \(m^3\)，但是能过。
int n,m;
int a[N],t;
int f[1505][1505];
int L[1540],R[1050];
inline int dfs(int l,int r){
if(~f[l][r])return f[l][r];
if(l>r)return 1;
int &val=f[l][r];
val=0;
int minl=a[l];
up(j,l,r)minl=min(minl,a[j]);
int p=-1;
int ans1=1;
up(j,l,r){
if(a[j]==minl) {
if(p!=-1)ans1=ans1*dfs(p+1,j-1)%mod;
p=j;
}
}
int lans=0;
up(j,l,L[minl]){
lans=(lans+dfs(l,j-1)*dfs(j,L[minl]-1)%mod)%mod;
}
int rans=0;
up(j,R[minl],r){
rans=(rans+dfs(R[minl]+1,j)*dfs(j+1,r)%mod)%mod;
}
return val=ans1*lans%mod*rans%mod;
}
signed main(){
memset(f,-1,sizeof f);
n=read();m=read();
int x,pre=0;
up(i,1,m){
x=read();
if(x!=pre)a[++t]=x;
pre=x;
}
if(t>2*n){
puts("0");
return 0;
}
up(i,1,n){
int l=t+1,r=0;
up(j,1,t){
if(a[j]==i){
l=min(l,j);
r=max(r,j);
}
}
up(j,l,r){
if(a[j]<i){
puts("0");
return 0;
}
}
L[i]=l;R[i]=r;
}
cout<<dfs(1,t);
return 0;
}
Palindrome
很经典的一道题和性质。
最长回文子序列等于原串和反串的最长公共子序列。
但是求 LCS 是 \(n^2\) 的。
思考一下，因为全是小写字母，所以如果字符串的长度大于 \(2600\) 那么一定有一个所有字符都相同的符合条件的串。
不然的话就直接输出 LCS。
int n;
string s,t;
int f[2600][2600];
char ans[5050],ans2[5050];
signed main(){
cin>>s;
n=s.size();
t=s;
reverse(t.begin(),t.end());
s=" "+s;t=" "+t;
if(n<=2600){
up(i,1,n){
up(j,1,n){
if(s[i]==t[j]){
f[i][j]=f[i-1][j-1]+1;
}
else{
f[i][j]=max(f[i-1][j],f[i][j-1]);
}
}
}
int i=n,j=n;
while(f[i][j]>0){
if(s[i]==t[j]){
ans[f[i][j]]=s[i];
i--, j--;
}
else{
if(f[i][j]==f[i-1][j]) i--;
else j--;
}
}
if(f[n][n]<100){
printf("%s",ans+1);
return 0;
}
else{
int t=0;
up(i,1,50)ans2[++t]=ans[i];
dn(i,49,0)ans2[++t]=ans[f[n][n]-i];
printf("%s",ans2+1);
}
}
else{
up(j,'a','z'){
int t=0;
up(i,1,n){
if(s[i]==j)t++;
}
if(t>=100){
up(i,1,100)putchar(j);
return 0;
}
}
}
return 0;
}
Constrained Tree
首先，我们已经知道了这个东西的先序遍历的顺序。
想一想如何判断一个点是在左子树还是右子树。
可以对每一个点求左子树的最小值，最大值，右子树的最小值，最大值。
然后递归求解。
int n,m;
int Lmax[N],Rmax[N],Lmin[N],Rmin[N];
int cnt=0;
bool flag=0;
vector<int>res;
inline void dfs(int l,int r){
if(flag) return;
++cnt;
if(Lmax[l]){
if(Lmin[l]<=cnt)flag=1;
dfs(cnt+1,Lmax[l]);
}
res.push_back(l);
if(Rmax[l]){
if(Rmin[l]<=cnt)flag=1;
dfs(cnt+1,max(Rmax[l],r));
}
else if(cnt<r)dfs(cnt+1,r);
}
signed main(){
n=read();m=read();
up(i,1,n){
Lmin[i]=n+1;
Rmin[i]=n+1;
}
int x,y;
char s[10];
up(i,1,m){
x=read();y=read();
if(x>=y){
puts("IMPOSSIBLE");
return 0;
}
scanf("%s",s+1);
if(s[1]=='L'){
Lmax[x]=max(Lmax[x],y);
Lmin[x]=min(Lmin[x],y);
}
else{
Rmax[x]=max(Rmax[x],y);
Rmin[x]=min(Rmin[x],y);
}
}
dfs(1,n);
if(!flag){
for(auto x:res){
cout<<x<<" ";
}
}
else puts("IMPOSSIBLE");
return 0;
}
来一张阿卡多：
再来一张沃尔特：
