清明欢乐赛(USACO选题)
总传送门
T1. [USACO19JAN] Redistricting P
luogu P5202
- 思路：
这种每次选出段长有个上限\(k\)的常常是和单调队列有关。
这里是单调队列优化dp
不过一开始想不太清有什么单调性。
发现每次的贡献为\(0/1\)
因此如果\(i
如果\(dp_i=dp_j\)你需要考虑中间段的贡献，决定是否删。
不过总之我们的目的是让优劣性单调递减（队首最优）
如果段\([i+1..j]\)中\(cnt('H')>cnt('G')\)在\(i\)能取到时一定会比\(j\)优，所以保留\(i\)
否则直接弹出\(i\) - code:
点击查看代码
#include
using namespace std;
const int N=1e6+5;
char s[N];
int dp[N],sh[N],sg[N];
int Q[N],hd=1,tl;
bool W(int l,int r) {
return (sg[r]-sg[l]>=sh[r]-sh[l]);
}
bool cmp(int x,int y) {return dp[x]==dp[y]?W(x,y):dp[x]>dp[y];}
int main() {
int n,k,l=1,r;
scanf("%d%d",&n,&k);
scanf("%s",s+1);
for(int i=1;i<=n;i++)sh[i]=sh[i-1]+(s[i]=='H'),sg[i]=sg[i-1]+(s[i]=='G');
dp[0]=0;Q[++tl]=0;
for(int i=1;i<=n;i++) {
while(hd<=tl&&Q[hd]+k T2.[USACO20JAN] Cave Paintings P
luogu P6008
- 思路：
并查集
最简单的思路就是从下往上灌水。
如果某两个节点在\(i+1\)行不连通，在第\(i\)行联通。然后这两个节点在\(i……n\)时是独立的。（如果独立就相当于乘法原理，不独立就会合成同类一起作贡献）
推广到带权并查集，合并两个联通块价值为它们乘积+1
当然我考场上想复杂了。
因为我一直往图论上套（思维僵化，犯了跟noionline一样的错误）。
不过还是搞了很久，我把它缩点（如果两个点通过往下、左、右走能联通就合成一个点一起作贡献）
可能因为我这种做法每行横向一段是手动缩点（而不是并查集），就跑的飞快。
缩点后成为森林，树上dp。（别忘了记录完起点）
具体缩点写法，（和正常写法很像）到能合并的时机时，加一个新点代表（合并后的点），连向所有每个都能到的下层的节点（下层的森林上的节点已经构造好了）。 - code:
点击查看代码
#include
using namespace std;
typedef long long ll;
const int N=1e3+5;
const int M=2e6+5;
const int mod=1e9+7;
int n,m,st[M],tp;
char s[N][N];
int tt[N],ct,Ll,Rl,fa[M],nxt[M],to[M],head[M],ecnt,nd,pos[N][N];
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
int gt_fa(int u) {return fa[u]==u?u:fa[u]=gt_fa(fa[u]);}
void Union(int u,int v) {fa[gt_fa(u)]=gt_fa(v);}
int rt[M];
void Build() {
bool bg=0;
for(int i=n;i;i--) {
// printf("!%d\n",i);
if(!bg) {
for(int j=1;j<=m;j++) {
if(s[i][j]=='.') {
++nd;fa[nd]=nd;pos[i][j]=nd;
while(s[i][j+1]=='.') {
j++;pos[i][j]=nd;
}
}
}
if(nd){Ll=1;Rl=nd;bg=1;}
continue;
}
for(int j=1;j<=m;j++) {
if(s[i][j]=='.') {
++nd;fa[nd]=nd;pos[i][j]=nd; //tmp node
if(pos[i+1][j])Union(nd,pos[i+1][j]);
while(s[i][j+1]=='.') {
j++;pos[i][j]=nd;if(pos[i+1][j])Union(nd,pos[i+1][j]);
}
}
}
// new node
int nwR=nd;
ct=0;
for(int j=1;j<=m;j++) {
if(s[i][j]=='#') continue;
int x=gt_fa(pos[i][j]);
if(!rt[x]) {rt[x]=++nd;tt[++ct]=x;fa[nd]=nd;}
pos[i][j]=rt[x];
}
for(int j=Ll;j<=Rl;j++) {
int x=gt_fa(j);
if(!rt[x]) st[++tp]=x; //beginning node
else add_edge(rt[x],j);
// printf("%d(%d) %d\n",rt[x],x,j);
}
Ll=nwR+1;Rl=nd;
while(ct) {rt[tt[ct]]=0;ct--;}
// printf("[%d,%d]\n",Ll,Rl);
}
}
ll dp[M];
void DP(int u) {
dp[u]=1;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];
DP(v);
dp[u]=dp[u]*dp[v]%mod;
}
dp[u]++;
}
int main() {
// int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
Build();
ll ans=1;
while(tp) {
int i=st[tp--];
DP(i);ans=ans*dp[i]%mod;
}
printf("%lld",ans);
return 0;
}
T3.[USACO20JAN] Non-Decreasing Subsequences P
P6009
-
题意：给每一个长为\(n\)的数列，每个数的上限是\(k\),\(Q\)次问\([l_i,r_i]\)内的最长不降子序列的方案数
-
思路：
动态dp
线段树维护\(z[x][y]\)表示上升子序列的权值为从\(x\)到\(y\)的方案数。
\(O(q\log_2{n}\ k^2)\)
难写又慢，而且发现玄机（\(q\)是\(n\)的\(20\)倍）
想要把询问\(q\)复杂度,转到\(n\)上。接下来用到：
中轴分治（自己乱创的，类似cdq）
即分治时每次处理跨过\(mid=(l+r)/2\)的区间。
然后这个区间的结果为\(mid\)左边的部分和右边的部分合并起来。
因此要预处理从\(mid\)往左的答案，从\(mid\)往右的答案。
如果处理和查询的每一步是\(O(1)\)的话，这个算法的复杂度是\(O(nlog_2n+q)\)
这样就能把\(q\)的复杂度转化到\(n\)上呢。
合并显然需要：
\(G[i][y]\):（右半边）开始的值为\(y\),前缀\(i\)的总方案数
\(F[i][y]\):（左半边）结束的值为\(y\),后缀\(i\)的总方案数
这里只说右半边（\(G\)）的做法，\(F\)同理
方便\(G\)的转移，我们定义\(g[x][y]\)为上面的\(z[x][y]\)的意思
然后每次新添加\(a_i\)时:只有\(g[y][a_i]\ \ (1<=y<=a_i)\)会受影响。
要找前面的一个\(z<=a_i\)
\(g[y][a_i]+=\sum\limits_{z=1}^{a_i}g[y][z]\)
还要考虑\(a_i\)独立为一个子序列
\(g[a_i][a_i]++\)
这样\(O(k^2)\)处理了\(g\)
\(G[i][y]=\sum\limits_{z=y}^kg[y][z]\) 知道开头\(y\)枚举结尾
\(O(k^2)\)而且这个跑的挺满的，实际需要\(O(k)\)就可以啦。
\(G[i-1][y]\)相比\(G[i][y]\)只有在\(y<=a_i\)时,\(g[y][a_i]\)的改变会影响\(G[i][y]\),此时加上\(g[y][a_i]\)的变化量即可。
总复杂度\(nlognk^2+qk\)而且肯定是跑不满的。
我翻了翻题解，题解搞了数据结构来优化到\(nklognlogk\)实际上因为数据结构卡死了上限还跑的比我慢很多。 -
code
戳我
#include
using namespace std;
typedef long long ll;
const int N=2e5+5;
const int M=N>>2;
const int K=21;
const int mod=1e9+7;
int a[N],b[N],q,n,k,rev[N],A[N],t1[N],t2[N];
//g[x][y]:(val)[x...y]; G[i][y]:(val)[y...],pre(pos) i
ll g[K][K],f[K][K],G[M][K],F[M][K],sG[M][K],ans[N];
struct query {int l,r;}Q[N];
void gt_gG(int l,int r) {
g[a[l]][a[l]]=G[l][a[l]]=1;
for(int i=l+1;i<=r;i++) {
int ai=a[i];
for(int y=1;y<=ai;y++) {
G[i][y]=G[i-1][y]-g[y][ai];
ll tmp=g[y][ai]+(y==ai);
for(int z=y;z<=ai;z++) tmp+=g[y][z];
g[y][ai]=(tmp%=mod);
G[i][y]=(G[i][y]+tmp)%mod;
}
for(int y=ai+1;y<=k;y++) {G[i][y]=G[i-1][y];}
}
}
void gt_fF(int l,int r) {
f[b[l]][b[l]]=F[l][b[l]]=1;
for(int i=l+1;i<=r;i++) {
int bi=b[i];
for(int y=bi;y<=k;y++) {
F[i][y]=F[i-1][y]-f[bi][y];
ll tmp=f[bi][y]+(y==bi);
for(int z=bi;z<=y;z++) tmp+=f[z][y];
f[bi][y]=(tmp%=mod);
F[i][y]=(F[i][y]+tmp)%mod;
}
for(int y=1;y>1;
gt_gG(mid+1,r);gt_fF(rev[mid],rev[l]);
int c1=L,c2=R;
for(int i=L;i<=R;i++) {
int x=A[i];
if(Q[x].l==Q[x].r) ans[x]=2;
else if(Q[x].l>mid) t2[c2--]=x;
else if(Q[x].r<=mid) t1[c1++]=x;
else {
int st=rev[Q[x].l],ed=Q[x].r;
ans[x]=1+SG(ed,k);
for(int yl=1;yl<=k;yl++) {
ans[x]=(ans[x]+F[st][yl]*(SG(ed,k)-SG(ed,yl-1)+1))%mod;
}
}
}
Clear(rev[mid],rev[l],mid+1,r);
if(c1!=L) {
for(int i=L;ic2;i--) A[i]=t2[i];
solve(mid+1,r,c2+1,R);
}
}
int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) {rev[i]=n-i+1;b[rev[i]]=a[i];}
// for(int i=1;i<=n;i++)printf("%d ",b[i]);puts("");
scanf("%d",&q);
for(int i=1;i<=q;i++) {scanf("%d%d",&Q[i].l,&Q[i].r);A[i]=i;}
solve(1,n,1,q);
for(int i=1;i<=q;i++) printf("%lld\n",(ans[i]+mod)%mod);
return 0;
}