首页 > 代码库 > Codeforces Round #256 (Div. 2)

Codeforces Round #256 (Div. 2)

2024-07-12 18:46:22   231人阅读

泛泛解：

D：求K大，如果我们二分枚举，如果有O(N)的方法统计，就OK了，先枚举,我们对每一行的统计能够达到O(1)，所以很简单了。

E:有思路，但是代码能了太弱了，DFS学得太水。

  我们发现其实就是一个深度递归结构,只有100000个元素，所以这是一个突破点。

  先求出所有因子，然后枚举因子，出现的话深度遍历，结束条件是达到第K层或者因子是1，注意：K大于100000时，要变为100000，因为不可能层数大于100000；

C:分治+贪心。

这道真是好题，题解的思路是：对区间（L,R)的点贪心，与r-l+1的值比较，是递归形式的，具体代码了

#include<stdio.h>#include<string.h>#include<iostream>using namespace std;int n;int a[123456];int dfs(int l,int r){   if (l>r) return 0;   int mm=9999999;   int pos;   for (int i=l;i<=r;i++)       if (mm>a[i])       {           mm=a[i];           pos=i;       }         int  ans=0;    for (int i=l;i<=r;i++)        a[i]-=mm;        ans+=mm;    ans+=dfs(l,pos-1);    ans+=dfs(pos+1,r);    return min(ans,r-l+1);}int main(){    int n;    cin>>n;    for (int i=1;i<=n;i++) cin>>a[i];    cout<<dfs(1,n)<<endl;    return 0;}

　　


联系
我们