2019-3-21训练赛总结

dp+二分（最长不降子序列问题）

题意
题目就是要你求出最长非递减的最长子序列长度
白书（挑战程序设计）中提供两种算法 $O\left(n^2\right)和O（nlogn）$O(n2)和O（nlogn）解决该问题
第一种算法用到的知识是dp
$dp\left[i\right]表示以a\left[i\right]结尾的最长子序列，更新方式是dp\left[j\right]-\>dp[i-1](即j从1到i-1)$dp[i]表示以a[i]结尾的最长子序列，更新方式是dp[j]−>dp[i−1](即j从1到i−1)
$if\left(a\right[i]\>=a[j\left]\right)dp\left[i\right]=max\left(dp\right[i],dp[j]+1)$if(a[i]>=a[j])dp[i]=max(dp[i],dp[j]+1)

    max_size=1;
for(int i=1;i<=n;i++){
   dp[i]=1;//单独以a[i]为序列的长度
   for(int j=1;j<i;j++){
   if(a[i]>=a[j]) dp[i]=max(dp[i],dp[j]+1);
   }
}
   max_size=max(max_size,dp[i]);

第二种算法用到的知识是二分+思维

$15大于12，进入stack里面，只要元素大于等于栈顶元素就可以让元素入栈$15大于12，进入stack里面，只要元素大于等于栈顶元素就可以让元素入栈

$如果15不大于20的话，我们就需要把17换成15，因为如果子序列的长度相同，那么末位置的元素较小的在之后会更加有优势$如果15不大于20的话，我们就需要把17换成15，因为如果子序列的长度相同，那么末位置的元素较小的在之后会更加有优势

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=1e6+5;
int a[maxn],cnt=0;
int main(){
     int n,k;
     scanf("%d",&n);
     for(int i=1;i<=n;i++){
	scanf("%d",&k);
	if(a[cnt]<=k){
		a[++cnt]=k;
	}
	else{
	a[lower_bound(a+1,a+cnt+1,k)-a]=k;
	}
     }
     if(n-cnt<=1){printf("YES\n");}
     else{
	printf("NO\n");
     }
    return 0;
}

区间dp+前缀和

题解
$sum表示当前前缀和$sum表示当前前缀和
$如果当前加入的数大于前缀和+1，那么输出前缀和+1，否则继续。$如果当前加入的数大于前缀和+1，那么输出前缀和+1，否则继续。
$因为需要表示连续的整数，那么相邻的数最多只能差1.$因为需要表示连续的整数，那么相邻的数最多只能差1.
$如果排序后k前面的数字之和\&lt;k-1,那么k-1这个数就无法表示。$如果排序后k前面的数字之和<k−1,那么k−1这个数就无法表示。
$再详细的说就是$再详细的说就是
$现在能表示出[0,0]这个区间，那么对于排序后接下来的数k，如果k\&gt;1，那么1$现在能表示出[0,0]这个区间，那么对于排序后接下来的数k，如果k>1，那么1
$这个数就永远也拼不出来。那么对于之前能拼出的区间为[0,x]，加上k之后能拼出$这个数就永远也拼不出来。那么对于之前能拼出的区间为[0,x]，加上k之后能拼出
$的数至少为[k,x+k],必须要求[0,x]这个区间的右端点和[k,k+x]的左端点连续才能把所有$的数至少为[k,x+k],必须要求[0,x]这个区间的右端点和[k,k+x]的左端点连续才能把所有
$数都拼出来，也就是k\&lt;=x+1$数都拼出来，也就是k<=x+1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll a[maxn],sum[maxn];
int n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
	scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
    	if(a[i]>sum[i-1]+1) {cout<<sum[i-1]+1<<endl;return 0;}
    	sum[i]=sum[i-1]+a[i];
    }
    cout<<sum[n]+1<<endl;
    return 0;
}

优化算法

直接 $O\left(n\right)+优化$O(n)+优化AC

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
ll cnt=0;
int main(){
	ll n;
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		ll num=n/i;
		i=n/num;
		cnt++;
	}
cout<<cnt<<endl;
    return 0;
}