一些题目

最近颓了很久……
还是给出一些题目(或许有做法)来做些笔记吧……
省选之前这状态目测要滚粗了……
(点开本日志,你将 不可避免地看到,project euler、不知从哪里弄来的省选模拟题、srm level3、cf某些题的题解)

project euler 389

https://projecteuler.net/problem=389
傻逼题的典范……
概率生成函数的基本应用
设五个多项式为……A(x),B(x),C(x),D(x),E(x)





接下来只要求出A(B(C(D(E(X)))))的系数……
就可以随便弄出方差了
多项式次数不高……多项式乘法直接暴力即可……不需要fft(你有fft模板也没人拦你)
精度的话,c++的double就够用了……
开o2后跑一会就能出解了……
解是2406376.3623

一些省选模拟题

时限2s
内存256M


如果x很小,我们可以做背包,问题在于x比较大……那么这个时候就只有暴搜了……bfs+去重就可以过了
复杂度不会估计
如果有更靠谱的方法……请告诉我!

时限2s
内存256M
dp……
dp[i][j]表示区间(-INF,i】已经挖好,并且坐标i挖下去的深度为j的最大收益(收益为得分-成本)
那么有dp[i][0]=max(dp[i-1][0],dp[i-1][1])
dp[i][j]=max(dp[i-1][j-1],dp[i-1][j],dp[j-1][j+1])+get[i][j]-j(get[i][j]为在点(i,j)的财宝价值之和减去j是往下挖j单位的代价)
然后有了这些方程……再弄点细节的东西就可以了……
最终的复杂度是O((max(x)-min(x))(max(y)-min(y)))……也就是说O(2*10^8)是可以过的……
说不定有O(n
(max(y)-min(y)))的做法……我没有仔细想

时限3s
内存256M
一般这种题目就是分层图……不过因为是交换权值……所以不好搞……

我们注意一些性质……首先我们最后的答案路径……里面被换走的边一定是权值比较大的边被换成了权值比较小的……来自路径外的边……

所以就有一个框架……把边排序之后……
我们枚举一个m,表示s->t的路径里面在交换后,一定要使用前m小的边权值被换到这条路径里面……求出在这个条件下到达t的最短距离。
那么f[i][j][k]表示已经使用了前j小的边,发生了k此边的交换到达i的最短距离……
因为这是一个图……所以不好dp……只能跑spfa之类的来松弛……
假设目前的状态为(i,j,k),枚举到一条边e:i->v,权值为w
设第x小的边的边权为weight[x]
如果e的权值大于第m小边的边权……
那么可以这样松弛f[v][j][k]=min(f[i][j][k]+w,f[v][j][k])……这个不解释
以及f[v][j+1][k+1]=min(f[i][j][k]+weight[j+1],f[v][j+1][k+1])……这就表示我们把第j+1条边的边权和当前边e的权值交换了……

然后如果e的权值小于等于第m小边的边权……
那么可以松弛的状态只有f[v][j+1][k]=min(f[i][j][k]+weight[j+1],f[v][j+1][k])……
这个解释稍微麻烦一些……就是说我们把e这条边和第j+1小的边的边权交换……但是之所以松弛的状态的交换次数依旧是k……是因为这次交换其实是不必要的,最后一定有条边的权值替换为了e的权值,设它为t,那么我们就相当于将e的权值和第j+1小的边的边权交换,然后将第j+1小的边的当前边权(e之前的边权)和t交换……这需要两次,但是实际上只需要1次,所以交换次数依旧是k而不是k+1


傻叉题的典范……拓扑排序最小字典序……和最大字典序……
不多讲了……

cf193D

tsinsen上有翻译……线段树的不显然的题……
还是比较好的……一时没有想出来……总之就是想个O(n^2)的然后优化到O(nlgn)就是了……
题解看集训队作业吧……我也不一定能讲明白

cf40E

同上……tsinsen上有翻译
0≤k<max(n,m)保证一定有一行或一列都是空的……
然后就可以开始乱搞了……
没啥好说的

srm576level3

实际上就是乱搞题的典范……
关键在于generator的长度是多少
给出的片段有两种可能……每个字符都来自generator的不同位置
或这有些字符来自generator的同一位置,这时候的长度一定是某两个位置标号之差的约数
分两种情况做就可以了……
分解质因数+乱搞

还有一些题目……下次再贴好了

Comments

comments powered by Disqus