3月6日考试总结:
T1
原题:(有改动)
得分情况 :
预计分数 : 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\)时会少经过一些无用情况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
原题:
得分情况 :
预计分数 : 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 , 就不管他了XDT3
原题:
得分情况 :
预计得分 : 22pts
实际得分 : 0pts 写法就是一发\(O(可过)\)的dfs 挂掉的原因是没有注意子串为空时合法 事实上子串为空的情况只有\(len=1\)没统计 然而捆了,而且基本每个点都有一串\(len=1\)的... 挂至0分quq 确实是自己犯蠢了Orz正解 :
考虑怎么对\(i\)串\(j\)位置的字符计算它之后接一些子串的方案数
然后你会发现 , 这完全没法搞设\(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 下次打暴力还是用下心吧@^@考试状态 :
并不是心理状态原因啥的
近期的问题大概在于大量的忽略边界导致的挂分 并且思维能力与知识积累不足导致的写不出正解 先好好考试 + 改题 , 有其它时间就去多刷题可能会好一点