8.1 NOIP模拟 11
今天上午返校之后，颓了一会，然后下午就开始考试，中午睡着了，然后刚开始考试的时候就困的一匹，我一看T1，woc，这不是之前线段树专题的题啊，和那道题差不多，所以我......想起来了，我当时没有做，完了，这就是之前坑哇的太大的缘故。我的内心当时就在滴血，心想推正解还不如先打个暴力，然后愉快的5分钟吗了一个暴力，整个就是俩sort，又花了五分钟改成了桶排，然后就愉快的交上去了，然后我T1还是没有思路，就15分钟的时候转了T2，T2一看就开始推组合数的柿子，但是由于我的误判成数学题，就完犊子了，那还等啥，一看20%的数据，就果断摔了一个dfs上去，然后就转T3，（此时内心虚的一批），T3一看，先想了一个啥都没有的暴力，然后又想到了前缀和优化，就优化一下，自己有造了几个极限数据，发现20%和40%应该都能过（当时心花怒放，但是其实60是不存在的），然后开考50分钟，打完了三个暴力，就歇菜了，剩下的时间就开始刚正解，最后的提交我也是挂着暴力交上去的，所以最后我的分数并没有因为我的覆盖而降低，但是也没有因为我的“正解”而分数增高，刚考完我就知道我这次凉凉，只打了3个暴力，肯定又垫底了，但是竟然还有暴力都没打对的大佬然后，我就和13个同学并列rank7，100分，虽然rank7，但是这是在别人失误的情况下得的，所以如果别人都没失误，那我这次就又垫底了，所以这次还是失败的考试。
T1 string
这这，一看就是之前学长讲过的那道用线段树维护的题，好像还带了二分，但是仔细一看略有不同，之前的那个是指询问地q个数，而这个是询问整个结果，所以我就（缨缨婴）只能打暴力，但是好像全场都没几个打正解的。在下面改题的过程中我就想到了一种奇爬的方法，就是维护一个每个字母出现次数的前缀和，然后通过一系列操作实现对字符串的变化，但是时间复杂度是$ O(n*m*26) $交上去T40，和我的暴力跑的时间一样，然后我就想怎么优化，有这么一种思路，就是我把前缀和的图像画在了之上，然后发现他是单调上升函数（这不是废话吗！），那么我就想到使用链表吧图像的拐点存下来，这样就可以知道了一些信息，而且可以 $ O(1) $计算出一些信息，但是需要 $ O(m*26) $的复杂度进行转移，所以应该比正解跑的还要快，但是男就难在了这个思路不好实现，所以我还是老老实实的打了线段树，最后还是没有忍住话了一点时间打了一下，发现确实很难条，我就暂且哇个坑，有神犇愿意为我条一下的也可以，后来我看cbx的T1快到飞起，其实他的思路和我的这个思路是一样的，就不赘述了;
我的T40暴力代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char cc;cc=getchar();
while(cc>''||cc<''){if(cc=='-')f=-;cc=getchar();}
while(cc>=''&&cc<=''){x=(x<<)+(x<<)+cc-'';cc=getchar();}
return x*f;
}
char s[];
int n,m,l,r,x;
inline bool cmp1(char a,char b){return a<b;}
inline bool cmp2(char a,char b){return a>b;}
int main()
{
//freopen("cnm.txt","r",stdin);
n=read();m=read();
scanf("%s",s+);
for(int i=;i<=m;i++)
{
l=read(),r=read(),x=read();
if(x==)sort(s+l,s+r+,cmp1);
else sort(s+l,s+r+,cmp2);
}
for(int i=;i<=n;i++)
printf("%c",s[i]);
puts("");
return ;
}
T40
我的AC线段树代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
const int maxn=;
using namespace std;
#define re register
#define debug(x) cout<<x<<" debug!"<<endl;
inline int read()
{
re int x=,f=;char cc;cc=getchar();
while(cc>''||cc<''){if(cc=='-')f=-;cc=getchar();}
while(cc>=''&&cc<=''){x=(x<<)+(x<<)+cc-'';cc=getchar();}
return x*f;
}
int m,n,k,t,sum[];
char s[maxn];
struct tree{
int l,r,vv,lev;
}tr[maxn<<];
inline void pushup(int x)
{
if(tr[x<<].vv==tr[x<<|].vv)
tr[x].vv=tr[x<<].vv;
else tr[x].vv=-;
}
inline void pushdown(int x)
{
if(tr[x].vv!=-)
tr[x<<].vv=tr[x<<|].vv=tr[x].vv;
else tr[x].vv=-;
}
inline void build(int x,int l,int r)
{
tr[x].l=l, tr[x].r=r;
tr[x].vv=-;
if(tr[x].l==tr[x].r)
{
tr[x].vv=s[l]-'a';
return;
}
int mid=(tr[x].l+tr[x].r)>>;
build(x<<,l,mid); build(x<<|,mid+,r);
pushup(x);
}
inline void query(int x)
{
if(tr[x].vv!=-)
{
for(register int i=;i<=tr[x].r-tr[x].l+;++i)
putchar(tr[x].vv+'a');
return;
}
query(x<<);
query(x<<|);
}
inline void make(int x,int l,int r)
{
if(l<=tr[x].l&&tr[x].r<=r)
{
if(tr[x].vv!=-)
{
sum[tr[x].vv]+=tr[x].r-tr[x].l+;
return;
}
}
pushdown(x);
int mid=(tr[x].l+tr[x].r)>>;
if(l<=mid)make(x<<,l,r);
if(mid+<=r)make(x<<|,l,r);
}
inline void change(int x,int l,int r,int vv)
{
if(l>r) return;
if(l<=tr[x].l&&tr[x].r<=r)
{
tr[x].vv=vv;
return;
}
int mid=(tr[x].l+tr[x].r)>>;
if(l<=mid)change(x<<,l,r,vv);
if(mid+<=r)change(x<<|,l,r,vv);
pushup(x);
}
int main()
{
//freopen("1.txt","r",stdin);
n=read(),m=read();
scanf("%s",s+);
build(,,n);
while(m--)
{
memset(sum,,sizeof(sum));
int l,r,x;
scanf("%d%d%d",&l,&r,&x);
make(,l,r);
if(x==)
{
int L=l;
for(register int i=;i<;++i)
{
change(,L,L+sum[i]-,i);
L+=sum[i];
}
}
if(x==)
{
int L=l;
for(register int i=;i>=;--i)
{
change(,L,L+sum[i]-,i);
L+=sum[i];
}
}
}
query();
puts("");
}
AC
还有cbx的代码就不放了，本人懒得征求版权了！
T2 Matrix
这到题是本人感觉正常最难的题，虽然看起来像组合数学（而且我也是按组合数学打的，但是并不是）
这是题解，其实就是一个贼神仙的dp，由于时间限制以及任务繁多，本人扔下代码就跑：
#include<iostream>
#include<cstdio>
using namespace std;
#define LL long long
#define re register
inline LL read()
{
re LL x=,f=;char cc;cc=getchar();
while(cc>''||cc<''){if(cc=='-')f=-;cc=getchar();}
while(cc>=''&&cc<=''){x=(x<<)+(x<<)+cc-'';cc=getchar();}
return x*f;
}
const LL p=;
LL n,m,dp[][],pw[],inv[],ipw[],l[],r[];
int main()
{
n=read(),m=read();
for(re LL i=;i<=n;++i)++l[read()],++r[read()];
for(re LL i=;i<=m;++i)l[i]+=l[i-],r[i]+=r[i-];
dp[][]=;
for(re LL i=;i<=m;++i)
{
dp[i][]=dp[i-][];
for(re LL j=;j<=r[i];++j)
dp[i][j]=(dp[i-][j]+dp[i-][j-]*(r[i]-j+)%p)%p;
for(re LL j=l[i-];j<l[i];++j)
for(re LL k=;k<=i-j;++k)
dp[i][k]=dp[i][k]*(i-k-j)%p;
}
printf("%lld\n",dp[m][n]);
}
T2
T3 big
本人也是先哇下坑，先沽了;
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define LL long long
#define re register
LL ch[][],tot;
LL num[],n,m;
LL ans,cnt,sum,pre[],x;
LL head[],nxt[],ver[],tot2,vvt[];
const int pc=;
inline LL read()
{
re LL x=,f=;char cc;cc=getchar();
while(cc>''||cc<''){if(cc=='-')f=-;cc=getchar();}
while(cc>=''&&cc<=''){x=(x<<)+(x<<)+cc-'';cc=getchar();}
return x*f;
}
void inser(LL x)
{
LL h=x%pc;
for(int i=head[h];i;i=nxt[i])
if(ver[i]==x)++vvt[i];
ver[++tot2]=x;
nxt[tot2]=head[h];
head[h]=tot2;
vvt[tot2]++;
}
LL query(LL x)
{
LL h=x%pc;
LL op=;
for(int i=head[h];i;i=nxt[i])
if(ver[i]==x)
op=vvt[i];
return op;
}
LL insert(LL x)
{
LL u=,wc=,xx=x;
for(register int i=n-;i>=;--i)
{
wc=(xx&(<<i))?:;
if(!ch[u][wc])
ch[u][wc]=++tot;
u=ch[u][wc];
}
}
inline void dfs(int x,int dep,int sum)
{
if(dep==-)
{
if(sum>=ans) ans=sum,inser(ans);
return;
}
if(!ch[x][]) dfs(ch[x][],dep-,sum^(<<dep));
if(!ch[x][]) dfs(ch[x][],dep-,sum^(<<dep));
if(ch[x][]&&ch[x][])
{
dfs(ch[x][],dep-,sum);
dfs(ch[x][],dep-,sum);
}
}
int main()
{
n=read(),m=read();
for(register int i=;i<=m;++i)
x=read(),pre[i]=pre[i-]^x;
for(register int i=,x;i<=m;++i)
{
x=((*pre[i])/(<<n)+*pre[i])%(<<n);
insert(x^pre[i]^pre[m]);
}
dfs(,n-,);
LL uu=query(ans);
printf("%lld\n%lld\n",ans,uu);
}
T3