Time Limit:1000ms Memory Limit:128MB
LYK对n个女生有好感。第i个女生的身高为ai。
LYK要在这些女生中选拔出一个女生来作为他的女朋友。选拔当然要排队咯。于是LYK想让这n个女生排成一行。
但LYK觉得对于两个身高相同的女生，谁排在前谁排在后其实让整个队列看上去并没有什么差别。
LYK想知道有多少个有差别的队列。
第一行一个数n表示女生个数。
第二行有n个数ai表示第i个女生的身高。
一个数表示答案。
3
1 2 2
3
对于40%的数据n<=5,。
对于60%的数据n<=20。
对于80%的数据n<=1000。
对于100%的数据n<=10000，1<=ai<=n。
1 2 3 4 5 5!
1 1 3 4 5 5!/2!
1 1 1 3 4 5!/3!
1 1 1 1 3 5!/4!
1 1 2 2 3 5!/2!/2!
分子分母都分解质因子，删去相同的部分。
压位，一般压9位
Time Limit:2000ms Memory Limit:128MB
LYK收到了n个数字作为新年礼物，第i个数字的值为ai。
除了这些数字，还有一个信封，上面写着：“如果你能从这n个数中选出k个数使得它们的和为奇数，那么我将会满足你一个愿望！”
LYK觉得这不可能，此处必有玄机，于是它想在满足信封里的要求的情况下满足选出的数字的和最大。LYK想知道最大是多少。
当然不止这一年LYK收到了礼物，以后的每一年都会有这样的一个礼物，具体的，总共有m年。神奇的是这些数字并没有发生变化，而k发生了变化，LYK想知道所有年的答案是多少。
可能会存在写信人在骗它，也就是说不存在一个可行的方案，此时输出-1就可以了。
第一行一个数n表示LYK收到的数字个数。
第二行n个数ai表示每个数字。
第三行一个数m。
第四行m个数表示每一年的k值。
m行，每行输出一个答案。
3
1 2 2
3
1 2 3
1
3
5
对于30%的数据n,m<=100。
对于60%的数据n,m<=1000。
对于另外10%的数据所有ai均为奇数。
对于再另外10%的数据所有ai均为偶数。
对于90%的数据n,m<=100000。
对于100%的数据n,m<=1000000，1<=ai<=n+2。
Note:
想拿满分的同学建议使用读入优化。
以下是读入优化模板：
void read(int &A)
{
char r; A=0;
for (r=getchar(); r<‘0‘ || r>‘9‘; r=getchar());
for (;r>=‘0‘ && r<=‘9‘; r=getchar()) A=A*10+r-‘0‘;
}
全是偶数，都不行。
全是奇数，k是偶数，都不行；k是奇数，输出最大奇数和。
从大到小排序，找尽可能靠前的，1……k和为奇数则为答案，和为偶数则不符合条件，从前面删掉一个偶数，后面加一个奇数；或从前面删掉一个奇数，后面加一个偶数。
只能删一个加一个。
对两种情况进行讨论。
—————A—————|—————B—————
最大pos=1 界线=k 最小
找到A中距离界线最近的偶数，与B中距离界线最近的奇数交换，计算一个答案
找到A中距离界线最近的奇数，与B中距离界线最近的偶数交换，计算另一个答案
输出最大的值
Time Limit:1000ms Memory Limit:128MB
随着WC的到来，LYK每天都在学习着新的知识。俗话说，比赛成绩=实力*经验。LYK相信它已经拥有了足够强的实力获得WC金牌。只要积累充足的经验，就能够获得强大的精神能量AK今年的WC！
于是LYK找来了n道题目想给自己做一个测试，对于第i道题目有ai分。LYK非常强大，能轻易地做出所有题目，但它觉得这样十分没意思。于是它给自己出了一道题目。
假如存在一个虚拟对手LYK2，对于每道题目它有50%的几率能够做对，做对一道题目能够获得其分数，做不对则得到0分。
LYK想知道，至少获得多少分数，使得至少有p的概率分数不低于LYK2。
第一行两个数n,p。
接下来一行n个数表示ai。
一个数表示答案。
2 0.6
1 2
2
对于20%的数据n<=5，ai<=1000。
对于40%的数据n<=30，ai<=1000。
对于60%的数据n<=60，ai<=1000。
对于另外10%的数据n<=25，ai<=10^9。
对于再另外10%的数据n<=35，ai<=10^9。
对于再再另外20%的数据p为整数，n<=60，ai<=10^9。
对于100%的数据0<=p<=1，p小数点后至多两位，2<=n，ai>=1 。
分数至少为2^n*p，上取整 = k，对方有2^n种分数
->在2^n找第k小 n<=35 与two point 的做法类似
拿满分要用动规 dp[i]表示分数为i的方案总数
原文：http://www.cnblogs.com/thmyl/p/6336449.html