这段时间比较忙，现在有时间写一写博客了。。
最近参加的比赛：
1.bupt2018归队赛
2.bupt2018新生赛
3.cccc2018天梯赛
4.bupt2018校赛(预选+复赛)
并且围观了在PKU举办的World Final，可惜与tourist擦肩而过。。。

1.归队赛：
做了两个签到水题，然后其他的都不会。。然后死了。。题我现在也记不清了。。
2.新生赛：
全是水题，然而还是有好多没做出来。。题我也记不清了。。似乎保密？
3.cccc2018
我感觉三等奖的锅不能我背啊！

我我我。我是队内rank1啊(虽然就比fqk大佬高1分)。可能还是我不够强。。
最后三题分别是：巨大模拟，乱搞计算几何，未知算法(依然不会)然后
计算几何可以说一下，里面的思想很好
题意：
给出平面上n个点，要求找出三个点构成三角形，三角形面积最小。n< =2000
直接暴力是n^3的。。显然不行
我们尝试枚举两个点。。然后找第三个，还是不好做。。
这时候引入一个思路：枚举一个点，以这个点为原点，题意就变成找到另外两个点，与原点构成的三角形面积最小。
这有什么好处呢：用叉积表示三角形面积异常简洁：abs(x1*y2-y1*x2)
我们想要答案最小，就是找到x1*y2-y1*x2的最小值。
想要找到x1*y2-y1*x2最小，就是让x1*y2-y1*x2最接近。
那么我们以x1*y2-y1*x2为判断标准排序就行啦！！这样排序算法会让两个x1*y2-x2*y1接近的点自然排在一起，然后只要计算相邻的就行啦！
这里一个换原点简化计算的思想，一个排序找相邻的思想，一定要记住。
代码:

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<map>
#include<string>
using namespace std;
const int N=6000;
struct pos
{
	long long x,y;
}s[N],t[N];
int n; 
bool cmp(pos a,pos b)
{
	return (a.x*b.y)< (a.y*b.x);
}
long long calc(int a,int b)
{
	long long x1=t[a].x,y1=t[a].y;
	long long x2=t[b].x,y2=t[b].y;
	return abs(x1*y2-y1*x2);
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld%lld",&s[i].x,&s[i].y);
	}
	long long ans=(1LL<&lt;62);
	for(int i=1;i<=n;i++)
	{
		memset(t,0,sizeof t);
		int p=0;
		for(int j=1;j<=n;j++)
		{
			if(i==j){continue;}
			t[++p].x=s[j].x-s[i].x;
			t[p].y=s[j].y-s[i].y;
		}
		sort(t+1,t+n,cmp);
		for(int j=2;j<n;j++)
		{
			ans=min(ans,calc(j,j-1));
		}
	}
	printf("%.3lf",ans*0.5);
	return 0;
}

还有一个未解决的字符串题。。贴在这里：
给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3 个字符，结果可能有多少种不同的字符串？n< =10^6

已经解决！
感谢@ypxrain大佬
f[i][j]表示前i个删了j个的答案。
如果没有重复的字母，则f[i][j]=f[i-1][j]+f[i-1][j-1]
考虑重复的字母，对答案造成影响的只有aa,a*a,a**a这三种。*代表任意字符。
如果是aa这样的，说明删这两个a实质上是一样的，这样一对字符使得答案被多算了f[i-2][j-1]次，就减去f[i-2][j-1]
如果是a*a，这样的会使得答案被多算f[i-3][j-2]次。
同理a**a会使得答案被多算f[i-4][j-3]次。
然后就没了，注意开long long。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000005;
long long f[N][4];
char s[N];
int main()
{
	scanf("%s",s+1);
	int len=strlen(s+1);
	f[0][0]=1;
	for(int i=1;i< =len;i++)
	{
		f[i][0]=1;
		for(int j=1;j<=3;j++)
		{
			f[i][j]=f[i-1][j]+f[i-1][j-1];
			if(s[i-1]==s[i])f[i][j]-=f[i-2][j-1];
			if(j>=2)
			{
				if(i>2&&s[i]==s[i-2]&&s[i]!=s[i-1])f[i][j]-=f[i-3][j-2];
			}
			if(j>=3)
			{
				if(i>3&&s[i]==s[i-3]&&s[i]!=s[i-1]&&s[i]!=s[i-2])f[i][j]--;
			}
		}
	}
	cout< <f[len][0]+f[len][1]+f[len][2]+f[len][3]<<endl;
	return 0;
}

然后是我们学校的校赛。。惨死。
我和另外两位大一种子选手参赛，预选赛被吊起来打，我写的题忘了取mod到死都没发现。。
预赛遇到一个有意思的题：
给一棵树，树的每个点有点权边权，定义从A到B距离为A点点权乘以AB间路径的边权和。求一个点P，要求其他所有点到这个点的距离和最小。
百度树的重心有真相。。
在树上找个带权重心，就是答案了。。。
代码找不到了。。。
然后是正赛。。我上来SB了，卡在水题上半天，然后就心态崩了。。不过后来A了四个题(队友NB)。。然后我们三个人卡在一个D题上好久。。最后5题滚粗。。
总结一下，应该在卡题时立马换题。事实上剩下的题并不是特别难，都是可做的，尤其是A题，就是个水DP，最后一紧张也没想出来。。
记录一下：
D：
统计有多少个区间，区间中相同数值的数字出现次数最多的出现次数大于等于k。
队友写了一个神奇算法。。
正解是利用区间的单调性。对于固定的k值来说，我们预处理出每个位置i向后数k个与a[i]数值相同的数的位置。
然后从后往前扫， f[i]=min(f[i],f[i+1]),i位置对答案的贡献是n-f[i]+1
因为左边固定，右边单调，所以不会重复算。
A:
给两个序列A,B，求k重最长公共子序列。 K重最长公共子序列S需要满足:
1)S是A和B的最长公共子序列。
2)S的长度为T * K。
3)S序列从头开始每k个元素分成一组，每组内元素的值相同。
这就是个水DP。。。
类比最长公共子序列 f[i][j]表示A串匹配到了i，B串匹配到了j的答案。
f[i][j]=f[p][q]+1 其中a[p]==b[q] 且满足转移条件
这里维护两个数组pa[i] pb[i]，分别记录a串中向前数k个与a[i]相同的字母的位置 pb同理。
然后f[i][j]=max(f[i][j],f[pa[i]-1][pb[j]-1]+1 即可。。
当时脑抽偏要把k放进状态表示里。。
代码不见了。。。
B
对于给定的长度为n的序列s，求(任意两段不相交的子段的最大值)的和对109 + 7取模的结果。(括号消歧义)
又是一个考思想的题。
我们注意到，对于序列的最大值x而言，只要是包含他的区间，最大值一定是他。
所以最大值在答案中出现了t*x次，t是选取这两个区间的方案数。
所以最后答案肯定是一个 t1*a[1]+t2*a[2]+t3*a[3]…tn*a[n]这样的
我们从这里得到启发，转而计算每个数字在答案中的出现次数t。
为了方便计算，我们把数字从大到小排列，由最大值开始向区间内插入。
插入几个数字后，整个[1,n]区间会被这几个数字划分成几个区间，这些区间中间的数都还没有被插入。
考虑新插入一个数a[i] 这个数字必定出现在某两个之前插入的数字之间(或者在整个[1,n]的最左侧或者最右侧)
设这两个数字为a[l]和a[r]，我们的a[i]就在区间[l,r]之间。
对于[l,r]这个区间中，找两个子区间，只要两个区间之中存在包含a[i]的区间，答案就是a[i]，所以我们可以用组合数学计算一下有多少组满足条件。
对于跨越l或者跨越r的区间，答案一定不是a[i]，因为a[l]和a[r]大于a[i]
然后考虑一个区间在[l,r]内且包含a[i]，另一个区间在[l,r]之外，但是不含已经插入的数。
这里我们用一个tot变量维护一下这种情况下的答案就行，每次插入数字时tot会减小。
至此，对于a[i]的ti就计算完了。然后插入下一个数字，再计算。
用一个set或者平衡树维护插入的过程即可。
（代码没写）
F
给若干木板，给出每个木板的初始高度，有m次机会将任意一个木板高度++，求解最高水位 n< =10^7 保证数据随机。
这题卡O(nlogn)的算法，必须用O(n)
首先我们知道快排完了之后贪心选一定是最优的。
用一个叫线性选择的东西在O(n)范围内完成这个贪心选的过程。
首先在区间[1,n]里我们选定一个数a[q]，然后像快排一样把比a[q]小的放左边，大的放右边。
然后判定a[q]左边是否能够提升到a[q]，如果能，则提升，并处理[q+1,n]，如果不能，则处理[1,q]。
说白了其实是快排只做一半，因为数据随机，复杂度可以证明(瞎猜)为期望O(n)
（口胡一下：如果每次选中间，则是O(n)+O(n/2)+O(n/4)+…+O(n/2^k) 大概是O(2*n) 如果每次不选中间。。不会了。。）
（代码写了，太丑不贴了）

K
题目：给一纯电阻电路，给出每个电阻的最大电流，求解最大功率。
这题好像BZOJ有原题，只要给定一个电压，高斯消元算出每个电阻的电流，然后看哪个电阻限制功率即可。
具体的，用电流上限除以算出来的电流，越小的限制越强，所以找最小的把他电流提到最大就行！
代码没写
感谢队友带我躺！
然后就是愉快的WF啦！
本来Yts神犇说带我们坐车去，后来商量了一下还是坐地铁去的。
到了PKU看到了TZG，一起进去找了个地方坐下开始看比赛。
比赛开始之前疯狂寻找tourist，看某群里拍到的照片感觉就在附近，然后没找到QAQ。
然后就开始了，然而没有题。。想去找人借，都是老外也不太好意思。好不容易找到一个毛子，发现他也没有完整的。。。
不出意外ITMO交了第一个题，然而评测极慢。。突然bupt也交题了。。然后秒WA。。。
然后大家纷纷交题。。bupt再没交过。。
看了看题，B题是个水题，只要用个map存一下每个单词的位置，然后暴力修改，如果每个单词前后都有逗号就删掉他，保证复杂度就行。
F题是个暴力，预处理之后暴力枚举就行，题意不太好懂。
K题是个贪心，贪心满足度数最小的点即可。。
别的没看了。。。。然后中午去用门票领了饭，开心的吃了赛百味！
然后回学校做物理实验去了。。。。。
下午一看榜。。我们学校凉凉。。但是恭喜PKU获得第三名的好成绩！

但愿这不是我最后一次参加的WF吧！
感谢TZG送我WF的票！