发现分那么多的博客让我非常的凌乱,于是我就开了这个博客
开场看了一遍题,认为T1十分的有趣,于是进行了一个做,一直到10点的时候我还兴致勃勃的在玩Excel
直到搞到了70pts,开始头疼,疼死那种,完全无法思考,尝试喝水和去楼下溜达都不管事...
后面两个题直接弃掉了
考场上的是垃圾做法,完全是碰巧了找到了这个做法
先考虑只有一个对角线的时候,这时就是让ij不相等于是变成1,那么考虑推广
发现我们可以对列分奇偶性,这样的活只处理奇数或者偶数的话发现两行可以缩在一起,于是变回了上一个题,但是复杂度变为两倍
这个东西是可以继续推广的
考虑求不同的数如何做,一般来说是枚举二进制位哪个不同,这样的话是2log的,因为要交换10
但是我们有一个小trick,就是我们保证1的数目是相等的,这样就不用交换了,因为如果有一位这里是1那边是0,那么肯定还有一位是恰好相反的
这里用13位数6个1是正好的,离散化一下就行了
#include using namespace std; #define fo(i,x,y) for(int i=(x);i<=(y);i++) #define fu(i,x,y) for(int i=(x);i>=(y);i--) int read(){ int s=0,t=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();} while(isdigit(ch)){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();} return s*t; } const int N=3005; int n,Q,ans; int wo[N],ys[1<<13],cwo; vector cz[15][2],an[32][2]; signed main(){ freopen("matrix.in","r",stdin); freopen("matrix.out","w",stdout); n=read();Q=read(); fo(i,1,(1<<13)-1)if(__builtin_popcount(i)==6)wo[++cwo]=i,ys[i]=cwo; fo(i,1,13){ fo(j,1,cwo){ if(wo[j]>>i-1&1)cz[i][1].push_back(j); else cz[i][0].push_back(j); } // cerr<<cz[i][0].size()<<" "<<cz[i][1].size()<<endl;="" }="" fo(i,1,13){="" ++ans;="" for(int="" x:cz[i][0]){="" if(x*2-1<="n)an[ans][0].push_back(x*2-1);" if(x*2<="n)an[ans][0].push_back(x*2);" x:cz[i][1]){="" cerr<<i<<"="" "<<cz[i][0][0]<<"="" "<<cz[i][1][0]<<endl;="" if(!an[ans][0].size()||!an[ans][1].size()){="" an[ans][0].clear();an[ans][1].clear();="" ans--;continue;="" ++ans;an[ans][0].push_back(1);="" if(x*2+1<="n)an[ans][0].push_back(x*2+1);" printf("%d\n",ans);="" fo(i,1,ans){="" printf("%d="" %d="" ",(int)an[i][0].size(),(int)an[i][1].size());="" x:an[i][0])printf("%d="" ",x);="" x:an[i][1])printf("%d="" printf("\n");="" return="" 0;="" }<="" code="">
T2 字符串
好像这玩意就是个后缀树,不对,是垃圾版的后缀树
于是我们直接做个区间本质不同子串数就行了
这个东西用lct维护,扫描线,额去luogu看吧...
AC_code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fo(i,x,y) for(int i=(x);i<=(y);i++)
#define fu(i,x,y) for(int i=(x);i>=(y);i--)
int read(){
int s=0,t=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')t=-1;ch=getchar();}
while(isdigit(ch)){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
return s*t;
}
const int N=1e6+5;
int n,ans;char s[N];
struct Q{int l,r;}q[N<<1];
bool comQ(Q a,Q b){return a.r<b.r;}
struct SAM{
struct POT{
int son[2],fail;
int len,pos;
}tr[N<<1];
int seg,las;
SAM(){seg=las=1;}
void ins(int c,int i){
int np=++seg,p=las;las=np;
tr[np].len=tr[p].len+1;tr[np].pos=i;
while(p&&!tr[p].son[c])tr[p].son[c]=np,p=tr[p].fail;
if(!p)tr[np].fail=1;
else {
int q=tr[p].son[c];
if(tr[q].len==tr[p].len+1)tr[np].fail=q;
else {
int nq=++seg;
tr[nq]=tr[q];tr[nq].len=tr[p].len+1;
tr[q].fail=tr[np].fail=nq;
while(p&&tr[p].son[c]==q)tr[p].son[c]=nq,p=tr[p].fail;
}
}
}
}sam;
struct XDS{
#define ls x<<1
#define rs x<<1|1
int sm[N*4],tg[N*4];
void pushup(int x){
sm[x]=sm[ls]+sm[rs];
}
void pushdown(int x,int l,int r){
int mid=l+r>>1;
sm[ls]+=tg[x]*(mid-l+1);tg[ls]+=tg[x];
sm[rs]+=tg[x]*(r-mid);tg[rs]+=tg[x];
tg[x]=0;
}
void ins(int x,int l,int r,int ql,int qr,int v){
if(ql>qr)return ;
if(ql<=l&&r<=qr){
sm[x]+=v*(r-l+1);
tg[x]+=v;
return ;
}
int mid=l+r>>1;if(tg[x])pushdown(x,l,r);
if(ql<=mid)ins(ls,l,mid,ql,qr,v);
if(qr>mid)ins(rs,mid+1,r,ql,qr,v);
pushup(x);
}
int qry(int x,int l,int r,int ql,int qr){
if(ql>qr)return 0;
if(ql<=l&&r<=qr)return sm[x];
int mid=l+r>>1,ret=0;if(tg[x])pushdown(x,l,r);
if(ql<=mid)ret+=qry(ls,l,mid,ql,qr);
if(qr>mid)ret+=qry(rs,mid+1,r,ql,qr);
return ret;
}
#undef ls
#undef rs
}xds;
struct LCT{
struct POT{
int son[2],fa;
int vl,tg;
}tr[N<<1];
void pushdown(int x){
if(tr[x].tg){
if(tr[x].son[0])tr[tr[x].son[0]].vl=tr[tr[x].son[0]].tg=tr[x].tg;
if(tr[x].son[1])tr[tr[x].son[1]].vl=tr[tr[x].son[1]].tg=tr[x].tg;
tr[x].tg=0;
}
}
bool nroot(int x){return tr[tr[x].fa].son[0]==x||tr[tr[x].fa].son[1]==x;}
bool get(int x){return tr[tr[x].fa].son[1]==x;}
void rotate(int x){
int y=tr[x].fa,z=tr[y].fa;
int xpos=get(x),ypos=get(y);
if(nroot(y))tr[z].son[ypos]=x;
tr[x].fa=z;tr[y].fa=x;
tr[y].son[xpos]=tr[x].son[xpos^1];
tr[x].son[xpos^1]=y;
tr[tr[y].son[xpos]].fa=y;
}
int pth[N<<1],pt;
void splay(int x){
int now=x;pth[++pt]=x;
while(nroot(now))pth[++pt]=now=tr[now].fa;
while(pt)pushdown(pth[pt--]);
while(nroot(x)){
int y=tr[x].fa;
int xpos=get(x),ypos=get(y);
if(nroot(y)){
if(xpos==ypos)rotate(y);
else rotate(x);
}rotate(x);
}
}
void access(int x,int v){
for(int y=0;x;y=x,x=tr[x].fa){
splay(x);tr[x].son[1]=y;
if(tr[x].vl)xds.ins(1,1,n,tr[x].vl-sam.tr[x].len+1,tr[x].vl-sam.tr[tr[x].fa].len,-1);
tr[x].vl=tr[x].tg=v;
}
xds.ins(1,1,n,1,v,1);
}
}lct;
int pos[N];
signed main(){
freopen("string.in","r",stdin);
freopen("string.out","w",stdout);
scanf("%s",s+1);n=strlen(s+1);reverse(s+1,s+n+1);
fo(i,1,n)sam.ins(s[i]-'0',i),pos[i]=sam.las;
fo(i,2,sam.seg){
q[i]=Q{sam.tr[i].pos-sam.tr[i].len+1,sam.tr[i].pos-sam.tr[sam.tr[i].fail].len};
lct.tr[i].fa=sam.tr[i].fail;
}
sort(q+2,q+sam.seg+1,comQ);int now=1;
fo(i,2,sam.seg){
while(now<=q[i].r)lct.access(pos[now],now),now++;
ans+=xds.qry(1,1,n,q[i].l,q[i].r);
// cerr<<ans<<" "<<q[i].l<<" "<<q[i].r<<" "<<xds.qry(1,1,n,q[i].l,q[i].r)<<endl;
}
printf("%lld\n",ans);
return 0;
}