Fork me on GitHub

20191105模拟赛题解

🐮🍻🐮

Work

思路

题目等价于找到一个数量最小的排列,使得对于这个排列里的任何一个$k$都有$\sum_{i=1}^{size}work_i - work_k >= sleep_k$.然后我们移项之后有$\sum_{i=1}^{size}>=work_k+sleep_k$.
所以我们可以令$x_i=sleep_i+work_i$,然后对于$x_i$从小到大排序.然后我们枚举每一个$x_i$,然后同时把所有遍历过的$work_i$从大到小排序,我们需要找到一个长度最小的区间使得$\sum work_j >= sleep_i$.
首先想一下暴力怎么维护这个东西:我们每读进来某个$w_i$,我们把这个元素连同之前的元素按照$work_i$为关键字从小到大排序,并且我们每次都重新记录一下$work$数组的前缀和,使用二分的方法找到这个最小的区间长度.
然后我们考虑怎么优化这个过程,我们发现我们可以维护一个小根堆,然后判断时,每次都弹出一个最小值.然后判断现在的$sum$是否还大于$sleep$.而且如果现在的$sum$本来就小于$sleep$时,我们也没必要再往堆里扔东西,因为如果要扔东西的话答案一定不会更优.所以直接忽略即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int N = 5e5 + 10;

int n;
struct Worker {
int work;
int sleep;
} w[N];
int fro[N];

inline bool cmp1 ( Worker x , Worker y ) {
return x.sleep + x.work < y.sleep + y.work;
}
inline bool cmp2 ( Worker x , Worker y ) {
return x.work < y.work;
}

inline int read () {
int s = 0 , w = 1;
char ch = getchar ();
while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}
while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}
return s * w;
}

priority_queue < int , vector < int > , greater < int > > qu;

signed main ( void ) {
n = read ();
for ( int i = 1 ; i <= n ; i++ )
w[i].work = read () , w[i].sleep = read ();
sort ( w + 1 , w + 1 + n , cmp1 );
int ans = 2147483647 , sum = 0 , size = 1;
for ( int i = 1 ; i <= n ; i++ ) {
if ( w[i].sleep <= sum ) {
while ( sum - qu.top() >= w[i].sleep ) {
sum -= qu.top();
qu.pop();
size--;
}
ans = min ( ans , size );
}
qu.push ( w[i].work );
sum += w[i].work;
size++;
}
if ( ans == 2147483647 )
puts ( "-1" );
else
cout << ans << endl;
return 0;
}

Seq

思路

我们首先考虑暴力怎么$DP$,我们可以设$f_{i,j,0/1}$表示现在对于串$A$我们考虑了前$i$位,对于串$B$我们考虑了前$j$位,其中现在比上一位大/小时,最长的公共波浪子序列的长度是多少.
那么我们可以$O(n^2)$枚举状态后再$O(n^2)$枚举转移,这样复杂度是$O(n^4)$的,可以过$40$分(其实可以过$60$).然后我们发现,我们可以把转移拆分成$(i,j)->(i,y)$,然后再由$(i,y)->(x,y)$.
然后我们可以对于每一位分别转移即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<set>
#include<vector>
#include<map>
#include<queue>

#define N 5005
#define M 8000005

#define ls (t<<1)
#define rs ((t<<1)|1)
#define mid ((l+r)>>1)

#define mk make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

int i,j,m,n,p,k,A[N],B[N],ans,a[N],b[N];

int f[N][N][2],g[N][N][2];

int Work(){
memset(f,0,sizeof(f));
for (i=1;i<=n;++i)
for(j=1;j<=m;++j){
f[i][j][0]=max(f[i-1][j][0],f[i][j-1][0]);
if(a[i]==b[j]) f[i][j][0]=max(f[i][j][0],f[i-1][j-1][0]+1);
}
return f[n][m][0];
}

int main(){
scanf("%d",&n); for (i=1;i<=n;++i) scanf("%d",&a[i]);
scanf("%d",&m); for (i=1;i<=m;++i) scanf("%d",&b[i]);
for (i=1;i<=n;++i)
for (j=1;j<=m;++j) if (a[i]==b[j]) f[i+1][j][0]=f[i+1][j][1]=1;
for (i=1;i<=n;++i)
for (j=1;j<=m;++j){
//k==0
if (a[i]>b[j])
g[i][j+1][0]=max(g[i][j+1][0],f[i][j][0]);
f[i+1][j][0]=max(f[i+1][j][0],f[i][j][0]);
if (a[i]==b[j]&&g[i][j][0])
f[i+1][j][1]=max(f[i+1][j][1],g[i][j][0]+1);
g[i][j+1][0]=max(g[i][j+1][0],g[i][j][0]);
//k==1
if (a[i]<b[j])
g[i][j+1][1]=max(g[i][j+1][1],f[i][j][1]);
f[i+1][j][1]=max(f[i+1][j][1],f[i][j][1]);
if (a[i]==b[j]&&g[i][j][1])
f[i+1][j][0]=max(f[i+1][j][0],g[i][j][1]+1);
g[i][j+1][1]=max(g[i][j+1][1],g[i][j][1]);
}
for (i=1;i<=n+1;++i)
for (j=1;j<=m+1;++j) ans=max(ans,max(f[i][j][0],f[i][j][1]));
printf("%d\n",max(min(2,Work()),ans));
}

Jump

只会$60$暴力,咕咕咕了x

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:20191105模拟赛题解

文章作者:KRrrrrrrrr

发布时间:2019年11月06日 - 08:11

最后更新:2019年11月07日 - 09:11

原始链接:http://krrrr.xyz/2019/11/06/20191105模拟赛题解/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。