srm 592 div 2
很少做TC，第一次写报告。
第一题：
题目意思：
有n个不同的数，求第二小的m个的和。
解题思路：
贪心，从小到大排序。去掉第m个加上第m+1个即可。
代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
class LittleElephantAndBooks
{
public:
int getNumber(vector<int>pages,int number)
{
int si=pages.size();
sort(pages.begin(),pages.end());
int sum=0;
for(int i=0;i<number-1;i++)
sum+=pages[i];
sum+=pages[number];
return sum;
}
};
第二题：
求两个1~n的排列A和B的种数，使得Σmax(Ai,Bi)>=k的。
解题思路：
直接暴力就可以。
先把A排成1~n,固定，然后枚举B的所有排列，对应关系确定后，全排列，也即乘以n!就行了。10！也就10^6
代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
vector<int>myv1;
vector<int>myv2;
long long getNumber(int N,int K)
{
myv1.clear(),myv2.clear();
for(int i=1;i<=N;i++)
{
myv1.push_back(i);
myv2.push_back(i);
}
ll ans=0;
do
{
int sum=0;
for(int i=0;i<myv1.size();i++)
sum+=max(myv1[i],myv2[i]);
if(sum>=K)
ans++;
}while(next_permutation(myv2.begin(),myv2.end()));
ll ff=1;
for(int i=2;i<=N;i++)
ff*=i;
return ans*ff;
}
第三题：
给一个A（A<=10^15),N(N<=100).这样就形成了一个数列A，A+1,....,A+N,现在可以对这N+1个数，删除某些数的某些位但不能把一个数所有的位都删掉，可以有前置零，要求删除后该序列满足非递减，求删除的种数，只要删除的有一位不同则记为不同的删除种数。什么都没删也记为一种。
解题思路：
LIS+状态压缩取数处理。
对于某一个数，一共只有15位，所有可以用15位的二进制保存每位是否还保存在。这样把数取出来后，LIS处理就行了。
熟悉各种STL。
代码：
[cpp]
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define Mod 1000000007
using namespace std;
struct Elem
{
LL va,sum;
};
bool operator < (const Elem & a,const Elem & b)
{
return a.va<b.va;
}
//满足非递减性质
long long getNumber(long long A,int N)
{
vector<Elem>dp;
Elem ee={0,1}; //初始化
dp.push_back(ee);
for(int i=0;i<=N;i++)
{
vector<Elem>tt; //将该位所有的状态放到一个vector里面
stringstream ss;
ss<<(A+i); //把A+i读进去
string str=ss.str(); //转化成字符串，对每一位好处理
for(int i=1;i<(1<<str.size());i++) //每一个二进制的i,对应一个取出来的数
{
LL tmp=0; //每一个数代表着一种状态
