01
题目大意
给定一个$01$串，找满足$0$的数量是$k$倍$1$的数量的最长子串
题解
可以发现一个$1$相当于$k$个$0$，所以记录$0$的数量，把$1$转换成$-k$个$0$，维护两个相同的前缀和的最远距离
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e6+5;
int n,k,_maxn;
char s[MAX];
map<LL,int> ma;
int main()
{
scanf("%d%d%s",&n,&k,s+1);
LL ans=0;
ma[0]=1;
for(int i=1;i<=n;++i)
{
if(s[i]=='0') ++ans;
if(s[i]=='1') ans-=k;
if(ma[ans]) _maxn=max(_maxn,i-ma[ans]+1);
else ma[ans]=i+1;
}
return printf("%d",_maxn),0;
}
biology
题目大意
给定矩阵$a,b$，要求找一条不一定连续的路径$L$，使得路径上的$a>0$且递增，求$\sum_{(x_i,y_i)\in L}b_{i,j}+\mid x_i-x_{i-1}\mid +\mid y_i-y_{i-1}\mid$的最大值
题解
显然排序$a$后可以$O(n^2\times m^2)$转移，发现要是没有绝对值就可以直接$O(n\times m)$转移
把$\mid x_i-x_{i-1}\mid +\mid y_i-y_{i-1}\mid$分情况拆开，维护$4$个值，然后就可以$O(n\times m)$转移了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=4e6+5,N=2e3+5;
struct p{
int x,_x,_y;
bool operator< (const p &a)
const{
return x<a.x;
}
}qwq[MAX];
int n,m,num;
LL ans;
int b[N][N];
LL f[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
qwq[++num]=(p){read(),i,j};
sort(qwq+1,qwq+1+num);
for(int i=1;i<=n;++i)
for(int j=1;j<=m;++j)
b[i][j]=read();
LL mx1=-1e18,mx2=-1e18,mx3=-1e18,mx4=-1e18;
for(int i=1,L=1;i<=num;++i)
if(qwq[i].x)
{
if(qwq[i].x!=qwq[i-1].x) for(;L<i;++L)
if(qwq[L].x) mx1=max(mx1,f[L]-qwq[L]._x-qwq[L]._y),mx2=max(mx2,f[L]-qwq[L]._x+qwq[L]._y),mx3=max(mx3,f[L]+qwq[L]._x-qwq[L]._y),mx4=max(mx4,f[L]+qwq[L]._x+qwq[L]._y);
ans=max(ans,f[i]=max(0ll,max(mx1+qwq[i]._x+qwq[i]._y,max(mx2+qwq[i]._x-qwq[i]._y,max(mx3-qwq[i]._x+qwq[i]._y,mx4-qwq[i]._x-qwq[i]._y))))+b[qwq[i]._x][qwq[i]._y]);
}
return printf("%lld",ans),0;
}
english
题目大意
给定一个序列$a$，求$\sum_{l=1}^{n}\sum_{r=l}^{n}(a_l\oplus a_r)\times max(a_i),l\le i\le r$和$\sum_{l=1}^{n}\sum_{r=l}^{n}[(a_l\oplus a_r)>max(a_i)]\times max(a_i),l\le i\le r$
题解
第一问是很好求的，维护两个单调栈，求出$a_i$左右第一个大于ta的位置，说明这一段区间最大值就是$a_i$，异或就每一位的维护，$num0_l\times num1_r+num1_l\times num0_r$
第二问考虑用$Trie$维护$a_i$二进制每一位，对于第一问求出$i$的区间$[l_i,r_i]$，枚举左右区间中较小的，查询另一半中异或枚举值大于$a_i$的个数
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e5+5,mod=1e9+7;
int tot,n,op;
struct Trie{
int siz[MAX<<5];
int son[MAX<<5][2];
void ins(int pre,int &i,int x,int k)
{
i=++tot,son[i][0]=son[pre][0],son[i][1]=son[pre][1],siz[i]=siz[pre];
if(k==-1) return void(++siz[i]);
int qwq=(x>>k)&1;
ins(son[pre][qwq],son[i][qwq],x,k-1);
siz[i]=siz[son[i][0]]+siz[son[i][1]];
}
LL ask(int pre,int i,int x,int _max,int k)
{
if(k==-1) return 0;
int qwq=(_max>>k)&1,qaq=(x>>k)&1;
if(qwq) return ask(son[pre][qaq^1],son[i][qaq^1],x,_max,k-1);
else return (ask(son[pre][qaq],son[i][qaq],x,_max,k-1)+siz[son[i][qaq^1]]-siz[son[pre][qaq^1]]+mod)%mod;
}
}Tree;
int rt[MAX],a[MAX],st[MAX],lm[MAX],rm[MAX];
LL sum1[21][MAX],sum0[21][MAX];
void count()
{
for(int i=1;i<=n;++i)
for(int j=0;j<=20;++j)
sum1[j][i]=sum1[j][i-1]+bool(a[i]&(1<<j)),sum0[j][i]=sum0[j][i-1]+!(a[i]&(1<<j));
}
void work1()
{
count();
LL qvq=0,ans=0;
for(int i=1,l,r;i<=n;++i)
{
if(!rm[i]) rm[i]=n+1;
l=lm[i]+1,r=rm[i]-1,qvq=0;
for(int j=0;j<=20;++j)
{
qvq=(qvq+(1ll<<j)*((sum0[j][r]-sum0[j][i])*(sum1[j][i-1]-sum1[j][l-1])%mod+(sum1[j][r]-sum1[j][i])*(sum0[j][i-1]-sum0[j][l-1])%mod)%mod)%mod;
if(a[i]&(1<<j)) qvq=(qvq+(1ll<<j)*(sum0[j][r]-sum0[j][l-1])%mod)%mod;
else qvq=(qvq+(1ll<<j)*(sum1[j][r]-sum1[j][l-1])%mod)%mod;
}
ans=(ans+qvq*a[i]%mod)%mod;
}
printf("%lld\n",ans);
}
void work2()
{
for(int i=1;i<=n;++i)
Tree.ins(rt[i-1],rt[i],a[i],20);
LL ans=0;
for(int i=1,l,r;i<=n;++i)
{
if(!rm[i]) rm[i]=n+1;
l=lm[i]+1,r=rm[i]-1;
if(i-l>r-i) for(int j=i;j<=r;++j)
ans=(ans+Tree.ask(rt[l-1],rt[i],a[j],a[i],20)*a[i]%mod)%mod;
else for(int j=l;j<=i;++j)
ans=(ans+Tree.ask(rt[i-1],rt[r],a[j],a[i],20)*a[i]%mod)%mod;
}
printf("%lld\n",ans);
}
int main()
{
scanf("%d%d",&n,&op);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1,top=0;i<=n;++i)
{
while(top&&a[st[top]]<=a[i]) --top;
lm[i]=st[top],st[++top]=i;
}
for(int i=n,top=0;i>=1;--i)
{
while(top&&a[st[top]]<a[i]) --top;
rm[i]=st[top],st[++top]=i;
}
if(op&1) work1();
if(op&2) work2();
return 0;
}
u
题目大意
给定一个$n\times n$的矩阵，初始矩阵全为$0$，有$q$次修改，每次给一个左上顶点为$(r,c)$、直角边长为$l$的下三角区域加上$s$
求$q$次修改后矩阵的异或和
题解
如果修改的是一段区间的话可以用修改差分数组$O(1)$实现，把直角三角形看成$l$条递增的区间依次修改，复杂度$O(nq+n^2)$
发现如果斜着看，直角三角形斜边上相当于修改区间，所以也可以用修改差分数组的方法修改，竖着同理，复杂度$O(q+n^2)$
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=1e3+5;
int n,q;
LL ans;
LL s1[MAX][MAX],s2[MAX][MAX];
int main()
{
scanf("%d%d",&n,&q);
for(int i=1,r,c,l,s;i<=q;++i)
{
scanf("%d%d%d%d",&r,&c,&l,&s),s1[r][c]+=s,s2[r][c+1]-=s;
if(r+l-1<=n) s1[r+l][c]-=s;
if(r+l-1<=n&&c+l<=n) s2[r+l][c+l+1]+=s;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
s2[i][j]+=s2[i-1][j-1],s1[i][j]+=s1[i-1][j];
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
ans^=(s1[i][j]+=s1[i][j-1]+s2[i][j]);
return printf("%lld",ans),0;
}
v
题目大意
给定一个字符串，里面字符可能是'W'和'B'，要操作$k$次，第$i$次等概率选择一个$[1,n-i+1]$中的数$x$，可以选择从左或者从右开始第$x$个不为空的位置，去掉上面的字符，求最优策略下去除'W'的期望个数
题解
可以用$2$进制表示字符串的状态，因为最大可能是$1«30$，所以小数用数组存，大数用map存
然后记忆化搜索即可
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<map>
# include<algorithm>
using namespace std;
const int MAX=(1<<18)+1;
int n,K;
char s[51];
double f[MAX][31];
map<int,double> ma[31];
int ss(int S,int k,int qwq)
{
int L=n-qwq,ll,SS=S,SSS=S;
ll=k,S>>=ll,SSS>>=(ll-1);
return (SS-(SSS<<(ll-1)))|(S<<(ll-1));
}
double dfs(int S,int k=0,int qwq=0)
{
double ans=0;
if(k==K) return qwq;
if(S<MAX&&f[S][k]) return f[S][k];
if(S>=MAX&&ma[k][S]) return ma[k][S];
int L=n-k;
for(int i=1;i<=L;++i)
{
int RS=ss(S,i,k),LS=ss(S,L-i+1,k),qcq=bool((1<<(i-1))&S),qvq=bool((1<<(L-i))&S);
if(qvq==qcq) ans+=1/double(L)*max(dfs(LS,k+1,qwq+qvq),dfs(RS,k+1,qwq+qcq));
else if(qvq) ans+=1/double(L)*(dfs(LS,k+1,qwq+qvq));
else ans+=1/double(L)*(dfs(RS,k+1,qwq+qcq));
}
if(S<MAX) f[S][k]=ans;
else ma[k][S]=ans;
return ans;
}
int main()
{
scanf("%d%d%s",&n,&K,s);
int S=0;
for(int i=0;i<n;++i)
S+=(1<<i)*(s[n-i-1]=='W');
return printf("%.10lf",dfs(S)),0;
}
