做了1001 1003 1005 1006
看题：http://bestcoder.hdu.edu.cn/contests/contest_show.php?cid=702
1001 区间的价值
乱搞？
做法简介：有多种做法，主要思想都是先算a[i]作为最小值能管辖的最大左右范围l[i], r[i]，然后求[ l[i], r[i] ]区间内的最大值ma，判断是否可以更新ans[r[i] - l[i] + 1] = ma*a[i]，能更新的话也可以更新更小的区间。
思路过程：
枚举所有区间？n^2，不行。
答案肯定是这样：大区间的结果小，小区间的结果大，单调的。那么如果算出了大区间的答案，可以更新到小区间。
发现很多区间的最小值是同一个，如果我们枚举最小值的话，可以求这个最小值管辖的最大左右范围。
求出了这个范围的话，我们再求一下这个区间的最大值，就能更新一下这个区间大小的答案，还可以更新小区间大小的答案。
这样能否得到所有区间大小的最优答案呢？
当然啦，因为我们固定了最小值，这个最小值能对应的最大的最大值被我们找到了，这就是这个最小值的最优答案。我们枚举最小值，就枚举了所有最优答案。
剩下的问题就是2个：
1.怎么确定某个最小值的管辖左右范围；
2.求某个区间的最大值
解：
1.两种方法：
（1）用DP，从做到右求l[i]，从右到左求r[i]，求好的值可以拿来用。（我没用这个方法
（2）用单调栈，二分找到比a[i]左边的比a[i]小的最右边的a[j]，l[i] = j+1，具体见我的代码。
2.两种方法：
（1）RMQ-ST（我没用这个
（2）还是用单调栈，要先对区间[Li,Ri]排序，让Li有序。例如从小到大排，我们从右往左扫，把[Li, n-1]的元素都加入递减单调栈，二分找下标小于等于Ri的最大的数。具体见我的代码。好像有点复杂，还是学一个RMQ-ST比较好。
代码（闲着没事写了个类看看是不是能看得比较清晰，就写成这样了，感觉也不是很清晰。还学了一波函数指针）：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; bool littleThan(int x, int y) {
return x<y;
}
bool biggerThan(int x, int y) {
return x>y;
} class MonoVector {
bool (*cmp)(int,int);
MonoVector() {}
public:
vector<PII> q;
MonoVector(bool isDecrease) {
if(isDecrease) cmp = biggerThan;
else cmp = littleThan;
q.clear();
}
void insert(int id, int value) {
while(!q.empty() && cmp(value, q.back().second))
q.pop_back();
q.push_back(MP(id,value));
}
///from right find to left, find the first one witch little/bigger than "value".
int LeftStrangeId(int value) {
int l = ,r = q.size()-;
while(l<=r){
int mid = (r-l)/ + l;
if(!cmp(q[mid].second , value)) r = mid - ;
else l = mid + ;
}
if(l->=) return q[l-].first;
else return -;
}
int getLeftestValueWithIdNoBiggerThan(int id){
int l = ,r = q.size()-;
while(l<=r){
int mid = (r-l)/ + l;
if(q[mid].first <= id) r = mid - ;
else l = mid + ;
}
return q[l].second;
}
int size() {
return q.size();
}
void clear(){
q.clear();
}
}; int n;
int a[MAXN];
LL ans[MAXN]; void updateAns(int range, LL value){
if(value > ans[range]){
ans[range] = value;
if(range>)updateAns(range - , value);
}
} PII lr[MAXN];
bool qcmp(int x,int y){
return lr[x].first < lr[y].first;
} void farm() {
int i,j;
MonoVector v = MonoVector(false);
REP(i,n) {
lr[i].first = v.LeftStrangeId(a[i]) + ;
v.insert(i,a[i]);
}
v.clear();
ROF(i,n-,){
int temp = v.LeftStrangeId(a[i]);
if(temp!=-)lr[i].second=temp - ;
else lr[i].second=n-;
v.insert(i,a[i]);
}
int q[MAXN];
REP(i,n)q[i]=i;
sort(q, q+n, qcmp);
v = MonoVector(true);
int left = n;
ROF(j,n-,){
i = q[j];
while(lr[i].first < left){
left --;
v.insert(left , a[left]);
}
int ma = v.getLeftestValueWithIdNoBiggerThan(lr[i].second);
// printf("%d [%d,%d], mi=%d, ma=%d, %d,%d\n",i,lr[i].first, lr[i].second, a[i], ma, a[i]*ma, lr[i].second - lr[i].first+1);
updateAns(lr[i].second - lr[i].first + , 1LL*ma*a[i]);
} } int main() {
int i;
while(RD(n)!=EOF) {
MZ(ans);
REP(i,n) RD(a[i]);
farm();
FOR(i,,n)cout<<ans[i]<<endl;
}
return ;
}
（这题我自己没想出来，看别人题解，怎么全会用那个DP求l[i] r[i]，for里面套while，看起来像O(n^2)的啊，想了一下发现好像并不是。我还是要学习一个。）
1003 瞬间移动
写个暴力打表找规律，发现是组合数。
使m<n（不小于的话就交换一下，对称的）， f(m,n) = C(m+n-2, m-1)
然后就变成怎么求大组合数取模了。这题的好像还不是很大，可以直接用逆元。再大的话要用Lucas定理加逆元了。
具体看我的另一题题解里有写：http://www.cnblogs.com/yuiffy/p/3909970.html
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; int n,m; LL PowerMod(LL a, LL b) {
LL tmp = a, ret = ;
while (b) {
if (b & ) ret = ret * tmp % MOD;
tmp = tmp * tmp % MOD;
b >>= ;
}
return ret;
} LL calC(LL n,LL m){
m=n-m>m?m:n-m;
LL up=,down=;
int i;
for(i=;i<=m;i++){
down*=i;
down%=MOD;
up*=(n-i+);
up%=MOD;
}
return (up*PowerMod(down,MOD-))%MOD;
} LL Lucas(LL n, LL m) {
if(m==)return ;
return (Lucas(n/MOD, m/MOD)*calC(n%MOD, m%MOD))%MOD;
} inline LL farm(){
int i,j;
if(n<m)swap(n,m);
///f(x,y) = C(x+y-2,x-1) (x>y)
LL re = ;
return Lucas(n+m-,n-);
} int main(){
while(RD2(n,m)!=EOF){
n--;m--;
cout<<farm()<<endl;
}
return ;
}
上面好像是用^(n-2)的那种逆元，下面我又搞了一个exgcd逆元的：
//#pragma comment(linker, "/STACK:102400000,102400000")
/**Header!**/ //{
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
#define cindiao ios_base::sync_with_stdio(0)
#define fcout(x,y) cout << fixed << setprecision(x) << (y) << endl
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
template <class T> inline T quickPow(T p,T e,const T &M){
LL ret = ;
for(; e > ; e >>= ){
if(e & ) ret = (ret * p) % M;
p = (p * p) % M;
} return (T)ret;
}
template <class T> inline T gcd(const T &a,const T &b){return (b==) ? a : gcd(b,a%b);}
template <class T> inline T niyuan(const T &a, const T &M){return quickPow(a,M-,M);}
template <class T> inline T exgcd(const T &a,const T &b,T &x,T &y) {
if (!b) {x=,y=;return a;}
T ret=exgcd(b,a%b,x,y), t;
t=x,x=y,y=t-a/b*y;
return ret;
}
template <class T> inline T niyuanex(const T &a, const T &M){
T x,y;
exgcd(a,M,x,y);
return (x+M)%M;
}
inline LL calC(const int &n,int m,const LL &MOD){
m=(n-m>m)?m:(n-m);
LL up=,down=;
int i;
for(i=;i<=m;i++){
down*=i;
down%=MOD;
up*=(n-i+);
up%=MOD;
}
return (up*niyuanex(down, MOD))%MOD;
}
inline LL Lucas(const int &n,const int &m, const int &MOD) {
if(m==)return ;
return (1LL * Lucas(n/MOD, m/MOD, MOD)*calC(n%MOD, m%MOD, MOD))%MOD;
}
const int gx[] = {-,,,};
const int gy[] = {,,,-};
const double PI=acos(-1.0);
//}
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; int n,m; inline LL farm(){
int i,j;
if(n<m)swap(n,m);
///f(x,y) = C(x+y-2,x-1) (x>y)
LL re = ;
return Lucas(n+m-,n-,MOD);
} int main(){
while(RD2(n,m)!=EOF){
n--;m--;
cout<<farm()<<endl;
}
return ;
}
1005 区间交
优先队列题。
把区间[Li,Ri]按照Li从小到大排序。
然后依次把区间加入候选集，把他们的Ri加入优先队列，记住最小的Ri。
加到够k个以后，每次就要看是否能更新答案了。
k个区间的交集，区间[L,R]，L就是最新加入的那个Li，R就是记着的最小的Ri。
如果光用优先队列来找最小Ri的话，会超时，我们来优化一下，就只在优先队列中存最大的k个Ri，不存太多的Ri。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; struct Node {
int l,r;
inline bool operator<(const Node &y)const {
return l<y.l;
}
}; int n,k,m;
int a[MAXN];
Node b[MAXN];
map<int,int> pq;
LL sm[MAXN];
inline LL farm() {
int i;
LL ans=;
sort(b,b+m);
sm[] = ;
FOR(i,,n)sm[i] = sm[i-] + a[i];
pq.clear();
int minR = INF;
REP(i,k-) {
pq[b[i].r]++;
minR = min(minR, b[i].r);
}
FOR(i,k-,m-) {
int L = b[i].l;
int R = b[i].r;
R = min(R,minR);
if(L<=R)ans = max(ans, sm[R] - sm[L-]);
// printf("%d,%d,%d,%d,%d,%lld\n",b[i].l, b[i].r, L,R,pq.size(),ans);
if(minR < b[i].r) {
map<int,int>::iterator it = pq.begin();
it->second--;
if(it->second<=) {
pq.erase(it);
pq[b[i].r]++;
it = pq.begin();
// printf("%d,%d\n",it->first, it->second);
minR = it->first;
}else pq[b[i].r]++; } }
return ans;
} int main() {
int i;
while(RD3(n,k,m)!=EOF) {
FOR(i,,n) RD(a[i]);
REP(i,m) RD2(b[i].l,b[i].r);
cout<<farm()<<endl;
}
return ;
}
1006 中位数计数
前缀和？
思路：枚举每个数作为中位数，如果能O(n)算出有多少个区间以它为中位数，就无敌。想到用前缀和的思想，统计比它大、比它小的数的个数，能行。
用类似前缀和的思想，枚举每个数a[i]作为中位数，从它往左扫一遍，
设定一个变量x，当遇到一个比a[i]大的数，x++，遇到比a[i]小的数，x--。用一个数组统计各种x的出现次数，b[x]++。
再往右扫一遍，用另一个数组c来统计。
假如b[0]=5，可以得知，有5个点x=0，x=0说明比a[i]大的数 和 比a[i]小的数 一样多，这个区间就要以a[i]为中位数，b[0]=5说明有5个这样的区间。
假如b[3]=2，c[-3]=3，那么以a[i]为中位数的区间个数，可以加上b[3]*c[-3]，因为左边多3个比a[i]大的，右边多3个比a[i]小的，正好抵消，他们组成的区间还是以a[i]为中位数。
就按照这个理论来一顿统计，就行啦。
因为数组不能有负数下标，x可以以8000为初始值。
注意各个数不相同，然后它设定偶数个数的话中位数为中间两个数的平均值，所以偶数个数组成的区间就不用管了，只算奇数个数组成的区间，特殊处理一下。
代码：
//#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
using namespace std; #define MZ(array) memset(array, 0, sizeof(array))
#define MF1(array) memset(array, -1, sizeof(array))
#define MINF(array) memset(array, 0x3f, sizeof(array))
#define REP(i,n) for(i=0;i<(n);i++)
#define FOR(i,x,n) for(i=(x);i<=(n);i++)
#define ROF(i,x,y) for(i=(x);i>=(y);i--)
#define RD(x) scanf("%d",&x)
#define RD2(x,y) scanf("%d%d",&x,&y)
#define RD3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define RD4(x,y,z,w) scanf("%d%d%d%d",&x,&y,&z,&w)
#define WN(x) printf("%d\n",x);
#define RE freopen("D.in","r",stdin)
#define WE freopen("huzhi.txt","w",stdout)
#define MP make_pair
#define PB push_back
#define PF push_front
#define PPF pop_front
#define PPB pop_back
#define lowbit(x) ((x)&(-x))
template<class T>inline void OA(const T &a,const int &st,const int &ed) {
if(ed>=st)cout<<a[st];
int i;
FOR(i,st+,ed)cout<<' '<<a[i];
puts("");
}
typedef long long LL;
typedef unsigned long long ULL;
const double PI=acos(-1.0);
const double EPS=1e-;
inline int sgn(double &x) {
if(fabs(x) < EPS)return ;
if(x < )return -;
else return ;
}
const int INF=0x3f3f3f3f;
const int NINF=0x80000001;
const int MAXN=;
const int MAXM=;
const int MOD = ; int n;
int a[MAXN];
int ans[MAXN]; inline void lisanhua() {
int b[MAXN];
int i;
map<int,int> mp;
REP(i,n)b[i]=a[i];
sort(b,b+n);
REP(i,n)mp[b[i]]=i;
REP(i,n)a[i]=mp[a[i]];
} void gank(int st, int ed, int step,bool dao, int flag,int myi, int sum[][MAXN*]) {
int j;
int now = ;
bool fg=;
if(!dao) {
for(j = st; j<=ed; j++) {
if(a[j]<a[myi])now--;
else now++;
sum[fg][now]++;
fg^=;
}
} else {
for(j = st; j>=ed; j--) {
if(a[j]<a[myi])now--;
else now++;
sum[fg][now]++;
fg^=;
}
}
} void farm() {
int i,j,k;
// lisanhua();
// OA(a,0,n-1);
REP(i,n) {
int lsum[][MAXN*];
int rsum[][MAXN*];
MZ(lsum);
MZ(rsum);
// gank(i-2,0,2,true,0,i,lsum);
gank(i-,,,true,,i,lsum);
// gank(i+2,n-1,2,false,0,i,rsum);
gank(i+,n-,,false,,i,rsum);
ans[i]= + lsum[][]+rsum[][];
REP(k,) {
REP(j,n) {
// printf("%d,%d,%d,%d\n",lsum[k][8000+j],rsum[k][8000-j],lsum[k][8000-j],rsum[k][8000+j]);
if(lsum[k][+j] && rsum[k][-j]) {
ans[i]+=lsum[k][+j]*rsum[k][-j];
}
if(j!=) {
if(lsum[k][-j] && rsum[k][+j]) {
ans[i]+=lsum[k][-j]*rsum[k][+j];
}
}
}
}
}
} int main() {
int i;
while(RD(n)!=EOF) {
REP(i,n) RD(a[i]);
farm();
OA(ans,,n-);
}
return ;
}