清北学堂金秋营 day2

%%%zhx

题解

（钟大爷血虐全场）
（笔者很糊，仅供借鉴）

T1

60分：

• 打表
• 枚举a和b

（钟大爷：掉陷阱里了）

100分：

等价于$\ a×b×c<=n$的有几个方案，（c认为是倍数，即$\ a×b=i$，$\ c=\frac{i}{a×b}$。可以钦定$\ a≤b≤c$然后轮换。
发现$\ a≤\sqrt[3]{n}$，
$\ a+1≤b≤\sqrt{n}$，
$\ b+1≤c≤\lfloor\frac{n}{a×b}\rfloor$

复杂度：

第一行最多$\ \sqrt[3]{n}$
第二重$\ \sqrt{n}$。
$\ O(n^{\frac{5}{6}})$

#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

T2

倍增求lca。
策略：
1. 向对面走
2. 抢子树，占一条边
3. 慢慢走
可以求出每人走的步数。
事实上，总有至少一个人在从下往上爬。
算出它们到lca的距离就知道是哪个人了。

T3

全员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）
（笔者已经疯了，上面都是瞎写的）
（钟大爷高二写的%%%）

例题：乌龟棋

数据结构

必须掌握：

• 数组、链表
• 队列、栈
• 堆
• 并查集

知道且会写：

• 树状数组、线段树选一个
  （可参考notonlysuccess线段树完全版，照着学学）
• 树
• 树上lca（倍增，tarjan）
• dfs序列、括号序列
• 启发式合并
• 单调队列
• 前缀和
• 二分
• 分治

dfs序列

能将一棵树变成一个序列。
每颗子树变成一个区间。
对一颗子树求和，就变成了对区间求和。

括号序列

正号换成左括号，负号换成右括号，即为一个合法的括号序列。

不属于136的，全部正负相消了。
把树上链的点权和，变成了区间和，但要求链为从上往下一条链，可不敢转弯。
转弯咋办？lca处拆开，分成两条链。

启发式合并

原来是随便选一堆并到另一堆，现在是每次选小的一堆并到大的一堆。
n2->nlogn

单调队列

今有元素：1 3 2 4
不断push：
1
1 3
1 3 2
不满足单调性，则不断删除队尾元素，直到可以满足单调。
应用：滑动窗口

滑动窗口(sliding window)

N个数，给定K。问各长度为K的子区间中最小值？
把k个数都往里插，插完了，则第一个元素必为最小的。
已研究了[1, k]，怎样求[2, k+1]?
他们只差两个数，即删一个数，加一个数。
如果删的是原来最小值，则必定在第一个，删了就好。
如果删的不是，则他早被删了。
（请思考2 3 1 4与1 3 2 4， 其中k=3这两组数据以理解）

一些问题

problem -5

n个数，平均值最大的子区间？请说出这个平均值。
范围1e5。
玄学解法：就是里头的最大值。

problem -4

n个数，求min(ai...aj)*(|i-j|+1)最大？（区间最小值乘区间长度最大）
范围十万。
正统做法：现找出一个区间内的最小值。如果包含它，则为它乘全长；不包含则划为两部分分治。
这就是笛卡儿树。
线段树找出区间内的最小值。

problem -3

n个数，求min(ai, aj)*|i-j|最大？
范围十万。
正统做法：枚举ai，在他右边找最后一个比他大的数。
可以二分一个长度，后缀最大值。（笔者不大明白）
线性做法：

两头砍最小的，不砍断就行。
（据说证明很麻烦）

problem -2

给定n个数,要求对于所有的子区间求出其中位数。
正统做法：枚举l，创建链表，把r从右往左移，链表维护，每次删一个数。
删的大于中位数，中位数向前走，删的小于中位数，中位数向后走。

problem -1

N行N列的点阵， k个特殊点 (xi,yi)
安全性 w(a,b)=min(|a-xi|+|b-yi|)
求一条从 (1,1) 到 (n,n) 的路径，使路径上安全性的最小值最大。
要求平方算法。
（凡是出现最小值的最大、最大值的最小，都要立刻想到二分，不过不一定用罢了）
正统做法：先删去所有点，安全值从大到小加点，并查集维护。倘若起点终点在一个集合了（联通了），当前安全值 即答案。（依然不大明白）
例题：饮水入城

problem 0

给定两个序列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]最大）。
因为是实数二分，终止条件就是二分了多少次，三十次五十次之类的。

problem 12

给一棵大小为N的树
换根
修改点权
查询子树最小值
N<=10,000
正统解法：只有新根到原根的路径上的点所对应的子树才会发生变化。路径上的点，有一个儿子变爸爸，爸爸变儿子。即：从新根过来的都不是它子树结点。去掉这一部分dfs序上的区间，剩下的两个区间就都是其子树结点。
从1换到3换到5和1换到5一样的。

problem x

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