10/13
明天开始的三天
就要跟历史地理化学说拜拜了
以诚待之
好运
10/20
P三角形计数：一看就是叉积。因为去年迪子讲过。但是我已经忘记了。所以重新写了一遍。把所有的点有序化，将三角形面积转化为两个的叉积。因为要把绝对值去掉，所以每次都要做一遍快排。Then，不难发现它们具有前缀和性质。就可以敲起来了。
bzoj4557侦察守卫：R老师讲的时候没听懂。。百度题解发现了很精妙的写法。。想法差不多RT了。。。
#include<cstdio>
#include<algorithm>
#define N 1000010
#define inf 1000000000
using namespace std;
][],f[][];
void add(int u,int v){
edgenum++;vet[edgenum]=v;next[edgenum]=head[u];head[u]=edgenum;
}
void dfs(int u,int ff){
g[u][D+]=inf;
)f[u][]=g[u][]=cost[u];
;i<=D;i++)g[u][i]=cost[u];
int e=head[u];
){
int v=vet[e];
if(v!=ff){
dfs(v,u);
;j--)
g[u][j]=min(g[u][j+],min(g[u][j]+f[v][j],g[v][j+]+f[u][j+]));
f[u][]=g[u][];
;j<=D+;j++){
f[u][j]=min(f[u][j-],f[u][j]+f[v][j-]);
}
}
e=next[e];
}
}
int main()
{
scanf("%d%d",&n,&D);
;i<=n;i++)scanf("%d",&cost[i]);
scanf("%d",&M);
;i<=M;i++)scanf(;
;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(,);
printf(][]);
}
bzoj4557
10/21
最近要干的活好多啊。。。。
P字符消除：hash+定理。今天太忙了，题解以后补。
初赛球rp++
百度了一下主定理：
/////以上格式被吞了。。。QAQ
观察到数据随机
因此操作3的期望次数是100000/3次，每次询问长度的期望是|S|/6
事实上直接暴力仅仅需要5s就能出解。
时限有2s。
考虑压位，对于每64个分为一组。
(0,0)(0,1)(1,0)(1,1)
这些都可以通过位运算来解决。
常数很小，可以在2s内出解。
假设已经知道原数列，那么将该数列排序，一定是从前往后第i个与从后往前第i个分为一组，总共n/2组，考虑dp，dp[i][j][k]表示已经到第i个，从前往后第i个数为j,从后往前第i个数为k，转移可以从dp[i-1][j-x][k+y]中转移得到，其中x,y>=0，可以通过前缀和做到2000^3，注意到很多j,k其实是不可能成为答案的，能够有机会作为状态的只有2000lg(2000)对数，因此复杂度可以降为2000^2lg(2000)。
假设左边有n个数，右边有n个数，那么可能的完备匹配有n!种，n^2条边可能对答案都有(n-1)!次贡献。
观察到k<=20，考虑容斥，即每条不见的边是否被选进答案里。
那么总答案为Σans*(-1)^t，其中t为我选择的边的条数。ans为当前已知存在的边集的情况下的答案。
完备匹配的个数和价值总和的做法类似。
XJOJ上面的比赛早上没有看到。。。下午登陆了一下居然被人冒充了。。。。>_<心情复杂。
T1string：考虑所有有k处不同字符串组成的trie，统计T之前有几个。逐位操作，对于第i位，k表示还需要k位不同的。每次走T的字符串，分情况讨论：c<T[i],c!=Str[i]，C(n-i,k-1)*25^(k-1);c<T[i],c=Str[i],C(n-i,k)*25^k;最后整个T走完了ans++；PS:数据有点弱的。奇错无比的程序可以拿20分~
T2跑跑步：可以发现（不要问我为什么发现），对于i同学所有可以走到的点，一定是gcd（a[i],n）的倍数。枚举所有n的约数d，如果d是某个gcd(a[i],n)的倍数，说明i这个人一定可以跑跑跑跑到d*K所有位置（K为任意整数∈【0，n/d】）。但是个别d*K的位置可能会被重复算，所以只保留phi（n/d）个，剩下的之后肯定可以算到了~——%%%数论之神shy
T3tree：突然发现最近做的题目中树形DP多了起来。。隐隐有种flag的预感<。)#)))≦自己先设计了一个状态，只能想到f[i][j]表示以i为根，最多取j个选择点，只能做到O（nlim^2）。。。题解中给出的状态是f[i][j]表示在当前“已经结束dfs的结点中”选择j个的最优效益，f[i][j]=max{f[i][j],f[v][j-1]+value[v]};(这下真的很精妙！！！学习了），另外看到C_SUNSHINE等人用到了题解之中第二种方法，看不懂。
bzoj2687:《交与并》。写道题像跳了个大坑。sorry to orzliyicheng....N次提交wa飞....。这道题总体可以分为三个步骤：发现答案必然是两个区间的并*交；将包含与非包含关系的操作分开来求；单调队列。有两个参数不好G（），我傻逼地以为不维护队尾也是可以的，结果为submit贡献了一堆分母。包含过程中，二分查找包含它的最大区间；至于非包含，神奇的证明它具有决策单调性，DPDP一下！
10/31（继续更交与并
要赶紧更这道题。。。因为YD现在要去卡时了QAQ。。。我马上就要time垫底了QAQ。。。
整个机房里四个人的做法包揽了全场倒5.。。。。。excited。。。。我们就是这么拽。。。
翻一番orzliyicheng的提交记录可以发现惨不忍睹，我经历了一个从sb不维护队尾的单调队列->sb二分求包含答案->类似分治求g函数的痛苦过程。。。。几次想放弃掉了
因为网上只有一篇题解而且比较高 妙，我很佩服他们YY的这些方法。。。。%%%ywn0726，and，这道题有以下两个结论：
1.两个区间必然是答案
2.转移具有单调性
（嘴巴选手依旧不会证明，嘴巴也不会证明