3月6日考试总结:
T1
原题:CF GYM 102056 I(有改动)
得分情况 :
预计分数 : 28pts
实际得分 : 28pts
似乎没啥好说的 暴力就是一个dfs
正解 :
考虑正向DP不行的原因
发现是2/3操作的贡献于它后边的攻击操作位置相关
而倒序DP可以处理这个问题
考虑2/3操作在知道后面的决策情况时的贡献
则在\(i\)位置 3 操作的贡献为 \(\sum_{j=i+1}^{n}[tag_j=1]*c[i]\)
在\(i\)位置时2操作的贡献为\(\sum_{j=i+1}^{n}[tag_j=1]*b[i]*(j-i)\)
设\(f[i][j][k]\)为处理\(i\)位置,攻击\(j\)次,攻击集合的标记的和为\(k\)时的最大伤害
注 : 这里的标记的意思是 : 从n至1的第几次攻击
则上式化为 :
\(tag_i=2,w_i=j*c[i]\)
\(tag_i=3,w_i = b[i]*((n-i+1)*j-k)\)
注 : 这里\(b[i]*((n-i+1)*j-k)\)实际上就是 :
\(\sum_{j=i+1}^{n}[tag_j=1]*b[i]*(j-i)\)
\(b[i]*\sum_{j=i+1}^{n}[tag_j=1]*(j-i)\)
\(b[i]*\sum_{j=i+1}^{n}[tag_j=1]*(n+1-n-1+j-i))\)
\(b[i]*\sum_{j=i+1}^{n}[tag_j=1]*(-(n-j+1)+(n-i+1)))\)
\(b[i]*(\sum_{j=i+1}^{n}[tag_j=1]*(n-i+1)-\sum_{j=i+1}^{n}[tag_j=1]*(n-j+1))\)
\(b[i]*(J*(n-i+1)-k)\)
这样处理的目的是卡这个\(O(n^4)\)的算法的上界,这样在枚举\(k\)时会少经过一些无用情况
不然n=150你拿头过
核心代码 :
vis[(n+1)&1][0][0]=1;
for(int i=n;i>=1;i=~(-i)){
int u=i&1,v=(i+1)&1,cnt=n-i;
for(int j=0;j<=cnt;j=-~j){
for(int k=0;k<=(cnt)*(cnt+1)/2;k=-~k){
if(!vis[v][j][k])continue;
f[u][j+1][k+cnt+1]=max(f[u][j+1][k+cnt+1],f[v][j][k]+a[i]);
f[u][j][k]=max(f[u][j][k],f[v][j][k]+1ll*j*c[i]);
f[u][j][k]=max(f[u][j][k],f[v][j][k]+1ll*((cnt+1)*j-k)*b[i]);
vis[u][j][k]=vis[u][j+1][k+cnt+1]=1;
vis[v][j][k]=0;f[v][j][k]=0;
}
}
}
T2
原题:CF 297 E
得分情况 :
预计分数 : 30pts
实际得分 : 30pts
似乎也没啥好写的......
15pts\(O(n^3)\)暴力,3pts特殊情况1直接算
12pts的特殊情况2就很鬼了, 考虑每个大段向其直接覆盖的小段连边,那么是一棵树
你考虑一下树的一颗子树,发现它代表的是序列的一段区间
然后统计 : 大区间包含小区间的贡献和连续不相交区间的贡献
一发树型DP就好辽
正解 :
发现合法情况为1,1,2,2,3,3,或1,2,3,1,2,3或1,2,2,3,3,1
发现直接统计合法三元组并不靠谱,反正我是卜会
然后就考虑统计不合法情况
对所有不合法情况进行手玩+归纳后可归为两大类
接下来就是代码注释里的东西了
核心代码 :
for(int i=1;i<=(n<<1);i=-~i){
if(!L[i])continue;
int Include=query(L[i]);
// 此时L[i]至n的点数为L[i]至i这条线段包含的线段数
int Intersect=(i-L[i]-1-(Include<<1));
// 此时L[i]+1至n-1的空位置数为与L[i]至i这条线段相交的线段数
// 因为被包含的线段两端都在区间内所以减两倍
int Disjoint=(n-1-Intersect);
// 不与当前线段相交的线段数(可以包含/相离)
// 还包括了A包含B,A包含C,BC相交时的情况,会在B/C处各算一次
int Apart=(n-1-Intersect-Include);
// 与当前线段相离的线段数
det1+=1ll*Intersect*Disjoint;
// (当前线段,与之相交的线段,不与之相交的线段)组成的"相交"不合法三元组数量
det2+=1ll*Include*Apart;
// (当前线段,被其包含的线段,与之相离的线段)组成的"包含"不合法三元组数量
update(L[i],1);
}
ll ans=1ll*n*(n-1)/2*(n-2)/3-det1/2-det2;
// 全部三元组数量 - "相交"不合法三元组量/2 - "包含"不合法三元组数量
// 因为 "相交"不合法三元组 会在相交的两个线段处各算一次,所以除二
printf("%lld\n",ans);
注 : query与update都是一个维护后缀和树状数组
其实是要-query(i+1)的 , 但这个一定是0 , 就不管他了XD
所以用正常树状数组也是可以的quq
T3
原题:LOJ 6071
得分情况 :
预计得分 : 22pts
实际得分 : 0pts
写法就是一发\(O(可过)\)的dfs
挂掉的原因是没有注意子串为空时合法
事实上子串为空的情况只有\(len=1\)没统计
然而捆了,而且基本每个点都有一串\(len=1\)的...
挂至0分quq 确实是自己犯蠢了Orz
过来YL第一次考字符串就连暴力都挂了,果然我和这玩意相性极差
正解 :
考虑怎么对\(i\)串\(j\)位置的字符计算它之后接一些子串的方案数
然后你会发现 , 这完全没法搞 反正我日常不会
那么和T1一样考虑倒着来
我们考虑两个数组维护 , \(f\)和\(g\)
\(f\)是\(i+1\)号串至\(n\)号串在SAM的root节点的匹配方案数的和
\(f_k\)就是\(i+1\)号串至\(n\)号串选出的串开头为\(k\)的方案数
并且从\(n\)扫至\(1\)后的\(f\)的和就是答案
设\(g\)是\(i\)号串在\(j\)位置的匹配的方案数
然后发现\(f_k\)的值只与\(g_{root->next[k]}\)有关
那么现在问题就是如何计算\(g_{j}\) , 这样就可以计算\(f\)了
考虑从\(j\)号点链接到它后一个字符
情况有两种
- \(j\)号点存在一个权值为\(k\)的出边
那么就可以直接从它指向的那个点的\(g\)值直接转移而来 - \(j\)号点没有为\(k\)的出边
那么就只能把它接到\(f_k\)上了
具体细节的就看代码8
for(int i=n;i>=1;i--){
int l=strlen(s[i]);sam.init();
for(int j=0;j< l;j=-~j)sam.insert(s[i][j]-'a'+1);
for(int j=0;j<=sam.sz;j=-~j)t[j]=j;
sort(t,t+sam.sz+1,cmp);// 按len从大至小
for(int J=0,j;J<=sam.sz;J=-~J){
j=t[J],g[j]=1;
for(int k=1;k<=26;k=-~k){
int v=sam.st[j].next[k];
if(v)g[j]=(g[j]+g[v])%mod;// 直接从v转移
else g[j]=(g[j]+f[k])%mod;// v不存在,从f转移
}
}
for(int k=1;k<=26;k=-~k){
int u=0,v=sam.st[u].next[k];
if(v)f[k]=g[v]; //更新f的值
}
}
总结 :
得分情况 :
80pts->rank11
58pts->rank17
下次打暴力还是用下心吧@^@
考试状态 :
并不是心理状态原因啥的
近期的问题大概在于大量的忽略边界导致的挂分
并且思维能力与知识积累不足导致的写不出正解
先好好考试 + 改题 , 有其它时间就去多刷题可能会好一点