srm 592 div 2
很少做TC，第一次写报告。
第一题：
题目意思：
有n个不同的数，求第二小的m个的和。
解题思路：
贪心，从小到大排序。去掉第m个加上第m+1个即可。
代码：
#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 1000000007using 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; //每一个数代表着一种状态 for(int j=0;j<str.size();j++) { if(i&(1<<j))//是1的话就把该位取出来 { tmp*=10; tmp+=str[j]-'0'; } } Elem cur={tmp,0}; //注意不存在的情况为0 vector<Elem>::iterator it=upper_bound(dp.begin(),dp.end(),cur);//注意是查找结构体 //在前面先找到大于tmp的，然后-1，表示小于等于tmp的 if(it!=dp.begin()) cur.sum=it[-1].sum; //注意迭代器的用法，-1表示前一个迭代器 tt.push_back(cur); } sort(tt.begin(),tt.end()); //对它按va排序 for(int i=1;i<tt.size();i++) //tt[i].sum表示当前这位,值小于等于tt[i].va,的总个数 tt[i].sum=(tt[i].sum+tt[i-1].sum)%Mod; dp.swap(tt);//交换两个vector } return dp.back().sum;}