ww3113306

摘要： 最近在写DP，今天把最近写的都放上来好了,,, 题意：给定两个正整数a和b，求在[a,b]中的所有整数中，每个数码(digit)各出现了多少次。 首先询问的是一个区间，显然是要分别求出1 ~ r ,1 ~ l的答案，然后相减得到最终答案 首先我们观察到，产生答案的区间是连续的，且可以被拆分， 也就是 阅读全文

摘要： 表示调这题调到失智了，，，调了好久发现是因为DP的方向反了。。。 首先我们观察到虽然动物和小朋友数量都很多，但是每个小朋友可以看到的动物只有连续的5个！ 因此我们考虑状压，2^5还是可以承受的。 再观察到因为是连续的5个，所以对于任意一段以i为开头的区间而言，区间都是已经被固定了的。 因此对于每个区 阅读全文

摘要： 做了好久。。。。 大致思路： 求出前k大的方格之和即为答案， 先考虑一维的情况，设f[i]为数位上各个数相乘为i的数的总数，也就是对于数i,有f[i]个数它们各个位相乘为i， 再拓展到二维，根据乘法原理（貌似是这个原理吧），方格(i , j)的金块数就是f[i] * f[j], 所以先数位DP求出f 阅读全文

摘要： 深感人类智慧的伟大啊，，， 第一次看这题简直毫无头绪， 其实状态设出来了，往下推就顺理成章了。 f[i][j][k]表示到第i位，选了j段，第i位有没有选（k）的最大子段和， 然后考虑用人类智慧暴力推倒所有情况的转移方程， f[i][1][1]:因为要取第i位，又只有一段，所以要么接这上一段来，要么 阅读全文

摘要： 大概内容是要维护一个数组，支持如下操作： 查询某个位置上的数 修改某个位置上的数 回到某个版本的数组（可持久化） 预备知识：平衡树（非必要，了解最好），主席树 为了维护这个结构，我们可以考虑使用主席树， 建树的时候按照下标来建（维护下标），此处类似于平衡树 要查询指定位置就按照找第k大，同样类似于平 阅读全文

摘要： 其实是一道性质题。 首先观察到插入的数是递增的， 那么根据上升子序列的性质， 我们的非法情况就是统计到了在一个数前面的后插入的数， 但是由于插入的数是递增的，显然插入这个数后，这个数就是最大的，所以除了它自己，不会有任何数统计到它， 也就是说，插入一个数时，因为它后面的数都比它小，所以不会对后面DP 阅读全文

摘要： 发现最近好少写博客啊（其实是各种摆去了） 更一点吧 这道题要求最小化均方差，其实凭直觉来说就是要使每个块分的比较均匀一点，但是单单想到想到这些还是不够的， 首先f[i][j][k][l][t]表示以(i,j)为左上角，(k,l)为右下角，一共分割的t次的矩形的最小xx， 其中xx是某个与最小均方差挂 阅读全文

摘要： 写了好久。。。。刚刚调了一个小时各种对拍，，，，最后发现是多写了一个等号，，，，内心拒绝表示一开始看真的是各种懵逼啊在偷听到某位大佬说的从高位开始贪心后发现可做首先考虑小数据(因为可以乱搞）所以先从高位开始枚举位数:for(int k=all; k ;k--)ans表示当前答案，f[i][j]表示d 阅读全文

摘要： （感觉洛谷上题面那一小段中文根本看不懂啊，好多条件都没讲，直接就是安装也要一个时间啊，，，明明不止啊！还好有百度翻译。。。。。。）题意：一棵树，一开始在1号节点（root），边权都为1，每个点有点权，要最小化max(点权+到达时间） < 所有点的首先这看起来就是一道DP题，但是根据直觉，，，应该跟贪 阅读全文

摘要： 第一次写这种二分来优化决策单调性的问题。。。。 调了好久，，，各种细节问题 显然有DP方程： $f[i]=min(f[j] + qpow(abs(sum[i] - sum[j] - L - 1)));$ 其中f[i]代表到了第i个句子的最小答案 qpow用于处理^p sum为前缀和 （同时为了处理句 阅读全文