题目大意： 不吉利的数字为所有含有4或62的号码 输入的都是整数对n、m（0<n≤m<100000000000），如果遇到都是0的整数对，则输入结束。 对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。 分析： 数位DP的模版题: 定义： f[i][0]表示i位数中吉利数字且末尾非6的个数 f[i][1]表示i位数中末尾为6的吉利数字的个数（因为它再加一个2就为不吉利的数字了 ） f[i][2]表示i位数中不吉利数字的个数 初始化： for(int i=1;i<=12;i++){ f[i][0]=9*f[i-1]...

分析： 用sumw[i]记录∑ij=1w[j]∑j=1iw[j]维护前缀和 用sumd[i]记录∑i−1j=1d[j]∑j=1i−1d[j]维护前缀和 Cost[i]表示将第一个锯木厂建在i的位置时，1~i第一段的木材运到i的费用： Cost[i]=Cost[i-1]+sumw[i-1]*d[i-1] 接着就可以用列出状态转移方程，设f[i]表示第二个锯木厂建在i时的费用 f[i]=min{ Cost[j]- sumw[j] (sumd[i]-sumd[j])- sumw[i] (sumd[n+1]-sumd[i]) } 令 y=sumw[j]*sumd[j] ，x=sumw[j] ...

很容易想到（n^3）的DP： 定义：f[i][j]表示前j个数构成的以j为结尾的数列中，长度为i的严格递增子序列的个数。 for(int i=1;i<=m;i++) for(int j=i;j<=n;j++) for(int k=0;k<j;k++) if(a[k]<a[j]) f[i][j]=(f[i][j]+f[i-1][k])%mod; int ans=0; for(int i=1;i<=n;i++) ans=(ans+f[m][i])%mod; 下面我们来想该怎样优化:...

首先通过dfs求出每个节点的时间戳，即第一次访问该节点的时间，将时间戳按照从小到大的顺序进行排序，并用ans累计相邻两节点的路径长度，可以发现所求的答案为ans/2 运用set记录当前出现的异象石，当询问和删除时，就很容易找到它左边的和右边的异象石 设d[i]为从i到跟节点的距离，用差分的思想，从i到j的路径的长度dis(i,j)=di+dj-2*d lca(i,j) 当插入节点x时，找到x左边和右边的节点l，r（注意边界的情况）ans减去dis(l,r)再加上dis(l,x)+dis(x,r) 删除时思路也一样只是先加再减 对于询问输出ans/2 代码 #include<bi...

#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre&quot...

int 注：”较“的原则：加法不爆。 极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80 long long 注：”较“的原则：加法不爆。 极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80 double 注：”较“的原则：保证一定位精度。 极大值：0x7f 较大值：0x43 较小值：0xc2 极小值：0xfe float （这个有用吗） 注：”较“的原则：保证一定位精度。 极大值：0x7f 较大值：0x4f 较小值：0xce 极小值：0xfe ```cpp#include <cstdio>#i...