B(two point)

题意：

　　给出长度为n的非递减数组E[1..n]，对于所有三元组(i,j,k),1<=i<j<k<=n且Ek-Ei<=U，我们需要计算出最大的(Ek-Ej)/(Ek-Ei)

　　n<=1e5

分析：

　　考虑枚举i和k，那么j一定是i+1

　　容易发现k越靠右值越大，所以k是满足Ek-Ei<=U的最大的k

　　于是two point就行了

C(思维)

题意：

　　主角每天对河流水位进行标记，相同水位不重复标记。给定每天的在河流水位上的标记数，求最小的所有天的河流水位下的标记数之和。

　　n<=1e5

分析：

　　等价于我们要最小化每天的标记总数

　　我们可以得到一些限制条件，f(i)>=f(i-1) f(i)>=m(i)+1

　　我们可以先从前到后扫一遍得到f

　　但有些问题，就是可能会发生标记数突变，即有两天标记数差值超过1

　　所以我们只能从后向前将依次递增，最后得到正确的f(i)

　　答案就是Σf(i)-m(i)-1

D(二维偏序)

题意：
　　在一个数轴上有n个飞机，每个飞机都有个飞行速度和初始位置。风速的范围是[-w,w]

　　若两架飞机i,j可以在某个风速下同时到达0号点，我们就计数一次

　　问最后计数的结果是多少

　　n<=1e5,w<=1e5

分析：

　　我们考虑作出每架飞机的到达时间与风速的函数图像，一定是光滑的单调曲线

　　如果两架飞机可以同时到达原点，那么就是两条曲线有交点，那就是(ta-ta')(tb-tb')<=0

　　于是就变成了一个二维偏序计数的问题，直接BIT就行了

E(dp)

题意：

　　有n个箱子，每个箱子都有一个高度，部分箱子是重要箱子，部分箱子是非重要箱子。

　　你需要找个垒箱子的顺序，使得底面高度在[l,r]范围内的重要箱子个数最多。

　　n<=10000，保证所有箱子的高度和<=10000

分析：

　　容易发现一个性质，那就是在[l,r]内连续放置的箱子一定是从小到大垒的

　　于是我们可以枚举在[l,r]内放连续的最小的x个重要箱子，然后其它箱子作为垒高度用的

　　但是可能会在这x个重要箱子上再放一个比较高的箱子，答案会+1

　　于是dp[j]表示凑出高度j最少需要多少个重要箱子，就可以根据dp[j]的值判断是否答案加1了

　　时间复杂度O(nh)

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 struct wjmzbmr

 {

     int a,b;

     bool operator < (const wjmzbmr &x) const

     {

         if(b!=x.b) return b<x.b;

         return a>x.a;

     }

 }a[maxn+];

 int dp[maxn+];

 int s[maxn+];

 int n,l,r,m;

 int ans;

 int main()

 {

     scanf("%d%d%d",&n,&l,&r);

     for(int i=;i<=n;++i) scanf("%d",&a[i].a);

     for(int i=;i<=n;++i) scanf("%d",&a[i].b);

     sort(a+,a+n+);

     for(int i=;i<=maxn;++i) dp[i]=n+;

     for(int i=n;i>=;--i) s[i]=s[i+]+a[i].a;

     for(int i=;i<=n;++i) if(a[i].b==) ++m;else break;

     //for(int i=1;i<=n;++i) printf("%d %d\n",a[i].a,a[i].b);

     dp[]=;

     for(int i=;i<=n;++i)

     {

         if(i>m)

             for(int j=l;j+s[i]<=r;++j)

                 if(dp[j]<=n)

                     ans=max(ans,n-i++(dp[j]+m<i-));

         for(int j=r;j>=a[i].a;--j)

             dp[j]=min(dp[j],dp[j-a[i].a]+a[i].b);

     }

     for(int j=l;j<=r;++j)

         if(dp[j]<n-m) ans=max(ans,);

     printf("%d\n",ans);

     return ;

 }

巴特西

codeforces #472(div 1)

B(two point)

C(思维)

D(二维偏序)

E(dp)

最新文章

热门文章