@poorpool
2017-10-05T13:06:04.000000Z
字数 3063
阅读 920
%%%zhx
(钟大爷血虐全场)
(笔者很糊,仅供借鉴)
60分:
(钟大爷:掉陷阱里了)
100分:
等价于的有几个方案,(c认为是倍数,即,。可以钦定然后轮换。
发现,
,
复杂度:
第一行最多
第二重。
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n, ans=0, v, tmp=0;
int main(){
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
scanf("%lld", &n);
//我们已经钦定a<=b<=c
for(ll a=1; a*a*a<=n; a++)
for(ll b=a+1; a*b*b<=n; b++)
tmp += n/(a*b) - b;//这里,a*b*c<=n,c<=n/(a*b),但我们钦定了c>=b,所以减去
ans += tmp * 6;
tmp = 0;
for(ll a=1; a*a<=n; a++){
tmp += n/(a*a);
if(a*a<=n/a) tmp--;//三个一样的情况
}
ans += tmp * 3;
for(ll a=1; a*a*a<=n; a++)
++ans;
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
怎样自动调整long long占位符
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
倍增求lca。
策略:
1. 向对面走
2. 抢子树,占一条边
3. 慢慢走
可以求出每人走的步数。
事实上,总有至少一个人在从下往上爬。
算出它们到lca的距离就知道是哪个人了。
全员0分。
可调整中间四包玄学值。
dp。
1. 考虑卡包卡包距离
2. 考虑玄学值玄学值距离
f[i][n1][n2][n3][n4][b1][b2][b3][b4]
i:已经考虑掉了1~i的玄学值
n1234对应卡包,指每个卡包分别使用了n1234个玄学值,他们都在[0,5]间。
b1234指是否有i这个玄学值。
大小30*5^4*2^4。
转移:
考虑四包卡要不要放进去i+1这个玄学值
(九层循环23333)
(笔者已经疯了,上面都是瞎写的)
(钟大爷高二写的%%%)
例题:乌龟棋
必须掌握:
知道且会写:
能将一棵树变成一个序列。
每颗子树变成一个区间。
对一颗子树求和,就变成了对区间求和。
正号换成左括号,负号换成右括号,即为一个合法的括号序列。
不属于136的,全部正负相消了。
把树上链的点权和,变成了区间和,但要求链为从上往下一条链,可不敢转弯。
转弯咋办?lca处拆开,分成两条链。
原来是随便选一堆并到另一堆,现在是每次选小的一堆并到大的一堆。
n2->nlogn
今有元素:1 3 2 4
不断push:
1
1 3
1 3 2
不满足单调性,则不断删除队尾元素,直到可以满足单调。
应用:滑动窗口
N个数,给定K。问各长度为K的子区间中最小值?
把k个数都往里插,插完了,则第一个元素必为最小的。
已研究了[1, k],怎样求[2, k+1]?
他们只差两个数,即删一个数,加一个数。
如果删的是原来最小值,则必定在第一个,删了就好。
如果删的不是,则他早被删了。
(请思考2 3 1 4与1 3 2 4, 其中k=3这两组数据以理解)
n个数,平均值最大的子区间?请说出这个平均值。
范围1e5。
玄学解法:就是里头的最大值。
n个数,求min(ai...aj)*(|i-j|+1)最大?(区间最小值乘区间长度最大)
范围十万。
正统做法:现找出一个区间内的最小值。如果包含它,则为它乘全长;不包含则划为两部分分治。
这就是笛卡儿树。
线段树找出区间内的最小值。
n个数,求min(ai, aj)*|i-j|最大?
范围十万。
正统做法:枚举ai,在他右边找最后一个比他大的数。
可以二分一个长度,后缀最大值。(笔者不大明白)
线性做法:
两头砍最小的,不砍断就行。
(据说证明很麻烦)
给定n个数,要求对于所有的子区间求出其中位数。
正统做法:枚举l,创建链表,把r从右往左移,链表维护,每次删一个数。
删的大于中位数,中位数向前走,删的小于中位数,中位数向后走。
N行N列的点阵, k个特殊点 (xi,yi)
安全性 w(a,b)=min(|a-xi|+|b-yi|)
求一条从 (1,1) 到 (n,n) 的路径,使路径上安全性的最小值最大。
要求平方算法。
(凡是出现最小值的最大、最大值的最小,都要立刻想到二分,不过不一定用罢了)
正统做法:先删去所有点,安全值从大到小加点,并查集维护。倘若起点终点在一个集合了(联通了),当前安全值 即答案。(依然不大明白)
例题:饮水入城
给定两个序列A、B。
求一个最大的子区间满足这段区间的A的区间和除以(实数除)B的区间和最大。
这是分数规划问题,它的一般做法是二分答案。
正统做法:二分出一个答案m,是否有a[l,r]/b[l,r]>=m?它等价于a[l,r]-m*b[l,r]>=0.令c[i]=a[i]-m*b[i],询问c[l,r]>=0成立吗,等价于是否存在c[i]>=0(即是否存在a[i]-m*b[i]>=0,即你要求一个i使a[i]/b[i]最大)。
因为是实数二分,终止条件就是二分了多少次,三十次五十次之类的。
给一棵大小为N的树
换根
修改点权
查询子树最小值
N<=10,000
正统解法:只有新根到原根的路径上的点所对应的子树才会发生变化。路径上的点,有一个儿子变爸爸,爸爸变儿子。即:从新根过来的都不是它子树结点。去掉这一部分dfs序上的区间,剩下的两个区间就都是其子树结点。
从1换到3换到5和1换到5一样的。
bzoj树上三角形
n个点树,每个点有权。m次询问,每次给p1和p2,问你p1到p2的路径是否存在三个点点权,使得这三个数能作为三角形三边长?
a+b>c,这是能组成的情况。
a+b<=c,这是不能。
极限情况是a+b=c。
斐波那契数列即为这种情况。
1,1,2,3,5,8,13...即为极限情况。
因为fibonacci在四十几位就爆int了,所以,倘若两点的距离大于四十几就yes,否则瞎暴力也过掉了。
BZOJ
2962 2096 2375 3333 2529 2441 3306
HDU
4467 1394 3333 3340
CC
DEC13 QTREE6
CC MLCHEF
Tsinsen
D7040