chenzhizhen2020

分类

未归档(2) 题解(5)

/ 注册

全部文章（共7篇）

数位DP Code1119【不要62】

题目大意：不吉利的数字为所有含有4或62的号码输入的都是整数对n、m（0<n≤m<100000000000），如果遇到都是0的整数对，则输入结束。对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。分析：数位DP的模版题: 定义： f[i][0...

2019-10-17

4 702

斜率优化DP P4360【锯木厂选址】

分析：用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...

2019-10-17

0 596

UVA12983The Battle of Chibi

很容易想到（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++) ...

2019-10-17

0 645

lca异象石

首先通过dfs求出每个节点的时间戳，即第一次访问该节点的时间，将时间戳按照从小到大的顺序进行排序，并用ans累计相邻两节点的路径长度，可以发现所求的答案为ans/2 运用set记录当前出现的异象石，当询问和删除时，就很容易找到它左边的和右边的异象石设d[i]为从i到跟节点的距离，用差分的思想，从i...

2019-10-17

0 1228

专业防卡常

#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize(...

2019-10-17

0 466

关于memset

int 注：”较“的原则：加法不爆。极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80 long long 注：”较“的原则：加法不爆。极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80 double 注：”较“的原则：保证一定位精...

2019-10-17

0 1438

DP+set+倍增P1081【开车旅行】

预备知识——关于set的用法定义：set<int>s;</int> 本题需要用到的几个函数: s.insert(x);//插入x s.lower_bound(x);//查找**大于等于**x的最小元素，返回迭代器 s.upper_bound(x);//查找**大于**x的最...

2019-09-24

2 2295