总结
今天的 (T2) 算是比较套路的一道题
不知道为什么就去想回滚莫队了
感觉最近的几场考试考场上思考的深度变浅了
要及时调整状态
A.划分序列
分析
对于 (a[i] geq 0) 和 (a[i] leq 0) 的点
可以二分的时候分别判断一下最小段数、最大段数和 (k) 的关系
对于全部的数据，答案显然是单调的
所以仍然是二分答案
利用数状数组维护后缀 (max) 和 后缀 (min)
分别求出能在当前的限制下能划分的最大段数和最小段数
如果 (k) 在这个区间里返回合法，否则不合法
找到最小的一个合法的就是答案
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e5+5;
int n,a[maxn],k,sum[maxn],sta[maxn],tp,wz[maxn];
int tr1[maxn],tr2[maxn];
int lb(rg int xx){
return xx&-xx;
}
int cx1(rg int wz){
rg int nans=-0x3f3f3f3f;
for(rg int i=wz;i<=n;i+=lb(i)){
nans=std::max(nans,tr1[i]);
}
return nans;
}
void xg1(rg int wz,rg int val){
for(rg int i=wz;i>0;i-=lb(i)){
tr1[i]=std::max(tr1[i],val);
}
}
int cx2(rg int wz){
rg int nans=0x3f3f3f3f;
for(rg int i=wz;i<=n;i+=lb(i)){
nans=std::min(nans,tr2[i]);
}
return nans;
}
void xg2(rg int wz,rg int val){
for(rg int i=wz;i>0;i-=lb(i)){
tr2[i]=std::min(tr2[i],val);
}
}
void init(){
for(rg int i=0;i<=n;i++){
tr1[i]=-0x3f3f3f3f;
tr2[i]=0x3f3f3f3f;
}
}
int getwz(rg int val){
return std::lower_bound(sta+1,sta+1+tp,val)-sta;
}
bool jud(rg int val){
init();
xg1(getwz(0),0),xg2(getwz(0),0);
for(rg int i=1;i<n;i++){
xg1(wz[i],cx1(getwz(sum[i]-val))+1);
xg2(wz[i],cx2(getwz(sum[i]-val))+1);
}
rg int tmp1=cx1(getwz(sum[n]-val))+1;
rg int tmp2=cx2(getwz(sum[n]-val))+1;
return tmp2<=k && tmp1>=k;
}
int main(){
n=read(),k=read();
for(rg int i=1;i<=n;i++) a[i]=read();
for(rg int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
for(rg int i=0;i<=n;i++) sta[++tp]=sum[i];
std::sort(sta+1,sta+1+tp);
tp=std::unique(sta+1,sta+1+tp)-sta-1;
for(rg int i=0;i<=n;i++) wz[i]=std::lower_bound(sta+1,sta+tp+1,sum[i])-sta;
rg int l=-0x7f7f7f7f,r=0x7f7f7f7f,mids;
while(l<=r){
mids=(l+r)>>1;
if(jud(mids)) r=mids-1;
else l=mids+1;
}
printf("%d
",l);
return 0;
}
B.Ring
分析
对于每一个左端点 (i) 维护 (mmax[i]) 表示以 (i) 为左端点，(mmax[i]) 为右端点形成的区间恰好有环，并且 (mmax[i]) 是最小的合法的值
这个东西显然是单调的
双指针扫一下用 (lct) 维护加边断边就行了
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e6+5;
int n,m,q,x[maxn],y[maxn],mmax[maxn];
struct LCT{
int ch[maxn][2],fa[maxn],rev[maxn],sta[maxn],tp;
void push_down(rg int da){
if(!rev[da]) return;
rg int lc=ch[da][0],rc=ch[da][1];
rev[lc]^=1,rev[rc]^=1,rev[da]^=1;
std::swap(ch[da][0],ch[da][1]);
}
bool isroot(rg int da){
return ch[fa[da]][0]!=da && ch[fa[da]][1]!=da;
}
void xuanzh(rg int x){
rg int y=fa[x];
rg int z=fa[y];
rg int k=(ch[y][1]==x);
if(!isroot(y)) ch[z][ch[z][1]==y]=x;
fa[x]=z;
ch[y][k]=ch[x][k^1];
fa[ch[x][k^1]]=y;
ch[x][k^1]=y;
fa[y]=x;
}
void splay(rg int x){
sta[tp=1]=x;
for(rg int i=x;!isroot(i);i=fa[i]) sta[++tp]=fa[i];
for(rg int i=tp;i>=1;i--) push_down(sta[i]);
while(!isroot(x)){
rg int y=fa[x];
rg int z=fa[y];
if(!isroot(y)) (ch[z][1]==y)^(ch[y][1]==x)?xuanzh(x):xuanzh(y);
xuanzh(x);
}
}
void access(rg int x){
for(rg int y=0;x;y=x,x=fa[x]){
splay(x);
ch[x][1]=y;
}
}
void makeroot(rg int x){
access(x);
splay(x);
rev[x]^=1;
push_down(x);
}
int findroot(rg int x){
access(x);
splay(x);
push_down(x);
while(ch[x][0]){
x=ch[x][0];
push_down(x);
}
splay(x);
return x;
}
void split(rg int x,rg int y){
makeroot(x);
access(y);
splay(y);
}
void link(rg int x,rg int y){
makeroot(x);
fa[x]=y;
}
void cut(rg int x,rg int y){
split(x,y);
fa[x]=ch[y][0]=0;
}
}lct;
int main(){
n=read(),m=read(),q=read();
for(rg int i=1;i<=m;i++) x[i]=read(),y[i]=read();
for(rg int i=1;i<=m;i++) mmax[i]=m+1;
rg int now=1;
for(rg int i=1;i<=m;i++){
while(now<=m && lct.findroot(x[now])!=lct.findroot(y[now])){
lct.link(x[now],y[now]);
now++;
}
mmax[i]=now;
lct.cut(x[i],y[i]);
}
rg int aa,bb;
for(rg int i=1;i<=q;i++){
aa=read(),bb=read();
if(bb>=mmax[aa]) printf(">_<
");
else printf("QAQ
");
}
return 0;
}
C.Match
分析
答案是一个次数比较低的多项式
打出前几项之后用高斯消元求一下系数就行了
代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#define rg register
inline int read(){
rg int x=0,fh=1;
rg char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') fh=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*fh;
}
const int maxn=1e2+5,mod=1e9+7;
inline int mulmod(rg long long now1,rg int now2){
return now1*=now2,now1>=mod?now1%mod:now1;
}
inline int addmod(rg int now1,rg int now2){
return now1+=now2,now1>=mod?now1-mod:now1;
}
inline int delmod(rg int now1,rg int now2){
return now1-=now2,now1<0?now1+mod:now1;
}
int ksm(rg int ds,rg int zs){
rg int nans=1;
while(zs){
if(zs&1) nans=mulmod(nans,ds);
ds=mulmod(ds,ds);
zs>>=1;
}
return nans;
}
int a[maxn][maxn],n,ans[maxn],totans;
void gsxy(){
for(rg int i=1;i<=n;i++){
rg int xs=ksm(a[i][i],mod-2);
for(rg int j=i;j<=n+1;j++){
a[i][j]=mulmod(a[i][j],xs);
}
for(rg int j=i+1;j<=n;j++){
xs=a[j][i];
for(rg int k=i;k<=n+1;k++){
a[j][k]=delmod(a[j][k],mulmod(xs,a[i][k]));
}
}
}
ans[n]=a[n][n+1];
for(rg int i=n-1;i>=1;i--){
ans[i]=a[i][n+1];
for(rg int j=i+1;j<=n;j++){
ans[i]=delmod(ans[i],mulmod(ans[j],a[i][j]));
}
}
}
int main(){
n=4;
for(rg int i=1;i<=4;i++){
a[i][1]=1;
a[i][2]=i;
a[i][3]=ksm(i,2);
a[i][4]=ksm(i,3);
}
a[1][5]=0;
a[2][5]=mulmod(333333336,2);
a[3][5]=mulmod(207407410,3);
a[4][5]=mulmod(800000008,4);
a[5][5]=mulmod(746666676,5);
gsxy();
n=read();
for(rg int i=1;i<=4;i++){
totans=addmod(totans,mulmod(ans[i],ksm(n,i-1)));
}
totans=mulmod(totans,ksm(n,mod-2));
printf("%d
",totans);
return 0;
}