[HAOI2007] 上升序列

6 4

Posted by: Qheldiv in: 题解

总是想得很复杂，其实很简单。

用O(n²)或者O(nlog_n)的时间复杂度统计出f_i即以i开始的最长上升序列是多少

因为字典序的缘故，暴力找最优解

假设某次询问是a，给定的数列是{A_i}

对于第一个位置，为了使字典序最小，我们一定选最早的i，使得f_i1>=a

对于第二个位置，A_i2一定且f_i1>=a-1所以接着向后找第一个满足着两个条件的位置

……

这一段的代码：

	for(int i=1;i<=M;i++){
	int j,a,b,pr;
		fin>>a;
		b=0;
		A[pr=0]=-1;
		for(j=1;j<=N;j++)
			if(f[j]>=a && A[j]>A[pr]){
				Ans[++b]=j;
				a--;
				if(!a)
					break;
				pr=j;
			}
		if(b<a){
			fout<<"Impossible\n";
			continue;
		}
		for(j=1;j<=b;j++)
			fout<<A[Ans[j]]<<" ";
		fout<<endl;
	}

刷题小记

4 4

Posted by: Qheldiv in: 题解

今天早上。。出于某种不可抗拒的原因，没心情写题，所以正好小记以下（我是按分类记录，不是按日期记录）：

动态规划：
- SCOI2008 着色方案很好的题，f[c1][c2][c3][c4][c5][k]表示状态进行转移(上网看)
- HAOI2010 计数主要是涉及到 具有不可区别物体的集合的排列（比如重新排列SUCCESS能构成多少种不同的串，公式是(n,k1)*(n-k1,k2)*(n-k1-k2,k3)... = n!/(k1!*k2!...*kn!）其中ki表示某种元素的个数
- SDOI2010 地精部落这个题网上说的方法看不太懂，神马之云想的方法是 f[i][j]表示长度为i的序列第1个是j且开始下降的序列个数，g[i][j]表示...且开始上升的序列个数，那么f[i][j]=Sigma(g[i-1][k])k<j，g[i][j]=Sigma(f[i-1][k])k>j，dp的时候记录一下Sigma信息就可以省掉转移的那一维。
- HAOI2010 最长公共子序列 dp时记录方案数，再容斥掉多计算的即可
- HAOI2010 软件安装 好题一开始看不就是个简单的树形依赖背包嘛，写出来才发现图里面竟然有环，不过既然是环，选一个就全都得选，所以缩成点，构成新的图，再在新图里面dp就可以了（注意环连接的要么什么都没有要么是外向树，对于外向树，缩点之后都不可能有前驱，所以连接到0，这样就是棵标准的树了，从0开始dp就行了）
- 越狱第1季第13集大神的做法不会，不过好像和我的方法有点像（二分答案，然后检查）
- 瑰丽华尔兹又是好题 f[k][y][x]表示第k段的结尾在y行x列的最长滑动距离，转移O（n）的，所以优先队列优化就可以Ac
图论
- 公路修建。。。看出来了很简单，裸的最小生成树，不过由于边数太多Kruskal会跪掉，所以只能用Prim了
- 卡赞群岛找到双连通分量，缩点然后dp（由于是无向图，缩点之后必然是个无根树，或者是无根树森林，所以可dp。
- HAOI 软件安装 见上文
贪心
- SCOI2008 斜堆很有意思的题，按照斜堆的规则，最后插入的点一定在最左边（也就是便利的时候从不向右转），如果没有根变成左子树的情况，每次找最左边的点，删掉，然后模拟一下就行了（基于字典顺序最小的原则）。考虑上较小元素会替代根的情况，如果我们发现某个极左点没有右子树，那么说明它是叶子结点或者是替代根的元素，此时必须先删它（否则不可能构成目标树），基于最小字典序的原则，这些步骤合在一起就是：每次从根向左找没有右子树的点，一旦发现就把它删掉，并且将它的祖先的左右子树互换，最后倒序输出删点顺序即可（有一个特殊情况，即某点的左子树只有一个叶子结点，而且它没右子树，那么此时删除那个叶子结点（基于字典序最小的原则）），相关拓展见这位大神网志
- 立春树树上贪心，比较简单，不说了
数论
- 双亲数貌似都是利用容斥搞的，用Mobius函数搞会快点，关于Mobius Function见Noi2010 能量项链，HAOI2011问题B，以及网上各种题解。

NOI2001 全部题解

6 1

Posted by: Qheldiv in: NOI题解

相对1999年和2000年的问题我花了更少的时间（其实是更集中精力）

以下排列大约是按难度排的。

聪明的打字员

反正切函数的应用

食物链

炮兵阵地

方程的解数

陨石的秘密

“聪明的打字员”是个简单的广度有限搜索，是个基础的问题，但是我花了不少时间。。。

“反正切函数的应用”有数学方法，但是我时暴力过得

“食物链”要用到并查集，算是一个小小的变形。

“炮兵阵地”是状态压缩的动态规划的典型问题，很早之前就写过了

“方程的解数”需要想到技巧的搜索，是这类方程类搜索的典型，没有想全面（只想到了将正负系数分开。。）。

“陨石的秘密”稍复杂的动态规划，我没有想出来，看Byvoid的题解才想出，不过我加以优化（降维）才通过了所有的测试点。

聪明的打字员

聪明的打字员

简单的搜索，需要记录状态（可以用平衡树也可以用hash（这个属于直接寻址表）），然后就没了

反正切函数的应用

反正切函数的应用

可以用高效率的数学方法,也可以朴素:

#include <fstream>
using namespace std;
ifstream fin("arctan.in");
ofstream fout("arctan.out");
long long A,Min=123456789;
int main()
{
	fin>>A;
long long B,C;
	for(B=1;B<=1234567;B++)
	{
		if(B==A)continue;
		if((A*B+1)%(B-A)!=0)continue;
		C=(A*B+1)/(B-A);
		if(C<=0)continue;
		Min=min(Min,B+C);
	}
	fout<<Min<<endl;
	fin.close();
	fout.close();
	return 0;
}

即枚举b的数值,然后c的值就是(A*B+1)/(B-A) 检查该值是否合法(是非负整数),如果合法,就更新Min变量记录的最小值(用b+c的值更新)

数学方法:

根据题中公式，可以推出 a=(b*c-1)/(b+c)。由此得出c=(a*b+1)/(b-a)。因为b,c均为正整数，所以b>a。

我们要求b+c最小，设函数y=f(x)，自变量x为b的取值，但不限于正整数。则有

f(x) = (a*x+1)/(x-a) + x = a + ((1+a^2)/(x-a)) + x

对f(x)求导，得导数

f’(x)=1-(1+a^2)/(x-a)^2

f’(x)=0 得出 x = a+(a^2+1)^0.5 或 x = a-(a^2+1)^0.5，由于x>0，取 x = a+(a^2+1)^0.5。

且x > a+(a^2+1)^0.5时，f’(x)>0，x < a+(a^2+1)^0.5时，f’(x)<0，所以当x = a+(a^2+1)^0.5时，f(x)取得最小值。

由于b和c都是正整数，只需在x一边寻找距离x最近的整数b,c，b+c即要求的最小值。