湖州 外贸网站建设,加盟创业商机网,网站app建设需要资源,wordpress is电影主题结论专场#xff0c;结果被踩暴了
青鱼和序列
赛时的做法是#xff0c;维护∑aii\sum a_i\times i∑aii的取值#xff0c;发现只和最后一次操作222的位置有关#xff0c;于是递推O(n)O(n)O(n)解决。
赛后发现还有更神奇的结论 第二个结论是#xff0c;第一次进行操作…结论专场结果被踩暴了
青鱼和序列
赛时的做法是维护∑ai×i\sum a_i\times i∑ai×i的取值发现只和最后一次操作222的位置有关于是递推O(n)O(n)O(n)解决。
赛后发现还有更神奇的结论 第二个结论是第一次进行操作222过后aaa序列变成回文的了所以这之后1,21,21,2操作就是等价的了。
这两个结论单独来看都很容易发现。不过接下来这个结论可能不容易看出只要进行了操作222那么最后的结果就是一定的。事实上这不难从前222个结论中看出。不过如果打表还是很容易看出的
看来我猜结论的功底还是太菜了还是要多尝试啊
青鱼和怪兽
猜了一个结论直接二分答案就可以解决。
同样不难通过打表证明这个结论是正确的
青鱼和区间
垃圾题解写的像shit一样真就谜语人呗
这个结论太小以至于我看不见
这道题的思维量还是非常高的不过nknknk这波玄学过题确实佩服。。。
我是joker以为这道题转移比较难想最后发现我连计数的对象都没搞清楚
如果不先入为主而是尝试推一下结论的话这道题还是可以分析的吧但是最后那一步凭考场上的我是无论如何也推不出来的
首先最直白的翻译是设SiS_iSi表示覆盖iii位置的区间的集合那么合法的条件等价于SiS_iSi互不相同。
然后有一个结论不存在i1i2j1j2i_1i_2j_1j_2i1i2j1j2使得Si1Sj1≠Si2Sj2S_{i_1}S_{j_1}\ne S_{i_2}S_{j_2}Si1Sj1Si2Sj2
这个结论的正确性其实挺显然的但是当时我没往这方面想而是直接去刚dpdpdp了现在想来确实是不明智的行为
那么我们把相同等价类的位置提出来记作区间[li:ri][l_i:r_i][li:ri]那么这些区间要么包含要么不相交这个结构就非常显而易见了我们可以把原序列划分成若干个连续段同时不存在两个不属于同一个连续段的i,ji,ji,j使得SiSjS_iS_jSiSj。这个性质也等价于什么呢对于询问区间[i:j][i:j][i:j]要么i,ji,ji,j在同一段中要么[i:j][i:j][i:j]不能制造断点也就是说[i:j][i:j][i:j]恰好是若干完整的段拼起来的。
现在我们只差最后一步如何对这些若干不相交的[li:ri][l_i:r_i][li:ri]计数
我竟就倒在了这里。。。
考虑一个普通至极的思路正难则反。也就是说我们减去分出来的段数nnn的方案数。那么我们考虑假设分成了jjj段根据前面的观察我们要把这分出来的jjj段区分出来然后对于长度为lll的一段我们需要注意端点是不能包括在区间中的因此有(l−2)(l−1)2\frac{(l-2)(l-1)}{2}2(l−2)(l−1)个可选择的区间方案数为2(l−2)(l−1)22^{\frac{(l-2)(l-1)}{2}}22(l−2)(l−1)。
有了上述动机我们设dpidp_idpi表示长度为iii的答案有转移式dpi2i(i1)2−∑jidpjfi,jdp_i2^{\frac{i(i1)}{2}}-\sum_{ji}dp_jf_{i,j}dpi22i(i1)−∑jidpjfi,j其中fi,jf_{i,j}fi,j表示把iii分成jjj段的所有方案的系数和。
复杂度O(n3)O(n^3)O(n3)。可以用多项式工业优化到O(npoly(n))O(n\text{poly}(n))O(npoly(n))但是有点复杂并且我不太懂所以就咕了
这就是天才和凡人的差距吗
#includebits/stdc.h
#define inf 0x3f3f3f3f
#define ll long long
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N305;
int n,mod;
ll pw[N*N],dp[N][N],res[N];
void add(ll x,ll y){x(xy)%mod;
}
int main(){cinnmod;pw[0]1;for(int i1;in*n;i)pw[i]pw[i-1]*2%mod;dp[0][0]1;for(int i0;in;i){for(int j0;ji;j){if(dp[i][j]){for(int k1;kn-i;k){add(dp[ik][j1],dp[i][j]*pw[(k-1)*(k-2)/2]);}}}}for(int i1;in;i){res[i]pw[i*(i1)/2];for(int j1;ji;j){res[i](res[i]-res[j]*dp[i][j])%mod;}}cout(res[n]mod)%mod;
}青鱼和游戏
考场上爆蛋了
这题爆蛋有两个原因一是确实不会做二是t3t3t3确实被卡住了
说白了就是太菜了
