Category: 其他

相关链接

题目传送门：https://arena.topcoder.com/#/u/practiceCode/15657/31723/12515/1/317358
中文题面及题解：http://picks.logdown.com/posts/208980-solutions-to-topcoder-open-2013s-hard-problems

解题报告

这题从头到尾都只会 $O(n^3)$ 的 $DP$
想了四个小时啊 QwQ

考虑搞出一个二叉搜索树
显然我们可以控制一个节点的左右儿子有多少个
因为我们可以询问当前区间的端点，所以我们还可以控制有没有左右儿子
换一句话说，我们可以钦定这棵搜索树的形态

我们继续观察可以发现一下两条：

1. 我们可以根据一个节点左右儿子子树的大小，求得往左、往右走的概率
2. 每一个深度在$[A,B]$的节点都是一个合法的结束

于是我们就可以枚举第$A$层有多少结点，然后贪心往下放就可以啦！

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

class WellTimedSearch {
    public:
	double getProbability(int n, int A, int B) {
		int vout = 0; 
		for (int i=1,up,down;i<=n;i++) {
			if (A > 1) up = Get_Top(i+1>>1, A-1);
			else {if (i == 1) up = 0; else up = 1e9;}
			if (n - up - i < 0) break;
			down = Get_Down(B-A, n - up - i, i<<1);
			vout = max(vout, i + down);
		}
		return (double)vout / n;
	}
   	private:
	int Get_Top(int len, int t) {
		if (t > 1) return min((int)1e9, len + (len>1? Get_Top(len+1>>1, t-1): t-1));
		if (t == 1 && len > 1) return 1e9;
		return 1;
	}
	int Get_Down(int t, int num_node, int cur) {
		if (!t) return 0;
		if (cur >= num_node) return num_node;
		return cur + Get_Down(t-1, num_node - cur, cur<<1);
	}
};

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4456
神犇题解：http://blog.csdn.net/neither_nor/article/details/51733997

解题报告

将询问离线后考虑分治
不停地将区间尽量划分成正方形
考虑每一个块内的询问：

1. 最优路径经过中轴线

那么我们枚举中轴线上的每一个点
跑一遍到块内所有点的最短路
然后用这个东西来更新答案

2. 最优路径不经过中轴线

那么我们递归处理

于是我们就在 $O(n\sqrt n {\log ^2}n)$ 的时间复杂度内解决这个问题了
然而复杂度可以被证明到少个 $log$ 参见：http://blog.csdn.net/neither_nor/article/details/51733997

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4377
神犇题解：http://blog.csdn.net/commonc/article/details/51282041

解题报告

考虑一个匹配的第一个位置是x的话
第i个位置实际的值就是 $ (x + (i – 1)a)\% n$
然后这个位置显然会受到限制，形如：$ {p_1} < x < {p_2}$的限制条件
于是对于限制条件的反区间取并，然后从总区间中减去，剩下的就是符合条件的开头啦！

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4059
神犇题解Ⅰ：http://blog.csdn.net/popoqqq/article/details/46380617
神犇题解Ⅱ：http://krydom.com/bzoj4059/

解题报告

考虑直接找出所有不无聊的区间
直接 $ O(n^2)$ 枚举的话，会T掉，于是考虑分治
假如当前考虑到的区间为(l,r)，且这个区间中一个只出现过一次的数为x，下标为p
那么显然，横跨x的区间合法，两边的区间就递归下去做就好啦！

但如果每一次我们从左到右扫描x的话，时间复杂度长这样：$ T(n) = T(n – 1) + n$
这样的话，上限是 $ O(n^2)$ 显然不清真
考虑同时从两边开始扫描的话，复杂度就变为了： $ T(n) = T(p) + T(n – p) + \min (n – p,p)$
于是这个是：$ O(n\log n)$ 的，于是就可以愉快的暴力啦！
至于复杂度的证明的话，我们发现这货的形式和线段树的启发式合并的式子长得一毛一样
因为线段树的启发式合并是 $ O(n\log n)$ 的，那么这货的复杂度也就是对的啦！

当然你也可以使用归纳法什么的来证明复杂度
甚至你可以根本不用这个暴力的算法，而使用优雅的矩形面积并来做：
http://www.cnblogs.com/DaD3zZ-Beyonder/p/5803964.html

相关链接

题目传送门：http://www.tsinsen.com/A1342
参考代码：http://paste.ubuntu.com/23803611/

解题报告

这题乍看需要 $ O({n^2})$ 的DP的样子
然而可以用 Tree 这道题一样，给每一次转移附加一个值 $ k$
然后直接转移，记录一下转移了多少次，根据次数的多少来调整 $ k$
然后再用上决策单调性来优化DP的话
这样似乎就可以在 $ O(n{\log ^{\rm{2}}}n)$ 的时间复杂度内解决这个问题了！

值得一提的是，毛爷爷讲了一下这个方法的适用范围：
DP的那个函数必须是一个凸包
不过毛爷爷也说了：
只要拍一拍，拍不出错就行啦！

相关链接

题目传送门：http://uoj.ac/contest/35/problem/246
官方题解：http://matthew99.blog.uoj.ac/blog/2085

解题报告

这题真™是套路深啊！
一言不合就根号大军了

具体来说的话，我们考虑答案的区间长度为 $ len$
并且钦定一个阀值 $ S$

1. 考虑 $ len<S$ 的情况
   我们枚举右端点，暴力向左扫 $ S$ 个就可以了

2. 考虑 $ len \ge S$ 的情况
   我们发现相似度不会超过 $ \frac{m}{{len – 1}}$
   于是考虑在权值上暴力向两边扫 $ S$ 个

这样的话，我们就可以在 $ O(nS + n\frac{m}{s})$ 的复杂度内解决这个问题了
不难发现，当 $ S = \sqrt m$ 时复杂度最优

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
LL vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read(); 
	K = read(); S = sqrt(m) + 1;
	for (int i=1;i<=n;i++) a[i] = read();
	
	memset(gap,60,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=i-1;j>=i-S&&j;--j) {
			gap[j] = min(gap[j], gap[j+1]);
			gap[j] = min(gap[j], abs(a[i] - a[j]));
			if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
		}
	}
	memset(gap,0,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=S;j++) {
			if (j) gap[j] = max(gap[j], gap[j-1]);
			if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
			if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
			if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1)); 
		}
		lst[a[i]] = i;
	}
	printf("%lld\n",vout);
	return 0;
}

相关链接

题目传送门：http://uoj.ac/contest/36/problem/278
解题报告：http://jiry-2.blog.uoj.ac/blog/2242

解题报告

这个题目看一眼就觉得搞一个差分约束系统
然后用函数式线段树优化建图
时间复杂度 $ O(nlo{g^2}n)$
感觉可以过的样子！

然后去看题解：

直接排一个序就可以了

不要问我为什么跪在地上

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100000+9;

int n,vout[N];
pair<int,int> arr[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		arr[i].first = read();
		arr[i].second = -i;
	}
	sort(arr+1, arr+1+n);
	for (int i=1;i<=n;i++)
		vout[-arr[i].second] = i;
	for (int i=1;i<=n;i++)
		printf("%d ",vout[i]);
	return 0;
}

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2456
神犇题解：https://oi.men.ci/bzoj-2456/

解题报告

考虑将不同的数抵消掉
因为题目所求的数多于一半
所以剩下的就一定是答案啦！

Code

#include<cstdio>
#define LL long long

int main() {
	int n,tot=0; LL num,cur;
	for (scanf("%d",&n);n;n--) {
		scanf("%lld",&cur);
		if (num != cur) {
			if (tot) tot--;
			else tot = 1, num = cur;
		} else tot++;
	} printf("%lld\n",num);
	return 0;
}

—– UPD 2016.12.29 —–
这题似乎还有一个做法：

考虑将原数分解成二进制
统计每一位二进制上0多还是1多

酱紫的话，最后在在二进制下逐位确定答案就好啦！