rp++
juruo的noip真实成绩：0+0+0+0=0 pts.
题目大意洛谷有，这里就不放了。
T1.种花
可以维护每一个点向下最多延伸多长$xia_i$，向右延伸最多多长$you_i$,这样C就好求了，可以维护$you_i$一个自下而上的后缀和。
至于F就维护一个$xia_i * you_i $的自下而上的后缀和，跟C类似。
查看代码
using namespace std;
#include<bits/stdc++.h>
namespace zhu{
# define int long long
int T,_type,N,M,C,F;
constexpr int maxn(1010),mod(998244353);
char mp[maxn][maxn];
int you[maxn][maxn],xia[maxn][maxn];
void add(int &x,int y){
if((x+=y)>=mod) x-=mod;
}
int MAIN(){
cin>>T>>_type;
while(T--){
scanf("%lld%lld%lld%lld",&N,&M,&C,&F);
for(int i=1;i<=N;i++) scanf("%s",mp[i]+1);
int ansc=0,ansf=0;
for(int i=1;i<=N;i++){
for(int j=M;j;j--){
if(mp[i][j]=='1') you[i][j]=0;
else you[i][j]=you[i][j+1]+1;
}
}
for(int j=1;j<=M;j++){
int sumc=0,sumf=0;
for(int i=N;i;i--){
if(mp[i][j]=='1') xia[i][j]=sumc=sumf=0;
else {
xia[i][j]=xia[i+1][j]+1;
if(mp[i+1][j]=='1') continue;
if(you[i+2][j]>1)add(sumc,you[i+2][j]-1);
if(you[i+2][j]>1&&xia[i+2][j]>1)add(sumf,(you[i+2][j]-1)*(xia[i+2][j]-1)%mod);
if(you[i][j]>1)add(ansc,sumc*(you[i][j]-1)%mod),add(ansf,sumf*(you[i][j]-1)%mod);
}
}
}
printf("%lld %lld\n",ansc*C,ansf*F);
for(int i=1;i<=N;i++){
for(int j=1;j<=M;j++){
you[i][j]=xia[i][j]=0;
mp[i][j]=0;
}
}
}
return 0;
}
};
#undef int
using namespace zhu;
int main(){
return MAIN();
}T2.喵了个喵
这道题快写吐了。。。
先考虑$k=2n-2$时怎么做，考虑留出一个空栈，剩下的每个栈放两个不同元素，来了一个元素$t$，如果$t$在栈顶，那么直接消去，否则将$t$ 放在空栈中再消去。
接下来考虑$k=2n-1$时，首先按照上面的方法，一直到所有栈中存在$2n-2$个元素，并且此时又来了一个栈中没有的元素$t$,考虑有以下解决方案：
- 若$t$下一次出现之前，没有任何一个栈底元素出现过，那么可以放在空栈，直到再次出现直接消去。
- 存在一个栈，设栈底为$x$,栈顶为$y$,$x$的下一次出现比$y$下一次出现早，这就可以把$t$放在这个栈最顶上，直到栈底出现并消去。
- 否则，现在所有栈都是先出现栈顶再出现栈底，这时把$t$放在空栈，找到一个栈底元素最先出现的栈（所以此栈底出现之前全部为栈顶元素），钦定其为新的空栈，把他的栈顶$y$消去之后别的$y$元素都放在$t$的那个栈里，然后其余的栈位置全部不变，直到新空栈的栈底元素出现。
在上面的情况进行时，一定不会再出现一个新的元素，因为所有的新元素都已经在栈内了。
查看代码
using namespace std;
#include<bits/stdc++.h>
namespace zhu{
constexpr int maxn(2e6+5);
struct opt{
int op,x,y;
opt(int a,int b,int c){
op=a,x=b,y=c;
}
};
std::vector<opt>__ans;
int N,M,K;
int xl[maxn];
int sta[604][2];
pii pos[604];
int isonline,dumped;
int insta=0,kz;
std::set<int>st[604];
void getnext(){
for(int i=1;i<=K;i++) st[i].clear();
for(int i=1;i<=M;i++) st[xl[i]].insert(i);
}
# define fi first
# define se second
void add(int a,int b,int c=0){
__ans.push_back(opt(a,b,c));
}
int nex(int x,int o){
return *st[o].upper_bound(x);
}
void work(){
scanf("%d%d%d",&N,&M,&K);
for(int i=1;i<=M;i++)
scanf("%d",&xl[i]);
getnext();
int l=1,kz=N;
isonline=0,dumped=0;
int havep=-1,haves=-1,haven=-1;
while(l<=M){
int x=xl[l];
if(havep==l-1){
sta[haves][1]=haven;
pos[haven]=mkp(haves,1);
insta++;
havep=haves=haven=-1;
}
if(haven==x){
add(1,haves);
havep=haven=haves=-1;
l++;
continue;
}
if(x==isonline){
add(1,kz);
l++;
isonline=0;
continue;
}
if(dumped&&pos[x]==mkp(dumped,1)){
add(1,dumped);
pos[x]=mkp(0,0);
sta[dumped][1]=0;
insta--;
kz=dumped;
l++;
continue;
}
if(dumped&&pos[x].fi==dumped){
add(1,dumped);
pos[x]=mkp(0,0);
sta[dumped][0]=0;
dumped=0;
l++;
continue;
}
if(pos[x].fi){
if(pos[x].se){
add(1,pos[x].fi);
insta--;
sta[pos[x].fi][1]=0;
}else{
add(1,kz);
add(2,kz,pos[x].fi);
pos[sta[pos[x].fi][1]]=mkp(pos[x].fi,0);
sta[pos[x].fi][0]=sta[pos[x].fi][1];
sta[pos[x].fi][1]=0;
insta--;
}
pos[x]=mkp(0,0);
l++;
}else if(insta<2*N-2){
for(int i=1;i<=N;i++){
if(i==kz) continue;
if(i==dumped) continue;
if(!sta[i][1]){
insta++;
if(sta[i][0]){
pos[x]=mkp(i,1);
sta[i][1]=x;
}else{
pos[x]=mkp(i,0);
sta[i][0]=x;
}
add(1,i);
break;
}
}
l++;
}else{
bool fg0=0,fg1=1;
int nxt=nex(l,x);
int zx=M+1,ss;
int zx2=M+1,ss1;
for(int i=1;i<=N;i++){
if(i==kz) continue;
int p0=nex(l,sta[i][0]),p1=nex(l,sta[i][1]);
if(p0<p1){
fg0=1;
if(p0<zx)
zx=p0,ss=i;
}
if(p1<=nxt&&p0<=nxt){
if(p0<zx2)
zx2=p0,ss1=i;
}
if(p0<=nxt) fg1=0;
}
if(fg1){
isonline=x;
add(1,kz);
}else if(fg0){
add(1,ss);
havep=zx;
haves=ss;
haven=x;
}else{
add(1,kz);
sta[kz][0]=x;
pos[x]=mkp(kz,0);
dumped=ss1;
}
l++;
}
}
printf("%d\n",__ans.size());
for(auto x:__ans){
if(x.op==1) printf("%d %d\n",x.op,x.x);
else printf("%d %d %d\n",x.op,x.x,x.y),assert(x.x!=x.y);
}
__ans.clear();
assert(!insta);
}
int MAIN(){
int T;
cin>>T;
while(T--) work();
return 0;
}
};
#undef int
using namespace zhu;
int main(){
return MAIN();
}T3.建造军营
首先跑边双缩点，最后成一棵树。
容易发现一种合法的方案在树上相当于所有选的点在一个边连通块内。
设$f_i$为以$i$为最高点的方案数。
这样的连通块有两种转移:
第一种是$i$只连接一个子树，这种情况$i$内部的点不能一个都不选。
第二种是$i$连接至少两个子树，这种情况$i$内部的点可以选择任意个。
转移时我们不考虑第一个限制，但是统计答案需要考虑。
然后再考虑边的方案，最开始无限制的时候边有$2^m$种方案，然后每强制选择一条边就会失去一半的方案，所以选一条边就要把方案数除以2。
令$a_i=1+\sum_{son} \frac{1}{2} f_{son}$ , $b_i=\prod_{son} (\frac{1}{2} f_{son} +1) - a_i$
有$f_i=(a_i+b_i)*2^{num_i}-1$
答案就是 $2^m\sum a_i*(2^{num_i}-1)+b_i*(2^{num_i})$
查看代码
using namespace std;
#include<bits/stdc++.h>
namespace zhu{
# define int long long
int N,M;
constexpr int maxn(5e5+5),mod(1e9+7);
constexpr int qp(int x,int y){
int ret=1;
while(y){
if(y&1) ret=ret*x%mod;
x=x*x%mod;
y>>=1;
}
return ret;
}
constexpr int ny(int x){
return qp(x,mod-2);
}
constexpr int n2=ny(2);
int dfn[maxn],low[maxn],clc=0,zhiz,gs[maxn],bel[maxn];
int p2p[maxn<<1];
std::vector<int>ed[maxn],e[maxn];
int sta[maxn],top=0;
void tarjan(int rt,int f){
sta[++top]=rt;
dfn[rt]=low[rt]=++clc;
for(auto x:ed[rt]){
if(x==f) continue;
if(!dfn[x]){
tarjan(x,rt);
low[rt]=min(low[rt],low[x]);
}else low[rt]=min(low[rt],low[x]);
}
if(low[rt]==dfn[rt]){
++zhiz;
while(sta[top+1]!=rt){
gs[zhiz]++;
bel[sta[top]]=zhiz;
--top;
}
}
}
int ans=0;
int f[maxn];
void dfs(int rt,int fa){
int a=1,b=1;
for(auto x:e[rt]){
if(x==fa) continue;
dfs(x,rt);
a=(a+f[x]*n2)%mod;
b=b*(f[x]*n2%mod+1)%mod;
}
b=(b-a)%mod;
ans=(ans+(p2p[gs[rt]]-1)*a+(p2p[gs[rt]])*b)%mod;
f[rt]=((a+b)*p2p[gs[rt]]-1)%mod;
}
int MAIN(){
cin>>N>>M;
for(int i=1;i<=M;i++){
int a,b;
scanf("%lld%lld",&a,&b);
ed[a].push_back(b),ed[b].push_back(a);
}
p2p[0]=1;
for(int i=1;i<=M||i<=N;i++) p2p[i]=(p2p[i-1]<<1)%mod;
tarjan(1,0);
for(int i=1;i<=N;i++){
for(auto x:ed[i]){
if(bel[x]^bel[i]) e[bel[x]].push_back(bel[i]);
}
}
dfs(1,0);
cout<<(ans*p2p[M]%mod+mod)%mod<<endl;
return 0;
}
};
#undef int
using namespace zhu;
int main(){
return MAIN();
}T4.比赛
设$A(l,r)=max(a_l,a_{l+1},\cdots,a_r)$,$B(l,r)=max(b_l,b_{l+1},\cdots,b_r)$
首先考虑线段树扫描线，设当前扫到$r$,线段树每个下标$l$,代表左端点为$l$的答案之和，即$\sum _{i=l} ^{r} A(l,i)*B(l,i)$.
利用单调栈求出每个数向左能影响到哪。
然后我们发现，每次右移指针相当于给所有节点的值$+=X*Y$,相当于维护历史和，这可以用矩阵来实现，对于每一个线段树节点对应一个矩阵：
$\left[ \begin{array} {}hans \\ \sum XY \\ \sum X \\ \sum Y \\ size \end{array} \right]$
然后赋值$X$,赋值$Y$，更新历史和的矩阵分别是：
$\left[ \begin{array} {}1 & 0 & 0 & 0 & 0 \\ 0 &0&0&0&x \\ 0&0&1&0&0 \\ 0&0&x&0&0 \\ 0&0&0&0&1 \end{array} \right]$,$\left[ \begin{array} {}1 & 0 & 0 & 0 & 0 \\ 0 &1&0&0&0 \\ 0&0&0&0&x \\ 0&x&0&0&0 \\ 0&0&0&0&1 \end{array} \right]$,$\left[ \begin{array} {}1 & 1 & 0 & 0 & 0 \\ 0 &1&0&0&0 \\ 0&0&1&0&0 \\ 0&0&0&1&0 \\ 0&0&0&0&1 \end{array} \right]$
但是这个玩应常数太大了，于是我们可以直接简化矩阵乘法，维护系数（具体看代码）。
查看代码
using namespace std;
#include<bits/stdc++.h>
namespace zhu{
using ull=unsigned long long;
constexpr int maxn(250005),maxt(maxn<<2);
int _type,N;
struct _tr{
ull hans,xy,x,y,sz;
_tr(){hans=xy=x=y=sz=0;}
};
struct _lzy{
ull a1,a2,a3,a4;
ull b1,b2,b3;
ull c,d;
_lzy(){a1=a2=a3=a4=b1=b2=b3=c=d=0;}
};
# define ls rt<<1,l,m
# define rs rt<<1|1,m+1,r
# define m ((l+r)>>1)
_tr tr[maxt];
_lzy tag[maxt];
bool istagd[maxt];
void pushup(int rt){
_tr *A=&tr[rt<<1],*B=&tr[rt<<1|1],*C=&tr[rt];
C->hans=A->hans+B->hans;
C->xy=A->xy+B->xy;
C->x=A->x+B->x;
C->y=A->y+B->y;
C->sz=A->sz+B->sz;
}
void build(int rt,int l,int r){
if(l==r) tr[rt].sz=1;
else build(ls),build(rs),pushup(rt);
}
void pushtag(int rt,_lzy& w){
_tr x;
x.sz=tr[rt].sz;
_tr &a=tr[rt];
x.hans=a.hans+w.a1*a.xy+w.a2*a.x+w.a3*a.y+w.a4*a.sz;
if(w.b1||w.b2||w.b3) x.xy=w.b1*a.x+w.b2*a.y+w.b3*a.sz;
else x.xy=a.xy;
if(w.c) x.x=w.c*a.sz;
else x.x=a.x;
if(w.d) x.y=w.d*a.sz;
else x.y=a.y;
a=x;
_lzy &t=tag[rt];
//hans
_lzy n;
n.a1=t.a1,n.a2=t.a2,n.a3=t.a3,n.a4=t.a4;
if(!t.b1&&!t.b2&&!t.b3){
n.a1+=w.a1;
}else{
if(t.c) n.a4+=t.c*t.b1*w.a1;
else n.a2+=t.b1*w.a1;
if(t.d) n.a4+=t.d*t.b2*w.a1;
else n.a3+=t.b2*w.a1;
n.a4+=t.b3*w.a1;
}
if(t.c) n.a4+=t.c*w.a2;
else n.a2+=w.a2;
if(t.d) n.a4+=t.d*w.a3;
else n.a3+=w.a3;
n.a4+=w.a4;
//xy
if(!w.b1&&!w.b2&&!w.b3){
n.b1=t.b1,n.b2=t.b2,n.b3=t.b3;
}else{
if(t.c) n.b3+=t.c*w.b1;
else n.b1+=w.b1;
if(t.d) n.b3+=t.d*w.b2;
else n.b2+=w.b2;
n.b3+=w.b3;
}
//x
if(!w.c) n.c=t.c;
else n.c=w.c;
//y
if(!w.d) n.d=t.d;
else n.d=w.d;
t=n;
istagd[rt]=1;
}
void pushdown(int rt){
if(istagd[rt]){
pushtag(rt<<1,tag[rt]);
pushtag(rt<<1|1,tag[rt]);
istagd[rt]=0;
tag[rt]=_lzy();
}
}
void ch(int rt,int l,int r,int L,int R,_lzy &w){
if(R<l||r<L||R<L) return;
if(L<=l&&r<=R){
pushtag(rt,w);
return;
}
pushdown(rt);
ch(ls,L,R,w);
ch(rs,L,R,w);
pushup(rt);
}
ull suan(int rt,int l,int r,int L,int R){
if(R<l||r<L||R<L) return 0;
if(L<=l&&r<=R){
return tr[rt].hans;
}
pushdown(rt);
return suan(ls,L,R)+suan(rs,L,R);
}
int a[maxn],b[maxn],Q;
ull ans[maxn];
struct xw{
int l,id;
};
std::vector<xw>q[maxn];
int la[maxn],lb[maxn];
int sta[maxn],top=0;
void cl(int a[],int la[]){
top=0;
for(int i=1;i<=N;i++){
while(top&&a[sta[top]]<a[i]) top--;
la[i]=sta[top]+1;
sta[++top]=i;
}
}
int MAIN(){
ASRT;
cin>>_type>>N;
for(int i=1;i<=N;i++) scanf("%d",&a[i]);
for(int i=1;i<=N;i++) scanf("%d",&b[i]);
cin>>Q;
for(int i=1;i<=Q;i++){
int l,r;
scanf("%d%d",&l,&r);
q[r].push_back((xw){l,i});
}
cl(a,la);
cl(b,lb);
build(1,1,N);
for(int i=1;i<=N;i++){
_lzy t;
int x=a[i],y=b[i];
t.b2=x;
t.c=x;
ch(1,1,N,la[i],i,t);
t.b2=0;
t.c=0;
t.b1=y;
t.d=y;
ch(1,1,N,lb[i],i,t);
t.b1=0;
t.d=0;
t.a1=1;
ch(1,1,N,1,i,t);
for(auto v:q[i]){
ans[v.id]=suan(1,1,N,v.l,i);
}
}
for(int i=1;i<=Q;i++) printf("%llu\n",ans[i]);
return 0;
}
};
#undef int
using namespace zhu;
int main(){
return MAIN();
}